How to prepare for an interview - 2

This is the second post in the How to prepare for an interview series, If you haven't read the last post you may like to read and practice previous problems here.

Today i will put another set of problems with its solutions in C++, again and again in order to get the best out of this training, you should read the problem, try to solve it and then read my solution, discuss it with me.

Remember you should discuss these solutions with me, and refer if there are mistakes or other good solutions.

Problems

11. Given a circular linked list, implement an algorithm to return the beginning of the loop in that list.

Example:

Input: A -> B -> C -> D -> E -> C [the same C as earlier]
Output: C



12. Design a CustomStack data structure which in addition to push, pop, also has a function min to return the minimum value in the stack, and should be in O(1).



13. Implement an algorithm to solve Tower of Hanoi puzzle. What is Tower of Hanoi?



14. Implement a queue data structure with two stacks.



15. Given a stack, sort it.



16. Given a tree data structure, implement a function to check if this tree is balanced or not, for the purpose of this problem a balanced tree is a tree such that no two leaf nodes differ in distance from root by more than one.



17. Given a directed graph, design an algorithm to find out whether there is a route between two nodes.



18. Given a sorted array (increasing order), write an algorithm to create a binary tree with minimal height.



19. Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth, (i.e., If you have a tree of depth D, you will have D linked lists).



20. Write an algorithm to find the next node (i.e., in-order successor) of a given node in a binary search tree where each node has a link to its parent.

Now we have solved all today's problems. I know it were harder than the previous one, But i'm sure you will enjoy solving them, read the next post.