Amazon Interview Question SDE-2s
Country: United States
Interview Type: In-Person
Create Set<List<Node>>
Iterate over all children of the given input Node.
For each:
Check if it was visited before. (Hashtable, Node->Boolean), skip if it was.
If it was not create a new List<Node> and insert the Node into it. insert the List<...> into Set<List<Node>>
Iterate over all children of the Node, for each discovered ChildNode check if it was visited before. (Hashtable, Node->Boolean), skip if it was. If it's not add into the List<Node>, mark as visited.
Print Set<List<Node>>
vector<vector<Node*> >
groupNode(Graph* g, Node* n)
{
vector<Node*> nodes = g->getNodes();
vector<Node*> connectedNodes
for (auto node::iterate it = nodes.begin(); it != nodes.end(); ++it)
{
if ((*it)->IsConnect(n))
connectedNodes.push_back(*it);
}
vector<vector<Node*> > output;
while ( connectedNodes.size() != 0 )
{
Node* tmp = connectedNodes.pop_back();
connectNodes.erase(connectNodes.end());
vector<Node*> result;
result.push_back(tmp);
int size = connectedNodes.size() - 1;
while(size != 0)
{
if ( tmp->IsConnect(connectedNodes[size]) )
{
result.push_back(connectNodes[size]);
connectNodes.erase(connectNodes.begin()+size);
}
--size;
}
output.append( result);
}
return output;
}
package main
import "fmt"
var graph = map[int][]int{
1: []int{2, 3, 4},
2: []int{3},
3: []int{2},
4: []int{1},
5: []int{},
}
func main() {
result := findConnectedChildNodes(1, graph)
prettyPrint(result)
}
func findConnectedChildNodes(start int, nodes map[int][]int) [][]int {
result := [][]int{}
visited := map[int]bool{}
for _, n := range graph[start] {
visited[n] = true
group := map[int]bool{}
group[n] = true
for _, nn := range graph[n] {
if !visited[nn] {
group[nn] = true
}
}
if len(group) > 1 {
list := []int{}
for k, _ := range group {
if k != start {
list = append(list, k)
}
}
result = append(result, list)
}
}
return result
}
func prettyPrint(vv [][]int) {
for _, v := range vv {
for i, k := range v {
if i > 0 {
fmt.Print(" ")
}
fmt.Print(k)
}
fmt.Println()
}
}
class Graph {
public:
vector<Node> nodes;
vector<vector<int>> edges;
};
vector<vector<int>> cliques(Graph& g, int s)
{
vector<vector<int>> ans = {{1}};
for (auto i : g.edges[s]) {
vector<vector<int>> tmp;
for (auto v : ans) {
vector<int> t;
for (auto k : v) if (isConnected(i, k)) t.push_back(i);
t.push_back(k);
tmp.push_back(t);
if (t.size() == v.size() - 1) tmp.push_back(v);
}
ans.swap(tmp);
}
return ans;
}
@Igor
I am unable to post a reply for some reason but
Consider the following example: 4 2 5 and 3 are connected to 1. 4 and 2 are also connected to 3 and 6 is just connected to 5. (Diagram may get messed up on posting)
4
|\
6-5-1-3
|/
2
From what I understand with your approach,
when we visit unvisited children of 2, it will only discover 3 and group it with 1. However, we also want 4 to be included as it is also connected to 1 and connected to 3.
Moreover in your approach, it will also end up grouping 6 with 5. But it should not happen as it is not connected to 1.
The correct output for this case should be
2 3 4
5
Whereas (correct me if I am wrong), your approach would give
2 3
4
5 6
Sorry if my simpler example in the question was not making the requirement clear.
package com.mahesh;
import java.util.*;
public class HashtableExample {
public static void main(String args[]) {
Map m1 = new HashMap();
ArrayList AL1 = new ArrayList();
ArrayList AL2 = new ArrayList();
ArrayList AL3 = new ArrayList();
AL1.add(2);
AL1.add(3);
AL1.add(4);
AL2.add(3);
AL3.add(4);
m1.put(1,AL1);
m1.put(2,AL2);
m1.put(3,AL3);
for (int i=1;i<=3;i++){
System.out.println("For Node-"+i+":"+m1.get(i));
}
}
}
import java.util.ArrayList;
public class ConnectedNode {
Node root;
ConnectedNode() {
root = new Node(1);
prepareNodes();
}
private static class Node {
int id;
boolean visited;
ArrayList<Node> nodes = new ArrayList<Node>();
public Node(int id) {
this.id = id;
}
}
void printConnectedEachOther(Node node) {
if (node == null || node.visited) {
return;
}
boolean print = true;
for (Node n : node.nodes) {
if (!n.nodes.contains(node)) {
print = false;
break;
}
}
if (print) {
System.out.println(node.id);
}
node.visited = true;
for (Node connected : node.nodes) {
printConnectedEachOther(connected);
}
}
void prepareNodes() {
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
root.nodes.add(n2);
root.nodes.add(n3);
root.nodes.add(n4);
n2.nodes.add(n3);
n3.nodes.add(n2);
n4.nodes.add(root);
}
public static void main(String[] args) {
ConnectedNode cn = new ConnectedNode();
cn.printConnectedEachOther(cn.root);
}
}
nodes = { 1: [ 2, 3, 4],
2: [ 1, 3 ],
3: [ 1, 2 ],
4: [ 1, ],
5: []}
def printGroups(n):
kids = nodes[n]; gps = [];
for k in kids:
gp = [k,]
for sk in nodes[k]:
if sk in kids and not sk in gp: # don't duplicate
gp.append(sk)
if len(gp) > 1:
gp.sort() # So you have an ordered list.
d = ",".join(["%d" % g for g in gp]) # if you have more than one.
else:
d = "%d" % k #A singleton
if not d in gps: gps.append(d)
for gp in gps: print gp # print per line
# ---------------------
if __name__ == '__main__':
printGroups(1)
Create a DS containing for each node its neighbours i.e
1 -> 2 3 4
2 -> 1 3
3 -> 1 2
4 -> 1
5-> nil
Now for the input node in question (here 1) check the neighbors node's DS. If the neighbor node has common entries in the DS of the node in question group them.
Eg. 1 has neighbor nodes as 2 3 4
now 2 has 3,1
hence group 2,3 as 1 also has 3.
- divm01986 April 05, 2016//Time complexity: O(V+E). Space complexity: O(V+E) //I assume there are several other ways of doing this as well. public class Node { int value; ArrayList<Node> connect; } public ArrayList<ArrayList<Integer>> groups(Node n) { HashMap<Integer,Boolean> connected=new HashMap<Integer,Boolean>(); //Hash map with keys for all nodes connected to input node. for(Node x: n.connect) { connected.put(x.value,false); } ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>(); for(Node x:n.connect) { ArrayList<Integer> connectedNodes=checkConnect(x,connected); results.add(connectedNodes); } return connectedNodes; } private ArrayList<Integer> checkConnect(Node x,HashMap<Integer,Boolean> mp) { ArrayList<Integer> r=new ArrayList<Integer>(); r.add(x.value); mp.put(x.value,true); if(x.connect!=null) { for(Node g:x.connect) { if(mp.containsKey(g.value)) { boolean visited=mp.get(g.value);//Check if this vertex has already been visited if(!visited) { r.add(g.value); } } } } return r; }