Determine if an array is almost sorted, if not, how to sort it efficiently?

Given an array A of distinct elements with length n, determine if the array is 90% sorted.

1. Considering the following algorithm:

• Choose an element with index i independently and uniformly at random from 0 < i < n - 1;
• Compare the element with A[i - 1], output false if they are not sorted correctly;
• Compare A[i] with A[i + 1], output false if they are not sorted correctly.

Prove that the algorithm will return false with probability at least 2 / 3 if A is not 90% sorted only the algorithm is repeated k = Ω(n). 

Given the following counter example:
A[n/2 + 1, ..., n, 1, 2, 3, ... n / 2].
It is obvious that A is not 90 % sorted. So if we want to use the above algorithm to prove that A is not 90% sorted, each iteration we need to choose the first element to be 1, and then compare it with n, or the first element must be n, which will return false when compare with the next element.
Either case, the probability is 2 / n. Now this leads the probability of not in either of the above case 1 - 2/n.
Moreover, we know that the algorithm will be terminated once either the above case is determined. So:

(1 - 2/n)^k <= 1/3

We know that ( 1 - 1 / x)^x < 1 / e

so performing a little bit math leads to k >= (ln3)/2 *n = Ω(n). 

2. Consider performing binary search on an unsorted array. Given key1 and key2 in A, it will return index i and j. We know that if key1 < key2, then i < j (why?). Now consider the following randomized algorithm:
Randomly pick up index i from A, performing binary search with key A[i], which will return index j. If i != j, return false. 
Show that the algorithm is correct and will return false with probability at least 2/3 if the list is not 90% sorted if k is sufficiently large constant. 

First, it is easy to understand that if the array is sorted, then BST will always return true. Now we want to know that if the array is not 90 % sorted, then it will return false with probability 2 / 3 with a proper k. Alternatively we can translate the problem into a typical probability problem:

Given a bag of balls, we know that at least 10% balls are blue, and the others are red, how many balls do we have to draw from the bag to get a blue ball with the probability at least 2/3? 

Similar to the first question we can get:

(9/10)^k <= 1/3

k >= (ln3)/(ln(10/9))

So if we iterate the algorithm greater than (ln3)/(ln(10/9)), we will find an unsorted element with probability 2/3.

3. So what if we want to check if the array is not (1 - ε) sorted? 

The same:

(1- ε)^k <= 1/3

k >= (ln3)/ε

4. Prove that if the given array is partially sorted in k slots, e.g., 

A={7, 8, 9, 4, 5, 6, 1, 2, 3}, then k = 3

Using insertion sort will lead to O(nk) complexity. 

We know that since that each element is in the right order within its slot, so elements in the first slot need not move, the second slot will move number of elements in the first slot, and so on. Given n elements and k slots, each slot will contain n / k elements. So we will have the following equation:

(n/k) * 0 + (n/k) * 1 + ... + (n/k) * (k - 1) = n(k-1)/2 = O(nk)

5. Find an algorithm that sort this partially sorted array in O(nlog k) times, where k is number of slots. 

This is just merge k sorted array algorithm. We use a priority queue, insert the first element in each slot into the queue, since the size of the queue is always k, inserting an element takes O(logk) time, we have n elements, thus merge the whole array takes O(nlogk) time.

Sort String

You are given two strings. String T is a string where characters need to be reordered. String O contains characters (none of them repeated) which defines the order/precendence to be used while reordering the string T. Write an algorithm to do the reordering.
*** SPOILER ALERT ***
The question was pusposefully underspecified - upon questioning it was revealed that the string O might not necessarily include all characters used in string T - the characters not included in string O are supposed to be placed at the beginning of the resulting string (in no particular order).

At first, I thought it is a type of counting sort, so I was trying to use an array. The spoiler reminds me that not all characters in String T is included in String O, so it probably is not. I finalized with a map implementation, which may not be the most optimal one consider the extra space I used.

