• 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)].
• Jan 25, 2020

  • Practice problems.
  • https://leetcode.com/problems/sort-list/. You can do bubble in n^2 time and 1 space, or use extra space to create another data structure regular sort nlogn with n space. Doing nlogn time and 1 space requires a weird in-place mergesort.
  • https://leetcode.com/problems/lru-cache/. Implemented my own lru cache with an eviction policy. Get() and Put() are both O(1) in time. Achieved with a deque (the keys) and a dict (the key-val mapping).
  • https://leetcode.com/problems/evaluate-reverse-polish-notation. Cool, but easy. Iterate through and simply perform operations as they come. Trick: manage your own index. You could use a stack, but mine collapses values in place, making it more memory efficient.
  • https://leetcode.com/problems/max-points-on-a-line. This one has a 16% acceptance rate, the lowest I’ve seen. Did it in about half an hour. Line math, mx + b, then iterate over and track points on that line. Lots of corner cases: divide by zero, high-precision math (using the Decimal library).
  • Youtube creator awards. The diamond play buttons is for >10m subs, and there are about 500 channels total that have been given it. The red play button is for >50m. The red diamond is for >100, and only a couple channels have gotten this (pewdiepie and t-series).
  • Confirmed disney onsite for next wed.
  • Watched rosemary’s baby for the first time. Maybe shocking 50 years ago, but not a great movie by today’s standards.
• Jan 24, 2020

  • Flatbuffer is a memory-efficient protobuf alternative.
  • Watched kingpin. Old, but great premise.
  • You can connect a websocket directly to a message queue like kafka.
  • Netflix responded to schedule an onsite next week. Looks like we can make Friday happen.
  • Disney responded to schedule a phone interview, I said asap, and talked to senior software engineer later in the day.
  • Amazon followup onsite interview for senior leveling today at the santa monica office.
  • FB wanted to chat again on monday.
  • Started watching the tv show sinner on the chicago flight, like it so far.
  • Ads becoming harder to spot in google search results now. Just a black word “ad” where the favicon should be.
  • 23andMe and DigitalOcean both laid off a substantial number. Surprising. I like both businesses.
  • AB was arrested, bailed, and required to go through a mental health evaluation.
  • Practice problems:
  • https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/. LCA if it’s a binary search tree.
  • https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree. LCA if it’s any binary tree. The problem from yesterday. Recurse node by node. Exits: (1) return false if none, past leaf (2) return true if node is equal to node1 or node2. Propagate that True up, bc you know it’s a child. Recurse down left and right. If ever left and right (or self) return True, that’s you’re answer.
  • https://leetcode.com/problems/sliding-window-maximum/. My solution worked, slicing the window and taking the max. This beat 20% time and 60% mem on leetcode. I actually got the optimizations right in the interview too, using deque, and only iterating through if the current_max is the one leaving on the left. This solution beat 33% and 24% on leetcode.
  • Scheduled citadel followup for monday.
• Jan 23, 2020

  • Practice problems.
  • https://leetcode.com/problems/linked-list-cycle/. Linked list cycle. Add visited to hash set(), then check if present.
  • https://leetcode.com/problems/majority-element/. Counter.most_common.
  • https://leetcode.com/problems/maximum-product-subarray/. Kadane’s for product instead of sum. You have to check min as well.
  • https://leetcode.com/problems/reverse-linked-list. Reverse linked list, both iteratively and recursively.
  • https://leetcode.com/problems/factorial-trailing-zeroes. Weird. Mathy.
  • https://leetcode.com/problems/house-robber/. Just recurse 2 ago, add current, take max of that and the one previous.
  • Citadel Interview in Chicago, went well. Took extensive notes in drive. Flew back to LAX at night.
  • The US market is 50% of the global market!
  • TSLA 600 call for 1/24 (tomorrow) was looking so good until now.
