Two Sigma OA, bombed the tree one
Two Sigma OA, bombed the tree one
Took the Two Sigma SWE OA on Sunday, 2 questions. I'm pretty sure I'm out, so writing this down while it's still fresh.
First one was fine. Second was Pythagorean Triples, and I'd never seen it before. You get a tree as two edge arrays, plus three distinct nodes x, y, z. For every node in the tree you look at its distance to each of those three, sort them, and check if they make a right triangle. Count how many nodes pass.
Once I stopped panicking it's really just three BFS passes from x, y and z, then a loop over nodes. My first attempt ran a BFS per node, which is n squared, and I didn't catch that until a couple of hidden tests timed out. Rewrote it with maybe 12 minutes left and I'm still not sure the rewrite passed everything.
I also tripped over a test where the target nodes sat right next to each other on a long chain. Kept trying to reason about 0 distance cases and wasted time.
Has anyone heard back from Two Sigma after a partial OA? Recruiter said 1 to 2 weeks.
Replies (5)
partial passed for me last year and I still got the phone screen, though that was a different track
did you get anything about doing it in fewer passes? someone told me a follow up asked about LCA but maybe that was a phone screen
no follow ups, it's just the OA. no human in the loop
had the same one in September. three BFS is the move, I also did per node first lol
did the first question involve IPO allocation? trying to figure out which pool they're using now
no it was a tree one too, subtree sums, cutting an edge to minimize the difference
0 distance only happens if the node is one of the targets so you can mostly ignore it, sucks to burn time on that though
yeah figured that out after submitting ofc