# 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?