Is it required to practice the code of these also as we do for binary search or other normal algorithm
I was asked once in past couple months.
Where....
Maybe it's just bad luck if you run into something like this. Great if you know it but not necessary.
How about KMP string maching algorithm? IMO these questions don't test someone's problem solving skills.
Hmm
OP if you are asking about typical SWE interviews at the companies you tagged the answer is pretty simple. You will not need to write a BBST or KMP from scratch. You should understand what a BBST does and how to use it. Not just as a black box but understand the BST layout and how searching the tree would work. You will not need to explain in detail how to rebalance after an insert, just understand that it happens.
AVL tree conceptually isnโt that bad. Each node just has an added height attribute. The hard part is implementing the rotation logic. But at that point, what is the interviewer getting when you try to rotate nodes p,q,v
I was asked a question which required me to implement a red Black tree at Google onsite interview
These are knowledge questions. You can memorize and go. What will the interviewer get?
Itโs good to know how to implement at least one self-balancing binary tree. This was asked at CEOI โ11. The problem is called โHotel.โ (Not a company, but still.)
This comment is misguided. "Hotel" doesn't ask you to implement a BBST. The interesting part is coming up with and proving the greedy algorithm. You can then use a built-in BBST like C++'s std::set to implement it.
Also the bar for "good to know" isn't "appeared on one contest at some point" unless you are trying to win IOI/ICPC/Code Jam or interview with the most selective place in the world.