CareerCup

This could be solved using minimum spanning tree concept

***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

I should add this to the problem: driver just pick up one person for each location.

Isn't it traveling salesman problem?

hmm... do you mean all permutations like
person1 - person6 - person 10 - person 13
person1 - person7 - person 10 - person 13
person1 - person8 - 10 - 13
1 - 9 - 10 - 13
1 - 6 - 11 - 13
etc...

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)

def combo(words,prefix=" "):
    if not words :
       print prefix
       return
    for i in words[0]:
        combo(words[1:],prefix+" "+i)
combo(locations)