Position: L3

[Q1] How do you find smallest non-negative integer that doesn't exist in the given array (including zero)

*array can have duplicates

followup:

• can you do it with space complexity O(1)?

Answer:

1. Sort the array
2. remove negatives
3. return if difference between two numbers is bigger than 1

[Q2] What's the slowest program you can write with n bits?

Answer:

• we need condition to stop the program.
• we can express the state of program with 2^n variation of bits.
• So if we make the program go through each state of the program, the maximum complexity is O(2^n) (We cannot create any more state with those bits)

afterthought:
The answer for Q1 the interviewer gave me before he moves to the second question. I got the second answer for Q2 after the interview ends and couldn't really explain well during the interview. I just finished the interview and don't think I pass it but hope this helps someone. I will keep trying. This was my 4th try for Google.

I should've done more hard question and practice outloud under the time pressure.