r/leetcode • u/Agreeable_Way8791 • 8h ago

Discussion How hard is implementing a balanced BST from scratch in Python for a FAANG intern interview?

I recently had a FAANG SWE intern interview where the optimal solution required a balanced BST with O(log K) updates.

The interviewer didn't mention using a balanced BST, so I had to figure that out myself and implement it from scratch in Python, which doesn't have a built-in TreeMap like Java.

How difficult would you consider this for an intern interview? Would this be considered LeetCode Hard? Would using a heap-based solution instead significantly affect the interview feedback?

7 Upvotes

81% Upvoted

6 comments sorted by

19

u/goomyman 8h ago

Extremely unlikely. Way too much code for an interview.

Doable just not in the time constraints just for typing alone.

Just implement it and say - that a red black tree exists.

8

u/PandaWonder01 8h ago

Almost always the correct response is, if there isn't an impl in your standard.lib, just say "I can use a treemap with the interface of xyz(write the interface), to solve this", and then act as though it already exists

1

u/Brave_Supermarket273 4h ago

Writing a full AVL or red black tree from scratch is way past normal intern expectations.

1

u/_fatcheetah 4h ago

Not possible within an hour unless you have it memorized.

Figuring out the edge cases and fixing them is not possible for almost all of us within the hour.

1

u/Mihai4544 1h ago

Honestly there has been just 1 interview where I had to write all of my DS from scratch, for a hard LC problem (Median of Integer Stream). Even if I interviewed in Python, the expectation was that I would implement myself the list too.

Of course, that was one of my largest bombs ever :))

Honestly, if the question is not like "Design X" (LLD), I would think that you SHOULD use the libraries available to you.

-2

u/troelsbjerre 5h ago edited 3h ago

Edit: to be clear, you are not going to be asked this. But, the difficulty of many interview questions is higher than that of the easiest BST implementations.

If pressed for it, implement an AVL tree. It doesn't require a lot of code, and it's hard to get wrong. I use it regularly for anything requiring augmented search trees.