Jumping Ship

To Do

• (/) go through CV and redact wrt contract
• (/) also redact wrt legal on website
• (/) add explainer about why I do vague stuff - not necessary I think
• (on) get Cath to read CV
• submit to headhunter
• redo everything in CoderPad
• note error correction codes

Financials

So... what's involved?

• Lost income during non-compete
  • I need to double-check contract, but about 9.5 * 6 = 57k of lost income during non-compete.
  • If I lose the engineering allowance during the 6 month notice period, that's maybe another 1.375*6 = 8.25k?
  • So maybe 65k in all
  • Maybe I'd get some contract work but I have no idea to what extent that practically be possible, need to research conditions
• Lost bonus
  • Also, a year's worth of bonus is effectively written off, e.g. 2024.
  • There's an element of time-is-money over bonus, I need to get a move on there.
  • I might get some help from JS but it's not guaranteed.
• Risk: this is the biggie. What happens if I go to Jane Street and it doesn't work out?
  • (If JS works out I could do very well. But this is not really about the money, right?)
  • I'd need to try other places
    • Rokos maybe. More money but a worse work/life balance - but for a few years, who cares?
    • Or go to gentler, slower places with a permanent drop in income
• GR is really a pretty good deal in many ways at the moment.
  • I could stay there for 5 years and not have a mortgage any longer.
  • An alternative really needs to make its case

Next steps

• Check the contract terms so I know exactly what's involved
  • Do I get paid engineering allowance if I'm on notice to leave for a competitor?
  • What are the terms of the non-compete - how is this defined?
• Draw up a firmer list of what's involved. What's your gut feel?
• Discuss with Cath

Questions

Remaining:

• distributed hard drive - look at RAID maybe?
• D1 although not sure what the Q actually is
• D2 look up heap algos, although again a bit of a shit question

Keep it simple!

class NodeNAry:
    def __init__(self, v):
        self.v = v
        self.desc = []
class NodeBinary:
    def __init__(self, v):
        self.v = v
        self.l = None
        self.r = None

Python

