Groupon Interview Question for Software Engineers


Country: United States




Comment hidden because of low score. Click to expand.
0
of 0 vote

In it a binary tree? if not, how are the children stored in the tree?

- MehrdadAP June 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

And What do you mean that tree can have any number of nodes? can't we do a simple BFS and print the nodes?

What about the number of nodes in each level, is there any restriction for that?

- MehrdadAP June 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry it can have any number of child node. It can be stored in list or something. There is no restriction on number of node in any level.

- snehit.gajjar June 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

BFS

- Anonymous June 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void levelOrderTraversal(BinaryTreeNode root) {
		BinaryTreeNode temp;
		Queue<BinaryTreeNode> q = new LinkedBlockingDeque<BinaryTreeNode>();
		q.add(root);
		q.add(new BinaryTreeNode(-1));
		while (!q.isEmpty()) {
			temp = q.poll();
			
			if (temp.getData() == -1) {
				System.out.println();
				if (!q.isEmpty())
					q.add(new BinaryTreeNode(-1));

			} else {
				System.out.print(" "+temp.getData());
				if (temp.getLeft() != null)
					q.add(temp.getLeft());
				if (temp.getRight() != null)
					q.add(temp.getRight());
			}
		}

	}

- Vir Pratap Uttam June 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Vir Pratap, it is not just for binary tree. There can be any number of child node for any node.

- snehit.gajjar June 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
 * Write a function to print a tree, which can have any number of nodes,
 * in level order, each level on a new line.  E.g.,
 * If the tree is :
 * 		1
 * 		2 3
 * 		4 5 6
 * then the answer should be:
 * 	1\n
 * 	2,3\n
 * 	4,5,6\n
*/

exports.Node = function (value, children) {
	this.value = value;
	this.child = [];
	for (var i = 0; i < children.length; i++) {
		this.child.push(children[i]);
	}
};
exports.printTree = function (rootNode) {
	var Q = [];
	Q.enqueue = Q.unshift;
	Q.dequeue = Q.pop;

	rootNode.visited = true;
	rootNode.level = 0;
	Q.enqueue(rootNode);
	
	var currLevel = 0;
	var s  = "";
	while (Q.length) {
		var p = Q.dequeue();
		if (p.level === currLevel) {
			s += p.value;
		}
		if (p.level === currLevel + 1) {
			s += '\n';
			s += p.value;
			currLevel++;
		}
		if (Q.length && Q[Q.length - 1].level === p.level) {
			s += ',';
		}
		for (var i = 0; i < p.child.length; ++i) {
			if (!p.child[i].visited) {
				p.child[i].visited = true;
				p.child[i].level = p.level + 1;
				Q.enqueue(p.child[i]);
			}
		}
	}
	return s;
};


jest.dontMock('../2015-06-25');

describe('A function to print a tree in level order, ' +
		'each level on a new line.', function () {
	it('prints each level on its own line', function () {
		var printTree = require('../2015-06-25').printTree
		, Node = require('../2015-06-25').Node
		rootNode = new Node(1, [
			new Node(2, [
				new Node (4, [])
			]),
			new Node(3, [
				new Node(5, []),
				new Node(6, [])
			])
		]);
		expect(printTree(rootNode)).toBe([
			"1",
			"2,3",
			"4,5,6"
		].join("\n"));
	});
});

- Anonymous June 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
 * Write a function to print a tree, which can have any number of nodes,
 * in level order, each level on a new line.  E.g.,
 * If the tree is :
 * 		1
 * 		2 3
 * 		4 5 6
 * then the answer should be:
 * 	1\n
 * 	2,3\n
 * 	4,5,6\n
*/

exports.Node = function (value, children) {
	this.value = value;
	this.child = [];
	for (var i = 0; i < children.length; i++) {
		this.child.push(children[i]);
	}
};
exports.printTree = function (rootNode) {
	var Q = [];
	Q.enqueue = Q.unshift;
	Q.dequeue = Q.pop;

	rootNode.visited = true;
	rootNode.level = 0;
	Q.enqueue(rootNode);
	
	var currLevel = 0;
	var s  = "";
	while (Q.length) {
		var p = Q.dequeue();
		if (p.level === currLevel) {
			s += p.value;
		}
		if (p.level === currLevel + 1) {
			s += '\n';
			s += p.value;
			currLevel++;
		}
		if (Q.length && Q[Q.length - 1].level === p.level) {
			s += ',';
		}
		for (var i = 0; i < p.child.length; ++i) {
			if (!p.child[i].visited) {
				p.child[i].visited = true;
				p.child[i].level = p.level + 1;
				Q.enqueue(p.child[i]);
			}
		}
	}
	return s;
};

- Anon June 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we assume that each node knows how many children it has. I.E it's stored in a vector of pointers not an array with no count. (C++ reference)

- SycophantEve June 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In Go :

type TNode struct {
	Value int
	Left  *TNode
	Right *TNode
	Level int
}

func DisplayBFS(root *TNode) {
	if root == nil {
		return
	}
	queue := NewQueue()
	currentLevel := 0
	nbItemByLevel := 0
	queue.Enqueue(root)
	for {
		if queue.IsEmpty() {
			return
		}
		current := queue.Dequeue().(*TNode)
		if currentLevel != current.Level {
			fmt.Println("")
			currentLevel++
			nbItemByLevel = 0
		}
		if nbItemByLevel > 0 {
			fmt.Print(",")
		}
		fmt.Print(current.Value)
		nbItemByLevel++

		if current.Left != nil {
			current.Left.Level = current.Level + 1
			queue.Enqueue(current.Left)
		}
		if current.Right != nil {
			current.Right.Level = current.Level + 1
			queue.Enqueue(current.Right)
		}
	}
}

