Bulbs - facebook code lab - five practices

July 16, 2016

 Work on facebook code lab - bulbs

N light bulbs are connected by a wire. Each bulb has a switch associated with it, however due to faulty wiring, a switch also changes the state of all the bulbs to the right of current bulb. Given an initial state of all bulbs, find the minimum number of switches you have to press to turn on all the bulbs. You can press the same switch multiple times.

Note : 0 represents the bulb is off and 1 represents the bulb is on.

Example:

Input : [0 1 0 1]
Return : 4

Explanation :
 press switch 0 : [1 0 1 0]
 press switch 1 : [1 1 0 1]
 press switch 2 : [1 1 1 0]
 press switch 3 : [1 1 1 1]

1. First practice:
Recursive solution - stack overflow issue:

https://gist.github.com/jianminchen/ae6ab2d83a090b79e161cb4c870d6aa8

2. Second practice:  Partial correct - work on time complexity

https://gist.github.com/jianminchen/fb463d7bfe70022f26fc6e0854f94228

Here is the error message:

• Time Complexity
  Almost there. Your solution is not well optimized for runtime. Focus your effort in solving the problem in shorter time frame.
• Partially Correct Answer. Make your solution more efficient

3. Third practice:
https://gist.github.com/jianminchen/7093c5dcd52dd72f1ecd06e1d969e648
    Same message, almost there!

4. Fourth practice:  Correct answer
https://gist.github.com/jianminchen/7e934805e2bfa9fe4ce79f3991a4b570

  Highlights of change:
  1. No change on input argument List<Integer>, no List.remove call, no function call of getOpposite

5. Standard answer provided by author - C++

https://gist.github.com/jianminchen/7857bba5138d6c72067eddf40f0f5d5b

Actually, just use one variable - state, and only two states: 0 or 1.

Actionable Items:

1. Go over Java List Interface, and list all APIs here. Try to memorize all APIs.

2. Go over Java Integer class, and list all APIs here.

Entertainment notes:

Julia's favorite practice, first, she forced herself to write Java code in the facebook code lab, no C# support; she started to read more about Java List API, and got some coding experience on basic List coding.

And then, she started to challenge herself to figure out step by step to elegant solution. One step a time.

The practices were quite entertaining, Julia likes the big surprise at the end.