Solutions to various Computer Science problems from around the internet!

Trapping Rain Water

array two pointers stack
28 Jul 2019

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.

Daily Capacity

binary search optimization
1 Jun 2019

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.

Alien Rhyme

Suffix Tree Post Order strings
13 Apr 2019

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.

Dat Bae

interactive binary search
13 Apr 2019

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.

Number of Islands

union find C calloc
21 Mar 2019

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.

Data Structure Design

array design hash map
13 Mar 2019

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.

Advent of Code D20

dictionary search time limit
20 Dec 2018

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.

Roads and Libraries

dfs graph optimization
29 Jul 2018

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
8 Jul 2018

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.

Bit Party

binary search equation optimization
13 Apr 2018

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.