Google Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
Can anyone please explain me the question itself ?
And from the example, how [-12.3,-13.3] is an answer when -13.3 is not even present.
The range needs to be length 1. In this case it ends at -12.3, and starts 1.0 before that. The range includes the elements {-12.9, -12.5, -12.3}. If the range could be less than length 1 it might as well have ended at -12.9
It means find two numbers so that
a) the difference between them is 1
b) most number of elements in the array lie between them.
To explain the answer [-12.3,-13.3], the difference between them is 1. Also -12.3, -12.5 and -12.9 lie between them. Similarly [-12,-13] also could've been an answer since it still would include those 3 numbers. But if we considered [-13,-14] then it will include only -13.7 so not a good answer.
I think I would need more details on the question. But, I think I understand the question enough. I unfortunately can't find a solution other than this quadratic one. But here's a solution in Python:
def find_max_range(data):
sorted(data)
max_range = [data[0], data[0] + 1]
max_elems = 0
lower, upper = data[0], data[0] + 1
while upper <= data[-1]:
tmp_count = 0
for n in data:
if n >= lower and n <= upper:
tmp_count += 1
if n > upper:
break
if tmp_count > max_elems:
max_elems = tmp_count
max_range[0] = lower
max_range[1] = upper
lower += 0.1
upper += 0.1
return max_range
this solution is O(n log n + kn) where n is the amount of floats and k is the max amount of elements in a range of 1.
# given a range of floats, [2.3, 2.4, 5.5, 5.9, 9.0]
# find the range of size 1 with max number of elements
def find_range_with_max_elements(a):
if not a:
return
a.sort()
beg_i = 0
num_elements = 1
for i, elem in enumerate(a):
walk = i+1
while walk < len(a) and a[walk] - elem <= 1:
walk += 1
# get to one after the end, walk - 1 is last one in range
if num_elements < walk - i:
beg_i = i
num_elements = walk - i
return a[beg_i], a[beg_i]+1
print(find_range_with_max_elements([13.7, 14.5, 12.3, 12.5, 12.9]))
Here is an O(nlg(n)) algorithm:
1) Sort the array (which is O(nlg(n)) or O(n) if bounded).
2) For i = 1 to n, x=arr[i], binary search the array in the index range [i + 1, n] for the largest index j such that arr[j - 1] <= x + 1 < arr[j]. Save count = j - i as the number of floats in the interval [x, x + 1]. This is O(nlg(n)).
3) Keep a running total of the max count and return it. O(1)
Would be nice to have a solution that didn't require sorting.
Let’s see, what would be the brute force solution here? any range we choose will have one of the array elements in it, so we can select each element a[i], and check how many elements are in the range a[i]+1 and a[i]-1. If we do this for every element the solution time complexity is O(n^2) with O(1) extra space. Now how can we make this better? If we sort the array we will have all elements that are close next to each other. We can then select the first element in the sorted array and count how many elements are inside a[0],a[0]+1. Now when we get to an element that’s outside the range, we check if we remove a[0] were back to a range smaller than one. So we have to pointers, left and right, and we expand when the range is smaller than one and de-queue when the range is bigger than one. Now this solution is better because it only has O(nlgn) time complexity and still O(1) extra space if we do the sorting in-place. Now we should use the fact that the range has to be of size one, this implies we can somehow hash the values into buckets. If all the numbers were in range 0-m we could make an array of size m with counters for all the numbers with the same round/floor number. If the number’s range isn’t bound we can still do this with a hash table, with the round/floor number as the key. Now the problem is that doesn’t give us the optimal range, consider for example 0.1,0.7,0.8,1.1,1.5,1.6,1.7 neither bucket 0 or 1 contains the count of the maximum range [0.7,1.7] and we can’t find it only with the counts. What we can change is that we can hash the elements themselves and then check every pair of consecutive buckets. We can go through every bucket and check if bucket with (key+1) exists. Then we can check a pair of buckets again using sorting. If the numbers are randomly distributed checking a pair of buckets can be done in constant time, and we check O(n) buckets so the time complexity drops to O(n). To be more specific, if the average number of elements in a bucket is k, that is to say the load factor is k, the overall complexity would be O(n/k*klgk), so O(nlgk). It would be O(nlgn) worst case when all elements hash to two consecutive buckets. The tradeoff we made is that now we use O(n) extra space. We can make one more improvement if we knew that the range has to be quantized in some way, i.e. all maximum ranges are rounded somehow to d decimal digits then we can just use buckets to count the rounded numbers to their d decimal digits. For example, if the range returned has to be of the form [a.x, c.y], then 12.63 adds to the 12.6 bucket. Now we can get the maximum range using only the counters by iterating the buckets and checking if 10^d buckets exist and accumulating their counters. That wouldn’t require sorting and would reduce the time complexity to O(n*(10^d)) which is especially attractive if d is small. It would reduce the extra space complexity O(n/k). Note that in the case of randomly distributed numbers, k is a decreasing function of d.
* Sort the no
* Maintain sliding window(Dequeue)
* For each no, remove numbers from back until sum >= 1
Keep track of count
Algorithm isn't clear after the first step.
What kind of sliding window? Do you mean a window of width 1? Where does the dequeue come into play?
Remove the number from that back of what? Sum of what is >= 1?
What are you even trying to do?
{
Pair<Float, Float> getRange(Float[] array) {
if (array == null || array.length == 0) {
return null;
}
if (array.length == 1) {
return new Pair(array[0], array[0] + 1.0);
}
Arrays.sort(array, Collections.reverseOrder());
int i = 0;
int maxCount = 0;
Pair<Float, Float> maxRange = null;
while (i < array.length) {
int count = 0;
Pair<Float, Float> range = new Pair(array[i], array[i] - 1.0);
for (int j = i; j < array.length; j++) {
if (array[j] <= range.first && array[j] >= range.second) {
count++;
} else {
break;
}
}
if (count > maxCount) {
maxCount = count;
maxRange = range;
}
i++;
}
return maxRange;
}
}
Hash the values of all elements. Then go through, and for each element x, check if x + 1 or x -1 exist in the hashtable. If so, add such elements to a specific set. With all the sets, go through and check which set has the greatest number of elements. Return that set.
We do not need to sort the whole array.
What about firstly distributing the array into groups of 1-intervals. For example 1-2,2-3... based on the integer part of the number (in java Map<Integer, List<Float>>).
Then sort these List<Float>s and for every single number, count it as : list.length + binarySearch on the group on the left and group on the right.
Complexity will be O(n) for dividing into the groups + O(k*logk) for sorting the groups + O(n*2*log k) for checking the neighbors.
I can only think of an exponential solution tothis problem
Algo:
- Get length of array (say 4)
- Generate all possible combinations of the ints between 0-3 (coz size 4)
avoiding same numbers in the combination so no 1231 or 11
So,
01
02
03
12
.
.
123
213
321
.
.
1230
0123
.
.
- Put these into a hashmap so these are the keys for which the values will be the resulting subtraction (maybe you can do that simultaneously as you generate the combinations to save some momory + runtime)
- Get the one with the max key length
Even if you:
- sort the array (so, O(nlg(n)) or O(n) if they are bounded)
- for each value x in the array, loop through _every_ other value and count how many are in the interval [x, x + 1] (so O(n^2))
- return the x with the largest count
you have an O(n^2) solution that requires O(n) space. This is brute force and very not exponential.
For each element in the vector(after sorting), find the elements within range of 1.0.
We can use the number of elements in range for input[0] to compute the range for input[1] . This means that we do not process any element more than once( except the one at the boundaries between the ranges)
Complexity should be O(n log n) + approx O(n). Therefore O(nlogn)
float arr[]={-13.7, -14.5, -12.3, -12.5, -12.9};
int size = sizeof(arr)/sizeof(arr[0]);
std::vector<float> input(arr, arr+size );
std::sort( input.begin(), input.end() );
int maxElems = 0; //max elems in a range of 1.0
int maxElemIndex = 0; //the index in the sorted array, of the beginning range
int numCurElems = 0;
for( int i=0,j=0; i<input.size()-maxElems; i++ ) {
while( j<input.size() && input.at(j)-input.at(i) <= 1 ) {
j++;numCurElems++;
}
if( numCurElems > maxElems ) {
maxElemIndex = i;
maxElems = numCurElems;
}
if( numCurElems + i <= j ) {
numCurElems = 0;
}
j-- ; //Start with the previous index to maintain the count
}
After sorting, For input[0], find the range. If the range, lets say x, is greater than 2, for input[1], we can use the range for input[0] and only process elements from input[x].
Complexity should be O(nlogn) + approx O(n) Therefore O(nlogn)
float arr[]={-13.7, -14.5, -12.3, -12.5, -12.9};
int size = sizeof(arr)/sizeof(arr[0]);
std::vector<float> input(arr, arr+size );
std::sort( input.begin(), input.end() );
int maxElems = 0;
int maxElemIndex = 0;
int numCurElems = 0;
for( int i=0,j=0; i<input.size()-maxElems; i++ ) {
while( j<input.size() && input.at(j)-input.at(i) <= 1 ) {
j++;numCurElems++;
}
if( numCurElems > maxElems ) {
maxElemIndex = i;
maxElems = numCurElems;
}
if( numCurElems + i <= j ) {
numCurElems = 0;
}
j--;
}
After sorting, For input[0], find the range. If the range, lets say x, is greater than 2, for input[1], we can use the range for input[0] and only process elements from input[x].
Complexity should be O(nlogn) + approx O(n) Therefore O(nlogn)
float arr[]={-13.7, -14.5, -12.3, -12.5, -12.9};
int size = sizeof(arr)/sizeof(arr[0]);
std::vector<float> input(arr, arr+size );
std::sort( input.begin(), input.end() );
int maxElems = 0;
int maxElemIndex = 0;
int numCurElems = 0;
for( int i=0,j=0; i<input.size()-maxElems; i++ ) {
while( j<input.size() && input.at(j)-input.at(i) <= 1 ) {
j++;numCurElems++;
}
if( numCurElems > maxElems ) {
maxElemIndex = i;
maxElems = numCurElems;
}
if( numCurElems + i <= j ) {
numCurElems = 0;
}
j--;
}
After sorting, For input[0], find the range. If the range, lets say x, is greater than 2, for input[1], we can use the range for input[0] and only process elements from input[x].
Complexity should be O(nlogn) + approx O(n) Therefore O(nlogn)
float arr[]={-13.7, -14.5, -12.3, -12.5, -12.9};
int size = sizeof(arr)/sizeof(arr[0]);
std::vector<float> input(arr, arr+size );
std::sort( input.begin(), input.end() );
int maxElems = 0;
int maxElemIndex = 0;
int numCurElems = 0;
for( int i=0,j=0; i<input.size()-maxElems; i++ ) {
while( j<input.size() && input.at(j)-input.at(i) <= 1 ) {
j++;numCurElems++;
}
if( numCurElems > maxElems ) {
maxElemIndex = i;
maxElems = numCurElems;
}
if( numCurElems + i <= j ) {
numCurElems = 0;
}
j--;
}
Sort and then binary search, O(nlogn)
Double[] findMaxRange(Double[] a) {
// step 1. sort the array
Arrays.sort(a, Collections.reverseOrder());
Double from = 0.0, to = 0.0;
int max = 0;
// step 2. for every element x, find the upper bound of x - 1
// upper bound here means the largest number >= x - 1
for (int i = 0; i < a.length; i++) {
int j = upper(a, 0, a.length - 1, a[i] - 1);
if (j - i + 1 > max) {
from = a[i];
to = a[i] - 1;
max = j - i + 1;
}
}
return new Double[]{from, to};
}
int upper(Double[] a, int lo, int hi, Double target) {
int mid = lo + (hi - lo) / 2;
if (a[mid] >= target && (mid == a.length - 1 || a[mid + 1] < target)) {
return mid;
}
if (a[mid] < target) {
return upper(a, lo, mid - 1, target);
} else {
return upper(a, mid + 1, hi, target);
}
}
Can be solved by sorting the array, and then using two pointers to maintain a window and finding max length of the window.
1. Sort array - O(nlogn)
2. Maintain two pointers
- User123 July 12, 2015start = 0, end = 0 ans = 0 while end < n: if arr[end+1] - arr[start] <= 1: end += 1 else: start += 1 ans = max(ans, end - start + 1) # also keep window track