Interview Question


Country: United States




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

I don't think this can be done. If you need to preserve Ancestry and each interior node other than 1 exception has 0 or N elements, then it can't be done.

See this example. Original tree:

_____1
____/__\
__2_____3
_/__\___/__\
4___5_6___7

If N were 3, then there is no logical way that you could reorder the tree to have only 0 or 3 children of each node (except for the single exception node) and to preserve ancestry.

Likewise, if the tree were:

________1
_____/___|____\
__2_____3_______4
_/_|_\__/_|_\____/__|__\
5_6_7_8_9_10_11_12_13

And N were 2, there is no way to reorganize the tree such that Ancestry is preserved. You'd have to add extra ancestors in the structural reordering. The tree would have to be something really deformed too like

_______1
_____/____\
____2_______3
___/__\_____/__\
__5___4___8___9
____/___\_______\
___6____7______10
_/___\____\
11__12___13

which is still invalid.

- zortlord July 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using BFS collect all nodes in queue using BFS;

Travers initial tree using iterQ;
Traverse result tree nodes to append childrens using nextQ;

Here is I am not using getters and setters
I haven't compiled code; i hope it works :)

class Resolve<T> {
	Queue<T> iterQ = new LinkedList<>();
	Queue<T> nextQ = new LinkedList<>();

	private class Node {
 		T item;
		List<Node> children;

		public Node(T i, int ch) {
		item = i;
		children = new ArrayList<Node>(ch)l
		}
        }	

	public Node buildNAryTree(Node root, int N) {
		Node resNode = new Node(root.item, N);
		if (N == 0) {
			return resNode;
		}
		Node curr = root;
		Node nextGenRoot = resNode;
		while (curr != null) {
			Node nextGenCurr = new Node(curr.item, N);
			nextQ.offer(nextGenCurr);
			nextGenRoot.children.add(nextGenCurr);

			if (nextGenRoot.children.size() == N) {
				nextGenRoot = nextQ.poll();
			}
			for(Node n: curr.children) {
				iterQ.offer(n)
			}
			curr = iterQ.poll();
		}	
		
	}

	public static void main (args [] input) {
		Resolve<Integer> rr = new Resolve<Integer>();
		....
		// build tree Node rootOfTree
		....
		Node rootOfNewTree = rr.buildNAryTree(rootOfTree);
		
		// let say output
	}
}

- Shmat sala July 30, 2015 | 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