public class SortString {
 public static String sortString(String T, String O){
  if(T == null || O == null || T.length() == 0 || O.length() == 0)
   return T;
  Map count = new HashMap ();
  for(int i = 0; i < O.length(); i++)
   count.put(O.charAt(i), 0);
  StringBuilder rst = new StringBuilder();
  for(int i = 0; i < T.length(); i++){
   char c = T.charAt(i);
   if(!count.containsKey(c))
    rst.append(c);
   else
    count.put(c, count.get(c) + 1);
  }
  for(int i = 0; i < O.length(); i++){
   char c = O.charAt(i);
   int num = count.get(c);
   while(num-- > 0){
    rst.append(c);
   }
  }
  return rst.toString();
 }

 public static void main(String[] args) {
  String T = "dcdavgtealgbm";
  String O = "abcdefghijkl";
  System.out.println(sortString(T, O));

 }

}

Largest number of people

A circus is designing a tower routine consisting of people standing atop one another’s shoulders.For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her.Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower.
EXAMPLE:
Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
Output: The longest tower is length 6 and includes from top to bottom: (56, 90) (60,95) (65,100) (68,110) (70,150) (75,190) 

The book (Cracking the coding interview) provides a solution that requires extra O(2n) space. I don't think they are necessary. Basically, sort the list first by height then by weight (or vice versa, doesn't matter), this operation takes O(n log n). Then go through the list, track the current min (min), if min is less both in height and weight than the current element in the list, add the maxLength by 1, set min to current element. Because if either height or weight equals to min, this element is not considered, since the list is sorted, the element with the smallest height and weight is always prior to current element. This operation takes another O(n) time, so totally O(nlogn) time, with no extra space.

public class LongestSequence {
 private static class HeightNWeight {
  int h;
  int w;
  public HeightNWeight(int h, int w){
   this.h = h;
   this.w = w;
  }
  public String toString() {
   String s = "height: ";
   s += String.valueOf(h) + "; weight: " + String.valueOf(w);
   return s;
  }
 }
 public static int largestNumber(List people) {
  if (people == null || people.size() == 0)
   return 0;
  Collections.sort(people, new HNWComparator());
  HeightNWeight min = people.get(0);
  int maxLength = 1;
  for (int i = 1; i < people.size(); i++){
   if (min.h < people.get(i).h && min.w < people.get(i).w) {
    maxLength++;
    min = people.get(i);
   }
  }
  return maxLength;
 }
 private static class HNWComparator implements Comparator {
  public int compare(HeightNWeight hw1, HeightNWeight hw2) {
   if (hw1.h < hw2.h)
    return -1;
   else if (hw1.h > hw2.h)
    return 1;
   else if (hw1.w < hw2.w)
    return -1;
   else if (hw1.w < hw2.w)
    return 1;
   return 0;
  }
 }
 public static void main(String[] args) {
  List people = new ArrayList ();
  people.add(new HeightNWeight(56, 90));
  people.add(new HeightNWeight(60, 90));
  people.add(new HeightNWeight(60, 95));
  people.add(new HeightNWeight(65, 100));
  people.add(new HeightNWeight(68, 150));
  people.add(new HeightNWeight(70, 100));
  people.add(new HeightNWeight(70, 160));
  people.add(new HeightNWeight(75, 180));
  people.add(new HeightNWeight(80, 180));
  people.add(new HeightNWeight(85, 190));
  System.out.println(largestNumber(people));
 }

}

External sort

If you have a 2 GB file with one string per line, which sorting algorithm would you use to sort the file and why? 

For large files that cannot be fit into the memory, we need to do external sort. Assume  the memory is 1 GB. 

1. Divide the file into K chunks, where X * K = 2GB. Bring each chunk into memory and sort the lines as usual using any O(n log n) algorithm, e.g., quick sort. 
2. Write the sorted data to disk. 
3. Repeat the above steps until all K chunks are sorted. 
4. Read the first N portion of each chunk (so that X * N < 1GB) into input buffers in main memory and allocate the remaining memory for an output buffer. 
5. Perform a k-way merge and store the result in the output buffer. Whenever the output buffer fills, write it to the final sorted file and empty it. Whenever any of the X input buffers empties, fill it with the next N portion of the chunk until no more data from the chunk is available. 

