array
two pointers
stack

link
By moving `once from left to right`

across the array of heights, it’s possible to calculate the total trapped rain water using a `stack`

.

binary search
optimization

link
To determine the minimum capacity required to ship all packages within D days, it was optimal to use a `binary search`

. Assuming that the minimum weight was `K`

, we know that all capacities less than `K`

will fail and all capacities larger will succeed. Thus, we perform a `binary search`

over the space of all possible capacities until we find then minimum capacity `K`

such that k-1 is false.

Suffix Tree
Post Order
strings

link
This problem is from Round 1A Google Code Jam 2019, I solved it by constructing a `suffix tree`

, which I then traversed using a `post order traversal`

in order to match strings into groups of two from longest to shortest suffix.

interactive
binary search

link
To solve this problem from the 2019 Google Code Jam Qualification Round, I recursively split bit strings and sent them to the server, in order to perform a binary search. I used the results of this binary search to determine the index of up to fifteen `broken machines`

out of a possible 1024 machines in 10 guesses or less.

union find
C
calloc

link
In order to find the number of non-connected islands. I implemented the `union find`

data structure in C. Union find is able to join groups and lookup the group an element belongs to in `O(1)`

. I also learnt about using `calloc`

in C to allocate a contiguous block of memory for use as an array.

array
design
hash map

link
This leet code problem involved designing a new data structure with a given set of properties. The requirements were `O(1)`

`insert`

, `remove`

, and `getRandom`

. A hash map allows for O(1) insert and removal. An array allows for uniformly random selection. To `insert`

, add an element to the hash map and append it to the array. Store the element’s array index as the value in the hash map. To `remove`

, remove the element from the hash map (save the index), swap the element at that index with the last element in the array, pop the new last element. Finally, update the value in the hash map of the moved element.

dictionary
search
time limit

link
I solved this problem in 53min 15sec and placed 79th on the daily leaderboard for Advent of Code. My solution involved using a dictionary to track visited cells while I recursively called a search function in order to explore all possible paths outlined by the input string.

dfs
graph
optimization

link
To find the number of connected components present in the graph of cities, we perform a DFS starting from each vertex and flaging any verticies we visit on the way. For each compoent, we determine if it is cheaper to build a library in each city or to build a single library and repair the edges between the cities.

modular arithmetic
competition
simplification

link
This problem was part of the Facebook Hacker Cup. To solve this problem, I had to determine how many times each attraction in a list would be visited given that the first K attractions would be visited once a day for N days. The key insight was that this could be calculated using MOD which allowed for a O(1) time solution. A brute force simulation would run over the time limit. Solving this question allowed me to advance beyond the hacker cup qualification round.

binary search
equation
optimization

link
This problem involved developing an equation to calculate the maximum number of items that could be purchased given a specified amount of time and information about cashier speed. Upon developing this equation, one had to perform a binary search over the space of possible times to determine the optimal checkout time.