Google Interview Question for Software Engineer / Developers


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

- w.y February 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- srcnaks February 02, 2015 | Flag
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

- Source February 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

CLEAR X:
  L10:  DBNZ L10

OR

CLEAR X:
  L10:  DBNZ X L10

Could you explain this? Thx.

- biolxj12 February 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi February 22, 2015 | Flag
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.

- Anonymous February 03, 2015 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More