# Practice questions – I

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

1. Get the middle of the linked list.
2. Reverse the second half of the linked list.
3. Compare the first and the second half.
4. 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?