float() to convert
s[::-1] reverses a string
anagram: ''.join(sorted(w)
permute: "from itertools import permutations" then for p in permutations(a):
deque: "from collections import deque" and add/popleft

Games

• G1: Build tetris - ffs I have done this
• (/) G2: Implement the game state for a variant of connect-four with infinite width
  • easy enough, just use hash on bignum and check for neighbouring columns?

Trees

• (/) T1: Inorder tree traversal. Given a tree, return a new tree with the same structure but all values replaced with Unit. Given the inorder tree traversal, and tree structure with Units, reconstruct the tree.
  • Given an OCaml representation of a pseudo-binary tree, describe how to compare two trees and hte run time.
  • I was asked to (equivalently) transform binary search tree into array and vice versa. Note that they keep doing gambling with you. You have to bet the number that payoff expectation is positive by your mental math.
  • To array: walk and recurse-l, do-current, recurse-r
  • From array: pick midpoint for node, l is left-of-mid, r is right-of-mid
• (/) T2: Several basic binary tree questions that built off of each other in difficulty. From implementation to finding the depth to checking if the tree is symmetrical.
  • the problem is write a binary tree and then write a function to get its depth.
  • Question involving a tree structure and operations to find specified values.
  • Give the type of a binary tree and an algorithm to compute its depth
  • Just recurse for depth - width means you gather at each level in q and then go through that, assembling next q
• (/) T3: Implement a binary search tree (BST) and judge a tree whether is a BST
  • Implement a binary search tree.
  • Not too hard, just walk and insert
• (/) T4: There is a company, modelled as a tree of employees and the people reporting to them. Every employee has a fun value. At a party, every employee only has fun if his direct boss is not at the party, otherwise he adds fun corresponding to his fun value to the party. Write code to find the maximum total fun that can be had at the party.
  • Return (fun_if_inc, fun_if_ninc) at each = then ret (vcurr + sum(lower, fun_if_ninc), max(sum(lower, fun_if_inc), sum(lower, fun_if_nnc))

Strings

• (/) S1: Variant of the leetcode stream of characters questions
  • Design a system for a game that can accept sequences of key combinations and pick them out when that sequence of keys is pressed.
  • Same street fighter question another Glassdoor interview mentioned. Write two functions: register and on_key. Register takes a combination of keys as a string and a name for the combo. On_key takes a single keypress and check if that keypress completes a combo registerd. Given possible inputs Up, Down, Left, Right, A, and B. Registered combos can be of unlimited length.
  • Describe how a hash table works. Design a street fighter game that displays a list of all combos given a button order. For example, if the user presses (->)AB, any move that activites on ->,A,B,->A,AB, or ->AB needs to be printed. Allow the user to define their own combos as well.
  • Just storing and incrementing/zeroing positions in a hash seems pretty good to me - and we know they don't want a trie
• (/) S2: Given a list of words, right a function to return a list of pairs of palindromes
  • Almost too easy? note that "w[::-1]" reverses a string
• (/) S3: Given a list of words as an input, group them by their anagrams.
  • Dict where keys are .join(sorted(w))

Other Data Structures

• D1: Build a new special container/Implement custom stack with various operations on it.
• D2: Given an array with a heap property, how do I insert and delete elements into the heap while maintaining the heap property. Followed up by, how to recursively delete the entire subtree.

Array stuff

• (/) A1: Given 2 sorted arrays of integers both of length n, find the element that would be n-th after merging arrays.
  • simple 2-step
• (/) A2: Given an array of paired integers, write an algorithm to find the integer that is not paired, using constant space.
  • I would say this is a bit of a trick queston. Could XOR the lot. Not sure what to do else since we can't build hashes etc
• (/) A3: Write a method that takes an int and an array and rotates the array right n times. Give an answer with constant space and linear time.
  • A bit of a maths trick? math.gcd and work within the cycles
• (/) A4: Find the smallest sublist size in a list of lists. Then after I came up with an algorithm that used List.length to compare which is an O(n^2) algorithm, he asked how could this be improved, which stumped me.
  • Don't really get that. You have to get the sublist lengths! Wonder if he was just being prodded?

State Machines and Parsers

• (/) SM1: Given an array of numbers check if it is possible to use basic arithmetic operations on them and receive goal number
  • Write a parser for arithmetic expressions using 4 basic operations, and compute ways of making 24 using 4 given numbers and any of the above operations.
  • Implement an expression evaluator for arithmetic expressions. Followed up by, how would I add operator precedence and variables.
  • not too bad, but quite a lot of faff. would I really be expected to do this in 30 minutes?
• (/) SM2: Given a matrix of chars from the set {"u", "l", "d", "r", "x"}, where the matrix is guaranteed to have one "x," and each of the other chars represent a direction up, down, left, and right, and a point on the matrix, write a function that returns true if "x" can be reached by following the specified path.
  • Problem 1: you are given matrix filled with letters "U" "D" "L" "R" "X". On "U" you can move only up etc... X is destination. Find if it is possible to reach X. (Watch out for loops)
    • easy enough - try "from collections import deque" and add/popleft
  • Problem 2: How many edits (e.x. change "U" -> "L") you need to make in order to reach X.
    • not sure how you would do this - could do repeated rounds of "change ones next to current ones and see how far you can reach?"

Combinatorics

• (/) C1: Select a random element from a stream with uniform probability (we only have access to the current element, and a function to get the next element which returns EOF when at the end of the stream).
  • aka "do you know about reservoir smapling>?" (I didn't) for k-select, build up a k-reservoir, then for i-th do rand(0,i) and replace if in [o,k)
• (/) C2: Given a list of N people. On the first day, divide them into N/2 groups, each group contains two people. On the day 2, divide them into groups of two again... Do this every day, until day N-1. In a way such that all pairs of people has been groupmates once.
  • one you just have to know? sit them facing each other, fix one (say, top left) and rotate the others
• (/) C3: 10 ropes with red and blue end. red end can only connect blue end. what is the expected number of loops?
  • chance # ticks up each time is 1/n so it's 1/10+1/9+...+1/2+1

Misc

• M1: Code a distributed hardrive retreival system.
• M2: Using some functions they gave me which operate with cells in spreadsheets, I had to compute sum of an array. Later I had to implement by myself those functions: the trickiest thing was to implement the part when some cell is a sum of two other cells and some of those two cells is a some of some other cells and so on ...
• (/) M3: Basketball player makes first free throw and misses the second. Thereon after, the probability of making the next free throw is the proportion of previous shots he has made. What is the probability he makes 50 of the first 100 shots?
  • 1/2, it's symmetrical. But ffs that's a terrible interview question