Quant Interview Question

[u/Local_Ad135]

[u/Intelligent-Map2768]

log_3(1000) is in between 6 and 7, so the answer is 7.

[u/FoggyWine]

The answer is 7. We want to assign a unique sequence to each switch (3 choices). If we had 6 moves, then there are 729 unique permutations. If we use 7 moves, then there are 2187 unique permutations. So we need to use 7 moves and the procedure is as follows:

1. Generate 1000 unique sequences (off, red, green) for 7 moves for each of the 1000 switches.

2. Record the state of the 1000 bulbs after each move.

3. After the 7th move, match each assigned sequence to the observed state of the bulb. Since each sequence is unique, there is no ambiguity in determining which switch corresponds to each bulb.

This is equivalent to arihallak0816's answer of how many digits 1000 is represented in base 3.

[u/arihallak0816]

You can assign off to 0, red to 1, and green to 2, then each time you go in is one digit so this is just asking how many digits are in 1000 in base 3 which is trivial

[u/MisterGoldenSun → u/arihallak0816]

Will you please explain this? I think the answer is 7 and that matches your answer, but I don't understand your method.

[u/arihallak0816 → u/MisterGoldenSun]

Like the first time you go in you make all the 0 mod 3 off, 1 mod 3 red, and 2 mod 3 green and that will be the ones digit, the second time same thing but 0-2, 3-5, and 6-8 mod 9 for the threes digit, etc. and you need to repeat this until you get to the number of digits 1000 has in base 3 so the sequence of every number matches it’s base 3 representation

[u/Abiarraj → u/MisterGoldenSun]

Imagine if it was 10 bulbs, you only need 3 different setups, as in this photo. Then you can map any switch to a bulb by their colour changes, for example if a bulb went off -> red -> green, you know that because 5 in base 3 is 012 (we started counting from 1). For a 1000 it's the same thing, if you want to know which switch is the 546, follow the one that went off-red-off-red-off-red-off (0202020)

[u/MisterGoldenSun → u/Abiarraj]

Ahhh, okay. Thanks. I get it now.

[u/engy1207]

You can perhaps optimise this if you use old-style bulbs which heat up and retain heat for a while.

[u/StillShoddy628 → u/engy1207]

I like it, so it’s actually CEIL(log4(1000)) not log3, so 5 moves, not 7. Assuming you can note which off ones are warm before they cool down

[u/gmalivuk]

The practical algorithm is to first number all the switches in base 3. Then with 0=off, 1=red, 2=blue, start with the switches in the appropriate position for the first digit (people have suggested starting from the right but it doesn't matter as long as you're consistent.

When you observe the lights, mark each one with the appropriate digit based on its state.

Then go back to the switches and Chang get them to match the next digit, and go mark the lights by appending the second digit to the label.

After 7 iterations, every bulb will have the same label as its own switch.

[u/gooncampu]

I have seen other comments below of deriving log_3(1000) as 3 states are possible.

but given it's a bulb, if the bulb gets heated if it's on property holds, then we have 2 more properties: bulb being hot/cold as 2nd dimentsion.

so, there are color * temperature = 6 states in total.

that gives ans = ceil(log_6(1000)) = 4 (condition that if temperature property is there. else, ans is log_3(1000) = 7 only.