Competitive Programming
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 C-c C-c.
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
- Use bitwise operators.
- Understand shifting and masks.
- Be comfortable with XOR.
- Understand integer storage (see information storage).
- Understand unsigned vs. signed and two's complement.
Arrays 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.
Random Subset
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]
Transpose Matrix
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]
Strings topic
Palindromic
Solution without using extra space:
def is_palindromic(s):
return all(s[i] == s[-(i + 1)] for i in range(len(s) // 2))
Base Conversion
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
digit with number % base (e.g. 321 % 10 = 1). The number without that
digit is 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 Values
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 Values
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.
Heaps topic
See Heaps for information and examples.
Searching topic
Binary search is an effective search tool. It is applicable to more than just searching in sorted arrays, e.g., it can be used to search an interval of real numbers or integers.
Also see selection.
Hash Tables topic
See Hash Tables for more information.
Sorting topic
See Sorting Algorithms for more information.
Intervals
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 topic
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.
Greedy Algorithms
See Greedy Algorithms.
Graphs
See Graphs.
Parallel Computing
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.
Concurrency Tips
- 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.