Amazon Interview Question for SDE-2s


Country: India
Interview Type: In-Person




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

Here is java code for api, works with O(logn) complexity.

public class CityPlanner {


    private int[] parents;
    private Set<Edge> edges = new HashSet<>();
    private int noOfVertex = 0;


    public CityPlanner(int noOfVertex) {
        this.noOfVertex = noOfVertex;
        parents = new int[noOfVertex];
        for (int i = 0; i < noOfVertex; i++) {
            parents[i] = -1;
        }
    }

    public void buildRoad(int a, int b){
        if (a == b) {
            throw new IllegalArgumentException("Source and destination is same");
        }
        Edge edge = new Edge(a, b);
        if (!edges.add(edge)) {
            throw new IllegalArgumentException("Road built already");
        }
        int aParent = getParent(a);
        int bParent = getParent(b);
        if (aParent != bParent) {
            parents[aParent] = bParent;
        }
    }

    public boolean isRoadExist(int a, int b){
        return getParent(a)==getParent(b);
    }

    private int getParent(int v) {
        while (parents[v]!=-1){
            v = parents[v];
        }
        return v;
    }

    private class Edge {
        int src;
        int dest;

        public Edge(int src, int dest) {
            this.src = src;
            this.dest = dest;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Edge edge = (Edge) o;

            if (src != edge.src || src !=edge.dest) return false;
            if (src != edge.src) {
                return dest==edge.src;
            }
            return dest == edge.dest;
        }

        @Override
        public int hashCode() {
            int result = src * dest;
            result = 31 * result + dest + src;
            return result;
        }
    }
}

- akshay June 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Complexity is O(log n) for both operations, building road and checking if the road exists.

Algorithm:
* Create DAGs (Directed Acyclic Graph) of road connectivity
* If two cities are part of same DAG, they are connected, otherwise not
* Find DAG root of both cities, if root is same for both, they are connected.
* If they have different roots, and we are building a road, connect both the DAGs, now all the cities in both DAGs are connected to each other.

class RoadNetwork {
	private:
		unsigned int n, *parent;
		unsigned int root(unsigned int x);

	public:
		void buildRoad(unsigned int a, unsigned int b);
		bool isRoadExists(unsigned int a, unsigned int b);

		RoadNetwork(unsigned int n) {
			this.n = n;
			parent = (unsigned int *) calloc (n, sizeof(unsigned int));
			if (parent == NULL)
				printf("Failed to allocate memory");
			else {
				unsigned int i;
				for (i = 0; i < n; i ++)
					parent[i] = n;
			}
		}

		~RoadNetwork() {
			free(parent);
		}
}

void RoadNetwork::buildRoad(unsigned int a, unsigned int b) {
	unsigned int r1 = root(a);
	unsigned int r2 = root(b);

	if (r1 == r2)
		return;
	parent(r1) = r2;
}

void RoadNetwork::isRoadExists(unsigned int a, unsigned int b) {
	if (root(a) == root(b))
		return true;
	return false;
}

unsigned int RoadNetwork::root(unsigned int x) {
	while (parent[x] != n)
		x = parent[x];
	return x;		
}

- Mukesh July 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

implement KRUSKAL ALGORITHM

- mayank goyal June 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

implement Kruskal algorithm

- MAYANK GOYAL June 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

implement KRUSKAL algorithm

- mayank9jung June 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use Disjoint Subsets with path compression.

- Parth Sharma June 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be done with union find as well

- xzx June 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can use Breadth First Search to find the connectivity between vertices in O(N).
Use improved Union-Find to find connectivity in O(log N).

- mrsurajpoudel.wordpress.com June 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

build a graph and do a bfs.

- Anonymous June 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use union-find; it's even faster than log(n).

- Roger June 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is something I came up with.

public class SiteNode
        {
            public string Name { get; set; }
            public List<SiteNode> Children { get; set; }

            public SiteNode(string name)
            {
                this.Name = name;
                this.Children = new List<SiteNode>();
            }
        }

        public class City
        {
            Dictionary<SiteNode, bool> CityMap { get; set; }

            public void AddConnection(SiteNode node1, SiteNode node2)
            {
                if (CityMap.ContainsKey(node1))
                {
                    node1.Children.Add(node2);
                }
            }

            private void SetVisited(SiteNode node)
            {
                CityMap.Remove(node);
                CityMap.Add(node, true);
            }

            private void UnvisitAll()
            {
                foreach (var kvp in CityMap)
                {
                    CityMap.Remove(kvp.Key);
                    CityMap.Add(kvp.Key, false);
                }
            }
            private bool IsConnection(SiteNode node1, SiteNode node2)
            {
                var currentNode = node1;
                SetVisited(node1);
                var result = false;
                foreach (var node in node1.Children)
                {
                    if (node == node2)
                        return true;

                    if (!CityMap[node])
                        result = result || IsConnection(node, node2);
                }
                return result;
            }

            public bool IsConnected(SiteNode node1, SiteNode node2)
            {
                var result = IsConnection(node1, node2);
                UnvisitAll();
                return result;
            }
        }

