logic

  • 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 

Since we can’t compare a nut with other nuts and a bolt with other bolts, we can’t sort them. So current best possibility seems to pick nuts one-by-one and find matching bolts for them. In this manner, we will match all the pairs in O(n^2) time complexity.
But though we can’t compare a nut with other nuts and so for bolts, we can compare a nut with bolts and vice-versa. Also keep in mind that if a Nut(N) is smaller than a Bolt(B) than N is fit only for bolts smaller than B. Similarly if a Bolt(B’) is smaller than a Nut(N’) than N is fit only for bolts smaller than B’. So we can go like following in solving this problem.
  • 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.
Now we have 2 subsets of Nuts and Bolts. If we pick a nut from small size nuts pile, we will get a corresponding bolt in smaller size bolts pile and similarly for large size piles. At every step, we will be able to divide these piles in 2 halves and reduce complexity by a factor of 2 in average case. In this case time complexity will be O(nlogn).

In worst case we might have choose the smallest/largest nut/bolt as reference and our one pile will have zero nut/bolt and another pile will have all the remaining. In this case time complexity will be O(n^2).
Algorithm:
Take a nut; partition the bolts with respect to this nut. We will find the matching bolt for this nut. Now take the bolt; partition the nuts.
In this manner, we have divided the Original problems into 2 sub-problems.
T(n) = T( i ) + T(n-i ) + O(n)
Where we have chosen the ith largest nut from a particular pile.
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
insertion sort
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
Quicksort
7. Minimum Difference between Two Arrays
Given 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 yelements. A brute force algorithm needs O(n^2) 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 differences are 3, 2, and 1, respectively. The definition 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 partcompute the sum of the numbers from 1 to N-1. Then sum the values 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.

Advertisements

Loop detection in Singly Linked List.

Floyd’s Cycle Detection Algorithm (The Tortoise and the Hare) :

In Brief : How do you determine if your singly-linked list has a cycle?
In the late 1960s, Robert W. Floyd invented an algorithm that worked in linear (O(N)) time. It is also called Floyd’s cycle detection algorithm or The Tortoise and the Hare

 tortoise = top
 hare = top
  
 forever:
      if hare == end :
          return 'No Loop Found'
      hare = hare.next
  
      if hare == end :
         return 'No Loop Found'
     hare = hare.next
 
     tortoise = tortoise.next
 
     if hare == tortoise:
         return 'Loop Found'	

hare

The easiest solution to the cycle detection problem is to run through the list, keeping track of which nodes you visit, and on each node check to see if it is the same as any of the previous nodes. It’s pretty obvious that this runs in quadratic (O(N^2)) time… not very efficient, and actually more complicated than this one.

The Tortoise and the Hare is possibly the most famous cycle detection algorithm, and is surprisingly straightforward. The Tortoise and the Hare are both pointers, and both start at the top of the list. For each iteration, the Tortoise takes one step and the Hare takes two. If there is a loop, the hare will go around that loop (possibly more than once) and eventually meet up with the turtle when the turtle gets into the loop. If there is no loop, the hare will get to the end of the list without meeting up with the turtle.

Why can’t you just let the hare go by itself? If there was a loop, it would just go forever; the turtle ensues you will only take n steps at most.

Note : Most of the part of this post is taken from http://www.siafoo.net/algorithm/10

Greatest Sum of Sub-Arrays…


Question : Given an integer array containing positive and negative numbers, how do you get the maximum
sum of its sub-arrays? Continuous numbers form a sub-array of an array.For example, if the input array is {1, -2, 3, 10, -4, 7, 2, -5}, the sub-array with the maximum sum is {3, 10, -4, 7,2} whose sum 18.

Let’s accumulate each number in the sample array from beginning to end. Our solution initializes sum
as 0. In the first step, it adds the first number 1, and sum becomes 1. And then if it adds the second
number -2, sum becomes -1. At the third step, it adds the third number 3. Notice that the previous sum is
less than 0, so the new sum will be 2 and it is less than the third number 3 itself. Therefore, the previous
accumulated sum -1 should be discarded.
The key point here is that when the sum becomes a negative number or zero, adding this sum to the
following array element will not be greater than the element itself, so the new sub-array will start from
the next element.
It continues accumulating from the next number with sum 3. When it adds the fourth number 10,
sum becomes 13, and it decreases to 9 when it adds the fifth number -4. Notice that the sum with -4 is
less than the previous sum 13 because of the negative number -4. It saves the previous sum 13 since it
might be the max sum of sub-arrays.
At the sixth step, it adds the sixth number 7 and sum becomes 16. Now sum is greater than the
previous max sum of sub-arrays, so the max sum is updated to 16. It is similar when it adds the seventh
number 2. The max sum of sub-arrays is updated to 18. Lastly it adds -5 and sum becomes 13. Since it is
less than the previous max sum of sub-arrays, the final max sum of sub-arrays remains 18, and the subarray
is {3, 10, -4, 7, 2} accordingly.


