Google Interview Question
Software Engineer / DevelopersCountry: -
Interview Type: In-Person
I gave the same answer!!!
I still don't know how to deal with the cases when initial X is 0 or negative!!!
I think this program will work
As stated above for DBNZ X L10 "This instruction decrement X by one and checks X, if X is not zero than branches line 10"
Hence, The statement first decrements!!
Let x = 0,
NEGATE X, Y:
Step 1. CLEAR Y
Step 2. L1: DBNZ Y L2
Step 3. L2: DBNZ X L1
Step 1. Y = 0
Step 2. Y = -1 , X = 0
Step 3. Y = -1 , X = -1
Step 2. Y = -2, X = -1
Step 3. Y = -2, X = -2
....
Step 2. Y = -65536, X = -65535
Step 3. Y = -65536, X = -65536
Step 2. Y = 65535, X = -65536
Step 3. Y = 65535, X = 65535
....
Step 2. Y = 1, X = 2
Step 3. Y = 1, X = 1
Step 2. Y = 0, X = 1
Step 3. Y = 0, X = 0
therefore Y = -X = 0 which is correct.
Now let x = -1,
NEGATE X, Y:
Step 1. CLEAR Y
Step 2. L1: DBNZ Y L2
Step 3. L2: DBNZ X L1
Step 1. Y = 0
Step 2. Y = -1 , X = -1
Step 3. Y = -1 , X = -2
Step 2. Y = -2 , X = -2
Step 3. Y = -2 , X = -3
....
Step 2. Y = -65535 , X = -65535
Step 3. Y = -65535 , X = -65536
Step 2. Y = -65536 , X = -65536
Step 3. Y = -65536 , X = 65535
Step 2. Y = 65535 , X = 65535
Step 3. Y = 65535 , X = 65534
...
Step 2. Y = 1 , X = 1
Step 3. Y = 1 , X = 0
For this one also Y = -X => Y = -(-1) => Y = 1
We can show that it's not possible to deal with the cases where X or Y start out negative or 0, so the solution given here is complete.
In the first problem, since there's no available instruction that increases the number, you cannot reach 0 if you start with a negative number. If you start with 0, you don't know that unless you first use the DBNZ instruction, and if you do, you now have a negative number.
In the second problem, we argue that if any variable starts out <= 0, it stays <= 0 forever, since there's no instruction that can increase the value of the variable. Then, that variable's DBNZ statements all have the same, *unconditional* action: they always branch and decrement by 1. We can think of it as replacing each DBNZ on that variable with an unconditional decrement followed by an unconditional jump to the label in the DBNZ instruction. This means that all conditions tested in the program pertain only to the other variable. We reach the conclusion that either the number of times Y is decremented depends only on X, only on Y, or on neither. Such a program could not be correct because the program is required to decrement Y precisely value(X) + value(Y) times.
Assume the initial X is a positive. I am not sure how to deal with the cases when initial X is 0 or negative.
- w.y February 02, 2015