• Jan 6, 2020

  • Practice problems.
  1. https://www.hackerrank.com/challenges/max-array-sum/problem. DP. Iterate through the array and notice patterns. What info do you need to hold on to? What are the possible answers? Keep track of the max by index and just walk through.
  2. https://www.hackerrank.com/challenges/abbr/problem. Easy to get most the cases, but hard to get all. Remember for DP you can sometimes build a 2D matrix of 1s and 0s and traverse it (like longest common substring/subsequence).
  3. https://www.hackerrank.com/challenges/candies/problem. An interesting one. Iterate through an array, once forward, once backward, and count the rising edges. Match them by index and take the max.
  4. https://www.hackerrank.com/challenges/decibinary-numbers/problem. Didn’t do it. Wrapped my head around it, but didn’t implement.
  5. https://www.hackerrank.com/challenges/min-max-riddle/problem. A cool problem. What mapping do you need to solve this? Can find the INVERSE of that mapping?. Swapping keys/values in a dict is easy.
  6. https://www.hackerrank.com/challenges/castle-on-the-grid/problem. Used a graph. Build an adjacency matrix of the 4 cardinal directions from each node and remove the ones that are off the grid or on an X. Then it’s simply a shortest-path problem. Use BFS (queue).
  7. https://www.hackerrank.com/challenges/poisonous-plants/problem. Got the easy solution.
  8. https://www.hackerrank.com/challenges/ctci-bfs-shortest-reach/problem. When using BFS for shortest path, remember to slice the list for each neighbor, so you’re not overwriting the root path. And just logically think through everything. Created visited set() and queue deque(). while queue. Get path. Get node. If node == end, exit. If node in visited, continue. Else, lookup the next nodes in the adjacency matrix, add to path, then append to queue.
  9. https://www.hackerrank.com/challenges/find-the-nearest-clone/problem. Getting good at the graph problems. It was a less-experienced topic for me before this.
  10. https://www.hackerrank.com/challenges/ctci-connected-cell-in-a-grid/problem. Could do DFS or recursion or iteration.
  11. https://www.hackerrank.com/challenges/matrix/problem. Fun problem. There’s actually a bug in a unittest in this one.
  • Done with the hackerrank kit. I’ve probably done 100 practice problems not in total across the platforms.
  • Confirmed the phone interviews this week.
  • Dijkstra’s algorithm is used to find the shortest path between two nodes in a graph with weighted edges. If you assigned no weights to edges (such that they’re all the same, 1), it reduces to plain old BFS!
  • BFS is exponential (based on how many neighbors each node has) in time and memory. It’s great for small problems, but solving something with a state space like a rubik’s cube is huge.
  • Sets and lists are unhashable in python. For most problems, you can just convert the (i, j) coordinates to a string or something similar.
  • collections.deque is faster. This whole package is great for performance. defaultdict is awesome. Counter is also really useful for counting stuff (like frequency of char in str, or others).
  • When using BFS for shortest path, put PATHS (lists of nodes) instead of nodes into the queue.
  • Append the new nodes to the right of a queue or a stack. But in a queue, pop the node off the left to search next. In a stack, pop the node off the right.
  • Run, pull, sauna, meditate.
  • Checked the snail mail. Probably 100 items. Everything was complete garbage except for 1 dmv registration. The signal to noise ratio is laughable (and wasteful of paper / people resources).
  • Renewed the BMW registration. $150 total. The DMV charges a 2.1% fee for online processing. Fuck them. It should be a discount for online logistics, which have significantly reduced overhead.
  • Even if it’s Elavon, you need to front that.
  • For number systems, the exponents always increase from 0 to n-1. This is known.
  • For binary, the base is 2, so the digits in the number (the constants before the base-exponents) can only be those 2:
  • [0, 1]
  • For decimal, the base is 10, so the digits in the number (the constants before the base-exponents) can only be those 10:
  • [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  • I had thought about the base/exponent before, but never the limited range of digit values.
  • For previous-project questions, use STAR: Situation, Task, Action, Result.
  • My Amazon interview is actually at the Santa Monica location, which is more convenient! The hiring managers can pass offers between sites after, if need be.
  • Took a ton of “give an example of …” notes. Moved gdrive docs around, cleaned.
  • Database partitioning. Horizontal partitioning is when you keep the table the same and split groups of rows across different machines. Each is usually called a shard. Vertical partitioning is when you split columns off into a new table. Both improve performance, making it distributed (but more complex).
  • Collections.deque is pronounced “deck” – it stands for double ended queue.
  • Of course threads in a process have their own stacks but share heap. Separate processes get their own stack and heap.
  • Disjoint sets. Another useful data structure. Usually implemented as trees. Two operations: find() and union().