# 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).

- Find a good

- Ask
- 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
- Understand integer storage (see information storage).
- Understand
**unsigned**vs.**signed**and**two's complement**.

- Understand

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

- 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

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