- Apt4791 June 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class SiteNode
        {
            public string Name { get; set; }
            public List<SiteNode> Children { get; set; }

            public SiteNode(string name)
            {
                this.Name = name;
                this.Children = new List<SiteNode>();
            }
        }

        public class City
        {
            Dictionary<SiteNode, bool> CityMap { get; set; }

            public void AddConnection(SiteNode node1, SiteNode node2)
            {
                if (CityMap.ContainsKey(node1))
                {
                    node1.Children.Add(node2);
                }
            }

            private void SetVisited(SiteNode node)
            {
                CityMap.Remove(node);
                CityMap.Add(node, true);
            }

            private void UnvisitAll()
            {
                foreach (var kvp in CityMap)
                {
                    CityMap.Remove(kvp.Key);
                    CityMap.Add(kvp.Key, false);
                }
            }
            private bool IsConnection(SiteNode node1, SiteNode node2)
            {
                var currentNode = node1;
                SetVisited(node1);
                var result = false;
                foreach (var node in node1.Children)
                {
                    if (node == node2)
                        return true;

                    if (!CityMap[node])
                        result = result || IsConnection(node, node2);
                }
                return result;
            }

            public bool IsConnected(SiteNode node1, SiteNode node2)
            {
                var result = IsConnection(node1, node2);
                UnvisitAll();
                return result;
            }

}

- Apt4791 June 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Scanner;

public class buildRoad {

boolean flag;



buildRoad(){
this.flag = false;
}

buildRoad(int a,int b){
this.flag = true;
}

public boolean checkRoad(){
return this.flag;
}

public static void main(String[] args) {
// TODO Auto-generated method stub


buildRoad br[][] = new buildRoad[10][10];

Scanner str = new Scanner(System.in);

for (int i=0;i<br.length;i++)
for(int j=0;j<br.length;j++)
br[i][j] = new buildRoad();


while(true){
System.out.println("Do you want to build Road y or n");
char c = str.next().charAt(0);

if (c=='n'||c=='N') {
break;
}

System.out.println("Enter paths");
int a=str.nextInt();
int b=str.nextInt();


if (br[a][b].flag)
System.out.println("Path already exists");
else
br[a][b] = new buildRoad(a,b);


}

while(true){
System.out.println("Do you want to check path");
char c = str.next().charAt(0);

if (c=='n'||c=='N') {
break;
}

System.out.println("Enter paths");
int a=str.nextInt();
int b=str.nextInt();

System.out.println("Path available? "+br[a][b].checkRoad());
}




}


};

- muralidhar78 July 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Scanner;

public class buildRoad {
	
	boolean flag;
	
	
	
	buildRoad(){
		this.flag = false;
	}
	
	buildRoad(int a,int b){
		this.flag = true;
	}
	
	public boolean checkRoad(){
		return this.flag;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		
		buildRoad br[][] = new buildRoad[10][10];
		
		Scanner str = new Scanner(System.in);
		
		for (int i=0;i<br.length;i++)
			for(int j=0;j<br.length;j++)
				br[i][j] = new buildRoad();
		
		
		while(true){
			System.out.println("Do you want to build Road y or n");
			char c = str.next().charAt(0);
			
			if (c=='n'||c=='N') {
				break;
			}
			
			System.out.println("Enter paths");
			int a=str.nextInt();
			int b=str.nextInt();
			
			
			if (br[a][b].flag)
				System.out.println("Path already exists");
			else
			br[a][b] = new buildRoad(a,b);
			
			
		}
		
		while(true){
			System.out.println("Do you want to check path");
			char c = str.next().charAt(0);
			
			if (c=='n'||c=='N') {
				break;
			}
			
			System.out.println("Enter paths");
			int a=str.nextInt();
			int b=str.nextInt();
			
			 System.out.println("Path available? "+br[a][b].checkRoad());
		}
		
		
	

	}
	
	
};

- muralidhar78 July 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use technique similar to connected components. Mark all vertices as cc = -1. (not part of a component).
When you get an add, check if either vertex is connected. If only one is connected, mark other with the cc. If both are having a cc that are different, mark second one's cc as same as first one's cc for all vertices having second one's cc.
If both are unconnected mark both with the same new new cc number.

Checking if two points i and j are connected is an O(1) operation as you will just check the cc[i] and cc[j] are same.

- arviman August 15, 2016 | 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