Google interview questions are popular since a while and it’s become a fashion to ask difficult to answer questions during interviews.
Here is one question :
Given an int array which might contain duplicates, find the largest subset of it which form a sequence.
Eg. {1,6,10,4,7,9,5}
then answer is 4,5,6,7
Sorting is an obvious solution. Can this be done in O(n) time?

here is my solution. Buy I can’t understand the reason for asking such questions to be solved in a very short time. I wonder who could really solve this problem in 5 minutes time and if someone can does it really mean that s/he is a good programmer?

Run the code below from here
 

import java.util.HashMap;
import java.util.Map;

/**
 * User: uerturk
 */

/**
 * Given an int array which might contain duplicates, find the largest
 * subset of it which form a sequence.
 * Eg. {1,6,10,4,7,9,5}
 * then answer is 4,5,6,7
 * Sorting is an obvious solution. Can this be done in O(n) time
 */
class FindTheLongestSequence {
    private int follow(int startNumber, Map<Integer, Pair<Boolean, Integer>> pairMap) {
        Pair<Boolean, Integer> currentPair = pairMap.get(startNumber);
        if (currentPair == null) {
            return 0;
        } else {
            if (currentPair.getFirst()) {
                return currentPair.getSecond();
            } else {
                int result = follow(startNumber + 1, pairMap) + 1;
                currentPair.setFirst(true);
                currentPair.setSecond(result);
                return result;
            }
        }
    }

    public void longestSequence() {
        int[] ints = {1, 6, 10, 4, 7, 9, 5};
        // in the map first is the number, in the pair first isVisited flag, second is the score
        Map<Integer, Pair<Boolean, Integer>> pairMap = new HashMap<Integer, Pair<Boolean, Integer>>();
        for (Integer i : ints) {
            pairMap.put(i, new Pair<Boolean, Integer>(false, 1));
        }

        int[] results = new int[ints.length];
        for (int i = 0; i < ints.length; i++) {
            int result = follow(ints[i], pairMap);
            results[i] = result;
            System.out.println(ints[i] + ":" + result);
        }

    }

    class Pair<First, Second> {
        First first;
        Second second;

        public Pair(First first, Second second) {
            this.first = first;
            this.second = second;
        }

        public void setFirst(First first) {
            this.first = first;
        }

        public void setSecond(Second second) {
            this.second = second;
        }

        public First getFirst() {
            return first;
        }

        public Second getSecond() {
            return second;
        }

        public void set(First first, Second second) {
            setFirst(first);
            setSecond(second);
        }
    }

    public static void main(String[] args) {
        new FindTheLongestSequence().longestSequence();
    }
}