Two Sigma Software Developer interview questions

Coding challenge: 1. You are given a matrix of Ys and Ns where a Y at (i,j) denotes that persons i and j are friends. Friendships are transitive, so if A is a friend of B is a friend of C, then A is in the same a friend circle as C even if A doesn't know C directly. How many friend circles are there? It's really a disjoint sets problem. 2. You are given a list of strings. Removing a letter from any string yields a different string that may or may not exist in the list as an independent entity. This is one link of a "string chain". Find the longest chain in the array. Solved with a hashtable. Interview day: 1. Code a function that matches regular expressions with targets. There is a DP and a recursive solution. 2. Test it extensively in a main. Write a function to autogenerate test cases. 3. Code a postfix notation calculator. Doable with a stack. Now, what if you wanted to support arbitrary operations on some variable number of preceding numbers? How does the code change? 4. You are given a tree in the form of a list of (value, parentndx, intree) tuples, where intree is a boolean denoting whether the node is in the tree, and parentndx is the location in the list of the parent node of this node. The root's parent is -1. Write a function remove(ndx) that removes the node at that ndx and all its children in O(n). It requires caching which nodes have been visited and a recursive function that checks whether a node in the list should be removed (terminates on parentndx==-1 || ndx or when it finds a cached node that was already removed and visited). 5. You are given two infinite streams of data, where each datum has fields (timestamp, value). The streams have a single function take() that pops the oldest thing off and returns it or "blocks" until something arrives in the queue for it to return. Data might arrive much later than its timestamp. You are given a function output(a,b), which takes two values, one from each stream, and computes something. You want to call output() on all (a,b) pairs that have timestamps less than some given interval apart, and you want to do this as soon as any data that completes such a pair arrives. Construct pseudocode that will do this. The answer involves two threads that each manage a list of numbers pulled off their stream, pull a number from the other thread's list, try to match it against everything, and then carefully discard data when appropriate. 6. You are managing a webservice and get a complaint about the page loading slowly. What is a possible cause of the problem? How would you check that? Okay, say that's not the problem. What else could it be?

Design questions