int getGreatestSumOfSubArray(int[] numbers) {
   int curSum = 0;
   int greatestSum = Integer.MIN_VALUE;
   for(int i = 0; i < numbers.length; ++i) {
     if(curSum <= 0)
        curSum = numbers[i];
     else
        curSum += numbers[i];

     if(curSum > greatestSum)
     greatestSum = curSum;
   }
   return greatestSum;
}

(Apress.Coding.Interviews.Questions.Analysis.and.Solutions)

Finding minimum and maximum value in Array in single pass…

To find the minimum value into an array of items, take the first item and to compare its value against the values of all other elements. Once we find a smaller element we continue the comparisons with its value. Finally we find the minimum.

We pass through the array with n steps and we need exactly n-1 comparisons.

Finding the maximum is identical to finding the minimum and requires n-1 comparisons!

Since they both are O(n) and need n-1 comparisons it’s natural to think that combining the two tasks will be O(n) and 2n – 2 comparisons. However we can reduce the number of comparisons!

Instead of taking only one item from the array and comparing it against the minimum and maximum we can take a pair of items at each step. Thus we can first compare them and then compare the smaller value with the currently smallest value and the greater item with the currently greatest value. This will make only 3 comparisons instead of 4.

The complexity of finding both minimum and maximum is O(n). Even after combining the both algorithms in one single pass the complexity remains O(n). However in the second case we can reduce the number of comparisons to 3 * ceil(n/2) instead of 2n – 2!

Finding duplicates in array…


An array contains n numbers ranging from 0 to n-1. There are some numbers duplicated in the
array. It is not clear how many numbers are duplicated or how many times a number gets duplicated. How do you
find a duplicated number in the array? For example, if an array of length 7 contains the numbers {2, 3, 1, 0, 2, 5,
3}, the implemented function (or method) should return either 2 or 3.

Indexes in an array with length n are in the range 0 to n-1. If there were no duplication in the n
numbers ranging from 0 to n-1, we could rearrange them in sorted order, locating the number i as the ith
number. Since there are duplicate numbers in the array, some locations are occupied by multiple
numbers, but some locations are vacant.
Now let’s rearrange the input array. All numbers are scanned one by one. When the ith number is
visited, first it checks whether the value (denoted as m) is equal to i. If it is, we continue to scan the next
number. Otherwise, we compare it with the mth number. If the ith number equals the mth number,
duplication has been found. If not, we locate the number m in its correct place, swapping it with the mth
number. We continue to scan, compare, and swap until a duplicated number is found.
Take the array {2, 3, 1, 0, 2, 5, 3} as an example. The first number 2 does not equal its index 0, so it is
swapped with the number with index 2. The array becomes {1, 3, 2, 0, 2, 5, 3}. The first number after
swapping is 1, which does not equal its index 0, so two elements in the array are swapped again and the
array becomes {3, 1, 2, 0, 2, 5, 3}. It continues to swap since the first number is still not 0. The array is {0,
1, 2, 3, 2, 5, 3} after swapping the first number and the number with index 3. Finally, the first number
becomes 0.
Let’s move on to scan the next numbers. Because the following three numbers, 1, 2 and 3, are all
equal to their indexes, no swaps are necessary for them. The following number, 2, is not the same as its
index, so we check whether it is the same as the number with index 2. Duplication is found since the
number with index 2 is also 2.


int duplicate(int numbers[]) {
int length = numbers.length;
for(int i = 0; i < length; ++i) {
if(numbers[i] < 0 || numbers[i] > length - 1)
throw new IllegalArgumentException("Invalid numbers.");
}
for(int i = 0; i < length; ++i) {
while(numbers[i] != i) {
if(numbers[i] == numbers[numbers[i]]) {
return numbers[i];
}
// swap numbers[i] and numbers[numbers[i]]
int temp = numbers[i];
numbers[i] = numbers[temp];
numbers[temp] = temp;
}
}
throw new IllegalArgumentException("No duplications.");
}

Finding the second highest value in array

// Initialize these to the smallest value possible
int highest = Integer.MIN_VALUE;
int secondHighest = Integer.MIN_VALUE;

// Loop over the array
for (int i = 0; i < array.Length; i++) {

    // If we've found a new highest number...
    if (array[i] > highest) {

        // ...shift the current highest number to second highest
        secondHighest = highest;

        // ...and set the new highest.
        highest = array[i];
    } else if (array[i] > secondHighest)
        // Just replace the second highest
        secondHighest = array[i];
    }
}

// After exiting the loop, secondHighest now represents the second
// largest value in the array<br />

Difference between for and forEach

Check below two constructs :

char[] arr1 = new char[]{'1','2'};
  for (char x : arr1) {
  System.out.println(x);
  arr1 = null;
}

char[] arr = new char[]{'3','4'};
  for (int i = 0; i &lt; arr.length; i++) {
  char x = arr[i];
  System.out.println(x);
  arr = null;
}

Both code compiles, but if you run them, you will find that the first loop terminates normally, while the second loop will throw a NullPointerException.

Output :
1
2
3

Exception in thread “main” java.lang.NullPointerException
at test.process.ThreadTestMain.main(ThreadTestMain.java:27)