Phone Screen 1
The interviewer gave me a distributed tree counting problem that took me a while to even understand. There was no starter code or example — he just said to imagine tree nodes distributed across different places on a network, and my job was to design a class to accomplish that. The problem was way too vague at the start, and we spent a long time discussing what exactly he wanted. I didn't manage to fully finish it, but the gist of what he wanted was:
A Node class containing id, children, parent (this helps with the methods later), and whatever other attributes are useful (design them yourself).
sendAsync(toNode, message): a pseudo function that's assumed to be able to deliver a message.
receive(fromNode, message): the thing we actually had to write — you design what behavior happens when you receive a given message here.
He called it a tree problem, but honestly I don't think it's really about tree traversal at all — it's more about thinking through, from a systems angle, how nodes should reasonably pass information to each other. At its core the problem wants each node to be an independent process: they have no global view, and can only talk to their direct parent and children. On top of that, the code can't block, so what each node really needs to handle is:
When it receives a count request from its parent, it sends a lookup instruction down to each of its children.
When it receives a count result from a child, it quietly increments the count and the number of responses received.
Once the number of responses received equals the number of children, it knows all the results are in, and at that point it sends the result up to its own parent.
They called it a tree problem, but it's really more like a state machine — once you see that, it's not that complicated (though there are a lot of edge cases).
On receiving a GET_COUNT instruction: a leaf node needs to send a report_count instruction to its parent; a non-leaf node just dispatches the same kind of instruction down to its children.
On receiving a report_count instruction: accumulate the data, and once all children have reported in, report up to the parent.
I barely managed to get through it, and then the follow-up was how to optimize this for an unreliable network (duplicate requests, dropped packets). I ran out of time to write anything for that.
After the first round I didn't have the heart to keep fighting for it. It's a little sad — I actually thought pretty highly of Snowflake — but I just didn't have the chops for it.
Discussion
Loading comments…