Yandex Interview Question for Software Engineer / Developers


Country: Germany
Interview Type: Phone Interview




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

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:
1. 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.

- JonathanBarOr November 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 November 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@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

- pavel.em November 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@pavel.em: ye , it's wrong :( .

- rezakakhki.RK November 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 November 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@JonathanBarOr: no, I was talking about rezakakhki.RK's suggestion
your solution looks correct ;)

- pavel.em November 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Boris November 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- anonymous November 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Raj Hirani November 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

how can you turn off all the cars bulbs? you never know whether you have reach the end or you are still going through

- Tim November 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Nagendra November 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- e.a.lapitskaya September 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- 1st, switch off the light at your position
- then go left car,
-- if light is off, turn it on, make N steps back to 1st positon
-- if light is on, then go on before 1st light
- if at 1st position light is on, then that is it
- if no, then make steps from 2

- bolshaaan October 27, 2017 | 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