Re:I had to give a wrong answer to get the job (2017)
by planet-and-halo on Monday July 19, 2021 @02:53PM
(#27886063)
I had a less dramatic one where someone argued with me that the lookup time on a binary tree was O(H), the height of the tree, not O(log2n). I was so baffled by the argument that I didn't realize until after the interview that I should have pointed out that the height of a binary tree is log2n.
[ Parent
| on HN ]
Re:I had to give a wrong answer to get the job (2017)
by slavak on Monday July 19, 2021 @03:27PM
(#27886378)
They were technically correct. The lookup time on a binary search tree is O(H), which is equal to O(log2n) if the tree is balanced. Tree data structures invest a lot of complexity into keeping the tree balanced.
Re:I had to give a wrong answer to get the job (2017)
by planet-and-halo on Monday July 19, 2021 @07:08PM
(#27888316)
Doesn't this only affect inserts and deletes though? I mean I get your point, but on a read you can assume that a binary tree is balanced (by definition). Or am I missing something?
Re:I had to give a wrong answer to get the job (2017)
by wtetzner on Monday July 19, 2021 @10:51PM
(#27889605)
No, not all binary trees are balanced binary trees.
Re:I had to give a wrong answer to get the job (2017)
by planet-and-halo on Monday July 19, 2021 @11:19PM
(#27889740)
Ah got it, thanks.