Interview Question for Software Developers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
1
of 1 vote

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <string>

using namespace std;

class Request
{
public:
	string name;
	int from;
	int to;

	Request(string n, int from, int to)
	{
		this->name = n;
		this->to = to;
		this->from = from;
	}
};

void dfs(unordered_map<int, vector<pair<int, string>>>& graph, vector<Request>& path, vector<Request>& result, int src, int dst, unordered_set<int>& marked)
{
	marked.insert(src);
	for (auto itr = graph[src].begin(); itr != graph[src].end(); ++itr)
	{
		if (itr->first == dst) // loop is detected
		{
			if (result.size() < path.size() + 1)
			{
				result = path;
				//add the last edge back to start
				result.push_back(Request(itr->second, src, itr->first));
			}
			continue;
		}

		// avoid to stuck in loops
		if (marked.find(itr->first) != marked.end())
			continue;

		path.push_back(Request(itr->second, src, itr->first));
		dfs(graph, path, result, itr->first, dst, marked);
		path.pop_back();
	}
}

vector<vector<string>> getPlan(vector<Request> v)
{
	unordered_map<int, vector<pair<int, string>>> graph;
	// build graph
	for (Request& r : v)
	{
		graph[r.from].push_back(make_pair(r.to, r.name));
	}

	vector<vector<string>> plan;
	// for all edges run dfs but it can be modified
	// to do in one dfs but that will be complicated
	for (Request& r : v) 
	{
		vector<Request> path;
		vector<Request> result;

		unordered_set<int> marked;
		dfs(graph, path, result, r.from, r.from, marked);
		if (!result.empty())
		{
			vector<string> names;
			for (Request& e : result)
			{
				names.push_back(e.name);
				//remove all edges from the path to avoid condidering this path next time
				// instead of using linear search, map can be used in graph for efficient
				// lookup
				for (auto nitr = graph[e.from].begin(); nitr != graph[e.from].end(); ++nitr)
				{
					if (e.to == nitr->first && e.name == nitr->second)
					{
						nitr = graph[e.from].erase(nitr);
						break;
					}
				}
			}

			plan.push_back(names);
		}
	}
	return plan;
}


int main()
{
	vector<Request> v;
	v.push_back(Request("Alex", 1, 2));
	v.push_back(Request("Ben", 2, 1));
	v.push_back(Request("Chris", 1, 2));
	v.push_back(Request("David", 2, 3));
	v.push_back(Request("Ellen", 3, 1));
	v.push_back(Request("Frank", 4, 5));

	vector<vector<string>> plan = getPlan(v);
	std::cout << "Input 1 movement plan" << endl;
	for (vector<string>& part : plan)
	{
		cout << "[";
		for (size_t i = 0; i < part.size(); ++i)
		{
			cout << part[i];
			if (i < part.size() - 1)
				cout << ",";
		}
		cout << "]" << endl;
	}

	v.clear();
	v.push_back(Request("Adam", 1, 2));
	v.push_back(Request("Brian", 2, 1));
	v.push_back(Request("Carl", 4, 5));
	v.push_back(Request("Dan", 5, 1));
	v.push_back(Request("Eric", 2, 3));
	v.push_back(Request("Fred", 3, 4));

	plan.clear();
	plan = getPlan(v);
	std::cout << endl << "Input 2 movement plan" << endl;
	for (vector<string>& part : plan)
	{
		cout << "[";
		for (size_t i = 0; i < part.size(); ++i)
		{
			cout << part[i];
			if (i < part.size() - 1)
				cout << ",";
		}
		cout << "]" << endl;
	}
}

- Ahmed Raza November 24, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)
}

- anp October 15, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
    }

}

- Biswajit Sinha October 15, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

- Honey November 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }
}

- Honey November 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }
}

- Honey November 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- Honey November 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

- Honey November 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }

}

- Honey November 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
    }

}

- Honey November 12, 2019 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More