Microsoft Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
What does K the torch represent? What does 'maximum of x people time' mean? Is it the maximum time a person in group takes?
But it seems like what we want to do is minimize the time required for all people to cross the bridge. If we let T = [a1,a2,...,an], we can sort T in descending order. Since x number of people can cross the bridge at a time, we can simply group T into T/x groups and move each group one at a time. To make it more clear, take the following instance:
N = 7 #number of people
T = [1,2,3,1,2,5,4] #time each person takes to cross
x = 3; #number of people that can pass per round
- sort T: [5,4,3,2,2,1,1]
- group T into T/x groups
- group1: [5,4,3]
- group2: [2,2,1]
- group3: [1]
- Now group1 crosses bridge, it takes Max([5,4,3]) = 5
- Now group2 crosses bridge, it takes Max([2,2,1]) = 2
- Now group3 crosses bridge, it takes Max([1]) = 1
- Total time: 5 + 2 + 1 = 7
The above is just a greed approach. But I maybe misinterpreting the question, @neer any more details or comments?
This question is a little complicate, isn't? Someone has some idea?
- tiandiao123 August 30, 2017