Google Interview Question
Country: United States
This is how switch-statements are implemented. Basically, base+offset a to piece of code based on integral value. This is less efficient though because it requires storage.
While I like this solution, it's one of those things that may or may not click. If it does, you'll impress the interviewer, if not, you're screwed.
After the code is compiled to assembly, we definitely need * to calculate the offset of arr[x]. So I do not think this is correct.
How about this?
nbits = sizeof(int) * 8 - 1; // this is a compile time constant, there is no * at runtime.
x1 = (int)((unsigned int)(x) << nbits) >> nbits;
y = (x1 && a) || (x1 && b);
I think the code below would work for the follow up case. Would love to see a simpler solution though.
int mask = 0;
int iter = x;
while (iter > 0) // if that's not allowed, can manually bitwise-or 32 times
{
mask |= iter;
iter = iter << 1;
}
int y = (b & mask) | (a & (~mask));
Don't read this if you haven't given it a try
.
This is an interesting question. I think the interviewer want to check if we have kind of rigid thinking or not.
y = f(x)
f(0) = a
f(1) = b
--> simplest solution would be a linear equation: f(x) = k*x + r
k*0 + r = a --> r = a
k*1 + r = b --> k = b-r = b-a
--> y = f(x) = (b-a) * x + a
Sorry, what do you mean?
>>> a = 5
>>> b= 20
>>> x = 1
>>> y = a ^ ((a ^ b) & (x))
>>> y
4
public class One {
private static int a,b,x,y;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Please Enter a and b values");
a = sc.nextInt();
b = sc.nextInt();
System.out.println("Please enter X value");
x = sc.nextInt();
y = (a&~-x)|(b&-x);
System.out.println("The y Value is "+y);
}
}
A solution in Java using bitwise operations, plus explanation (similar to another posted here)
public static int assignYBitwise(int a, int b, int x){
/*
* The interesting thing here is to obtain a proper
* mask from x. Since x is a signed integer, ~x doesn't
* work:
* ~0 = ~000...0 = 111...1 = -1 (OK)
* ~1 = ~000...1 = 111...0 = -2 (Not OK, should be 0)
*
* A way around this is to shift x 31 bits left, so
* 000...0 becomes 000...0 but 000...1 becomes 100...0
* (that is, Integer.MIN_VALUE). Then, shift 31 bits
* right, which won't undo the whole thing but instead
* copy bit at pos 31 all the way to pos 0, as >> preserves
* the sign of the integer. After that, the binary complement
* can be applied:
*
* 000...0 --(<<31)--> 000...0 --(>>31)--> 000...0 --(~)--> 111...1
* 000...1 --(<<31)--> 100...0 --(>>31)--> 111...1 --(~)--> 000...0
*/
int m = x<<31;
m = m>>31;
m = ~m;
System.out.println("X="+x+" M="+m);
int y = m&a | ~m&b ;
return y;
}
public static int assignYBitwise(int a, int b, int x){
/*
* The interesting thing here is to obtain a proper
* mask from x. Since x is a signed integer, ~x doesn't
* work:
* ~0 = ~000...0 = 111...1 = -1 (OK)
* ~1 = ~000...1 = 111...0 = -2 (Not OK, should be 0)
*
* A way around this is to shift x 31 bits left, so
* 000...0 becomes 000...0 but 000...1 becomes 100...0
* (that is, Integer.MIN_VALUE). Then, shift 31 bits
* right, which won't undo the whole thing but instead
* copy bit at pos 31 all the way to pos 0, as >> preserves
* the sign of the integer. After that, the binary complement
* can be applied:
*
* 000...0 --(<<31)--> 000...0 --(>>31)--> 000...0 --(~)--> 111...1
* 000...1 --(<<31)--> 100...0 --(>>31)--> 111...1 --(~)--> 000...0
*/
int m = x<<31;
m = m>>31;
m = ~m;
System.out.println("X="+x+" M="+m);
int y = m&a | ~m&b ;
return y;
}
- ranjeet July 01, 2015