• Jan 22, 2020

  • Amazon is making a palm reader payment service.
  • Placed some tsla calls, but in bigger news, the $1000 1yr is over $45. Ridiculous.
  • Added KTN and FFN to the chicago flight.
  • Popular hash functions: MD5, SHA, NTLM, LANMAN.
  • FB coding interview. This guy was awesome. Did well, good convo.
  • Great answer to my question, Future success in data or product? It’s neither. It’s having the best tech stack, the best engineering talent. This will make you more agile in bringing NEW products to market in the future, whatever that landscape may look like.
  • Practice problems.
  • https://leetcode.com/problems/word-break/. Did it very fast with my recursive solution, but need a way to memoize. DP is crucial for this one. Think about it logically. Try every word at every starting position, and mark the index of the end of the word as findable if there are any matches. I still like my solution better.
  • https://leetcode.com/problems/min-stack/. Build your own stack.
  • Max path length in tree. This is the same as max path sum (https://leetcode.com/problems/binary-tree-maximum-path-sum/), but treat each val as 1 (unweighted, basically). It’s a recursion problem. Look to the left, recurse to the max depth there. Look to the right, recurse to the max depth there. Add the two together. That’s the max path for this root. Keep a global variable for the max found so far, and then on each recursion just check against it.
  • https://leetcode.com/problems/gas-station/. This one was weirdly hard. There’s such a wide variety in problems. I crush some “hard” ones, some “medium” ones are impossible. There’s definitely a bit of luck in the selection of the questions interviewers ask you.
  • https://leetcode.com/problems/longest-consecutive-sequence. Smartly keep track of visited nodes in sets. Little harder than it appears, but approach logically. The hard part of this one is the recognizing the complicated for/while solution is actually only n, not nested n^2, because you’re checking existence in set.
  • https://leetcode.com/problems/copy-list-with-random-pointer/. Deep copy a linked list, iterate through and keep track of a few things. A different type of problem. Can recurse like usual, and assign both pointers, with one tricky part: keep a memoization dict of the visited nodes. This is just a mapping of original node -> copied node.
  • https://leetcode.com/problems/palindrome-partitioning/. This one is tough too. I’ll have to do some easy/medium to get up for tomorrow. Remember that recursion is almost always a good answer, even for string/list problems. Iterate through the beginning till you hit some criteria, then recurse on the remainder. Keep track of all valid answers in a global variable, rather that directly in the recursive call scope.
  • Flew to chicago for citadel.
  • FB uses mercurial, not git.
  • Scheduled the amazon sr followup for friday, 1-3.
  • Citadel research.
  • 10s of billions of assets under management.
  • Ken Griffin founder, Peng Zhao current CEO.
  • Reviewed my tradebot.
  • Nasdaq for all tickers on the nyse.
  • Yahoo-fin and robin-stocks for history/data.
  • Backtrader for backtesting.
  • Simple moving average (and a few other basic one) for strategies.
  • Robin-stocks to wrap the rh api.
  • Scikit-learn/numpy/pandas/matplotlib for analysis.
• Jan 21, 2020

  • System design, whiteboard and youtube, ~1hr each. Mostly from Naren’s channel.
  • Uber. Path planning. Websockets to keep gps locations updated every few seconds.
  • Fandango. All booking sites are comparable (airbnb etc) where you find a match. Suggestions are an important piece here (netflix etc), use heuristics from previous content.
  • Webcrawler. Probably the most different one. Follow links, basically just a gigantic 100b node graph. Use a bloom filter for the “in visited?” portion. Used for search engines, copyright police, more.
  • Twitter. Social media, read-heavy. Precompute feeds on write for most users. For celebrities, read on call.
  • Whatsapp. Any chat service. XMPP, or websockets as the persistent protocol to read-write with new messages. And session, for delivered/read receipts. Message queue for the actual text, before db.
  • Google docs.
  • Dropbox/gdrive/stash. Just remote file representation, upload/download/sync. History is the most important piece here. Store diffs, not copies. Chunk files so you can diff efficiently.
  • Gdocs. Collaborative editing. Just like optimistic locks. Like the previous, chunk for differential syncing. Could be character by character, or batched in whole lines, etc. This is called operational transformation, everything is captured in an event (insert, delete, update…) and replayed for all other clients. Or you could just do raw diffs (patches) and try to apply, raising conflict if need be.
  • Curated list of interesting stuff: https://github.com/sindresorhus/awesome.
  • Watched the ted interview with jim simons: https://www.youtube.com/watch?v=U5kIdtMJGc8. Not a ton of info.
  • Subscribed to https://eng.uber.com/.
  • Went through a bit of https://github.com/yangshun/tech-interview-handbook.
  • Spoke with fb to schedule the coding interview, asap today or tomorrow morning before flight. Talked about instagram and whatsapp team matching. She was actually chicago based and mentioned citadel!
  • Later in the day we scheduled for tomorrow morning before the flight to Chicago.
  • Quick call with citadel for Thurs prep. The importance of tech in finance, and how that’s reflecting in recent numbers (vs companies married to legacy finance fundamentals).
  • Practiced a few behavioral orations again.
  • Run, core, sauna, stretch, meditate.
  • Another amazon feedback survey. Good all around.
  • Watched a few videos on vocal coaching, remembering that breath class I took at stanford and how powerful of a speaker the professor was. Some were more focused toward singing, some toward presenting. Do mouth/face/voice warmups, stretch, posture, confidence, smile; treat it like a conversation not a stage.
  • XMPP is very similar in functionality to websockets. Persistent connection, peer-peer. XMPP is decentralized, can be distributed; websockets are centralized.
  • TCP is more reliable than UDP. It establishes a connection/handshake. UDP just sends data. Faster, but could be lossy.
  • The python logo is 2 snakes curled into a cross, just to represent the snake name.
  • Python isnum, isalpha, isalnum.
  • Problems:
  • https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/. Same as the usual level-order traversal (do iteratively, keep children), but keep a boolean that you swap each time for the direction of level printout.
  • https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree. Interesting new class of problem for me. Rather than converting a tree into a list via traversal, you’re given the traversal lists and you have to create a possible tree (there are many valid ones).
  • https://leetcode.com/problems/pascals-triangle/. Recursion. Add above two numbers.
  • https://leetcode.com/problems/populating-next-right-pointers-in-each-node/. Cool problem, another level-order traversal, just a slight constant-mem twist.
  • https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/. A bit harder. Still recurse the traversal lists to create the nodes, but you have to think a bit more deeply. Use the preorder array to grab the root, find the root in the inorder array to bisect it, then get the lengths of both halves. Use that to split the remainder of the preorder array. Then just recurse as usual.
  • https://leetcode.com/problems/binary-tree-maximum-path-sum. Use a postorder traversal. Recurse left right, calculating the max for those child nodes, then calc the max for this node by simply adding its val.
  • https://leetcode.com/problems/valid-palindrome. Easy. Just compare palindrome fwd and rev.
  • https://leetcode.com/problems/word-ladder/. Interesting problem. Jumping through available words, only allowing one letter change at a time. It’s a graph problem, but takes a minute to realize this. I had first leaned toward a Trie. Once you realized graph, just build it and run BFS for the shortest path.
  • https://leetcode.com/problems/surrounded-regions/. Used DFS to find the unsurrounded nodes from the edge, then simply moved everything other than that to X. Uses nodes for this one (not paths), which I haven’t done in a while. It’s simpler.
  • Reread https://github.com/donnemartin/system-design-primer. Great document.
  • Remember to always popleft() with doing DFS or BFS. It’s just for BFS, append to end. For DFS, appendleft().
• Jan 20, 2020

  • Practice problems.
  • https://leetcode.com/problems/set-matrix-zeroes/. Solved. To be even more memory efficient, you can set the matrix values in-place to a known flag (None or something) rather than keep track or row and col sets to zero in the next iteration.
  • https://leetcode.com/problems/sort-colors/. Easy to solve, not so easy to do in constant memory.
  • https://leetcode.com/problems/minimum-window-substring/. A bit harder. Can iterate and store in dict, removing letters as necessary, like I did, or you can use 2 pointers. Right for expansion until you get all of T, then left for contraction to try to minimize it. Continue until it’s not a valid substring, then move left forward one and repeat.
  • https://leetcode.com/problems/decode-ways/. Cool problem. Simply recurse on the different options, one or two digits. Always remember to memoize. In this case, the DP cuts the time in half. I scored faster that 95% of submissions.
  • https://leetcode.com/problems/binary-tree-inorder-traversal/. Traversing with recursion easy. To do iteratively, look at it like BFS/DFS. Manage a stack/queue and pop off appropriately according to inorder/preorder/postorder.
  • https://leetcode.com/problems/validate-binary-search-tree/. When recursing and check left/right less/greater than, don’t compare to the node’s value. You have to propagate the parent’s bounds, just add a lower and upper param. Compare to that, not node.val.
  • For leetcode specifically, I’ve now finished the top 50 questions and the top 50 interview questions. Will finish the top 100 liked questions next (almost done), then continue through 51-150 for the top interview questions.
  • https://leetcode.com/problems/symmetric-tree. Level-order stuff is a bit easier with iteration than recursion, similar to BFS.
  • https://leetcode.com/problems/binary-tree-level-order-traversal/. BFS, but the simplified version. Just an iterative while loop with a list of children, then collect the vals.
  • https://leetcode.com/problems/maximum-depth-of-binary-tree/. Basic BFS, just count the layer for max depth. You can do this recursively in a one-liner with:
  • def foo(root): return 1 + max(foo(root.left), foo(root.right)) if root else 0
  • Markets closed today for MLK holiday.
  • Dinner last night with the snyders (+baby) and everyone in culver.
  • Confirmed no supercontest late-pick-reminder email on saturday, as designed.
  • Python 3 type hint with default:
  • def sqrt(number: int = 0) -> float:
  • Orated the 4 behavioral questions in prep.
  • Run, push, sauna, meditate.
  • Emailed Netflix to keep them in sync with the others.
  • Roasted 5lbs of peanuts (450F 15min). Made 2.5lbs regular peanut butter and 2.5lbs pumpkin peanut butter.
  • Reread https://github.com/donnemartin/system-design-primer and did a ton more practice system design questions, including whiteboard. Boggle, twitter.