[anonymoushn]

Recently I failed an interview at Facebook because I chose to serialize a binary tree into a list of N items, rather than a list of N items and O(N) sentinels. Most of the interview was spent convincing the interviewer that this could possibly be correct.

[z3t4]

i recently failed a programming test after acing all tests except one where i needed a text diff and pulled in a library instead of writing my own in less then ten minutes. they said i need to get better at algos. which is fair. but i dont know anyone that can program a decent working text diff in less then ten minutes.

[mquander]

Based on your description, it sounds possible they were just looking for a Levenshtein distance implementation, which is definitely in the Universal Weird Corpus of Interview Questions and for which people who prepare for interviews a ton would have a good shot.

[flukus]

I ported a diff algorithm (a simple one at that) just a few months ago because the language I was working in didn't have one. I couldn't do it off the top of my head today, or probably the day after, it was transient knowledge that I didn't even try to remember.

[mquander]

Why did you conclude that you failed because of that? That sounds like a pass with flying colors. Did you specifically get feedback about that segment?

[anonymoushn]

In the few remaining minutes after we agreed that it was possible to correctly deserialize a tree serialized in this way, I did not produce a linear time deserializer.

[mquander]

:-(

[dastbe]

was it a binary tree or a binary search tree? a BST can be uniquely identified by one of pre/post-order traversal, whereas a binary tree requires an in-order traversal and one other. or placing sentinels that specify a state machine [PUSH_LEFT, PUSH_RIGHT, POP] that specify how to move down and up the tree structure.

[anonymoushn]

It was a BST.

[akhilcacharya]

n sentinels? What do you mean?

Do you mean characters to indicate a null child?