• Jan 26, 2020

  • Practice problems:
  • https://leetcode.com/problems/intersection-of-two-linked-lists/. To find the FIRST COMMON element in two arrays, or two linked lists, etc, the most natural way is to loop over one and create a set (hash table) and then loop over the second until you find a match. This is O(m+n) time and O(n) space. You can improve by using two pointers. Iterate one by one, and then if you’ve reached the end of the list, move it to head of the other list. Conclude once you’ve reached the end of that one. If there’s a match, you’ll find the first one. Write it out to see how it makes sense.
  • https://leetcode.com/problems/word-break-ii/. Harder, but cool. Just like the other word break, just keep track of a dp memo that tracks word combinations up to that index. Then only check that index out if the previous index is non-empty (words ended there, so we have more possibilities).
  • https://leetcode.com/problems/find-peak-element/. Interesting. Just check the right side (half, so log) instead of both left and right comparisons each time. The solution is wrong for this one, assuming a sorted input.
  • https://leetcode.com/problems/fraction-to-recurring-decimal. This problem is much harder than it seems. Basically recurse down and perform the division each time, like you would in handwritten longdivision, and carry the decimal place over by 1 each time. Memoize to detect if you’ve seen a cycle already.
  • https://leetcode.com/problems/excel-sheet-column-number. Very elegant solution, oneliner. ord of the char, adjusted, then * 26 raised to the power of the digit.
  • https://leetcode.com/problems/excel-sheet-column-title/. Little tougher, but still an easy problem.
  • https://leetcode.com/problems/rotate-array. Easy oneliner. Another cool solution is reverse the string, then reverse the first k items, then reverse the last n-k items.
  • https://leetcode.com/problems/largest-number. Cool problem. Remember if you want to do any custom sorting, like by digit value or ANYTHING else, you can define your own custom Comparator class with __lt__ defined, then pass it as a key to sorted().
  • Scheduled haircut for wed.
  • Remember heaps, min and max. Can create (heapify) in O(n). Check the top element (min/max) is O(1). Popping the top, or removing an element, or inserting an element are all the same O(logn), because you have to rebuild part of the heap after.
  • Great bday for Katilin, they did an awesome job planning dinner/jeop/paintNsip.
  • Watched the Bellator and UFC fights from last night.
  • Kobe.
  • Pro Bowl.
  • Remember that [None]*5 in python will make all items mirror each other, since lists are mutable. To make individual pointers, just do [None for _ in range(5)].