Google Interview Question Applications Developers
Country: India
Interview Type: Phone Interview
How the complexity of the above algorithm/implementation is O(3n) => O(n); looks like its O(n^2)?
@Jose Cuervo, shsf, elber.kam
Since someone down voted without giving any reason, please test this array {5,4,3,2,1} and tell me what do you get?
I am really thinking hard to understand the solution.
Sorting is an obvious solution with O(nlgn) time complexity. This can be solved using connected components of a graph in O(n) time and space complexity as discussed at question?id=19778663
The graph in this case is 'linear', with each node having at most 2 edges, and hence can be built in O(n) time. Finding connected components, and storing the maximal connected component, in this graph using DFS has O(n) time complexity. Hence overall complexity is O(n).
Java implementation given below. Provide the input as:
16 1 21 7 4 6 15 3 2 8 14 9 17 35 19 45 18 73 22 44 43 71 20 33
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.regex.Pattern;
public class MaxConsecSubset {
int ccSize = 0, ccMin = 0, ccMax = 0;
int tmpSize = 0, tmpMin = 0, tmpMax = 0;
static HashMap<Integer, HashMap<Integer, Integer>> graph = new HashMap<Integer, HashMap<Integer, Integer>>();
public void DFS(int nodeId, int groupId) {
if (graph.get(nodeId).get(nodeId) == null) {
graph.get(nodeId).put(nodeId, groupId);
tmpSize++;
if (nodeId > tmpMax) {
tmpMax = nodeId;
}
if (nodeId < tmpMin) {
tmpMin = nodeId;
}
for (Map.Entry<Integer, Integer> entry: graph.get(nodeId).entrySet()) {
if (entry.getKey() != nodeId) {
DFS(entry.getKey(), groupId);
}
}
}
}
public void findEquivalenceClasses() {
for (Map.Entry<Integer, HashMap<Integer, Integer>> entry: graph.entrySet()) {
if (entry.getValue().get(entry.getKey()) == null) {
tmpSize = 0; tmpMax = -999999; tmpMin = 999999;
DFS(entry.getKey(), entry.getKey());
if (tmpSize > ccSize && (1 + tmpMax - tmpMin) == tmpSize) {
ccSize = tmpSize;
ccMin = tmpMin;
ccMax = tmpMax;
}
}
}
}
public void readInput() {
Scanner scanner = new Scanner(System.in);
scanner.useDelimiter(System.getProperty("line.separator"));
Pattern delimiters = Pattern.compile(System.getProperty("line.separator")+"|\\s");
scanner.useDelimiter(delimiters);
int i;
while(scanner.hasNextInt()) {
i = scanner.nextInt();
if (!graph.containsKey(i)) {
HashMap<Integer, Integer> adjElements = new HashMap<Integer, Integer>();
adjElements.put(i, null);
graph.put(i, adjElements);
}
if (graph.containsKey(i + 1)) {
graph.get(i).put(i+1, null);
graph.get(i+1).put(i, null);
}
if (graph.containsKey(i - 1)) {
graph.get(i).put(i-1, null);
graph.get(i-1).put(i, null);
}
}
}
public static void main(String[] args) {
MaxConsecSubset maxCS = new MaxConsecSubset();
maxCS.readInput();
maxCS.findEquivalenceClasses();
System.out.println("The maximum consecutive subset is: [" + maxCS.ccMin + "," + maxCS.ccMax + "]" );
}
}
Hello guys I have little bit problem in understanding the problem.
1,4 output because 1,2, 3, 4 exists; that's why ? could some1 please answer ? ;)
Java Implementation using hashMap in time complexity O(n)...
//Time Complexity: O(n)
public static int[] longestConsecutiveSequence(int[] data){
int first = Integer.MAX_VALUE; // the first number of the maximum consecutive sequence
int length = 0; // the length of the maximum consecutive sequence
Map<Integer, Integer> table = new Hashtable<Integer, Integer>();
for(int value: data) {
if(!table.containsKey(value)) {
int start = value;
int end = value;
if(table.containsKey(value + 1) && table.get(value + 1) >= value + 1) {
end = table.get(value + 1);
table.remove(value + 1);
table.remove(end);
}
if(table.containsKey(value - 1) && table.get(value - 1) <= value - 1) {
start = table.get(value - 1);
table.remove(value - 1);
table.remove(start);
}
table.put(start, end);
table.put(end, start);
if(end - start + 1 > length) {
first = start;
length = end - start + 1;
}
}
}
int[] seq = new int[length];
for(int i = 0; i < length; i++){
seq[i] = first + i;
}
return seq;
}
I Think sorting the array... and comparing all the conective elements will solve the proble,
please correct me if i am wrong
Sorting takes too long. It takes like nlogn time. This onecan be solved in o(n) time. 2 possible ways I can think of. Using hash table or dynamic programming
@Anonymous: I'm curious on the DP and hash method.
Hash table, you need to store them, which would be O(n) * O(1) for the inserts, but you need to traverse the results.
DP has more promise, but I'm trying to come up with a good example. Since the order of the inputs doesn't matter (like strictly increasing subsequence), then you're still going to have to deal with *some* data structure to store the linkage information.
However, my DP background is weak, so I'm eager to learn.
Sort the array O(nlogn)
Then start from the beginning scanning the array for consecutive elements.
Store the start and end index of the consecutive element sub-array and modify when a new larger sub-array is found.
At the end return the start and end index of the larget sub-daary having consecutive elements.
O(n)
So final complexity = O(nlogn + n) = O(nlogn)
Please let me know for errors or corner cases
public class BiggestIntervalWithElementsInArray {
private static void sort(int[] array, int left, int right) {
int pivotIndex = left + (right - left)/2;
int i = left - 1;
int j = right + 1;
while(i <= j) {
i++;
while(array[i] < array[pivotIndex] && i < right) i++;
j--;
while(array[j] > array[pivotIndex] && j > left) j--;
if(i < j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
if(i < right) sort(array, i, right);
if(j > left) sort(array, left, j);
}
public static void printInterval(int[] arr) {
if(arr == null || arr.length == 0) {
System.err.println("Empty array");
return;
}
sort(arr, 0, arr.length-1);
for(int i = 0; i < arr.length; i++) System.out.print(arr[i] + ", ");
int maxIntervalStartIndex = 0;
int maxIntervalEndIndex = 0;
int currentIntervalStartIndex = 0;
int currentIntervalEndIndex = 0;
for(int i = 1; i < arr.length; i++) {
if(arr[i] - arr[i-1] == 1) currentIntervalEndIndex++;
else {
if(maxIntervalEndIndex - maxIntervalStartIndex < currentIntervalEndIndex - currentIntervalStartIndex) {
maxIntervalEndIndex = currentIntervalEndIndex;
maxIntervalStartIndex = currentIntervalStartIndex;
}
currentIntervalStartIndex = currentIntervalEndIndex = i;
}
}
if(maxIntervalEndIndex - maxIntervalStartIndex < currentIntervalEndIndex - currentIntervalStartIndex) {
maxIntervalEndIndex = currentIntervalEndIndex;
maxIntervalStartIndex = currentIntervalStartIndex;
}
System.out.println("Biggest Interval that has all its elements in the array is ["
+ arr[maxIntervalStartIndex] + ", " + arr[maxIntervalEndIndex] + "]");
}
}
But if that is then question does not seem clear ;)
Still I can't believe ........... if so then my 1st question is this a Google Question ?
From the given input it seems that If I do swap across elements whenever I shall not find any suitable elements then I shall break.
1 is @ first position
2 is 7th position and 7 is 2nd position
3 is 4th position and 4 is 3rd position
I am not sure the pattern is always like this
If the pattern is not so then complexity is n + n = 2n
First I shall take same sized array then I shall place elements on the basis of it's value
Whenever placing the elements if the element is out of the range then skip it
In second phase longest sequential array
I am not sure, anonymous says right ? ;) lolz
Answer 1 seems overly complicated. Simply sort the list, and the iterate through keeping track of what ranges your have seen.
Here is a simple mock up of this in MATLAB
function largestRange = largestSubRange(arr)
arr = sort(arr);
largestRange= [];
current = [];
current(1) = arr(1);
largestRange(1) = arr(1);
for i = 2:length(arr)
if arr(i) == current(end)+1;
current = [current,arr(i)];
else
if length(current) > length(largestRange)
largestRange = current;
current = arr(i);
else
current = arr(i);
end
end
end
end
This should work in n*log(n) time complexity time just because of the sort function, else it is O(n) with O(n) space complexity as well
public class BiggestInterval {
public static void main(String[] args) {
int[] A = {1,7,4,6,3,10,2};
int[] endPoints = new int[2];//endpoints[0] stands for the 、 //left endpoint while endpoints[1] stands for the right point.
Arrays.sort(A);
int max = -1;
for(int i=0; i<A.length;i++){
for(int j=i; j<A.length;j++){
if(A[j] - A[i]==j-i && j-i>max){
endPoints[0] = A[i];
endPoints[1] = A[j];
max = j-i;
}
}
}
System.out.println("the biggest interval is: " + max );
System.out.println("the interval is : [" + endPoints[0] + ", " + endPoints[1]+"]");
}
}
Here's a C# example. I've tested this against a single element array, an array containing all of the same elements, and against the sample posted above.
public int[] GetMaxInterval(int[] input) {
// Jagged array will store a pair of values for the difference between the two values
int[][] differences = null;
Array.Sort(input);
int maxDiff = input[input.Length-1] - input[0];
differences = new int[maxDiff+1][];
for (int i = 0; i < input.Length - 1; ++i) {
int j;
for (j = i + 1; j < input.Length; ++j) {
if((j - i) == (input[j] - input[i])) {
continue;
} else {
differences[j - i - 1] = new int[] {input[i], input[j - 1]};
i = j - 1;
break;
}
}
// Check the edge case where the last element of the array is included in the max range.
if(j == input.Length) {
differences[j - i - 1] = new int[] {input[i], input[j - 1]};
}
}
// Iterated through the jagged array backwards to find the max difference.
for (int i = differences.Length - 1; i >= 0; --i) {
if (differences[i] != null)
return differences[i];
}
return null;
}
Based on the solution from Stackoverflow (stackoverflow.com/a/17592550/538743),
it can be done with hashtable in O(n)
l = [1, 7, 4, 6, 3, 10, 2]
d = {x:None for x in l}
for k,v in d.iteritems():
if v is not None:
continue
a,b = d.get(k-1), d.get(k+1)
if a is not None and b is not None:
d[k], d[a], d[b] = k, a, b
elif a is not None:
d[k], d[a] = a, k
elif b is not None:
d[k], d[b] = b, k
else:
d[k] = k
m = max(d, key=lambda x: d[x]-x)
print m, d[m]
One more implementation
import java.util.*;
public class LargestRange {
public static void main(String[] args){
int[] arr = {1, 7, 4, 6, 3, 10, 2};
int[] range = {0,0};
Set<Integer> hs = new TreeSet<Integer>();
for(int i : arr)
hs.add(i);
Iterator it = hs.iterator();
int a = (Integer) it.next();
int b = -1;
int currentStart = a;
int currentEnd = 0;
while(it.hasNext())
{
b = (Integer) it.next();
if((b == a+1))
{
currentEnd = b;
}
else{
currentStart = b;
}
if(range[1] - range[0] < currentEnd - currentStart){
range[0] = currentStart;
range[1] = currentEnd;
}
a=b;
}
System.out.println("largest range : [" + range[0] + "," + range[1] + "]");
}
}
One of the O(N) solutions, with HashSet:
public void biggestInterval2(Collection<Integer> is) {
Set<Integer> all = new HashSet<Integer>(is);
Set<Integer> visited = new HashSet<Integer>();
int bestStart = 0;
int bestLen = 0;
for(int i : is) {
if(! visited.contains(i)) {
visited.add(i);
int start = i;
while(all.contains(start - 1)) {
start --;
visited.add(start);
}
int end = i;
while(all.contains(end + 1)) {
end ++;
visited.add(end);
}
int len = end - start + 1;
if(len > bestLen) {
bestStart = start;
bestLen = len;
}
}
}
System.out.println("[" + bestStart + ", " + (bestStart + bestLen - 1) + "]");
}
One of the O(N) solutions, with HashSet:
public void biggestInterval2(Collection<Integer> is) {
Set<Integer> all = new HashSet<Integer>(is);
Set<Integer> visited = new HashSet<Integer>();
int bestStart = 0;
int bestLen = 0;
for(int i : is) {
if(! visited.contains(i)) {
visited.add(i);
int start = i;
while(all.contains(start - 1)) {
start --;
visited.add(start);
}
int end = i;
while(all.contains(end + 1)) {
end ++;
visited.add(end);
}
int len = end - start + 1;
if(len > bestLen) {
bestStart = start;
bestLen = len;
}
}
}
System.out.println("[" + bestStart + ", " + (bestStart + bestLen - 1) + "]");
}
You can find my implementation below:
/*
Given a list of integers, find out the biggest interval that has all its members in the given list.
e.g. given list 1, 7, 4, 6, 3, 10, 2 then answer would be [1, 4]. Develop algorithm and write code for this.
*/
import java.util.BitSet;
public class LargestContiguousInterval {
public static void main(String[] args) {
int[] arr = {1, 7, 4, 6, 3, 10, 2};
printLargestContInterval(arr);
}
private static void printLargestContInterval(int[] arr) {
BitSet bits = new BitSet();
for (int i = 0; i < arr.length; i++) {
bits.set(arr[i]);
}
// scan through the bit set
int len = bits.length();
int count = 0;
int maxCount = Integer.MIN_VALUE;
int maxStart = -1;
int start = -1;
for (int i = 0; i<len; i++) {
if (bits.get(i)) {
count++;
if (start == -1)
start = i;
} else {
if (count > maxCount) {
maxCount = count;
maxStart = start;
}
start = -1;
count = 0;
}
}
// print the max cont range in 'arr'
System.out.println("[" + maxStart + " - " + (maxStart+maxCount-1) + "]");
}
}
It uses the BitSet type from Java.
#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
int no[100]={0},cnt=0,x,y,n,xf,yf,cntf=0;
bool nohash[100]={false};
cout<<"enter the no of elements"<<endl;
cin>>n;
cout<<"enter the elements"<<endl;
for(int i=0;i<n;i++)
{
cin>>no[i];
nohash[no[i]]=true;
}
for(int i=0;i<100;i++)
{
if(nohash[i]==true)
{x=i;
while(nohash[i]==true)
{
cnt++;i++;
}
y=i-1;
}
if(cnt>cntf)
{
cntf=cnt;
xf=x;
yf=y;
}
cnt=0;
}
cout<<"range is"<<xf<<"to"<<yf<<endl;
}
//an O(n) soln. using hash table
public static void findInterval(List<Integer> myList){
int noOfElements=0;
int priviousElementCount=0;
int intStart=0;
int intEnd=0;
String output="";
/* Sorting Will Take nLog(n) */
Collections.sort(myList);
/* 0(n) Time */
for (int i=0; i<myList.size(); i++){
if(i < myList.size()-1){
if(myList.get(i)+1 == myList.get(i+1)){
/* For Every New Interval Set Start Value */
if(noOfElements==0)
intStart = myList.get(i);
/* Increament For Every Sequence. */
noOfElements++;
}
else{
/* Assign End Sequence interval. */
intEnd = myList.get(i);
/* If interval has more value than previous One */
if (priviousElementCount <= noOfElements){
priviousElementCount = noOfElements ;
output = "[" + intStart + "," + intEnd + "]";
}
/* Reset the interval, to calculate again */
noOfElements=0;
}
}
else {
/* Case When Last Value will be not compare. */
intEnd = myList.get(myList.size()-1);
if (priviousElementCount <= noOfElements){
priviousElementCount = noOfElements ;
output = "[" + intStart + "," + intEnd + "]";
}
}
}
System.out.println("Interval -> " + output);
}
A different approach: (space utilization: O(n), Time Complexity: O(n))
1) Make a binary search tree or any balanced tree out of the values in given array
2) Get the output of in-order of that tree (to get a sorted array)
3) Find max interval from this sorted array in O(n)
public class MaxRange {
private BST<Integer> bst = new BST<Integer>();
private int[] x;
private Pair<Integer, Integer> ans;
public MaxRange(int[] y) {
x = new int[y.size()];
for (int i = 0; i < x.size(); i++) {
x[i] = y[i];
}
ans = getAnswer();
ans.printPair();
}
private Pair<Integer, Integer> getAnswer() {
for (int i : x) {
bst.add(i);
}
int counter=0;
for (int i : bst.inorder()) {
x[counter++] = i;
}
int start = 0;
int end = 0;
int max = 0;
int i = 0;
while (i < x.size()) {
for (int count = 0, j = i + 1; x[j] = x[j-1] + 1; j++, count++;) {}
if (max < count) {
max = count;
start = i;
end = j;
}
i = j + 1;
}
return new Pair<Integer, Integer>(start, end);
}
private class Pair<Key, Key> {
private Key start, end;
public Pair(Key k1, Key k2) {
this.start = k1;
this.end = k2;
}
public void printPair() {
StdOut.println("["+this.start+","+this.end+"]");
}
}
public static void main(String[] args) {
int[] y = {1,7,4,6,3,10,2};
MaxRange m1 = new MaxRange(y);
}
}
}
import java.util.HashSet;
public class Solution{
public int[] Interval(int[] arr){
HashSet<Integer> ht = new HashSet<Integer>();
for(int i = 0 ; i < arr.length ; i++)
ht.add(arr[i]);
int res = 0 ;
for(int i = 0 ; i < arr.length ; i++)
if(ht.contains(arr[i]))
res = Math.max(res, scan(ht , arr[i]));
return res;
}
public int scan(Hashset ht, int k ){
if(!ht.contains(k)) return 0;
ht.remove(k);
return 1+scan(ht,k-1) + scan(ht,k+1);
}
}
public static String findMaxInterval(int[] arr){
if(arr == null || arr.length == 0){
throw new IllegalArgumentException("Array must not be empty");
}
Arrays.sort(arr);
String endResult = "";
int startIndex = 0;
int endIndex = 0;
int pass = 0;
int endMax = 0;
while(startIndex + pass < arr.length - 1){
pass++;
endIndex = startIndex + pass;
if(arr[startIndex] + pass == arr[endIndex]){
continue;
}
if(arr[startIndex] + pass != arr[endIndex]){
if(pass > endMax){
endMax = pass;
endResult = "[" + Integer.toString(arr[startIndex]) + " , " + Integer.toString(arr[endIndex-1]) + "]";
}
startIndex++;
pass = 0;
}
}
return endResult;
}
public static String findMaxInterval(int[] arr){
if(arr == null || arr.length == 0){
throw new IllegalArgumentException("Array must not be empty");
}
Arrays.sort(arr);
String endResult = "";
int startIndex = 0;
int endIndex = 0;
int pass = 0;
int endMax = 0;
while(startIndex + pass < arr.length - 1){
pass++;
endIndex = startIndex + pass;
if(arr[startIndex] + pass == arr[endIndex]){
continue;
}
if(arr[startIndex] + pass != arr[endIndex]){
if(pass > endMax){
endMax = pass;
endResult = "[" + Integer.toString(arr[startIndex]) + " , " + Integer.toString(arr[endIndex-1]) + "]";
}
startIndex++;
pass = 0;
}
}
return endResult;
}
Javascript solution
function compute(arr) {
// sort O(n^2)
for (var i = 0; i < arr.length - 1; ++i) {
for (var j = i + 1; j > 0; j--) {
if (arr[j] > arr[j - 1]) break;
var tmp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = tmp
}
}
// search O(n)
var start = arr[0], interval = [];
for (var i = 1; i < arr.length; i++) {
var end = arr[i - 1];
if (end + 1 != arr[i]) {
if (interval.length == 0 || (end - start) > (interval[1] - interval[0]))
interval = [start, end];
start = arr[i];
}
}
console.log(interval);
}
compute([1, 7, 4, 6, 3, 10, 2, 5]);
Ruby O(n log n):
def biggest_interval(arr)
arr.sort!
bidx = cidx = 0
bl = cl = 1
arr.each_with_index do |a, i|
next if 0 == i
if(a == arr[i - 1] + 1)
cl += 1
if(cl > bl)
bl = cl
bidx = cidx
end
else
cidx = i
cl = 1
end
end
return [arr[bidx], arr[bidx + bl - 1]]
end
p biggest_interval([1, 7, 4, 6, 3, 10, 2, 8, 11, 9])
shsf has a good solution. Do you need to have the second hash? Can't you remove already examined values from the hash as you go? Here's an example in C#:
static int[] largestRange(int[] array) { int[] range = { 0, -1 }; HashSet<int> set = new HashSet<int>(); foreach (int i in array) // O(n) set.Add(i); while (set.Count > 0) // each element gets tested once. Misses happen at most 2 times per entry (when there are no contiguous numbers) so the worst case is O(3n) for this part when largest range is length 1. { int j = set.First(); set.Remove(j); int a, b; // iterate backwards and forwards from j for (a = j; set.Count > 0; a--) { if (!set.Contains(a-1)) break; set.Remove(a-1); } for (b = j; set.Count > 0; b++) { if (!set.Contains(b+1)) break; set.Remove(b + 1); } if (b - a > range[1] - range[0]) { range[0] = a; range[1] = b; } } return range; }The google seems to ask a lot of graph related questions so maybe that's what they are looking for. The hash solution is easier to code.
- Jose Cuervo July 10, 2013