Interview Question
Software DevelopersCountry: United States
Interview Type: In-Person
question is for finding path in directed graph. The solution is naive and needs bit of modification to be viable.
data class Request(val name: String, val from: Int, val to: Int)
fun allocateReq(requests: List<Request>): List<List<String>> {
if(requests.size < 2) return emptyList()
val current = requests.first()
val requestsToAllocate = requests.subList(1, requests.size)
return allocateReq(current, requestsToAllocate, emptyList(), emptyList()).map { it.map { it.name } }
}
fun allocateReq(
current: Request,
requests: List<Request>,
inAllocation: List<Request>,
allocated: List<List<Request>>
): List<List<Request>> {
val canAllocate = requests.firstOrNull {
current.to == it.from
} ?: run {
// nothing more to search, return currently allocated elements
return if(requests.isEmpty()) {
allocated
} else {
// search next element
val newRequests = requests.subList(1, requests.size)
allocateReq(requests.first(), newRequests, inAllocation, allocated)
}
}
// allow mutable state!
val updatedRequest = requests.toMutableList()
val updatedInAllocation = inAllocation.toMutableList()
// add current to inAllocation elements
updatedInAllocation.add(current)
// allocated when
val updatedAllocation = if(updatedInAllocation.isNotEmpty() && updatedInAllocation.first().from == canAllocate.to) {
// finish allocation
val allocation = updatedInAllocation.plus(canAllocate)
updatedRequest.remove(canAllocate)
updatedInAllocation.removeAll(allocation)
allocated.plus(listOf(allocation))
} else allocated
if(updatedRequest.isEmpty()) {
return allocated
}
val nextCurrent =
if(updatedRequest.contains(canAllocate)) canAllocate
else updatedRequest.first()
return allocateReq(nextCurrent, updatedRequest, updatedInAllocation , updatedAllocation)
}
This one is related to finding cycles in your graph...The strategy would be if a move-out request came to, check that whether there is an opposite path present in graph or not...means check using dfs whether 'to' to 'from' is possible or not...if possible then try to find a cycle or add that edge in the graph...
import java.util.*;
class Request {
String name;
int from;
int to;
public Request(String n, int from, int to) {
this.name = n;
this.to = to;
this.from = from;
}
}
public class EmployeeMovingPlan {
boolean findMovingPlanWrapper(Set<Set<String>> plan, Map<Integer, Map<Integer, List<String>>> g, Set<String> p, int src, int dst, String name) {
if (src == dst) {
p.add(name);
plan.add(new HashSet<>(p));
return true;
} else {
Map<Integer, List<String>> neighbors = g.getOrDefault(src, new HashMap<>());
for (int i : neighbors.keySet()) {
List<String> l = neighbors.get(i);
if (l.size() == 0) continue;
String n = l.get(l.size() - 1);
l.remove(l.size() - 1);
p.add(n);
if(!findMovingPlanWrapper(plan, g, /*v,*/ p, i, dst, name)) {
p.remove(n);
l.add(n);
}else{
break;
}
}
return false;
}
}
List<List<String>> findMovingPlans(List<Request> requests) {
Set<Set<String>> finalPlan = new HashSet<>();
Map<Integer, Map<Integer, List<String>>> graph = new HashMap<>();
for (Request r : requests) {
if (!graph.containsKey(r.to)) {
Map<Integer, List<String>> neighbors = graph.getOrDefault(r.from, new HashMap<>());
List<String> l = neighbors.getOrDefault(r.to, new ArrayList<>());
l.add(r.name);
neighbors.put(r.to, l);
graph.put(r.from, neighbors);
} else {
Set<String> names = new HashSet<>();
findMovingPlanWrapper(finalPlan, graph, names, r.to, r.from, r.name);
}
}
List<List<String>> l = new ArrayList<>();
for (Set<String> s : finalPlan) {
l.add(new ArrayList<>(s));
}
return l;
}
public static void main(String[] args) {
List<Request> l = new ArrayList<>() {{
add(new Request("Alex", 1, 2));
add(new Request("Ben", 2, 1));
add(new Request("Chris", 1, 2));
add(new Request("David", 2, 3));
add(new Request("Ellen", 3, 1));
add(new Request("Frank", 4, 5));
}};
System.out.println(new EmployeeMovingPlan().findMovingPlans(l));
}
}
import java.util.*;
/**
* Created by honey.k on 11/12/2019.
*/
public class NBuilding {
public static void main(String arr[]) {
NBuilding backToBusines = new NBuilding();
List<Request> listOfRequest = new ArrayList<Request>();
addRequests("Alex", 1, 2, listOfRequest);
addRequests("Ben", 2, 1, listOfRequest);
addRequests("Chris", 1, 2, listOfRequest);
addRequests("David", 2, 3, listOfRequest);
addRequests("Ellen", 3, 1, listOfRequest);
addRequests("Frank", 4, 5, listOfRequest);
List<List<String>> response= movingRequest(listOfRequest);
System.out.println(response.toString());
}
/*
Add all the user request in list
*/
public static void addRequests(String employee_name, int fromBuilding, int toBuilding, List<Request> listOfRequest) {
Request request = new Request(employee_name, fromBuilding, toBuilding);
listOfRequest.add(request);
}
/*
Add all the moving request in list
*/
public static List<List<String>> movingRequest(List<Request> listOfRequest) {
List<List<String>> listOfPeopleNames = new ArrayList<List<String>>();
Stack<Request> stackOfReq = new Stack<Request>();
listOfRequest.forEach(currentRequest ->
{
if (stackOfReq.size() > 0) {
Request oldRequest = stackOfReq.peek();
stackOfReq.push(currentRequest);
if (currentRequest.from_building == oldRequest.to_building && currentRequest.to_building == stackOfReq.get(0).from_building) {
List<String> peopleName = new ArrayList<String>();
while ((!stackOfReq.isEmpty())) {
peopleName.add(stackOfReq.peek().employee_names);
stackOfReq.pop();
}
Collections.reverse(peopleName);
listOfPeopleNames.add(peopleName);
peopleName = new ArrayList<String>();
}
} else {
stackOfReq.push(currentRequest);
}
}
);
return listOfPeopleNames;
}
}
class Request {
String employee_names;
int from_building;
int to_building;
public Request(String employee_name, int fromBuilding, int toBuilding) {
this.employee_names = employee_name;
this.from_building = fromBuilding;
this.to_building = toBuilding;
}
}
import java.util.*;
/**
* Created by honey.k on 11/12/2019.
*/
public class NBuilding {
public static void main(String arr[]) {
NBuilding backToBusines = new NBuilding();
List<Request> listOfRequest = new ArrayList<Request>();
addRequests("Alex", 1, 2, listOfRequest);
addRequests("Ben", 2, 1, listOfRequest);
addRequests("Chris", 1, 2, listOfRequest);
addRequests("David", 2, 3, listOfRequest);
addRequests("Ellen", 3, 1, listOfRequest);
addRequests("Frank", 4, 5, listOfRequest);
List<List<String>> response= movingRequest(listOfRequest);
System.out.println(response.toString());
}
/*
Add all the user request in list
*/
public static void addRequests(String employee_name, int fromBuilding, int toBuilding, List<Request> listOfRequest) {
Request request = new Request(employee_name, fromBuilding, toBuilding);
listOfRequest.add(request);
}
/*
Add all the moving request in list
*/
public static List<List<String>> movingRequest(List<Request> listOfRequest) {
List<List<String>> listOfPeopleNames = new ArrayList<List<String>>();
Stack<Request> stackOfReq = new Stack<Request>();
listOfRequest.forEach(currentRequest ->
{
if (stackOfReq.size() > 0) {
Request oldRequest = stackOfReq.peek();
stackOfReq.push(currentRequest);
if (currentRequest.from_building == oldRequest.to_building && currentRequest.to_building == stackOfReq.get(0).from_building) {
List<String> peopleName = new ArrayList<String>();
while ((!stackOfReq.isEmpty())) {
peopleName.add(stackOfReq.peek().employee_names);
stackOfReq.pop();
}
Collections.reverse(peopleName);
listOfPeopleNames.add(peopleName);
peopleName = new ArrayList<String>();
}
} else {
stackOfReq.push(currentRequest);
}
}
);
return listOfPeopleNames;
}
}
class Request {
String employee_names;
int from_building;
int to_building;
public Request(String employee_name, int fromBuilding, int toBuilding) {
this.employee_names = employee_name;
this.from_building = fromBuilding;
this.to_building = toBuilding;
}
}
import java.util.*;
/**
* Created by honey.k on 11/12/2019.
*/
public class NBuilding {
public static void main(String arr[]) {
NBuilding backToBusines = new NBuilding();
List<Request> listOfRequest = new ArrayList<Request>();
addRequests("Alex", 1, 2, listOfRequest);
addRequests("Ben", 2, 1, listOfRequest);
addRequests("Chris", 1, 2, listOfRequest);
addRequests("David", 2, 3, listOfRequest);
addRequests("Ellen", 3, 1, listOfRequest);
addRequests("Frank", 4, 5, listOfRequest);
List<List<String>> response= movingRequest(listOfRequest);
System.out.println(response.toString());
}
/*
Add all the user request in list
*/
public static void addRequests(String employee_name, int fromBuilding, int toBuilding, List<Request> listOfRequest) {
Request request = new Request(employee_name, fromBuilding, toBuilding);
listOfRequest.add(request);
}
/*
Add all the moving request in list
*/
public static List<List<String>> movingRequest(List<Request> listOfRequest) {
List<List<String>> listOfPeopleNames = new ArrayList<List<String>>();
Stack<Request> stackOfReq = new Stack<Request>();
listOfRequest.forEach(currentRequest ->
{
if (stackOfReq.size() > 0) {
Request oldRequest = stackOfReq.peek();
stackOfReq.push(currentRequest);
if (currentRequest.from_building == oldRequest.to_building && currentRequest.to_building == stackOfReq.get(0).from_building) {
List<String> peopleName = new ArrayList<String>();
while ((!stackOfReq.isEmpty())) {
peopleName.add(stackOfReq.peek().employee_names);
stackOfReq.pop();
}
Collections.reverse(peopleName);
listOfPeopleNames.add(peopleName);
peopleName = new ArrayList<String>();
}
} else {
stackOfReq.push(currentRequest);
}
}
);
return listOfPeopleNames;
}
}
class Request {
String employee_names;
int from_building;
int to_building;
public Request(String employee_name, int fromBuilding, int toBuilding) {
this.employee_names = employee_name;
this.from_building = fromBuilding;
this.to_building = toBuilding;
}
}
import java.util.*;
/**
* Created by honey.k on 11/12/2019.
*/
public class NBuilding {
public static void main(String arr[]) {
NBuilding backToBusines = new NBuilding();
List<Request> listOfRequest = new ArrayList<Request>();
addRequests("Alex", 1, 2, listOfRequest);
addRequests("Ben", 2, 1, listOfRequest);
addRequests("Chris", 1, 2, listOfRequest);
addRequests("David", 2, 3, listOfRequest);
addRequests("Ellen", 3, 1, listOfRequest);
addRequests("Frank", 4, 5, listOfRequest);
List<List<String>> response= movingRequest(listOfRequest);
System.out.println(response.toString());
}
/*
Add all the user request in list
*/
public static void addRequests(String employee_name, int fromBuilding, int toBuilding, List<Request> listOfRequest) {
Request request = new Request(employee_name, fromBuilding, toBuilding);
listOfRequest.add(request);
}
/*
Add all the moving request in list
*/
public static List<List<String>> movingRequest(List<Request> listOfRequest) {
List<List<String>> listOfPeopleNames = new ArrayList<List<String>>();
Stack<Request> stackOfReq = new Stack<Request>();
listOfRequest.forEach(currentRequest ->
{
if (stackOfReq.size() > 0) {
Request oldRequest = stackOfReq.peek();
stackOfReq.push(currentRequest);
if (currentRequest.from_building == oldRequest.to_building && currentRequest.to_building == stackOfReq.get(0).from_building) {
List<String> peopleName = new ArrayList<String>();
while ((!stackOfReq.isEmpty())) {
peopleName.add(stackOfReq.peek().employee_names);
stackOfReq.pop();
}
Collections.reverse(peopleName);
listOfPeopleNames.add(peopleName);
peopleName = new ArrayList<String>();
}
} else {
stackOfReq.push(currentRequest);
}
}
);
return listOfPeopleNames;
}
}
class Request {
String employee_names;
int from_building;
int to_building;
public Request(String employee_name, int fromBuilding, int toBuilding) {
this.employee_names = employee_name;
this.from_building = fromBuilding;
this.to_building = toBuilding;
}
}
import java.util.*;
public class NBuilding {
public static void main(String arr[]) {
NBuilding backToBusines = new NBuilding();
List<Request> listOfRequest = new ArrayList<Request>();
addRequests("Alex", 1, 2, listOfRequest);
addRequests("Ben", 2, 1, listOfRequest);
addRequests("Chris", 1, 2, listOfRequest);
addRequests("David", 2, 3, listOfRequest);
addRequests("Ellen", 3, 1, listOfRequest);
addRequests("Frank", 4, 5, listOfRequest);
List<List<String>> response= movingRequest(listOfRequest);
System.out.println(response.toString());
}
public static void addRequests(String employee_name, int fromBuilding, int toBuilding, List<Request> listOfRequest) {
Request request = new Request(employee_name, fromBuilding, toBuilding);
listOfRequest.add(request);
}
public static List<List<String>> movingRequest(List<Request> listOfRequest) {
List<List<String>> listOfPeopleNames = new ArrayList<List<String>>();
Stack<Request> stackOfReq = new Stack<Request>();
listOfRequest.forEach(currentRequest ->
{
if (stackOfReq.size() > 0) {
Request oldRequest = stackOfReq.peek();
stackOfReq.push(currentRequest);
if (currentRequest.from_building == oldRequest.to_building && currentRequest.to_building == stackOfReq.get(0).from_building) {
List<String> peopleName = new ArrayList<String>();
while ((!stackOfReq.isEmpty())) {
peopleName.add(stackOfReq.peek().employee_names);
stackOfReq.pop();
}
Collections.reverse(peopleName);
listOfPeopleNames.add(peopleName);
peopleName = new ArrayList<String>();
}
} else {
stackOfReq.push(currentRequest);
}
}
);
return listOfPeopleNames;
}
}
class Request {
String employee_names;
int from_building;
int to_building;
public Request(String employee_name, int fromBuilding, int toBuilding) {
this.employee_names = employee_name;
this.from_building = fromBuilding;
this.to_building = toBuilding;
}
}
import java.util.*;
class Request {
String name;
int from;
int to;
public Request(String n, int from, int to) {
this.name = n;
this.to = to;
this.from = from;
}
}
public class EmployeeMovingPlan {
boolean findMovingPlanWrapper(Set<Set<String>> plan, Map<Integer, Map<Integer, List<String>>> g, Set<String> p, int src, int dst, String name) {
if (src == dst) {
p.add(name);
plan.add(new HashSet<>(p));
return true;
} else {
Map<Integer, List<String>> neighbors = g.getOrDefault(src, new HashMap<>());
for (int i : neighbors.keySet()) {
List<String> l = neighbors.get(i);
if (l.size() == 0) continue;
String n = l.get(l.size() - 1);
l.remove(l.size() - 1);
p.add(n);
if(!findMovingPlanWrapper(plan, g, /*v,*/ p, i, dst, name)) {
p.remove(n);
l.add(n);
}else{
break;
}
}
return false;
}
}
List<List<String>> findMovingPlans(List<Request> requests) {
Set<Set<String>> finalPlan = new HashSet<>();
Map<Integer, Map<Integer, List<String>>> graph = new HashMap<>();
for (Request r : requests) {
if (!graph.containsKey(r.to)) {
Map<Integer, List<String>> neighbors = graph.getOrDefault(r.from, new HashMap<>());
List<String> l = neighbors.getOrDefault(r.to, new ArrayList<>());
l.add(r.name);
neighbors.put(r.to, l);
graph.put(r.from, neighbors);
} else {
Set<String> names = new HashSet<>();
findMovingPlanWrapper(finalPlan, graph, names, r.to, r.from, r.name);
}
}
List<List<String>> l = new ArrayList<>();
for (Set<String> s : finalPlan) {
l.add(new ArrayList<>(s));
}
return l;
}
public static void main(String[] args) {
List<Request> l = new ArrayList<>() {{
add(new Request("Alex", 1, 2));
add(new Request("Ben", 2, 1));
add(new Request("Chris", 1, 2));
add(new Request("David", 2, 3));
add(new Request("Ellen", 3, 1));
add(new Request("Frank", 4, 5));
}};
System.out.println(new EmployeeMovingPlan().findMovingPlans(l));
}
}
- Ahmed Raza November 24, 2019