Amazon Interview Question for Software Developers


Team: Alexa
Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
0
of 2 vote

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

//Employee Class:
public class Employee{
	public String fName;
	public String movingFrom; //Building number;
	public String movingTo; //Building number;
	...
}

/* Here's how you'd add data to a HasMap:
	Map<String, String> map = new HashMap<>();
	//Concat strings for from and to, it'd look like this: '1,2', which means
	// the employee is moving from building 1 to building 2
	map.add(emp.fromBuilding +","+ emp.ToBuilding, emp.fName);
	.... //Repeat for all employees.

//Here's how you'd do the matchup
pubic ArrayList<String> matchUp(HashMap map)
{
	List<String> list = new ArrayList<>();

	Iterator it = mp.entrySet().iterator();
	while( it.hasNext() )
	{
		Map.Entry pair = (Map.Entry) it.next();
		String temp = getReversed(pair.getKey());
		if(map.containsKey(temp))
			list.add(pair.value() + ", " + map.get(temp));
	}
	return list;
}

private String getReversed(String s)
{
	String[] temp = s.split(",");
	return temp[1] + "," + temp[0];
}

- parikksit.b March 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- shamsminoo April 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- vashir May 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- vashiR May 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- Faisal May 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- KC June 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- KC June 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- KC June 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- NinjaCoder July 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

{{
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 March 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

{{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 March 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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 March 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- chhabaria.vandita March 08, 2017 | 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