Additional passes, e.g., if we have 500 chunks, after sorting each chunk, we can run a first merge pass combining 25 chunks at a time, resulting in 20 large sorted chunks. Run a second merge pass to merge the 20 larger sorted chunks. 

Efficient external sorts require O(n log n) where n is the total elements to be sorted. Using parallelism may improve performance. 

Sort anagram lists

Write a method to sort an array of strings so that all the anagrams are next to each other.

The basic idea is to write a function and rearrange the string to its lexicographic order, and use String comparator to compare two strings. Some concepts about String comparator from Java doc: 

Compares two strings lexicographically. The comparison is based on the Unicode value of each character in the strings. The character sequence represented by this String object is compared lexicographically to the character sequence represented by the argument string. 

The result is a negative integer if this String object lexicographically precedes the argument string. The result is a positive integer if this String object lexicographically follows the argument string. The result is zero if the strings are equal;compareTo returns 0 exactly when the equals(Object) method would return true.

If two strings are different, then either they have different characters at some index that is a valid index for both strings, or their lengths are different, or both. If they have different characters at one or more index positions, let k be the smallest such index; then the string whose character at position k has the smaller value, as determined by using the < operator, lexicographically precedes the other string.  

private static class AnagramComparator implements Comparator {
  public static String sortChars(String s) {
   char[] content = s.toCharArray();
   Arrays.sort(content);
   return new String(content);
  }
  public int compare(String s1, String s2) {
   return sortChars(s1).compareTo(sortChars(s2));
  }
 }
 public static void sortStrings(List list) {
  Collections.sort(list, new AnagramComparator());
 }

Sort color

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

I have solved this four times, but I still couldn't remember it correctly. It is similar to dual pivot quick sort.
1. We take two pivots, the left one (pl) initialized at index 0 and the right one initialized at index A.length - 1;
2. Then we loop the array, if A[index] == 0, we swap it with pl, increment pl; if A[index] == 2, we swap it with pr, decrement pr.

public void sortColors(int[] A) {
        if (A == null || A.length < 2)
            return;
        int pl = 0;
        int pr = A.length - 1;
        int index = 0;
        while (index <= pr){
            if (A[index] == 0){
                swap(A, index++, pl++);
            }
            else if (A[index] == 2)
                swap(A, index, pr--);
            else
                index++;
        }
    }
    private void swap(int[] A, int i, int j){
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }

Insertion Sort List

"Sort a linked list using insertion sort."

3 -> 1 -> 12 -> 6

dummy(0) -> null
dummy(0) -> 3 -> null
dummy(0) -> 1 -> 3 -> null
dummy(0) -> 1 -> 3 -> 12 -> null
dummy(0) -> 1 -> 3 -> 6 -> 12 -> null

 
public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
  }
 
public class InsertionSort {
    public ListNode insertionSortList(ListNode head) {
        if (head == null)
            return null;
        ListNode dummy = new ListNode(0);
        while (head != null)
        {
            ListNode node = dummy;
            while (node.next != null && node.next.val < head.val)
                node = node.next;
            ListNode tmp = head.next;
            head.next = node.next;
            node.next = head;
            head = tmp;
        }
        return dummy.next;
    }
}

Quicksort!

The algorithm is very easy to understand. I used C++ due to the lack of updated Java complier on our cluster.

Be careful on the boundaries of each recursion.

      

    void qsort (int col, int left, int right)
          {
              int i = left, j = right;
              vector tmp;
              double pivot = output[(left + right)/2][col];
  
              //sort
              while (i <= j)
              {
                 while (output[i][col] < pivot && i < right)
                 {
                     i++;
                 }
                 while (output[j][col] > pivot && j > left)
                 {
                     j--;
                 }
 
                 if(i <= j)
                 {
                     tmp = output[i];
                     output[i] = output[j];
                     output[j] = tmp;
                     if(i < right)
                         i++;
                     if(j > left)
                         j--;
                 }
              }
             if (left < j)
             {
                 qsort(col,left,j);
             }
             if (i < right)
             {
                 qsort(col,i,right);

             }
         }