Solutions to various Computer Science problems from around the internet!
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.
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.
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.
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.
This leet code problem involved designing a new data structure with a given set of properties. The requirements were
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.
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.
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.
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.
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.