Aristocrat Gaming Interview Question
Software Engineer / DevelopersTeam: game development
Country: India
Interview Type: In-Person
package com.linus.interview.ds.graph;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class BFS {
private Node rootNode;
int size;
/**
* @param args
*/
public static void main(String[] args) {
BFS bfs = new BFS();
Node nA=new Node("1");
Node nB=new Node("2");
Node nC=new Node("3");
Node nD=new Node("4");
Node nE=new Node("5");
Node nF=new Node("6");
Node nG=new Node("7");
bfs.setRootNode(nA);
connectedNode(nA, nB, nC);
connectedNode(nB, nD, nE);
connectedNode(nC, nF, nG);
bfs.doBFS();
}
public static void connectedNode(Node parentNode, Node leftNode, Node rightNode) {
Node parent = new Node();
parentNode.setLeftNode(leftNode);
parentNode.setRightNode(rightNode);
parent.setParentNode(parentNode);
}
public Node getRootNode() {
return rootNode;
}
public void setRootNode(Node rootNode) {
this.rootNode = rootNode;
}
public void doBFS() {
Queue<Node> queue = new LinkedList<Node>();
Stack<Node> stack = new Stack<Node>();
queue.add(this.rootNode);
stack.push(this.rootNode);
while (!queue.isEmpty()) {
Node node = queue.remove();
if (node.getRightNode() != null) {
stack.push(node.getRightNode());
queue.add(node.getRightNode());
}
if (node.getLeftNode() != null) {
stack.push(node.getLeftNode());
queue.add(node.getLeftNode());
}
}
while (!stack.isEmpty()) {
System.out.println(stack.pop().getNode());
}
}
}
//Class for Node
package com.linus.interview.ds.graph;
public class Node {
public boolean visited = false;
public boolean pVisited=false;
public String label;
private Node parentNode;
private Node leftNode;
private Node rightNode;
private String node;
public Node() {
}
public Node(String node) {
this.node = node;
}
public String getNode() {
return node;
}
public void setNode(String node) {
this.node = node;
}
public Node getLeftNode() {
return leftNode;
}
public void setLeftNode(Node leftNode) {
this.leftNode = leftNode;
}
public Node getRightNode() {
return rightNode;
}
public void setRightNode(Node rightNode) {
this.rightNode = rightNode;
}
public Node getParentNode() {
return parentNode;
}
public void setParentNode(Node parentNode) {
this.parentNode = parentNode;
}
}
#include<stdio.h>
#include<malloc.h>
typedef struct node_targ
{
int data;
struct node_targ *left;
struct node_targ *right;
} node;
void bfs( node *root)
{
node **a;
int head = 0, tail = 1;
a=(node**) malloc(50*sizeof(node*));
a[0] = root;
while(head != tail){
root = a[head];
if(root!=NULL){
if(root->right !=NULL) a[tail++]=root->right;
if(root->left !=NULL) a[tail++]=root->left;
}
head++;
}
for(head = tail-1; head>=0 ;head--){
printf("%d ",a[head]->data);
}
}
main()
{
node n7 = {7, NULL, NULL};
node n6 = {6, NULL, NULL};
node n5 = {5, NULL, NULL};
node n4 = {4, NULL, NULL};
node n3 = {3, &n6, &n7};
node n2 = {2, &n4, &n5};
node n1 = {1, &n2, &n3};
bfs(&n1);
}
Idea is good.
I would have upvoted this, if it weren't for the silly malloc (hardcoded) call and the memory leak...
Better than other one..Just that memory management was not that good as rightly pointed by somebody above..Nontheless +1.
#include <stack>
typedef struct node_targ
{
int data;
struct node_targ *left;
struct node_targ *right;
} node;
typedef node* BTree;
void print_btree_breadth(const BTree &tree)
{
deque<node *> level;
stack<node *> round;
level.push_front(tree);
while(level.size() != 0)
{
node *cur = level.front();
level.pop_front();
round.push(cur);
if(cur->right != NULL)
level.push_back(cur->right);
if(cur->left != NULL)
level.push_back(cur->left);
} // while
while(round.size() != 0)
std::cout << '[' << round.top()->data << ']' << std::endl , round.pop();
} // print_btree_breadth
int main(void)
{
node n7 = {7, NULL, NULL};
node n6 = {6, NULL, NULL};
node n5 = {5, NULL, NULL};
node n4 = {4, NULL, NULL};
node n3 = {3, &n6, &n7};
node n2 = {2, &n4, &n5};
node n1 = {1, &n2, &n3};
BTree tree = &n1;
print_btree_breadth(tree);
return 0;
}
This can be one solution,
public class PrintingLeftToRight {
public void printLToR(Node root, List<Node> traverseList) {
if ( root != null ) {
// 1. If the list is empty add root
if ( traverseList.isEmpty() ) {
traverseList.add(root);
}
// 2. If right child is not null
if ( root.getRight() != null ) {
traverseList.add(root.getRight());
}
// 3. If left child is not null
if ( root.getLeft() != null ) {
traverseList.add(root.getLeft());
}
// 4. Call the recursive method
printLToR(root.getRight(), traverseList);
printLToR(root.getLeft(), traverseList);
}
}
public void printLToR(Node root) {
if ( root != null ) {
List<Node> traversalList = new ArrayList<Node>();
printLToR(root, traversalList);
Object[] traverseNode = traversalList.toArray();
for ( int i = traverseNode.length - 1 ; i >= 0; i--) {
Node node = (Node) traverseNode[i];
System.out.print(node.getValue() + " ");
}
}
}
#include <memory>
#include <iostream>
#include <queue>
#include <algorithm>
template <class T>
struct node {
public:
typedef node<T> node_t;
T value_;
std::unique_ptr<node_t> left_;
std::unique_ptr<node_t> right_;
node(T value) : value_ (value) { }
void add_left(T value) { left_ = std::move(std::unique_ptr<node_t>(new node<T>(value))); }
node& left() { return *left_; }
void add_right(T value) { right_ = std::move(std::unique_ptr<node_t>(new node<T>(value))); }
node& right() { return *right_; }
T value() const { return value_; }
bool is_leaf() const { return !right_ && !left_; }
};
template <class T>
void bfs_print(node<T>& start_node)
{
typedef node<T> node_t;
typedef std::pair<node_t*, int> node_and_level_t;
typedef std::deque< node_and_level_t > nodes_and_levels_t;
nodes_and_levels_t nodes;
nodes.push_back(std::make_pair(&start_node, 0) );
typename nodes_and_levels_t::iterator itr = nodes.begin();
while (itr != nodes.end()) {
node_and_level_t current_node = *itr;
if ( !current_node.first->is_leaf() ) {
if (current_node.first->left_ ) {
nodes.push_back(std::make_pair(&(current_node.first->left()), current_node.second+1));
}
if (current_node.first->right_ ) {
nodes.push_back(std::make_pair(&(current_node.first->right()), current_node.second+1));
}
}
++itr;
}
std::stable_sort(nodes.begin(), nodes.end(), [] (const node_and_level_t& a, const node_and_level_t& b) { return a.second > b.second; } );
std::for_each(nodes.begin(), nodes.end(), [] (const node_and_level_t& a) { std::cout << a.first->value() ; } );
}
int main()
{
node<int> root(1);
root.add_left(2);
root.add_right(3);
root.left().add_left(4);
root.left().add_right(5);
root.right().add_left(6);
root.right().add_right(7);
bfs_print(root);
return 0;
}
so lets look at the normal BFS algo for the this tree first:
and the algo:
assuming that process delegates to System.out.print(), then we will print:
1234567
if we instread enqueue the right child before the left, like this
this will print:
1327654
which is our goal but revered... so we can use a stack to reverse it:
This gives the correct answer, namely
- matthewrobertwalters September 06, 20124567231