News for hackers. Stuff that matters.
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.
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.