Aristocrat Gaming Interview Question for Software Engineer / Developers


Team: game development
Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
2
of 6 vote

so lets look at the normal BFS algo for the this tree first:

1
       /    \
      2     3
     /  \    /   \
  4    5 6    7

and the algo:

void BFS(Node root){
    Queue q = new Queue();
    q.enqueue(root);
    while(!q.isEmpty()){
        Node node = q.dequeue();
        process(node);
        q.enqueue(node.left);  // queue automatically rejects null vals
        q.enqueue(node.right);
    }
}

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

void BFS(Node root){
    Queue q = new Queue();
    q.enqueue(root);
    while(!q.isEmpty()){
        Node node = q.dequeue();
        process(node);
        q.enqueue(node.right);
        q.enqueue(node.left);
    }
}

this will print:
1327654
which is our goal but revered... so we can use a stack to reverse it:

void BFSPostOrder(Node root){
    Queue q = new Queue();
    Stack s = new Stack();
    q.enqueue(root);
    while(!q.isEmpty()){
        Node node = q.dequeue();
        s.push(node);
        q.enqueue(node.right);
        q.enqueue(node.left);
    }
    while(!s.isEmpty()){
        Node node = s.pop();
        process(node);
    }
}

This gives the correct answer, namely
4567231

- matthewrobertwalters September 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}


}

- Sunil Kumar Tamoli September 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

#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);
	
}

- j.a.b. September 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Idea is good.

I would have upvoted this, if it weren't for the silly malloc (hardcoded) call and the memory leak...

- Anonymous September 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Better than other one..Just that memory management was not that good as rightly pointed by somebody above..Nontheless +1.

- Prashant R Kumar September 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This method require O(n) extra memory which is definitely not necessary.
The code also employed a very bad memory management style.
Strongly depreciated. Thus -1

- Ares.Luo.T September 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

starting from* the lowest level.
The tree being.

1

2       3

4   5   6  7

- sakar8828 September 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- hwen.tmp September 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

level order traversal ....

- vivek September 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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() + " ");
				
			}
		}
	}

- belligerentCoder September 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- skwllsp September 09, 2012 | 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