Google Interview Question
Software Engineer / DevelopersCountry: United States
It is an old interview question from google. here is my solution:
#include <iostream>
#include <vector>
using namespace std;
typedef vector<pair<int, int> > Vec;
Vec v;
void Preprocess(vector<int>& input)
{
int max = input[0];
v.push_back(make_pair(0, input[0]));
for (int i = 1; i < input.size(); ++i)
{
if (input[i] > max) {
max = input[i];
v.push_back(make_pair(i, input[i]));
}
}
/*
for (int i = 0; i < v.size(); ++i)
{
cout << v[i].first << " " << v[i].second << endl;
}
*/
}
int FindGreaterIndex(int n)
{
int low = 0, high = v.size() - 1;
int mid;
while (low < high - 1)
{
mid = low + (high - low) / 2;
if (v[mid].second >= n) {
high = mid;
} else {
low = mid;
}
}
if (v[low].second >= n) {
return v[low].second;
} else if (v[high].second >= n) {
return v[high].second;
}
return -1;
}
int main()
{
vector<int> input;
input.push_back(2);
input.push_back(10);
input.push_back(5);
input.push_back(6);
input.push_back(80);
Preprocess(input);
int n;
while (cin >> n) {
cout << FindGreaterIndex(n) << endl;
}
}
yes, i think O(logn) is not possible the first time I saw the question. If the found integer is not in the array, we must scan the whole array and it is O(n) time complexity. I think this question is not very good as the preprocess time is O(n) and every query time is O(lgn)。 I don't know whether it is the answer that the interviewer wants
The code has some problem. Please think about find A=7 in the following array [2,9,10,5,6,8,17,80]. The code will return 9 instead of the right answer 8.
If O (logn) is not possible and we should find the answer in O (n) then we don't need all this stuff like preprocessing and binary search. We can just iterate the array from the beginning and stop as we hit a number which is greater than or equal to A. Something like this:
int find_first_greater_element(size_t A, size_t array[], size_t size)
{
for (int i = 0; i < size; ++i) {
if (array[i] >= A) {
return i;
}
}
return -1;
}
Please correct me if I'm wrong.
Right. O(log n) solution is not possible. Since the numbers in the array are not ordered there is no way to split the input into two parts and be able to select one over the other.
My solutions O(logn)
public static int find2ND(int [] array, int left,int right,int target){
if (left<right){
int mid=(left+right)/2;
int left_val=find2ND(array,left,mid-1,target);
int right_val=find2ND(array,mid+1,right,target);
if (left_val>target&&right_val>target){
return left_val<right_val? left_val:right_val;
}else if (left_val>target){
return left_val;
}else if (right_val>target){
return right_val;
}else {
return -1;
}
}
return array[left];
}
O(log N) is not possible. Here's the proof. Assume that is possible, find an instance of problem such that
1. the answer is the last element.
2. the algorithm produces correct answer.
Since the algorithm has O(log N) complexity, it can see at most O(log N) elements of the array. Hold these elements fixed and change the rest of the elements such that the correct answer changes. Feed the changed array to the algorithm. Since none of the elements the algorithm sees is changed, the algorithm is going to produce the same old answer which is wrong.
how about if u can use extra memory?
pay attention normally O(lgn) come from binary search
how about
b[i]=max(a[0]..a[i])
then b[i] will contain the biggest number greater than [a],
so we just need to do binary search to find the index of input number in a, then we can return b[i]
For binary search to work which essentially is dynamic programming, we need to be able to make a decision at each bifurcation. In binary search, that decision came from sorted-ness of array which allowed to leave one half on certainty that number being searched does not belong there. In this case, we do not have any decision making property. The number being searched can be anywhere. And whatever technique you put, there always is a worst case. So IMO O(n) is not possible
My Solution O(logn)
public static int find2ND(int [] array, int left,int right,int target){
if (left<right){
int mid=(left+right)/2;
int left_val=find2ND(array,left,mid-1,target);
int right_val=find2ND(array,mid+1,right,target);
if (left_val>target&&right_val>target){
return left_val<right_val? left_val:right_val;
}else if (left_val>target){
return left_val;
}else if (right_val>target){
return right_val;
}else {
return -1;
}
}
return array[left];
}
I agree with all of you, Is impossible to find a number in a not sorted array.
If the interviewer as you and your solution is not as expected. you can as the interviewer if he/she can show you the right answer or how he/she will do it!! in that way you are gonna show you are interested in the right solution and you want to learn and improved your programming skills
Pre-process the array and build a binary search tree. Now for a given number n, find the number in tree O(log n), then call its findSuccessor function (pick the left most node from the right sub tree), this would take O(logn). This would be the next higher value in the array.
Complexity: O(logn + logn)
but the successor might not be the first element in the array. in the example case [2, 10,5,6,80] input 4 u will get 5 but the answer is 10
Oh yes. You are right, I missed the part where only the first integer that is greater than input must be returned. I assumed it was the next largest element from the entire array.
I think there is a solution.
To do it in O(logn) time we should traverse the array in the way as how we traverse "Array Representing heap". I know that all the nodes will not follow the heap property and henc it is not heap. I am just asking to traverse elements as if it was a heap starting from 1st element and everytime checking its children. Start with (i=1st) element and everytime check 2i and (2i+1)th elements. If the element is greater than A then store the position of number. Do this till we reach N/2th positioned element. (heap's second last level element). Everytime we find a number greater we check if the position of this element is falling earlier than the previously matching element( if there was one). Hence This will be done (logn) times.
I will interpret the requirement as "after preprocessing, use O(lgn) time". Then this problem can be solved by sorting decreasing subsequences in the array and search it.
Example: [ 3 2 8 7 3 6 4 5]
Decreasing subsequences[ [3 2] [8 7 3] [ 6 4] [5] ]
The sorting uses the first element of each subsequence as the key, namely 3, 8, 6, 5.
Note the answer to the question must be one of 3 8 6 5.
import java.util.ArrayList;
public class Test1 {
public static void main(String[] args) {
String test="dabc";
ArrayList<String> results = findCombos(test);
for(String res : results) {
System.out.println(res);
}
}
public static ArrayList<String> findCombos(String input) {
ArrayList<String> buffer = new ArrayList<String>();
if(input == null || input.length() == 0) {
return buffer;
}
if(input.length() == 1) {
buffer.add(input);
return buffer;
}
String firstChar = input.substring(0,1);
buffer.add(firstChar);
ArrayList<String> results = findCombos(input.substring(1));
buffer.addAll(results);
for(String result : results) {
buffer.add(firstChar + result);
}
return buffer;
}
}
just use approach similar to quicksort. Choose the center value of the list as the pivot.
quicksort() {
choose center value as pivot;
if (pivot <= input) {
scan the list from pivot to the right and if the value is > 6, put into a new list;
quicksort();
else {
scan the list from the 1st to the pivot and if the value is > 6, put into a new list;
quicksort();
}
}
Build a Cartesian Tree in O(N)
Then every query is O(lgN)
[2, 10,5,6,80] can be
80
/
10
/ \
2 6
/
5
This is a heap and when we find one node that is = than VAL and its parent is >= VAL,we return its parent if it's the right child, otherwise return itself.
But if the node is < VAL and parent is >= than VAL, we return its parent.
for 6, we traverse to 6 and return 10. (Right child,return parent)
for 5, we traverse to 5 and return 5. ( Left child)
for 20 we traverse to 10 and return 80. (Not equal, return parent)
The only way to achieve O(long) is with a sorted array, I assume the interviewer would allow to sort the array if the interviewee asks, so the code looks like this:
public static int firstGreatest(Integer[] arr, Integer findMe)
{
// array needs to be sorted !
Arrays.sort(arr);
// base cases
if (findMe >= arr[arr.length -1])
{
return arr[arr.length -1];
}
if (findMe <= arr[0])
{
return arr[0];
}
int low = 0;
int high = arr.length - 1;
int middle = 0;
// case item found in array O(logn)
while (low <= high)
{
middle = (low + high) / 2;
if (findMe > arr[middle])
{
low = middle +1;
}
else if (findMe < arr[middle])
{
high = middle - 1;
}
else
{
if (middle == arr.length-1)
{
return arr[middle];
}
else
{
return arr[middle + 1];
}
}
}
return arr[middle];
}
}
We can achieve O(log n) in average cases, by binary search (keep reducing the search space by half if possible)
int find(int *a, int s, int e, int target)
{
if (s>e) return MAX_INT;
int idx;
int mid = (s+e)/2;
if (a[mid] > target)
{
//if a[mid] is already large than target
//we do only need to check the left part of the array
idx = find(a,s,mid-1,target);
if (idx != MAX_INT) return idx;
else return mid;
}
else
{
//first find in left part, if found, we do not have to deal with right part
int idx = find(a,s,mid-1,target);
if (idx!=MAX_INT) return idx;
return find(a,mid+1,e,target);
}
}
int solve(int *a, int len, int target)
{
int index = find(a,0,len-1,target);
if (index==MAX_INT) return -1;
return a[index];
}
int findfirstgreaterthanequal(int *a, int start, int end , int &index, int val)
{
if (start > end ) return 0;
int mid = (start + end )/2;
if(a[mid] >= val && mid < index )
{
index = mid;
}
findfirstgreaterthanequal(a, start, mid-1, index, val);
findfirstgreaterthanequal(a, mid+1, end, index, val);
return a[index];
}
// very nice question. needs a simple array (preprocessed)
// eg, suppose the input is 4, (assume we do linear search as of now)
// 2 : 4 > 2 next
// 10 : 4 < 10 , so ans is 10 and not 5..
// now 6
// 2 : 2 < 6 so next
// 10 : 10 > 6 and 10 is the first element greater than 6
for (int i=0; i < n; i++)
{
if (pre.size() == 0) pre.push_back(a[i]);
else if (a[i] > pre.back()) pre.push_back(a[i]);
}
while (cin >> query)
{
int lo(0), hi(pre.size()-1), x, ans(-1);
while (lo <= hi)
{
x = lo + (hi-lo)/2 ;; // avoids overflow
if (a[x] >= query) { ans = x; hi = x-1; }
else if (a[x] < query) { lo = x+1; }
}
cout << ans << endl;
}
#include<stdio.h>
#include<stdlib.h>
void sort(int arr[] ,int n)
{
int i,j,temp;
for (i = 0 ; i < ( n - 1 ); i++)
{
for (j = 0 ; j <( n - i - 1); j++)
{
if (arr[j] > arr[j+1]) /* For decreasing order use < */
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
int main()
{
int a[] = {2,10,5,6,80};
int i, num = 2;
sort(a,5);
for(i=0;i<sizeof(a)/sizeof(int);i++)
{
if(a[i] <= num)
;
else
{
printf(" The next value of given number is %d \n ",a[i]);
break;
}
}
return 0;
}
Traverse the array, keeping track of the smallest value seen that is larger than A.
int FindIndexOfNextGreater(int intArray[], int arraySize, int A)
{
int index = -1;
for (int i = 0; i < arraySize; ++i)
{
if (intArray[i] > A)
{
if (index == -1 || intArray[i] < intArray[index])
index = i;
}
}
return index;
}
I guess the situation was like this:
During the interview, this guy brought up a solution which takes O(n) time for a query.
Then the interviewer asked, could you do it better?
So he supposed the interviewer was looking for a O(logn) solution for each query.
Actually, we can do it better, but not this way. We can preprocess the whole array in O(nlogn) time, then use O(1) time for each query.
I wrote a piece of code for this:
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
class BST
{
struct _Node {
int val;
_Node * left, * right;
_Node (int v = 0, _Node * l = nullptr, _Node * r = nullptr):val(v), left(l), right(r){
}
};
_Node * _root;
int _insert_and_report(int val, _Node *& pos)
{
if (pos == nullptr)
{
pos = new _Node(val);
return numeric_limits<int>::min();
}
if (val < pos->val)
{
_insert_and_report(val, pos->left);
return pos->val;
}else {
return _insert_and_report(val, pos->right);
}
}
public:
BST():_root(nullptr){}
~BST(){//delete all nodes ...
}
int find(int val)
{
return _insert_and_report(val, _root);
}
};
vector<int> buildFirstGreaterTable(int arr[], int size)
{
vector<int> table;
BST bst;
for (int i = 0; i < size; ++i)
{
table.push_back(bst.find(arr[i]));
}
return table;
}
int main()
{
int arr[] = {2 , 6,2, 9, 8,3,12,8,1,0};
vector<int> table = buildFirstGreaterTable(arr, sizeof(arr)/sizeof(int));
for (int i = 0; i < table.size(); ++i)
{
cout<<table[i]<<endl;//all queries
}
}
The logic is quite simple.
Why do yo even need to preprocess the list when you can do it in O(n) as you have already pointed out.
I think the question should be: you can do a pre-process, and after than, every search time is O(log n).
- flybug March 19, 2012My solution is remove some un-usefull value (2,3,1,6,5,4) = > (2,3,,6,,) , because 1< 3, and 5,4<6. and then put the rest value in a binary search tree with their order number.
After the pre-process, the following search should be O(log n).