11.9 – applied
11.12 – OA
11.24 – got the invite for the next round
12.1 – interview
12.3 – rejection letter
The interviewer's English was really good, and he was patient and kept trying to guide me, but at the time I just couldn't understand why we needed to build a tree to encode things. It wasn't until later that it clicked — it's to get a unique binary representation, so that the most frequent character ends up with a shorter binary representation.
Difficulty was Medium to Hard. The main issue was that the problem statement was really long — I spent ten minutes clarifying it and still didn't fully get it. In the end I started coding in kind of a daze, and I only finished the encode function.
My personal feeling is that the main difficulty is understanding the problem. Once you understand what the problem is actually asking you to do, you're already 30% of the way there.
The problem description was pretty complex. The gist of it was: implement a binary encoding function and a decode function.
Given a string, encode it and decode it according to the problem's requirements.
encode: Starting from the characters with the lowest frequency, build leaf nodes. A parent node's value is the sum of the frequencies of its left and right leaf nodes, and a node's value is the character. Build a binary tree in a specific order. Branch (edge) values are 0 and 1. After building the tree, traverse from the root down to a leaf, and the sequence of edge values you collect along the way (e.g. 01001) is that leaf's binary representation.
decode: Convert the binary representation back into the original string.
Last year I applied to Two Sigma and didn't even clear the OA. This year, getting knocked out after one round still counts as progress. Moving on!
Discussion
Loading comments…