Uber Interview Question
Software EngineersCountry: United States
If the question is to get all permutations then this should do the trick:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* Created by dirkhain on 4/10/17.
*/
public class UberPickup {
public static void main (String[] args) {
UberPickup u = new UberPickup();
List<String[]> input = new ArrayList<>();
input.add(new String[]{"P1", "P2", "P3"});
input.add(new String[]{"P4", "P5", "P6"});
input.add(new String[]{"P7", "P8"});
List<String> result = u.getPermutations(input);
for (String s : result) {
System.out.println(s);
}
}
public List<String> getPermutations(List<String[]> input) {
ArrayList<String> result = new ArrayList<>();
if(input.size() == 0) {
return Arrays.asList("");
}
String[] current = input.get(0);
//copy rest of array
List<String[]> rest = input.subList(1, input.size());
List<String> subCombos = getPermutations(rest);
for(String s : current) {
for(int i = 0; i < subCombos.size(); i++) {
String combo = subCombos.get(i);
result.add("->" + s + combo);
}
}
return result;
}
}
If the question is not about retrieving the permutations then this solution will not work.
{{ # Below is a rough implementation in python
locations = [
"p1,p2,p3,p4,p5",
"p6,p7,p8,p9",
"p10,p11,p12",
"p13,p14,p15"
]
def getSchedules(locations, capacity):
# format locations to some thing usable
locations = [ location.split(',') for location in locations ]
current_index = 0
result = []
def visitPeople(current_index):
allEmpty = True
for person in locations:
if current_index < len(person) and len(result) < capacity:
allEmpty = False
result.append(person[current_index])
if len(result) < capacity and not allEmpty:
visitPeople(current_index + 1)
visitPeople(current_index)
print(result)
# U can invoke the above function like so.
getSchedules(locations, 16) }}
# Below is a rough implementation in python
locations = [
"p1,p2,p3,p4,p5",
"p6,p7,p8,p9",
"p10,p11,p12",
"p13,p14,p15"
]
def getSchedules(locations, capacity):
# format locations to some thing usable
locations = [ location.split(',') for location in locations ]
current_index = 0
result = []
def visitPeople(current_index):
allEmpty = True
for person in locations:
if current_index < len(person) and len(result) < capacity:
allEmpty = False
result.append(person[current_index])
if len(result) < capacity and not allEmpty:
visitPeople(current_index + 1)
visitPeople(current_index)
print(result)
# U can invoke the above function like so.
getSchedules(locations, 16)
This could be solved using minimum spanning tree concept
- Harsh Bhardwaj February 17, 2017***assume taxi is large enough for all passengers****
Arrange all the pickup locations as vertices of a graph along with the present location of the taxi as
one of the vertex
now start with the present location and add that edge with has lowest weight ,this means we have
visited to the location which is nearby and pic all the passangers, then search for the next nearby location
locations and so on until all the locations are visited once