See full Google Software Engineer Interview or all Google Interviews
Interview Question for Software Engineer at Google: |
Oct 19, 2009 |
The implementation question: Find a max and min in an array simaltaneously. I used a 2n comparisons approach and a 1.5n on-average approach.
Add Tags
[?]
Helpful Question?
Yes |
No
Share:
Answers & Comments (6)
0 of 1 people found this helpful
Oct 29, 2009
You can use a simple divide and conquer technique in which you divide up the array recursively and only compare when you reach the leaf node, in which case you only have two numbers in your divided array. Then recursively go up to compare with the results from other sub-arrays. This should give you a worst case 1.5n comparison performance.
Helpful Answer?
Yes |
No
Inappropriate?
Nov 7, 2009
Hey neakor,
please do not keep misleading others, divide and conquer will lead u O(nlogn).
please do not keep misleading others, divide and conquer will lead u O(nlogn).
Helpful Answer?
Yes |
No
Inappropriate?
Nov 7, 2009
hi cockroachzl:
a complete sorting using divide and conquer will lead to worst case O(nlogn).
however, in this case, the merging steps can be simplified to just two comparisons, thus allowing the worst case performance to be 1.5n. i have the algorithm implemented in java. you can try it out. for the merging step, just check the first and last elements of the 2 sub arrays and do swaps.
a complete sorting using divide and conquer will lead to worst case O(nlogn).
however, in this case, the merging steps can be simplified to just two comparisons, thus allowing the worst case performance to be 1.5n. i have the algorithm implemented in java. you can try it out. for the merging step, just check the first and last elements of the 2 sub arrays and do swaps.
Helpful Answer?
Yes |
No
Inappropriate?
Nov 14, 2009
I'm confused... why not just:
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i = 0; i < a.length; i++{
if (a[i] > max) {
max = a[i];
}
else if (a[i] < min)
min = a[i];
}
}
Is this the 2n approach? O(2n) = O(n)....
What am I missing?
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i = 0; i < a.length; i++{
if (a[i] > max) {
max = a[i];
}
else if (a[i] < min)
min = a[i];
}
}
Is this the 2n approach? O(2n) = O(n)....
What am I missing?
Helpful Answer?
Yes |
No
Inappropriate?
Nov 14, 2009
Sorry... found it. Thank you CLR!
int tempMin, tempMax;
int max = a[0];
int min = a[0];
for (int i = 1; i < n-1; i = i+2){
if (a[i] <= a[i+1]){
tempMin = a[i];
tempMax = a[i+1];
}
else {
tempMin = a[i+1];
tempMax = a[i];
}
if (tempMax > max) {
max = tempMax;
}
if (tempMin < min) {
min = tempMin;
}
}
if (n % 2 == 0) { // Do this if there are an even number of elements
if (a[n-1] < min) min = a[n-1];
else if (a[n-1] > max) max = a[n-1];
}
int tempMin, tempMax;
int max = a[0];
int min = a[0];
for (int i = 1; i < n-1; i = i+2){
if (a[i] <= a[i+1]){
tempMin = a[i];
tempMax = a[i+1];
}
else {
tempMin = a[i+1];
tempMax = a[i];
}
if (tempMax > max) {
max = tempMax;
}
if (tempMin < min) {
min = tempMin;
}
}
if (n % 2 == 0) { // Do this if there are an even number of elements
if (a[n-1] < min) min = a[n-1];
else if (a[n-1] > max) max = a[n-1];
}
Helpful Answer?
Yes |
No
Inappropriate?
Post your anonymous review or
sign in to
answer or comment on this question
0 of 0 people found this helpful
by Interview Candidate: