Find the maximum repeating number in O(n) time and O(1) extra space

original post: http://www.geeksforgeeks.org/find-the-maximum-repeating-number-in-ok-time/

Given an array of size n, the array contains numbers in range from 0 to k-1 where k is a positive integer and k <= n. Find the maximum repeating number in this array. For example, let k be 10 the given array be arr[] = {1, 2, 2, 2, 0, 2, 0, 2, 3, 8, 0, 9, 2, 3}, the maximum repeating number would be 2. Expected time complexity is O(n) and extra space allowed is O(1). Modifications to array are allowed.

I solved it in Java. The key of this question is how to prove, after first scan, the max element's index is the maximum repeating element.

Prove: Assume mi * k + ai > mj * k + aj && mj > mi && 0 <= ai < k && 0 <= aj < k.
So, ai - aj > (mj - mi) * k. (mi - mj) * k >= k. Therefore, ai - aj > k, which is impossible. so mi >= mj

Note that the above solutions may cause overflow if adding k repeatedly makes the value more than INT_MAX.

800 interview question!

I will try to collect 800 interview question! The category follows the chapter of CC150

1. Arrays and Strings
2. Linked Lists
3. Stacks and Queues
4. Trees and Graphs
5. Bit Manipulation
6. Brain Teasers
7. Mathematics and Probability
8. Object-Oriented Design
9. Recursion and Dynamic Programming

Branch Prediction

original post

The question is 

Why is processing a sorted array faster than an unsorted array?

I got this question from mitbbs, it's a interview question.

在下面这个程序中，如果sort后的totalTime 总是比不sort的totalTime 小，
你可否解释是啥原因？

public class Work {

    public static void main(String args[]) {
    
        int a[] = new int[1000000000];
        
        //fill a
        
        //sort a 
        //do not sort a
        
        starttime=System.currentTimeMillis() 
        for (int i=0;i<a.length;i++) {
            process(a[i]);
        }
        endtime=System.currentTimeMillis() 
        
        totalTime = endtime-starttime;
    }
     
    process(int element) {

     if (element > 256) 
         System.out.println(element);
     else
         System.out.println(element);
     
    }
}