prior knowledge do make you look brainy: algo IV

After solving the min-stack problem, I found something paradoxical , even nonsensical — Someone said this question is considered “easy”, but if you have not seen it before then you may find it extremely hard. I thought O(1) worst case was impossible. I have experienced many similar situations where prior knowledge can make you look very brainy.
  • example — detect loops in a singly linked list, where the loop could be far out.
  • example — reverse an extremely long singly linked list which breaks any recursive solution, so you must use non-recursion
  • example — in a regular unsorted binary tree (every node has up to 2 child nodes and no uplink to parent) how to print all nodes in-order but with O(1) additional space and O(N) time
I feel west coast (and Bloomberg) tend to ask this type of questions because they expect their candidates to study and acquire the knowledge before applying.
If you don’t study, and hope to come up with a reasonable solution on the spot, then you must be extremely intelligent or lucky. I think the math Olympiad gold medalists also need to study before their competitions.

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

您正在使用您的 WordPress.com 账号评论。 登出 /  更改 )

Google photo

您正在使用您的 Google 账号评论。 登出 /  更改 )

Twitter picture

您正在使用您的 Twitter 账号评论。 登出 /  更改 )

Facebook photo

您正在使用您的 Facebook 账号评论。 登出 /  更改 )

Connecting to %s