Yandex Interview Question
Software Engineer / DevelopersCountry: Germany
Interview Type: Phone Interview
according to your solution if we have N cars that all of them have turned-on lights , we need [(N*(N+1))/2] + N steps to determine the size of the train , but we can do it with 3*N steps :
we start randomly from one car . turn off the light in current car ( if it's on ) and then go left . we keep going to left until no more turned-on light remain . now there is no more turned-on light so we turn one light on and keep going to left and keep in mind our step until we reach to turned-on light again
@rezakakhki.RK: I have also thought something about these lines. But the point is there is really *no way* to know when "no more turned-on light remain". So that we can go on in circles indefinetely
It's not wrong. You determine that all lights are turned off when the beginning position has been turned off. Explanation: each time you go left and turn off the lights you see, while the start position's light is on. When returning to the starting position, if it has been turned off - it means that you went a whole circle to the left! Then you can be sure that all lights are indeed turned off.
@JonathanBarOr: no, I was talking about rezakakhki.RK's suggestion
your solution looks correct ;)
You dont need to go back, as you may save the pointer to the beginning.
so
1) Turn off the light at the beginning
2) go left 1 step -
- if light is on, just go to next step
- if light is off - turn it on
3) check beginning - if suddenly ou see light is on - you made the loop of K steps.
On step 4 you should not increment k, but increase it by some factor (for example 2). Then performance will be linear in N - the length of the train. For scale factor 2 worst case performance is when N = 2^M+1, you would travel back and force total distance of sum(2*k)=sum(2*2^m), for m=1,(M+1), which is approximately 2*2^(M+2) = 8*2^M ~ 8*N.
step 1:turn off all the cars bulbs and count=0 select 1 starting car.
step 2:Start with car turn "on" it's bulb and increment count by 1.
then try to go left and do step 2 until u got again "on" bulb.
I think the critical point here is finding when to stop the loop. If we are going in only one direction, we cannot be sure if the loop again started or it is going on. I thought the solution would be
1. Start from a random car
2. Go left side 1 step turn off light and come back
3. Go right side 1 step and turn on the light and come back
4. Go left side 2 steps and turn off the light and come back
while going each side keeping in mind the count of the steps we turned on/off previous step
5 Do this until the previous on/off count mismatches one side.
6. Once mismatched come back to original position and start switch on/off the light from original position and counting
7. iterate through untill it reaches to the first point as now we are sure one side lights are on and other side off. So if we start counting from on side, once we cross off side, it is the end and vice versa.
My strategy based on the light on/off condition and the light bulb temperature. How it works:
1. enter the first car with the light on.
2. turn it off. //it will be the first worm off light bulb, that will stop the cycle(steps 3-4-5).
3. increase the value by 1.
4. enter the next car.
5. if the light is on - turn it off. if the light is off - touch the bulb and if its cold - turn the light on. In both such cases - go to step 3 and continue. (But if its worm - go to step 6.)
6. return the current value.
Do the following: turn on the light at starting position. Now, let's keep in mind a variable k, initialized as 1 and increased in each iteration. This is the algorithm:
- JonathanBarOr November 04, 20151. Go left k steps, turn off the light in each cart.
2. Return k steps right (not touching any lights).
3. Now you're at the starting position. If the light is turned off - quit the loop.
4. Increase k and re-iterate (1).
If the light is off at the starting position - it means that we made a full circle. Now, turn on the light at starting position (again), go left and count until you reach a turned-on cart. This is the number of carts.