## Qualcomm Interview Question

Country: India

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

using a queue, construct the tree level by level. Each queue node stores the start, end index in the in order and preorder lists.

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

Explain?

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

Jack Williams posts again

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

it is subbu punk

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

void inOrder (Tree *current) {

while (current) {
if (current->left) {
push (current);
current = current->left;
} else {
print (current);
while (current && current->right == NULL)
current = pop ();

current = current->right;
}
}

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

Thank you. Come again.

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

This is actually an interesting question.

Using the Inorder, given a and b, we can determine whether a > b or a < b, say by using a hastable and recording the index. We won't code that up and assume we are given the compare function.

(I am assuming all distinct).

Now given the preorder, we try to construct the tree, and insert the new value into the appropriate location.

We maintain a stack. If the new value to be entered is smaller than the value at the top of the stack, the it becomes the left child.

If it is greater, we keep popping until we find a suitable parent.

Here is some quick C++.

``````// Inorder is implicit.
Tree *FromPreorderInorder(std::vector<int> preorder) {
std::stack<Tree *> nodes;
Tree *root = new Tree(preorder[0]);
nodes.push(root);
for (int i = 1; i < preorder.size(); i++) {
int val = preorder[i];
Tree *top = nodes.top();
// Left child.
if (val < top->Value) {
top->Left = new Tree(val);
nodes.push(top->Left);
continue;
}

// Right child of some node.
// Find it.
Tree *parent = NULL;
while (val > top->Value) {
parent = top;
nodes.pop();
if (nodes.empty()) break;
top = nodes.top();
}
parent->Right = new Tree(val);
nodes.push(parent->Right);
}
return root;
}``````

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

typedef struct Node_tag {
int value;
struct Node_tag* left;
struct Node_tag* right;
} Node;

int SearchNodeinOrder(int value, int* inorder, int left, int right)
{
while (left <= right)
{
int middle = (left + right) / 2;
if (inorder[middle] == value) return middle;
else if (inorder[middle] < value) left = middle+1;
else right = middle-1;
}

return -1;
}

Node* BuildBST(int* inorder, int* preorder, int size)
{
int cur;
int alloc_cur = 0;

typedef struct {
int left_in;
int right_in;
int left_pre;
int right_pre;
Node* parent;
int isLeft;
} TREE_STACK_ENTRY;

Node* r = NULL;
Node* tmp = (Node*)malloc(sizeof(Node)*size);
TREE_STACK_ENTRY* s = (TREE_STACK_ENTRY*) malloc(sizeof(TREE_STACK_ENTRY* size));
if (!s || !tmp)
{
if (s) free(s);
if (tmp) free(tmp);
return NULL;
}

memset(s, 0, sizeof(TREE_STACK_ENTRY)*size);

s[0].left_in = s[0].left_pre = 0;
s[0].right_in = s[0].right_pre = size-1;
s[0].parent = NULL;
s[0].isLeft = 1;
cur = 1;

while (cur)
{
Node* n;
int pos;
TREE_STACK_ENTRY e = s[cur-1];
cur--;

n = &tmp[alloc_cur++];
n->value = preorder[e.left_pre];

if (e.left_in != e.right_in)
{
pos = SearchNodeinOrder(n->value, inorder, e.left_in, e.right_in);
if (e.left_in < pos)
{
s[cur].left_in = e.left_in;
s[cur].right_in = pos-1;
s[cur].left_pre = e.left_pre + 1;
s[cur].right_pre = e.left_pre + pos - e.left_in;
s[cur].parent = n;
s[cur].isLeft = 1;
cur++;
}
if (pos < e.right_in)
{
s[cur].left_in = pos+1;
s[cur].right_in = e.right_in;
s[cur].left_pre = e.left_pre + 1 + pos - e.left_in;
s[cur].right_pre = e.right_pre;
s[cur].parent = n;
s[cur].isLeft = 0;
cur++;
}
}
if (n->parent)
{
if (n->isLeft) n->parent->left = n;
else n->parent->right = n;
}
else r = n;
}
free(s);
return r;
}

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

a!o! forget to handle the -1 search result.

typedef struct Node_tag {
int value;
struct Node_tag* left;
struct Node_tag* right;
} Node;

int SearchNodeinOrder(int value, int* inorder, int left, int right)
{
while (left <= right)
{
int middle = (left + right) / 2;
if (inorder[middle] == value) return middle;
else if (inorder[middle] < value) left = middle+1;
else right = middle-1;
}

return -1;
}

Node* BuildBST(int* inorder, int* preorder, int size)
{
int cur;
int alloc_cur = 0;

typedef struct {
int left_in;
int right_in;
int left_pre;
int right_pre;
Node* parent;
int isLeft;
} TREE_STACK_ENTRY;

Node* r = NULL;
Node* tmp = (Node*)malloc(sizeof(Node)*size);
TREE_STACK_ENTRY* s = (TREE_STACK_ENTRY*) malloc(sizeof(TREE_STACK_ENTRY* size));
if (!s || !tmp)
{
if (s) free(s);
if (tmp) free(tmp);
return NULL;
}

memset(s, 0, sizeof(TREE_STACK_ENTRY)*size);

s[0].left_in = s[0].left_pre = 0;
s[0].right_in = s[0].right_pre = size-1;
s[0].parent = NULL;
s[0].isLeft = 1;
cur = 1;

while (cur)
{
Node* n;
int pos;
TREE_STACK_ENTRY e = s[cur-1];
cur--;

n = &tmp[alloc_cur++];
n->value = preorder[e.left_pre];

if (e.left_in != e.right_in)
{
pos = SearchNodeinOrder(n->value, inorder, e.left_in, e.right_in);

if (pos == -1)
{
free(s);
free(tmp;
return NULL;
}
if (e.left_in < pos)
{
s[cur].left_in = e.left_in;
s[cur].right_in = pos-1;
s[cur].left_pre = e.left_pre + 1;
s[cur].right_pre = e.left_pre + pos - e.left_in;
s[cur].parent = n;
s[cur].isLeft = 1;
cur++;
}
if (pos < e.right_in)
{
s[cur].left_in = pos+1;
s[cur].right_in = e.right_in;
s[cur].left_pre = e.left_pre + 1 + pos - e.left_in;
s[cur].right_pre = e.right_pre;
s[cur].parent = n;
s[cur].isLeft = 0;
cur++;
}
}
if (n->parent)
{
if (n->isLeft) n->parent->left = n;
else n->parent->right = n;
}
else r = n;
}
free(s);
return r;
}

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

Do it recursively. Assume the lists are arrays.

Pseudocode:

``````fn tree(inorder, postorder){
if array length is 1, return new node with the only value (termination condition)

find position of postorder[0] in inorder

split inorder there into inorder_left, inorder_right (leaving out the number at postorder[0])

find position of the last value in inorder_left in postorder

split postorder at the position after that (again, leave out the first number)

new node with value postorder[0]
node.left = tree(inorder_left, postorder_left)
node.right = tree(inorder_right, postorder_right)

return node
}``````

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

Didn't read the question properly. OOps. This is if recursive were allowed.

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.