Solutions

homepage

Solutions to various Computer Science problems from around the internet!

Alien Rhyme

Suffix Tree Post Order strings
13 Apr 2019
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.

Dat Bae

interactive binary search
13 Apr 2019
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.

Number of Islands

union find C calloc
21 Mar 2019
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.

Data Structure Design

array design hash map
13 Mar 2019
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.

Advent of Code D20

dictionary search time limit
20 Dec 2018
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.

Roads and Libraries

dfs graph optimization
29 Jul 2018
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.

Tourist

modular arithmetic competition simplification
8 Jul 2018
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.

Bit Party

binary search equation optimization
13 Apr 2018
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.

homepage