Amazon Interview Question
SDE1sTeam: Machine learning
Country: India
Interview Type: Phone Interview
Let assume that you are given class Graph and source vertex: (i) push the source to the stack and mark it as visited, (ii) unless stack is empty, pop the vertex, if not visited add its adjacent vertices to the stackan mark as visited.
public void dfs(Graph G, int source) {
boolean[] isVisited = boolean[G.V()];
Stack<Integer> stk = new Stack<Integer>();
stk.push(source);
isVisited[source] = true;
while (!stk.isEmpty()) {
int v = stk.pop();
for (int w : G.adjacent(v))
if (!isVisited[w]) {
isVisited[w] = true;
stk.push(w);
}
}
}
Now the question is what the interviewer wanted you to do with the dfs.
Hi Darkhan, thx for noticing me about marking the source. Why you think that it fail if there is a cycle? It does not since already visited node is not gonna be pushed to the stack ever again.
Well, that's not very big mistake, but if interviewer asks to print the vertexes in say post(pre) order traversal, I'm afraid source vertex will be printed twice. The thing is that source vertex will be 2 times in stack instead of 1.
0 -> 1
0 -> 2
1 -> 2
2 -> 0
dfs(0)
Correct me if I'm mistaken
Can someone please point out if there are any logical errors in this algorithm. Thank you!!
public static boolean DFS(Node A, Node root){
if(root.data == null) return false;
if(root.data == A.data) return true;
root.visited = true;
for(Node x: root.adjecent()){
if(x.visited != true){
DFS(A, x);
}
}
return false;
}
Actually there is a logical error. You should put:
if (DFS(A, x)) {
return true;
}
because otherwise your code will always return false if root.data != A.data once you begin to visit neighbors.
Here is my implementation of dfs in non-recursive way
private void dfs(int source, int n, LinkedList<Integer>[]g){
boolean []visited = new boolean[n];
Stack<Integer> stack = new Stack<Integer>();
visited[source] = true;
stack.push(s);
while(stack.size() > 0){
int v = stack.peek();
if (g[v].hasNext()){
int u = g[v].next();
visited[u] = true;
stack.push(u);
}else{
stack.pop();
}
}
}
static void DFS(TreeNode node) {
Stack stack = new Stack();
stack.push(node);
while(!stack.isEmpty()) {
while(node.left!=null) {
if(node.left!=null) {
stack.push(node.left);
node = node.left;
}
}
while(true) {
if(stack.isEmpty())
break;
TreeNode n = (TreeNode) stack.pop();
System.out.println(n.data+" ");
if(n.right!=null) {
stack.push(n.right);
n = n.right;
break;
}
}
}
}
Here is my Code
/**
*
*/
package com.unmetric.others;
import java.util.Stack;
/** @author User */
public class rg1 {
/** @param args */
public static void main(String[] args) {
dfsPreOrder(getRoot());
System.out.println("---------Pre Order");
dfsInOrder(getRoot());
System.out.println("---------In Order");
dfsPstOrder(getRoot());
System.out.println("---------Post Order");
dfsStackPreOrder(getRoot());
System.out.println("---------with statck Pre Order");
dfsStackInOrder(getRoot());
System.out.println("---------with statck In Order");
dfsStackPstOrder(getRoot());
System.out.println("---------with statck Post Order");
}
private static Node getRoot() {
final Node root = new Node(7);
final Node lvl1Lft = new Node(3);
final Node lvl1Rgt = new Node(9);
root.leftNode = lvl1Lft;
root.rightNode = lvl1Rgt;
lvl1Lft.leftNode = new Node(1);
lvl1Lft.rightNode = new Node(4);
return root;
}
private static void dfsPreOrder(Node node) {
if (node == null) { return; }
System.out.print(node.i);
dfsPreOrder(node.leftNode);
dfsPreOrder(node.rightNode);
}
private static void dfsInOrder(Node node) {
if (node == null) { return; }
dfsInOrder(node.leftNode);
System.out.print(node.i);
dfsInOrder(node.rightNode);
}
private static void dfsPstOrder(Node node) {
if (node == null) { return; }
dfsPstOrder(node.leftNode);
dfsPstOrder(node.rightNode);
System.out.print(node.i);
}
private static void dfsStackPreOrder(Node root) {
final Stack<Node> stack = new Stack<Node>();
stack.push(root);
while (!stack.isEmpty()) {
final Node currNode = stack.peek();
if (!currNode.leftVisited || !currNode.rightVisited) {
if (currNode.leftNode != null && !currNode.leftVisited) {
System.out.print(currNode.i);
currNode.leftVisited = true;
stack.push(currNode.leftNode);
} else if (currNode.rightNode != null && !currNode.rightVisited) {
currNode.rightVisited = true;
stack.push(currNode.rightNode);
} else {
System.out.print(currNode.i);
stack.pop();
}
} else {
stack.pop();
}
}
}
private static void dfsStackInOrder(Node root) {
final Stack<Node> stack = new Stack<Node>();
stack.push(root);
while (!stack.isEmpty()) {
final Node currNode = stack.peek();
if (!currNode.leftVisited || !currNode.rightVisited) {
if (currNode.leftNode != null && !currNode.leftVisited) {
currNode.leftVisited = true;
stack.push(currNode.leftNode);
} else if (currNode.rightNode != null && !currNode.rightVisited) {
System.out.print(currNode.i);
currNode.rightVisited = true;
stack.push(currNode.rightNode);
} else {
System.out.print(currNode.i);
stack.pop();
}
} else {
stack.pop();
}
}
}
private static void dfsStackPstOrder(Node root) {
final Stack<Node> stack = new Stack<Node>();
stack.push(root);
while (!stack.isEmpty()) {
final Node currNode = stack.peek();
if (!currNode.leftVisited || !currNode.rightVisited) {
if (currNode.leftNode != null && !currNode.leftVisited) {
currNode.leftVisited = true;
stack.push(currNode.leftNode);
} else if (currNode.rightNode != null && !currNode.rightVisited) {
currNode.rightVisited = true;
stack.push(currNode.rightNode);
} else {
System.out.print(currNode.i);
stack.pop();
}
} else {
System.out.print(currNode.i);
stack.pop();
}
}
}
}
class Node {
Node(int i) {
this.i = i;
}
int i;
boolean leftVisited = false;
boolean rightVisited = false;
Node leftNode;
Node rightNode;
}
- Vir Pratap Uttam May 20, 2015