Information on this page is taken from Competitive Programmer's Handbook and Elements of Programming Interviews. These tricks are also applicable to interview questions (e.g. LeetCode).
Note: add a heading tag with
Plan of Attack
- Understand the problem.
- Ask clarification questions.
- Work on concrete examples.
- Apply patterns.
- Find a good data structure (e.g. priority queue, graph)
- See if the problem fits an algorithmic technique (e.g. sort, divide-and-conquer, recursion, dynamic programming).
- Develop a simple brute-force solution.
- Analyze the brute-force solution and write a more efficient algorithm.
- Test the program on concrete input.
- Analyze time and space complexity.
Primitive Types topic
- Take advantage of both ends of the array.
- For example, suppose we'd like to place the even entries of an array first. Easy with \(O(n)\) space. Two indices can solve this problem without additional storage. We would partition the array into three subarrays: even, unclassified, and odd, appearing in that order.
Trick is to reuse the given array.
import random def sample(count, array): for i in range(count): r = random.randint(i, len(A) - 1) array[i], array[r] = array[r], array[i]
def transpose(matrix): """Calculate A^T on a 2D array.""" list(zip(*matrix))
Rotate Matrix 90 Degrees
def rotate_clockwise(matrix): """Rotate a matrix 90 degrees with flip(A)^T.""" return list(zip(*matrix[::-1])) def rotate_anticlockwise(matrix): """Rotate a matrix -90 degrees with flip(A^T).""" return list(zip(*matrix))[::-1]
Solution without using extra space:
def is_palindromic(s): return all(s[i] == s[-(i + 1)] for i in range(len(s) // 2))
Use multiplication and division to convert to base-10. For example, \(1101 = 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0 = 13\).
from functools import reduce from string import hexdigits def to_decimal(number: str, base: int): return reduce(lambda total, d: total * base + hexdigits.index(d), number, 0)
Use modulus and division to convert base-10 to another base. We find the next
number % base (e.g.
321 % 10 = 1). The number without that
number // base (e.g.
321 // 10 = 32).
from string import hexdigits def to_base(number: int, base: int): if number: digit = hexdigits[number % base] return to_base(number // base, base) + digit else: return ''
Inserting into a array without using additional memory requires two passes: (1) find the final size, (2) work backwards moving characters to the end.
import reduce from functools def insert_dd(s, size): """Replace 'a' with 'dd'. Assume the string has room.""" final_size = size + s.count('a') write_index = final_size - 1 for letter in s: if letter = 'a': s[write_index - 1:write_index + 1] = 'dd' write_index -= 2 else: s[write_index] = letter write_index -= 1 return final_size
Deleting from an array without using additional memory requires two indices.
def remove_b(s, size): """Remove 'b' from a string.""" write_index = 0 for letter in s: if letter != 'b': nums[write_index] = num write_index += 1
Linked Lists topic
See Linked Lists and the examples on that page.
Stacks and Queues topic
See Bags, Stacks, and Queues for more information.
Queue with Stacks
def Queue: def __init__(self): self.first =  self.second =  def enqueue(self, value): self.first.append(value) def dequeue(self): while self.first: self.second.append(self.first.pop()) return self.second.pop()
Binary Trees topic
Consider left- and right-skewed trees when doing complexity analysis. Note that \(O(h)\) complexity, where \(h\) is the tree height, translates into \(O(log n)\) complexity for balanced trees, but \(O(n)\) complexity for skewed trees.
See Trees for more information.
See Heaps for information and examples.
Hash Tables topic
See Hash Tables for more information.
See Sorting Algorithms for more information.
Given a list of intervals (
(start_time, end_time)), determine the maximum
number of events that take place concurrently. The trick is to focus on the
endpoints. This algorithm is \(O(n\logn)\) (dominated by the sort).
from collections import namedtuple Endpoint = namedtuple("Endpoint", ["time", "is_start"]) def find_max_simultaneous(intervals): endpoints = [endpoint for start, end in intervals for endpoint in [Endpoint(start, True), Endpoint(end, False)]] # Sort by time, break ties by putting start times before end times. endpoint.sort(key=lambda endpoint: (endpoint.time, not endpoint.is_start)) max_simultaneous, current_simultaneous = 0, 0 for endpoint in endpoints: if endpoint.is_start: current_simultaneous += 1 max_simultaneous = max(max_simultaneous, current_simultaneous) else: current_simultaneous -= 1 return max_simultaneous
Another interval problem that benefits from sorting is computing the union of intervals. First sort the intervals by their start date. Then traverse the i]ntervals joining when the current interval's start is before the previous interval's end.
Binary Search Trees topic
See Trees for more information. Remember standard traversal methods (and BFS).
Recursion is especially suitable when the input is expressed using recursive rules (e.g. recurrence relation). Consider recursion in search, enumeration, and divide-and-conquer.
Two key ingredients to a successful use of recursion are identifying the base cases, which are to be solved directly, and ensuring process, that is the recursion converges to the solution.
Backtracking is a useful technique for combinatorial search that uses recursion.
Dynamic Programming topic
See Dynamic Programming.
See Greedy Algorithms.
The two primary models for parallel computation are the shared memory model, in which each processor can access any location in memory, and the distributed memory model, in which a processor must explicitly send a message to another processor to access its memory. The former is more appropriate in the multicore setting and the latter is more accurate for a cluster.
Challenges in parallel computing include
- Races: two concurrent instruction sequences access the same address in memory and at least one of them writes to that address.
- Starvation: a processor needs a resource but never gets it.
- Deadlock: thread A acquires lock 1 and thread B acquires lock 2, following which A tries to acquire 2 and B tries to acquire 1.
- Livelock: a processor keeps retrying an operation that always fails.
A semaphore is a very powerful synchronization construct. Conceptually, a
semaphore maintains a set of permits. A thread calling
acquire() on a
semaphore waits, if necessary, until a permit is available, and then takes
it. A thread calling
release() on a semaphore adds a permit and notifies
threads waiting on that semaphore potentially releasing a blocking acquirer.
- Start with an algorithm that locks aggressively and is easily seen to be correct. Then add back concurrency, while ensuring the critical parts are locked.
- Try to work at a higher level of abstraction. Know the concurrency libraries.