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   meta

1. Understand the problem.
• 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. divide-and-conquer, recursion, dynamic programming).
2. Develop a simple brute-force solution.
3. Analyze the brute-force solution and write a more efficient algorithm.
4. Test the program on concrete input.
5. Analyze time and space complexity.

Primitive Types   topic

• Use bitwise operators.
• 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]
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


See Linked Lists and the examples on that page.

Stacks and Queues   topic

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.