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.

- Jason November 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Explain?

- Anonymous November 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Jack Williams posts again

- undefined November 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it is subbu punk

- Anonymous November 04, 2013 | Flag
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;
}
}

- Shekhar November 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Pls be reading question again.

Thank you. Come again.

- Anonymous November 07, 2013 | Flag
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;
}

- Anonymous November 12, 2013 | Flag Reply
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;
}

- Anonymous August 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous August 27, 2014 | Flag
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
}

- Anonymous December 06, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous December 06, 2018 | Flag


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