Problems

Most repeating element

Problem Statement: Given an array find the most repeating element

Approach:

1. Sort and count. TC: O(n log n)
2. Counting Sort. TC: O(n), SC: O(k)
3. AVL Trees: TC: (n log k), SC: O(k)

---

Problem Statement: Given an array of n numbers, each of which is in the range [0 ... \(n^2\)]. Sort then im O(n)

Approach:
Radix sort

---

Nearly Sorted

Problem Statement: Given an array of n elements, each which is at most K positions from its target position. Sort them in O(n log K)

Approach:

---

Sort Linked Lists

Problem Statement: Given a linked lists. Sort it using quick sort

Approach:

---

Telephone directory

Problem Statement: Given a telephone directory with 10 million records, which sorting algorithm is best?

Approach:

---

Nuts and bolts

Problem Statement: Given a set of n nuts of different sizes and bolts such that there is one-to-one correspondence between the nuts and bolts. Find for each nut its corresponding bolt.

Approach:

---

Squares of a sorted array

Problem Statement: Given a sorted array of integers. Find the sorted array of their squares.

Approach:

---

Problem Statement:

Approach: