## Google Interview Question for Software Engineer / Developers

• 0

Country: -
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
4
of 4 vote

Assume the initial X is a positive. I am not sure how to deal with the cases when initial X is 0 or negative.

``````CLEAR X:
L10:  DBNZ L10

NEGATE X, Y:
CLEAR Y
L1: DBNZ Y  L2
L2: DBNZ X  L1``````

Comment hidden because of low score. Click to expand.
0

I still don't know how to deal with the cases when initial X is 0 or negative!!!

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

``````CLEAR X:
L10:  DBNZ L10``````

OR

``````CLEAR X:
L10:  DBNZ X L10``````

Could you explain this? Thx.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

My guess is that if x is negetive decrementing it will result in the end that the binary representation of x is zero.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.