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.
    • 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. 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.
    • 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

See Heaps for information and examples.

Searching

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.

TODO Hash Tables