**Sorting**

**1. Alternating sort**

Given a list of pairwise distinct integers, sort it in alternating order: The second number is larger than the first, the third is smaller than the second, the fourth is larger than the third etc. (This order is not unique.) E.g., `5 7 3 4 2 9 1`

would be valid output.

**Solution **

You can do this in O(n) by placing each element in turn at the end, or at the penultimate position based on a comparison with the current last element.

For example,

```
1,4,9,2,7,5,3,8,6
Place 1 at end, current list [1]
4>1 true so place 4 at end, current list [1,4]
9<4 false so place 9 at penultimate position [1,9,4]
2>4 false so place 2 at penultimate [1,9,2,4]
7<4 false so place 7 at penultimate [1,9,2,7,4]
5>4 true so place 5 at end [1,9,2,7,4,5]
3<5 true so place 3 at end [1,9,2,7,4,5,3]
8>3 true so place 8 at end [1,9,2,7,4,5,3,8]
6<8 true so place 6 at end [1,9,2,7,4,5,3,8,6]
```

Note that the equality tests alternate, and that we place at the end if the equality is true, or at the penultimate position if it is not true.

**2. Turning Number in an Array**

Turning number is the maximum number in an array which increases and then decreases. This kind of array is also named unimodal array. Please write a function which gets the index of the turning number in such an array.

For example, the turning number in array {1, 2, 3, 4, 5, 10, 9, 8, 7, 6} is 10, so its index 5 is the expected output.

**3. Sum Of Three**

Given three sets A, B, and C of at most N integers each, determine whether this is a triple a in A, b in B,

and c in C such that a + b + c = 0.

**Solution**

Sort B in increasing order; sort C in decreasing order; for each a in A, scan B and C for a pair that sums to – a

(when the sum is too small, advance in B, when the sum is too large, advance in C).

**4. Expensive exchange**

A clerk at a shipping company is charged with the task of rearranging a number of large crates in order of the time they are to be shipped out.

Thus, the cost of compares is very low (just look at the labels) relative to the cost of exchanges (move the crates). The warehouse is nearly full—there is extra space sufficient to hold any one of the crates, but not two. What sorting method should the clerk use?

**5. Nuts and bolts(G. J. E. Rawlins) **

You have a mixed pile of N nuts and N bolts and need to quickly find the corresponding pairs of nuts and bolts. Each nut matches exactly one bolt, and each bolt matches exactly one nut. By fitting a nut and bolt together, you can see which is bigger, but it is not possible to directly compare two nuts or two bolts. Give an efficient method for solving the problem.

**Solution **

- Take a nut from the nuts pile
- Divide bolts around it in 2 parts, which are smaller and larger than this.
- Find a matching bolt to this nut.
- Divide nuts in 2 parts, which are smaller and larger than matching bolt.

**Algorithm:**

**Average time complexity**= O(nlogn).

**Worst time complexity**= O(n^2).

**6. The way a card game player arranges his card as he pick them up 1 by 1 is an example of :**

**Solution**

**7. Which sorting algorithm should not be used in below case :**

**1) data is already sorted in same order.**

**2) data is already sorted in reverse order.**

**3) All elements are same (special case of case 1 and 2)**

**Solution**

**7. Minimum Difference between Two Arrays**

*x*[1], …,

*x*[

*m*] and

*y*[1], …,

*y*[

*n*], design an algorithm to find two elements

*x*[

*i*] and

*y*[

*j*] such that the absolute value |

*x*[

*i*] –

*y*[

*j*]| is minimized over all posibble pairs of

*x*and

*y*elements. A brute force algorithm needs O() time. Your algorithm should be far more efficient than that. Analyze the time complexity of your algorithm.

**Solution**

First, sort array x. Then, for each element in y, use Binary Search method to find the element with the closest value in array x. In this way, we can find the pair with the minimum absolute value of the difference. Sorting the array takes O(m lg m) time and binary search takes O(n lg m) time.

**8. Pancake Sorting**

Jeremy is a waiter working in a restaurant. The chef there is sloppy; when he prepares a stack of pancakes, they come out all different sizes. When Jeremy delivers the pancakes to the customer, he wants to rearrange them by grabbing several from the top and flipping them over on the way. After repeating this for several times, the smallest pancake is on top, and so on, down to the largest at the bottom. If there are n pancakes, how many flips are required? Design an algorithm to help Jeremy, and analyze its time complexity.

**Solution**

This problem is called pancake sorting. For a stack of pancakes, we first locate the largest pancakes. Then we flip the largest pancakes to the top by using one flip and use another flip to move the largest pancaked to the bottom. Then, we recursively sort the top n-1 pancakes. Since every pancake except the smallest one needs at most two flips to move to the correct position, the number of flips is 2(n – 1).

**Arrays **

**2. Jolly Jumpers**

A sequence of n integers is called a jolly jumper if the absolute values of the differences between successive elements take on all possible values 1 through n − 1.Where n > 0.

For instance, 1 4 2 3 is a jolly jumper, because the absolute diﬀerences are 3, 2, and 1, respectively. The deﬁnition implies that any sequence of a single integer is a jolly jumper. Write a program to determine whether each of a number of sequences is a jolly jumper.

**3. Given an array of n integers, where one element appears more than n/2 times, find that element in linear time and constant extra space. **

**Solution**

*There is a beautiful algorithm for solving this that works in two passes (total time O(N)) using only constant external space (O(1)).*

*The intuition behind the algorithm is actually quite beautiful. Suppose that you were to have a roomful of people each holding one element of the array. Whenever two people find each other where neither is holding the same array element as the other, the two of them sit down. Eventually, at the very end, if anyone is left standing, there’s a chance that they’re in the majority, and you can just check that element. As long as one element occurs with frequency at least N/2, you can guarantee that this approach will always find the majority element.*

*To actually implement the algorithm, you make a linear scan over the array and keep track of your current guess as to what the majority element is, along with the number of times that you’ve seen it so far. Initially, this guess is undefined and the number of repeats is zero. As you walk across the array, if the current element matches your guess, you increment the counter. If the current element doesn’t match your guess, you decrement the counter. If the counter ever hits zero, then you reset it to the next element you encounter. You can think about this implementation as a concrete realization of the above “standing around in a room” algorithm. Whenever two people meet with different elements, they cancel out (dropping the counter). Whenever two people have the same element, then they don’t interact with each other.*

items = [1, 2, 3, 4, 5, 5, 5, 5, 5 ]

# shuffle the items

random.shuffle(items)

print(“shuffled items: “, items)

majority_elem = items[0]

count = 1

for i in range(1,len(items)):

if items[i] == majority_elem:

count += 1

else:

count -= 1

if count == 0:

majority_elem = items[i]

count = 1

print(“majority element : %d” % majority_elem )

**4. Given an array of size N that contains values between 1 and N-1, find the duplicate element (assuming there is only one). If it contains values between 1 and N+1, how would you find the missing element (again assuming there is only one missing)? Do each in O(N).**

**Solution**

*For the **first** **part**, **compute** the **sum** of the **number**s from 1 to N-1. Then sum the **value**s in the **array**. The **duplicate** number is the **difference** between these sums.*

*For the second part, compute the sum of the numbers from 1 to N+1. Then sum the values in the array. The **missing** number is again the difference between these sums.*