Practice questions – I
Please try on your own first before peeking into the Hints.
Linked lists
Problems
- How would you insert, delete and search a key in the linked list?
- Insert a node in a sorted linked lists such that the sorted order is preserved.
Find the suitable position before inserting the node.
- Write an algorithm to detect a cycle in a linked list.
Maintain two pointers – a slow pointer (which moves forward one node at a time) and a fast pointer (which moves forward two nodes at a time). If they meet that is a cycle.
- Remove consecutive duplicate entries from a given linked list.
- Get the k-th to the last element in a singly linked list (when the size of the list is not known/tracked).
Maintain two pointers with a distance of k.
- Check if the linked list is a palindrome.
- Get the middle of the linked list.
- Reverse the second half of the linked list.
- Compare the first and the second half.
- Reconstruct back by reversing the second half again.
- Reverse a singly linked list.
Stacks and queues
- How would you implement a stack using an array?
- How would you implement a stack using a linked list?
- How would you implement a queue using an array?
- How would you implement a queue using a linked list?
- Write an algorithm to match parentheses of various kinds: {}, (), [].
- How to design a stack such that getMinimum() is O(1)?
Maintain another stack which tracks the minimum as the stack gets pushed and popped.
Recursion
- Write a recursive algorithm to perform x^n.
- Write a recursive algorithm to count the number of 1’s in a given binary representation.
- Write a recursive algorithm to reverse a string.
Rooted trees
- Find the nearest match of a given key in a binary search tree.
- Write a function to check whether two binary trees are structurally identical.
- Write a function find the size of a binary tree.
- Write a function to compute the sum of all elements in a BST.
Complexity analysis
- Given an algorithm, find the timing complexity.
- What is the difference between Big-oh and Big-sigma?