- maxime June 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You did it only for two child node. Question is that each node can have any number of child.

- snehit.gajjar June 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi!
I'm a little confused by some of the answers I'm seeing here.
Are we assuming then that the nodes in the tree already contain a level property in them?
So if I am iterating through the nodes, I could check the current node's level by

curr.level

? That seems too easy.

- ryangurney December 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.LinkedList;

/**
 * Created by Ryan on 12/8/2015.
 */
public class Test
{
    public static class Node
    {
        int data;
        Node[] children;

        public Node( int data, Node[] children )
        {
            this.data = data;
            this.children = children;
        }
    }
    public static void main(String args[])
    {
        //Testy test
        /*
         0
        /|\
       1 2 3
      / /\ 
     4 5  6
      /  /|\ 
     7  8 9 10
         */
        Node leaf1 = new Node(4, null);
        Node leaf2 = new Node(7, null);
        Node leaf3 = new Node(8, null);
        Node leaf4 = new Node(9, null);
        Node leaf5 = new Node(10, null);

        Node inner5 = new Node(6, new Node[]{leaf3, leaf4, leaf5});
        Node inner4 = new Node(5, new Node[]{leaf2});
        Node inner3 = new Node(3, null);
        Node inner2 = new Node(2, new Node[]{inner4, inner5});
        Node inner1 = new Node(1, new Node[]{leaf1});
        Node root = new Node(0, new Node[]{inner1, inner2, inner3});

        printTree(root);

    }

    public static void printTree(Node root)
    {
        LinkedList<Node> current = new LinkedList<>();

        if(root == null)
            return;

        current.add(root);

        while(current.size() > 0)
        {
            printLevel(current);
            LinkedList<Node> parents = current;
            current = new LinkedList<>();

            for(Node parent : parents)
            {
                if( parent.children != null)
                {
                    for (Node c : parent.children)
                    {
                        current.add(c);
                    }
                }
            }
        }
    }

    public static void printLevel( LinkedList<Node> level)
    {
        if(level.size() <= 0)
        {
            return;
        }

        StringBuilder str = new StringBuilder();
        for(Node c : level)
        {
            if (str.length() > 0)
            {
                str.append(", ");
            }
            str.append(c.data);
        }
        System.out.println(str);
    }

}

- ryangurney December 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Also, you could also do this using a single queue with two counters, which would be more efficient. In this case you would only have a space complexity of O(n).

- ryangurney December 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

var i, j, k : Int
let numberOfRows = 4

for (i = 1; i <= numberOfRows; i++) {
    j=1
    while (j <= i)
    {
        print("\(k) ");
        ++k;
        j++
    }
    print("\n");

}

- Anonymous January 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

var i, j, k : Int 
 let numberOfRows = 4
for (i = 1; i <= numberOfRows; i++) {
    j=1
    while (j <= i)
    {
        print("\(k) ");
        ++k;
        j++
    }
    
    print("\n");
}

- Partha January 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void printTreeWithDepth( Tree root){
List<Tree> treeList = new ArrayList<Tree>();
Queue<Tree> queue = new LinkedList<Tree>();
queue.add(root);
System.out.print(root.value);
while(!queue.isEmpty()){
Tree tempNode= queue.poll();
Tree unprintedNode = null;
while((unprintedNode =getUnPrintedTreeNode(tempNode, treeList))!= null){
System.out.print(unprintedNode.value+" ");
treeList.add(unprintedNode);
queue.add(unprintedNode);
}
}
}
Tree getUnPrintedTreeNode(Tree node, List<Tree> treeList){
for(Tree n :node.nodes)
if(!treeList.contains(n)){
return n;
}
return null;
}

- Anonymous August 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void printTreeWithDepth( Tree root){
		List<Tree> treeList = new ArrayList<Tree>();
	  Queue<Tree> queue = new LinkedList<Tree>();
	  queue.add(root);
		 System.out.print(root.value); 
	  while(!queue.isEmpty()){
		 Tree tempNode= queue.poll();
		  Tree unprintedNode = null;
		  while((unprintedNode =getUnPrintedTreeNode(tempNode, treeList))!= null){
			 System.out.print(unprintedNode.value+" "); 
			 treeList.add(unprintedNode);
			 queue.add(unprintedNode);
		  }
	  }		
	}
	Tree getUnPrintedTreeNode(Tree node, List<Tree> treeList){
		for(Tree n :node.nodes)
			if(!treeList.contains(n)){
				return n;
			}
		return null;
	}

- Ravi August 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void printTreeWithDepth( Tree root){
		List<Tree> treeList = new ArrayList<Tree>();
	  Queue<Tree> queue = new LinkedList<Tree>();
	  queue.add(root);
		 System.out.print(root.value); 
	  while(!queue.isEmpty()){
		 Tree tempNode= queue.poll();
		  Tree unprintedNode = null;
		  while((unprintedNode =getUnPrintedTreeNode(tempNode, treeList))!= null){
			 System.out.print(unprintedNode.value+" "); 
			 treeList.add(unprintedNode);
			 queue.add(unprintedNode);
		  }
	  }		
	}
	Tree getUnPrintedTreeNode(Tree node, List<Tree> treeList){
		for(Tree n :node.nodes)
			if(!treeList.contains(n)){
				return n;
			}
		return null;

}

- Ravi August 05, 2016 | 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