Amazon Interview Question
Software DevelopersTeam: Alexa
Country: United States
Interview Type: Phone Interview
Hi. I enhanced @parikksit.b solution for repeated keys and for cases where there are more than one match
public class Employee
{
private string _name;
private string _building1;
private string _building2;
public Employee(string name, string building1, string building2)
{
this._name = name;
this._building1 = building1;
this._building2 = building2;
}
public string Name
{
get
{
return _name;
}
set
{
_name = value;
}
}
public string Building1
{
get
{
return _building1;
}
set
{
_building1 = value;
}
}
public string Building2
{
get
{
return _building2;
}
set
{
_building2 = value;
}
}
public string MakeKey()
{
return _building1 + "," + _building2;
}
}
public class MatchEmployee
{
private Dictionary<String, List<string>> dict = new Dictionary<String, List<string>>();
private void ReArrenge(List<Employee> inputList)
{
foreach (Employee e in inputList)
{
if (dict.ContainsKey(e.MakeKey()) == false)
{
List<string> lst = new List<string>();
lst.Add(e.Name);
dict.Add(e.MakeKey(), lst);
}
else
{
dict[e.MakeKey()].Add(e.Name);
}
}
}
public List<string> MatchUp(List<Employee> inputList)
{
List<string> result = new List<string>();
ReArrenge(inputList);
foreach (KeyValuePair<string, List<string>> entry in dict)
{
if (entry.Value.Count != 0)
{
String rev = GetReversed(entry.Key);
if (dict.ContainsKey(rev) && dict[rev].Count != 0)
{
result.Add(entry.Value[0] + ", " + dict[rev][0]);
entry.Value.Remove(entry.Value[0]);
dict[rev].Remove(dict[rev][0]);
}
}
}
return result;
}
private string GetReversed(string s)
{
String[] temp = s.Split(new char []{','});
return temp[1] + "," + temp[0];
}
}
static void Main(String[] args)
{
MatchEmployee mE = new MatchEmployee();
List<Employee> emps = new List<Employee>();
emps.Add(new Employee("A", "1", "2"));
emps.Add(new Employee("B", "1", "3"));
emps.Add(new Employee("C", "1", "3"));
emps.Add(new Employee("K", "1", "3"));
emps.Add(new Employee("D", "2", "1"));
emps.Add(new Employee("E", "2", "3"));
emps.Add(new Employee("F", "2", "3"));
emps.Add(new Employee("G", "3", "2"));
emps.Add(new Employee("H", "3", "2"));
emps.Add(new Employee("I", "3", "1"));
emps.Add(new Employee("J", "3", "1"));
List<string> matched = mE.MatchUp(emps);
}
Solution in JavaScript.
var map = {};
var data = [
{alias:"user1", from: 1, to: 2},
{alias:"user2", from: 2, to: 1},
{alias:"user3", from: 3, to: 7},
{alias:"user4", from: 7, to: 3},
{alias:"user5", from: 4, to: 6},
]
for(var i=0; i < data.length; i++) {
if(typeof map[data[i].to] !== "undefined" &&
map[data[i].to].to === data[i].from) {
console.log("match found ", map[data[i].to].alias, " ", data[i].alias)
}
map[data[i].from] = {alias:data[i].alias, to: data[i].to};}
Here is the JS solution.
for(var map={},data=[{alias:"user1",from:1,to:2},{alias:"user2",from:2,to:1},{alias:"user3",from:3,to:7},{alias:"user4",from:7,to:3},{alias:"user5",from:1,to:2}],i=0;i<data.length;i++)void 0!==map[data[i].to]&&map[data[i].to].to===data[i].from&&console.log("match found ",map[data[i].to].alias," ",data[i].alias),map[data[i].from]={alias:data[i].alias,to:data[i].to};
public class Employee {
public static Map<String,String> buildingParkers=new HashMap<>();
public static void main(String[] args) {
addDetails("adrian",new EmployeeDetails("building1","building2"));
addDetails("john",new EmployeeDetails("building2","building1"));
addDetails("andrew",new EmployeeDetails("building3","building2"));
addDetails("william",new EmployeeDetails("building4","building3"));
addDetails("John",new EmployeeDetails("building2","building4"));
addDetails("Doe",new EmployeeDetails("",""));
System.out.println("Details successfully added ");
for(Map.Entry<String,String> entry: buildingParkers.entrySet()){
if(entry.getValue().contains(",") && !entry.getKey().equalsIgnoreCase("00"))
System.out.println(entry.getValue());
}
}
public static void addDetails(String alias, EmployeeDetails emp){
String code=emp.getBuildingCode();
String names="";
if(buildingParkers.containsKey(code))
{
names=buildingParkers.get(code)+","+alias;
buildingParkers.put(code, names);
}
else
buildingParkers.put(code,alias);
}
}
class EmployeeDetails{
private String fromBuilding;
private String toBuilding;
public EmployeeDetails(String fromBuilding, String toBuilding) {
this.fromBuilding=fromBuilding;
this.toBuilding=toBuilding;
}
public String getBuildingCode(){
String buildingCode="00";
if(Integer.parseInt(getBuildingNumber(fromBuilding)) > Integer.parseInt(getBuildingNumber(toBuilding)))
buildingCode=toBuilding+fromBuilding;
else
buildingCode=fromBuilding+toBuilding;
return buildingCode;
}
private String getBuildingNumber(String building){
if(building.isEmpty())
return "0";
else
return building.substring(8,building.length());
}
}
import java.util.*;
public class BuildingPasses {
public static void main(String[] args) {
List<List<String>> list = new ArrayList<>();
list.add(new ArrayList<String>());
list.add(new ArrayList<String>());
list.add(new ArrayList<String>());
list.add(new ArrayList<String>());
list.add(new ArrayList<String>());
list.get(0).add("adrian");
list.get(0).add("building1");
list.get(0).add("building2");
list.get(1).add("john");
list.get(1).add("building2");
list.get(1).add("building1");
list.get(2).add("andrew");
list.get(2).add("building3");
list.get(2).add("building2");
list.get(3).add("william");
list.get(3).add("building4");
list.get(3).add("building3");
list.get(4).add("john doe");
list.get(4).add("building2");
list.get(4).add("building4");
System.out.println(list);
List<List<String>> outputList = findPasses(list);
System.out.println(outputList);
}
public static List<List<String>> findPasses(List<List<String>> list){
List<List<String>> outputList = new ArrayList<>();
int c=0;
for(int i=0,j=i+1;i<list.size()&&j<list.size();i++,j++){
if(list.get(i).get(1).equals(list.get(j).get(2))){
outputList.add(new ArrayList<String>());
outputList.get(c).add(list.get(i).get(0));
outputList.get(c).add(list.get(j).get(0));
c++;
}
continue;
}
return outputList;
}
}
import java.util.*;
public class BuildingPasses {
public static void main(String[] args) {
List<List<String>> list = new ArrayList<>();
list.add(new ArrayList<String>());
list.add(new ArrayList<String>());
list.add(new ArrayList<String>());
list.add(new ArrayList<String>());
list.add(new ArrayList<String>());
list.get(0).add("adrian");
list.get(0).add("building1");
list.get(0).add("building2");
list.get(1).add("john");
list.get(1).add("building2");
list.get(1).add("building1");
list.get(2).add("andrew");
list.get(2).add("building3");
list.get(2).add("building2");
list.get(3).add("william");
list.get(3).add("building4");
list.get(3).add("building3");
list.get(4).add("john doe");
list.get(4).add("building2");
list.get(4).add("building4");
System.out.println(list);
List<List<String>> outputList = findPasses(list);
System.out.println(outputList);
}
public static List<List<String>> findPasses(List<List<String>> list){
List<List<String>> outputList = new ArrayList<>();
int c=0;
for(int i=0,j=i+1;i<list.size()&&j<list.size();i++,j++){
if(list.get(i).get(1).equals(list.get(j).get(2))){
outputList.add(new ArrayList<String>());
outputList.get(c).add(list.get(i).get(0));
outputList.get(c).add(list.get(j).get(0));
c++;
}
continue;
}
return outputList;
}
}
import java.util.*;
public class BuildingPasses {
public static void main(String[] args) {
List<List<String>> list = new ArrayList<>();
list.add(new ArrayList<String>());
list.add(new ArrayList<String>());
list.add(new ArrayList<String>());
list.add(new ArrayList<String>());
list.add(new ArrayList<String>());
list.get(0).add("adrian");
list.get(0).add("building1");
list.get(0).add("building2");
list.get(1).add("john");
list.get(1).add("building2");
list.get(1).add("building1");
list.get(2).add("andrew");
list.get(2).add("building3");
list.get(2).add("building2");
list.get(3).add("william");
list.get(3).add("building4");
list.get(3).add("building3");
list.get(4).add("john doe");
list.get(4).add("building2");
list.get(4).add("building4");
System.out.println(list);
List<List<String>> outputList = findPasses(list);
System.out.println(outputList);
}
public static List<List<String>> findPasses(List<List<String>> list){
List<List<String>> outputList = new ArrayList<>();
int c=0;
for(int i=0,j=i+1;i<list.size()&&j<list.size();i++,j++){
if(list.get(i).get(1).equals(list.get(j).get(2))){
outputList.add(new ArrayList<String>());
outputList.get(c).add(list.get(i).get(0));
outputList.get(c).add(list.get(j).get(0));
c++;
}
continue;
}
return outputList;
}
}
Have a hashMap<String, ArrayList<String>>
Key is the move 1,2 or 2,3 or 2,1 etc. And the ArrayList will have the list of employees doing that move.
Fill this hashMap.
Then iterate through the hashMap from the top. Check if there is a key with reverse of move in the map.
If there is then, keep matching and removing from the arrayLists till one of them becomes empty.
import java.io.*;
import java.util.*;
public class BuildingSwap {
public static void main(String[] args) {
String [] input = {"John,1,2","Dan,2,3","Mary,2,1","Eli,3,2","Sam,1,3","Tarly,3,2",
"Joey,1,2","Emma,2,3","Stone,2,3","Snow,2,1"};
ArrayList<String> swaps = findSwaps(input);
System.out.println(swaps);
}
static ArrayList<String> findSwaps (String input[]) {
HashMap <String,ArrayList<String>> map = new HashMap<>();
ArrayList<String> swaps = new ArrayList<>();
for(String emp : input) {
String move = emp.substring(emp.length()-3); // will give the moves like 1,2
if(map.get(move) == null) {
ArrayList<String> arr = new ArrayList<>();
arr.add(emp.substring(0,emp.length()-4));
map.put(move,arr);
}
else
map.get(move).add(emp.substring(0,emp.length()-4));
}
for(Map.Entry<String,ArrayList<String>> entry : map.entrySet()) {
String move = entry.getKey();
ArrayList<String> emps = entry.getValue();
String revMove = getReverse(move);
if(map.containsKey(revMove)) {
ArrayList<String> revEmps = map.get(revMove);
while(emps.size() > 0 && revEmps.size() > 0) {
String emp1 = emps.get(0);
String emp2 = revEmps.get(0);
swaps.add(new String(emp1 + " & " + emp2));
emps.remove(emp1);
revEmps.remove(emp2);
}
}
}
return swaps;
}
static String getReverse(String move) {
return new String(move.charAt(2) + "," + move.charAt(0));
}
}
{{
public class Person
{
public string AliasName;
public string FromBuilding;
public string ToBuilding;
}
class Program
{
public static void Main()
{
Console.WriteLine("******START*************");
Program p = new Program();
Dictionary<Person, Person> result = p.CalulateTuples();
foreach(var pair in result)
{
Console.WriteLine("Match found for : " + pair.Key.AliasName + " and " + pair.Value.AliasName);
}
Console.WriteLine("******END*************");
Console.ReadLine();
}
public Dictionary<Person, Person> CalulateTuples()
{
List<Person> persons = new List<Person>();
persons.Add(new Person() { AliasName = "Ardian", FromBuilding = "B1", ToBuilding = "B2" });
persons.Add(new Person() { AliasName = "John", FromBuilding = "B2", ToBuilding = "B1" });
persons.Add(new Person() { AliasName = "Andrew", FromBuilding = "B3", ToBuilding = "B2" });
persons.Add(new Person() { AliasName = "William", FromBuilding = "B4", ToBuilding = "B3" });
persons.Add(new Person() { AliasName = "John doe", FromBuilding = "B2", ToBuilding = "B4" });
Dictionary<Person, Person> tuples = new Dictionary<Person, Person>();
foreach(Person p in persons)
{
Person matched = persons.Where(per => per.ToBuilding == p.ToBuilding && per != p).FirstOrDefault();
if (matched != null)
{
if(!tuples.Keys.Contains(matched))
tuples.Add(p, matched);
}
}
return tuples;
}
}
}}
{{public class Person
{
public string AliasName;
public string FromBuilding;
public string ToBuilding;
}
class Program
{
public static void Main()
{
Console.WriteLine("******START*************");
Program p = new Program();
Dictionary<Person, Person> result = p.CalulateTuples();
foreach(var pair in result)
{
Console.WriteLine("Match found for : " + pair.Key.AliasName + " and " + pair.Value.AliasName);
}
Console.WriteLine("******END*************");
Console.ReadLine();
}
public Dictionary<Person, Person> CalulateTuples()
{
List<Person> persons = new List<Person>();
persons.Add(new Person() { AliasName = "Ardian", FromBuilding = "B1", ToBuilding = "B2" });
persons.Add(new Person() { AliasName = "John", FromBuilding = "B2", ToBuilding = "B1" });
persons.Add(new Person() { AliasName = "Andrew", FromBuilding = "B3", ToBuilding = "B2" });
persons.Add(new Person() { AliasName = "William", FromBuilding = "B4", ToBuilding = "B3" });
persons.Add(new Person() { AliasName = "John doe", FromBuilding = "B2", ToBuilding = "B4" });
Dictionary<Person, Person> tuples = new Dictionary<Person, Person>();
foreach(Person p in persons)
{
Person matched = persons.Where(per => per.ToBuilding == p.ToBuilding && per != p).FirstOrDefault();
if (matched != null)
{
if(!tuples.Keys.Contains(matched))
tuples.Add(p, matched);
}
}
return tuples;
}
}}}
public class Person
{
public string AliasName;
public string FromBuilding;
public string ToBuilding;
}
class Program
{
public static void Main()
{
Console.WriteLine("******START*************");
Program p = new Program();
Dictionary<Person, Person> result = p.CalulateTuples();
foreach(var pair in result)
{
Console.WriteLine("Match found for : " + pair.Key.AliasName + " and " + pair.Value.AliasName);
}
Console.WriteLine("******END*************");
Console.ReadLine();
}
public Dictionary<Person, Person> CalulateTuples()
{
List<Person> persons = new List<Person>();
persons.Add(new Person() { AliasName = "Ardian", FromBuilding = "B1", ToBuilding = "B2" });
persons.Add(new Person() { AliasName = "John", FromBuilding = "B2", ToBuilding = "B1" });
persons.Add(new Person() { AliasName = "Andrew", FromBuilding = "B3", ToBuilding = "B2" });
persons.Add(new Person() { AliasName = "William", FromBuilding = "B4", ToBuilding = "B3" });
persons.Add(new Person() { AliasName = "John doe", FromBuilding = "B2", ToBuilding = "B4" });
Dictionary<Person, Person> tuples = new Dictionary<Person, Person>();
foreach(Person p in persons)
{
Person matched = persons.Where(per => per.ToBuilding == p.ToBuilding && per != p).FirstOrDefault();
if (matched != null)
{
if(!tuples.Keys.Contains(matched))
tuples.Add(p, matched);
}
}
return tuples;
}
}
public class Person
{
public string AliasName;
public string FromBuilding;
public string ToBuilding;
}
class Program
{
public static void Main()
{
Console.WriteLine("******START*************");
Program p = new Program();
Dictionary<Person, Person> result = p.CalulateTuples();
foreach(var pair in result)
{
Console.WriteLine("Match found for : " + pair.Key.AliasName + " and " + pair.Value.AliasName);
}
Console.WriteLine("******END*************");
Console.ReadLine();
}
public Dictionary<Person, Person> CalulateTuples()
{
List<Person> persons = new List<Person>();
persons.Add(new Person() { AliasName = "Ardian", FromBuilding = "B1", ToBuilding = "B2" });
persons.Add(new Person() { AliasName = "John", FromBuilding = "B2", ToBuilding = "B1" });
persons.Add(new Person() { AliasName = "Andrew", FromBuilding = "B3", ToBuilding = "B2" });
persons.Add(new Person() { AliasName = "William", FromBuilding = "B4", ToBuilding = "B3" });
persons.Add(new Person() { AliasName = "John doe", FromBuilding = "B2", ToBuilding = "B4" });
Dictionary<Person, Person> tuples = new Dictionary<Person, Person>();
foreach(Person p in persons)
{
Person matched = persons.Where(per => per.ToBuilding == p.ToBuilding && per != p).FirstOrDefault();
if (matched != null)
{
if(!tuples.Keys.Contains(matched))
tuples.Add(p, matched);
}
}
return tuples;
}
}
@Vandita.Chhabaria, Your solution is n^2, that's not very good for a larger data sets. Here's what you can change to make the solution better wrt to time complexity. I believe this can be done in O(n)
- parikksit.b March 08, 2017