unknown Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

C++ version using recursion. First I sort the elements by parent: O(nlogn). Then I do a binary search O(logn) to find each parent on the list and recursively print it's children.


A (parent id = null)
  B (parent id = A)
    C (parent id = B)
      D (parent id = C)
    H (parent id = B)
  E (parent id = A)
    F (parent id = E)
      G (parent id = F)


#include <iostream>
#include <vector>
#include <algorithm>

template <typename T>
struct node {
    typedef T value_type;
	node(T id, T parent_id) : id_(id), parent_id_(parent_id) { }
	node(T id) : id_(id), parent_id_(0) { }
	T id_;
	T parent_id_;

template <typename T>
std::ostream& operator<<(std::ostream& os, const node<T>& n) {
	os << n.id_ << " (parent id = ";
	if (!n.parent_id_)
		os << "null)";
		os << n.parent_id_ << ")";
	os << std::endl;
	return os;

template <typename T>
struct order_by_parent {
	bool operator()(const node<T>& a, const node<T>& b) {
		// Is it the root?
		if (!a.parent_id_)
			return true;
		// Is  the same parent?
		if (a.parent_id_ == b.parent_id_) {
			// Order by id
			return a.id_ < b.id_;
		// Else, order by parent
		return a.parent_id_ < b.parent_id_;

template <typename T>
struct find_by_parent {
	bool operator()(const node<T>& a, const node<T>& b) {
		return a.parent_id_ < b.parent_id_;

template <typename ForwardIt>
void print_children_tree(ForwardIt begin, ForwardIt end, int indent) {
	// Base case
	if (begin >= end)
    typename ForwardIt::value_type node = *begin;

    // Print node
    for (int i = 0; i < indent; i++)
        std::cout << "  ";
    std::cout << node;
	// Binary search all childrens of this node
    typename ForwardIt::value_type parent(0, node.id_);
	ForwardIt it = std::lower_bound(begin, end, parent, find_by_parent<typename ForwardIt::value_type::value_type>());
	if (it == end) {
        // No children for this node.
	// Print all children
	for (;;) {
		const typename ForwardIt::value_type& curr_n = *it;
		if (curr_n.parent_id_ != node.id_)
		// Recurse
		print_children_tree(it++, end, indent + 1);

template <typename ForwardIt>
void print_tree(ForwardIt begin, ForwardIt end) {
	// Print children
	print_children_tree(begin, end, 1);

int main() {
	// Create the nodes
	std::vector<node<char>> nodes{{'A'}, {'B', 'A'}, {'C', 'B'}, {'D', 'C'},
        {'H', 'B'}, {'E', 'A'}, {'F', 'E'},
        {'G', 'F'}};
	// Sort all nodes by parent
	std::sort(nodes.begin(), nodes.end(), order_by_parent<char>());
	// Print all the nodes
	print_tree(nodes.begin(), nodes.end());

- Diego Giagio November 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
of 0 votes

I edited the question to show the white spaces in the sample input. Its like a tree and we need to print it out in the format as specified in the question

- anonymous November 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
of 0 votes

I edited the answer after better explanation of the question.

- Diego Giagio November 27, 2013 | Flag

Add a Comment

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.


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


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