Google Interview Question Software Engineer / Developers
Country: United States
But for finding the first maximum and first minimum also we need to traverse through all elements of the array right which leads to O(N). Could you explain more with some code. Please.
@TapeRecordia, Arunkumar's solution is right. We are basically arranging the values in ascending order in such a way that every element in the newly formed list is interleaved with first maximum, second maximum, and so on. One issue to consider is whether the original data is all positive or not. If not, then we can do the following:
val1=max(max(w,x),max(y,z));
val2=min(main(w,x),min(y,z));
s1=w+x+y+z;
s2=val1+val2;
diff=s1-s2;
val4=diff-val1;
val3=s1-(val1+val2+val4);
sum[0]=val1;
sum[1]=val2;
sum[2]=val3;
sum[3]=val4;
However, if the data is all positive we need to check the condition for val3 and val4 one by one since the summation and the difference may not provide any useful information, as in the case data=5,1,6,2. Here val1=6, val2=1, s1=14, s2=7, and diff =7. So if we use the aforementioned code we get val4=1, val4=6 which is incorrect.
summ[0]=second maximum,
summ[1]=first minimum,
summ[2]=first maximum,
summ[3]=second minimum..
this is incorrect.
think of {10, 3, 2, 1}. the above proposed solution gives {10, 1, 3, 2}, yielding a result of 9+2+1=12.
the actual maximizing permutation is {2, 10 , 1, 3}, yileing a result of 8+9+2=19.
zoro is correct.
suppose that w>x>y>z, the above proposed solution {w, z, x, y} gives a value |w-z| + |z-x| + |x-y| = w-x+x-z+x-y = w+x-z-y
then the maximizing permutation should be {y, w, z, x} or {x, z, w, y}, yielding |y-w|+|w-z|+|z-x| = w-y+w-z+x-z = 2w+x-y-2z > w+x-z-y.
For the given sample input, the permutation suggested by ArunKumar, {5, -1, 5, 3}, gives 6 + |-6 + 2| = 10 but the permutation {5, 3, -1, 5} gives 2 + |4 + 6| = 12.
Am I missing something here?
Since the input is guaranteed to be of length 4 at all times, why is the brute force 4! recursive approach wrong? It's still O(1) time and space.
How is the solution to this supposed to run in O(1) ? Are you sure it's not O(n) time and O(1) space?
Let’s say, we have an array that has w,x,y,z by sorted.
a[0] will be smallest element in w,x,y,z. a[3] will be maximun.
The answer is
summ[0] = a[3]
summ[1] = a[0]
summ[2] = a[2]
summ[3] = a[1]
public int answer(int w, int x, int y, int z){
int[] a = new int[4];
a[0] = w;
a[1] = x;
a[2] = y;
a[3] = z;
Arrays.sort(a);
return Math.abs(a[3] - a[0]) + Math.abs(a[0] - a[2]) + Math.abs(a[2] - a[1]);
}
Note I don't think sorting a is O(n), because 4 is the constant.
if this sorting means O(n), then func(summ) should be O(n) thus we can't solve
this problem.
///public class MaxValue {
public static void main(String[] args) {
MaxValue maxValue = new MaxValue();
maxValue.maxValue(7,7,1,4);
}
public int maxValue(int a,int b,int c,int d){
int max = 0;
int min = 0;
//a=2.b=7,c=1,d=4
max = Math.max(Math.max(a,b),Math.max(c,d));//7
min = Math.min(Math.min(a,b),Math.min(c,d));//1
int sum = a+b+c+d;//14
int aPlusB = max+min;
int cPlusD = sum - aPlusB;
int v4 = Math.max(Math.abs(cPlusD - max),Math.abs(cPlusD-aPlusB));
int v3 = sum - (aPlusB+v4);
System.out.println("a "+max);
System.out.println("b "+min);
System.out.println("c "+v3);
System.out.println("d "+v4);
return 0;
}
}\\\
summ[0]=first maximum,
- Arunkumar Somalinga October 24, 2013summ[1]=first minimum,
summ[2]=second maximum,
summ[3]=second minimum..
.now these could be found using some conditional statements that would run for O(1) time and also since the number of variables are constant the space complexity is O(1)...now u can apply the formula to find the value