Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
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;
}
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;
}
}
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;
}
}
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());
}
}
};
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());
}
}
};
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.
Here is java code for api, works with O(logn) complexity.
- akshay June 14, 2016