## Google Interview Question: Find the Longest Sequence in an…

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?

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(); } }

## 4 COMMENTS

Tonda BabaHey Umut, your code complexity is O(n^2).

Worst case is: {1, 2, 3, .. n}. It can be done in O(n).

HeviNope the solution is in O(n). Pair’s first element is also the visited flag, all the elements are traced once.

MichaelWhat is the output of your solution? I got here

1:1

6:2

10:1

4:4

7:1

9:2

5:3

but should be this

4,5,6,7

How to print result from your solution?

HeviThis code finds all the solutions;

6:2 –>6,7

4:4 –> 4,5,6,7

7:1 –> 7