## unknown Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
0
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.

Output:

``````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)``````

Code:

``````#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)";
else
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)
return;

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

// Print all children
for (;;) {
const typename ForwardIt::value_type& curr_n = *it;
if (curr_n.parent_id_ != node.id_)
break;

// 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());
}``````

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

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

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

I edited the answer after better explanation of the question.

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.

### 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.