Google Interview Question
Web:
www.google.com
|
HQ:
Mountain View, CA
Overview |
| |
Salaries |
| |
Reviews |
| |
Interviews |
| |
Photos |
| |
Jobs |
| |
|
1,223 Interview Reviews |
Back to all Google Interview Questions & Reviews
Interview questions and reviews posted anonymously by interview candidates
Interview Question for Software Engineer at Google:
Dec 7, 2011
How to find the max number of a shift buffer queue. For instance, there is an array like 5, 6,8,11,1,2, how to find the max number, which is 11 in this example.
Add Tags
[?]
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (10)
Dec 16, 2011
This post has been removed. Please see our
Community Guidelines or
Terms of Service for more information.
0 of 1 people found this helpful
Dec 19, 2011
Of course you can use binary search! :) Think about it! You just have to know where you are!
Helpful Answer?
Yes |
No
Inappropriate?
0 of 2 people found this helpful
Jan 7, 2012
int[] list = new int[]{5, 6, 8, 11, 1, 2};
int max = list[0];
for(int i = 1; i < list.length; i++)
{
if (i > max)
{
max = i;
}
}
return max;
int max = list[0];
for(int i = 1; i < list.length; i++)
{
if (i > max)
{
max = i;
}
}
return max;
Helpful Answer?
Yes |
No
Inappropriate?
2 of 3 people found this helpful
Jan 7, 2012
I see a couple of people suggested use binary search to find the max above, In order to do perform binary search, the list needs to be sorted. If the list is already sorted, you don't need a binary search to find the max number since it's located at the end of the list.
Helpful Answer?
Yes |
No
Inappropriate?
1 of 3 people found this helpful
Jan 15, 2012
int[] arr = new int[]{5,6,8,11,1,2};
int max = arr[0];
for (int i =0; i<arr.length; ++i){
if (arr[i] < max){
return arr[i];
}
else{
max = arr[i];
}
}
return max;
int max = arr[0];
for (int i =0; i<arr.length; ++i){
if (arr[i] < max){
return arr[i];
}
else{
max = arr[i];
}
}
return max;
Helpful Answer?
Yes |
No
Inappropriate?
Feb 21, 2012
This post has been removed. Please see our
Community Guidelines or
Terms of Service for more information.
Feb 22, 2012
This answer is not the best one but it can work with time complex as O(lgn).
bool searchforcyclearray(int cyclearray[],int index, int beginning, int end, int &res,int &time)
{
int mid=0;
time++;
if(beginning+1==end){
if(cyclearray[beginning]==index) {
res = beginning;
return(true);
}
else if(cyclearray[end]==index) {
res = end;
return(true);
}
else return(false);
}
mid = (int)((beginning+end)/2);
int a,b,c;
a = cyclearray[beginning];
c = cyclearray[end];
b = cyclearray[mid];
if(a<b&&b<c){
if(index<b) {
if(a<index) return(searchforcyclearray(cyclearray,index,beginning,mid,res,time));
else if(a==index) {
res = beginning;
return(true);
}
else return(searchforcyclearray(cyclearray,index,mid,end,res,time));
}
else if(index>b) return(searchforcyclearray(cyclearray,index,mid,end,res,time));
else {
res = mid;
return(true);
}
}
else if(a>b&&b<c){
if(index<b) return(searchforcyclearray(cyclearray,index,beginning,mid,res,time));
else if(index>b) {
if(index<c) return(searchforcyclearray(cyclearray,index,mid,end,res,time));
else if(index==c){
res = end;
return(true);
}
else return(searchforcyclearray(cyclearray,index,beginning,mid,res,time));
}
else {
res = mid;
return(true);
}
}
else if(a<b&&b>c){
if(index<b) {
if(a<index) return(searchforcyclearray(cyclearray,index,beginning,mid,res,time));
else if(a==index) {
res = beginning;
return(true);
}
else return(searchforcyclearray(cyclearray,index,mid,end,res,time));
}
else if(index>b) searchforcyclearray(cyclearray,index,mid,end,res,time);
else {
res = mid;
return(true);
}
}
else return(false);
}
bool searchforcyclearray(int cyclearray[],int index, int beginning, int end, int &res,int &time)
{
int mid=0;
time++;
if(beginning+1==end){
if(cyclearray[beginning]==index) {
res = beginning;
return(true);
}
else if(cyclearray[end]==index) {
res = end;
return(true);
}
else return(false);
}
mid = (int)((beginning+end)/2);
int a,b,c;
a = cyclearray[beginning];
c = cyclearray[end];
b = cyclearray[mid];
if(a<b&&b<c){
if(index<b) {
if(a<index) return(searchforcyclearray(cyclearray,index,beginning,mid,res,time));
else if(a==index) {
res = beginning;
return(true);
}
else return(searchforcyclearray(cyclearray,index,mid,end,res,time));
}
else if(index>b) return(searchforcyclearray(cyclearray,index,mid,end,res,time));
else {
res = mid;
return(true);
}
}
else if(a>b&&b<c){
if(index<b) return(searchforcyclearray(cyclearray,index,beginning,mid,res,time));
else if(index>b) {
if(index<c) return(searchforcyclearray(cyclearray,index,mid,end,res,time));
else if(index==c){
res = end;
return(true);
}
else return(searchforcyclearray(cyclearray,index,beginning,mid,res,time));
}
else {
res = mid;
return(true);
}
}
else if(a<b&&b>c){
if(index<b) {
if(a<index) return(searchforcyclearray(cyclearray,index,beginning,mid,res,time));
else if(a==index) {
res = beginning;
return(true);
}
else return(searchforcyclearray(cyclearray,index,mid,end,res,time));
}
else if(index>b) searchforcyclearray(cyclearray,index,mid,end,res,time);
else {
res = mid;
return(true);
}
}
else return(false);
}
Helpful Answer?
Yes |
No
Inappropriate?
Mar 4, 2012
the 5th person is right. you need a sorted array to perform binary search. if you are looking for the max element in a sorted array (ascending), you know the max element is the last element.
Helpful Answer?
Yes |
No
Inappropriate?
1 of 1 people found this helpful
Apr 20, 2012
Is the shift buffer queue a circular buffer? If so, and if the elements are sorted then the biggest element is NOT in the last position in the array and you DO need a modified version of binary search to find it.
I think something like this would work (first call between the first and last indices of the array):
int binarySearchCircularBuffer(int[] buffer,int start,int end){
if(buffer[start]<buffer[end])
return buffer[end];
int middle = (start-end)/2;
if(buffer[middle]>buffer[start])
return binarySearchCircularBuffer(buffer,middle,end);
else
return binarySearchCircularBuffer(buffer,start,middle);
}
I think something like this would work (first call between the first and last indices of the array):
int binarySearchCircularBuffer(int[] buffer,int start,int end){
if(buffer[start]<buffer[end])
return buffer[end];
int middle = (start-end)/2;
if(buffer[middle]>buffer[start])
return binarySearchCircularBuffer(buffer,middle,end);
else
return binarySearchCircularBuffer(buffer,start,middle);
}
Helpful Answer?
Yes |
No
Inappropriate?
To comment on this
question,
Sign In with Facebook or
Sign Up
You might also be interested in: Interview Questions, Software Engineer Interview Questions, Google Interview
0 of 3 people found this helpful
by Interview Candidate: