• August 3
  • July 31
    • Disjoint Set
      • https://www.hackerrank.com/challenges/merging-communities
        • First attempt: Naive DisjointSet Implementation, with union by rank – in particular, need to go up the forest to find ancestor every time – O(log n) merge and O(log n) query. TLE for most cases.
        • Second attempt: Optimize by caching index to oldest ancestor. Lazy updates. TLE for most cases.
        • Third attempt: Go back to attempt 1, but use path compression as well. Used array list to track the visited nodes whose parents have to be updated. TLE for most cases.
        • Fourth attempt: Use recursion directly to do path compression. Passed.
        • Conclusion: it looks like the main reason I get TLE was that in merging, I didn’t return when the two sets already have same ancestor. The official solution doesn’t do union by rank or path compression at all.
      • https://www.hackerrank.com/challenges/components-in-graph
        • Strongly suspect that bfs would be fast enough as well, but nonetheless solved by disjoint set.
      • https://www.hackerrank.com/challenges/kundu-and-tree
        • Fairly straightforward, once you realize that you should think of red edges as non-existent edges, and that you are trying to count the number of unordered triples coming from three distinct connected components (only with the black edges).
  • July 30
    • Basic tree problems
    • Stacks
      • https://www.hackerrank.com/challenges/balanced-brackets
      • https://www.hackerrank.com/challenges/game-of-two-stacks
        • First attempt: recursion, TLE for half the test cases.
        • Second attempt: key is to build a list of the “smallest” element you can take from the stack each time. Once you build this list, just keep polling until you hit the maximum allowed total. This can be done by tracking two pointers of the respective arrays. Some WA, some TLE
        • Third attempt: no need to build out that list – you can track the total sum so far in the process of updating the two pointers, and return the answer right away when ready.
        • Fourth attempt: the above is actually wrong: the greedy way of picking the lowest number at every step is logically wrong… does need recursive ideas, so let’s do memoization. Memoization done by a HashMap<Index Pair, Capacity> TLE for half the test cases.
        • Fifth attempt: Same as last idea, do bfs on the indices – add index 1 only when permissible, and if this has been calculated before (tracked by a HashSet), don’t do the calculation again. TLE for half of the test cases.
        • Sixth attempt: two pointer passing solution. Passed
  • July 29

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s