Amazon Interview Question for Interns


Country: United States
Interview Type: Phone Interview




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

One way you can do this is make nodes for each number, then add connections in code.
Put all of these nodes into a List (L)

Now, run DFS on one node- All nodes in the visited list of this DFS will be part of a set (group), Now, remove all the nodes in the visited list from L. With whatever node is left in L,run DFS and repeat the same process until L is empty.

- Skor January 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

Elements can be expressed by an array for union find operartions

0 1 2 3 4 5 6 7 8 9 <- Connected to
------------------------
0 1 2 3 4 5 6 7 8 9 <— Element


Step 1: (1,2)


0 1 1 3 4 5 6 7 8 9
------------------------
0 1 2 3 4 5 6 7 8 9

Step 2: (2,3)


0 1 1 1 4 5 6 7 8 9
------------------------
0 1 2 3 4 5 6 7 8 9

Step 3: (5,6)


0 1 1 1 4 5 5 7 8 9
------------------------
0 1 2 3 4 5 6 7 8 9

Step 4: (2,9)


0 1 1 1 4 5 5 7 8 1
------------------------
0 1 2 3 4 5 6 7 8 9

Now go through all the array and print out connected components

0: 0
1: 1 2 3 9
4: 4
5:5 6
6:
7: 7
8: 8
9:

- BT January 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Isnt this n*logn worst case? Let's say you have 8 elements and you have pairs (0,1) (2,3) (4,5) (6,7) (1,2) (5,6) (3,5). Then your algorithm would have to perform nlogn in the worst case, althought depending on the order the pairs are processed, it could also end up being linear. So the order of the pairs matter, but the worst case complexity is still nlogn. A fine algorithm but slower than some of the ones presented here.

- Anonymous January 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

union-find + sort
O(log*(number_of_elements) * number_of_edges + number_of_elements * log(number_of_elements))

- Anonymous January 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you give it a detailed explanation?

- Henrywang0113 January 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why the output is {1,2,9} and {5,6} can you explain that?

- MIG January 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It should be either {1,2,3} and {5,6} if we are not considering the second occurance. else it should {1,2,3,9} and {5,6} ..??

- varun.me15 January 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

(1,2)
(2,3)
(5,6)
(2,9)
(3,4)
(5,9)
(9,10)

in this case what should be the output?

- MIG January 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create a graph of connections between elements (undirected) and a set containing every single element (etc. unvisited(1,2,3,9,5,6)) . Start from any element in the unvisited set and make a dfs or bfs on the graph. Delete the element from the set when it's visited. And as long as there are still elements at the end of each bfs/dfs, continue the above algorithm. Each separate dfs/bfs gives you the different connections

import collections

def findComponents(connections):
    unvisited = set()
    graph = collections.defaultdict(list)

    for x, y in connections:
        graph[x].append(y)
        graph[y].append(x) # Graph is undirected
        unvisited.add(x)
        unvisited.add(y)

    components = [[]]
    stack = collections.deque()

    stack.append(unvisited.pop())
    while len(stack) != 0:
        node = stack.pop()  
        components[-1].append(node)

        print node, unvisited
        for nbr in graph[node]:
            if nbr in unvisited:
                stack.append(nbr)
                unvisited.remove(nbr)

        if len(stack) == 0:
            if len(unvisited) == 0:
                return components
            else:
                components.append([])
                stack.append(unvisited.pop())

connections = [(1,2), (2,3), (5,6), (2,9)]
components = findComponents(connections)
print components

- haydum January 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

(1,2)
(2,3)
(5,6)
(2,9)
(3,4)
(5,9)
(9,10)

in this case what should be the output?

- MIG January 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution is not linear...I know that. However, I do not need to create a graph and perform DFS. Simply sort pairs based on smallest value in pair.

(2,3), (5, 1) => (5, 1), (2, 3) because 1 is the smallest value in (5, 1) and is smaller than 2 (the smallest value in (2, 3)).

Now, simply iterate through pairs and determine if consecutive pairs are in the same group (if they contain one of the same numbers). The code is shown below:

public class Pair implements Comparable<Pair> {
    int x;
    int y;
    
    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
    
    public boolean contains(int num) {
        return this.x == num || this.y == num;
    }
    
    @Override
    public int compareTo (Pair other) {
        return new Integer(Math.min(x, y)).compareTo(Math.min(other.x, other.y));
    }    
}


//In some other class
public List<Set<Integer>> computeGroups(List<Pair> pairs) {
        List<Set<Integer>> groups = new ArrayList<Set<Integer>>();
        Collections.sort(pairs);
        Pair pair = pairs.get(0);
        Set<Integer> group = new HashSet<Integer>();
        group.add(pair.x);
        group.add(pair.y);
        for(int i = 1; i < pairs.size(); i++) {
            if(!pairs.get(i).contains(pair.x) && !pairs.get(i).contains(pair.y)) {
                groups.add(group);
                group = new HashSet<Integer>();
            }
            pair = pairs.get(i);
            group.add(pairs.get(i).x);
            group.add(pairs.get(i).y);
        }
        groups.add(group);
        return groups;
    }

- akyker20 January 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A very simple code which uses only a string and trivial delimiters.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;


class List {
	
	String list;
	
	List() {
		list="";
	}
	
	boolean last(int a) {
		return list.contains(a+";");
	}
	
	void append(int b, int a) {
		int i;
		list = list.substring(0,(i=list.indexOf(a+";"))+1)+","+b+list.substring(i+1);
	}
	
	void add(int a, int b) {
		list+=a+","+b+";";
	}
	
	void printGroup() {
		char c;
		for(int i=0; i<list.length();i++) 
			System.out.print((c=list.charAt(i))==';'?"\n":c);
	}
	
}

public class Group {

	public static void main(String args[]) {
		
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		List list=new List();
		
		for(int i=1;i<=n; i++) {
			int a = s.nextInt(), b=s.nextInt();
			if(list.last(a))
				list.append(b,a);
			else list.add(a,b);		
		}
		
		list.printGroup();
		
	}
}

- Anindya Dutta January 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about build a map<integer, list<integer>>, and then put all the pairs in it. For (2,3), (2,9), it will be {2: [3, 9]}.

And then pop every key from the map, and then concat the corresponding value as well as corresponding value of the value recursively, until there is no corresponding value. Then we get a group.

Repeat above steps until there is no pair left in the map, and then we get all the groups.

- Wang Yuanzhi February 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

var data = [[1,2], [2,3], [5,6], [2,9]];

function func (data) {

	var ht = {};
	for (var i=0; i<data.length; i++) {

		var point = data[i];
		if (ht[point[0]] === undefined) {
			ht[point[0]] = [];
		}
		ht[point[0]].push(point[1]);
	}

	// ht will be something like
	// [1] => [2]
	// [2] => [3, 9]
	// [5] => [6]

	var result = [];
	var index = 0;
	for (var u in ht) {

		result.push([parseInt(u)]);
		var v_collection = ht[u];

		for (var j=0; j<v_collection.length; j++) {

			result[index].push(v_collection[j]);
			var v = v_collection[j];
			if (ht[v] !== undefined) {

				result[index] = result[index].concat(ht[v]);
				delete ht[v];
			}
		}
		index +=1
	}

	return result;
}

func(data);

- Mr Peru February 07, 2015 | 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