## Amazon Interview Question for SDE1s

• 0

Country: India
Interview Type: Phone Interview

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

A pretty neat way is the recursive formulation as such:

``````def Node{
def \$\$(value, l=null, r=null){
\$.value = value
\$.children = [l,r]
}
def s_rep(){ // for string format
r_str = \$.children == null ? '' : \$.children.s_rep()
l_str = \$.children == null ? '' : \$.children.s_rep()
str( '(%s %s %s)', l_str, \$.value, r_str )
}
}
// call it off
ll = new ( Node , 10 )
lr = new ( Node , 30 )
l = new ( Node , 100 ,ll, lr )
r = new ( Node , 130 )
root = new ( Node , 42 , l , r ) // root node
println( root.s_rep() )``````

Which produces :

``((( 10 ) 100 ( 30 )) 42 ( 130 ))``

From this, it is very easy to parse back into the tree.
The recursive formula of a any tree in this form is :

``( ( left_sub_tree_rep )  my_value ( right_sub_tree_rep ) )``

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

Can you please tell your approach, what exactly you are trying to do.

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

Just sample, albiet not the cleanest implementation:

``JSBin: jsbin.com/habamet/2/edit?js,console``

``````function Node(val, left, right) {
this.val = val;
this.left = left;
this.right = right;
}

var root = new Node(
1,
new Node(2, new Node(3, null, new Node(4)) ),
new Node(5, new Node(6) )
);

function printTree(node) {
if (node) {
var left = printTree(node.left);
var mid = [node.val];
var right = printTree(node.right);
return mid.concat(left).concat(right);
}else return [];
}

function serializeTree(node) {
if (node) {
var s0 = node.val;
var left = serializeTree(node.left);
var right = serializeTree(node.right)
var s1 = left.length ? '(' + left + ')' : '';
var s2 = right.length ? '(' + right + ')' : '';
var s = s1.length || s2.length ? '(' + s0 + s1 + s2 + ')' : '' +s0;
return s;
}else {
return '';
}
}

function deserializeTree(serialized) {
if (!serialized.length) {
return null;
}else {
var token = parse(serialized);
//console.log(token);
var left = deserializeTree(token.left);
var right = deserializeTree(token.right);
var node = new Node(token.val, left, right);
return node;
}
}
function parse(serialized) {
function getToken(s, offset) {
if (!s.length || s[offset] !== '(') return '';
var count = 0;
var r = '';
for(var i = offset; i < serialized.length; ++i) {
var c = serialized[i];

if (c === '(') ++count;
else if (c === ')') --count;

r+= c;

if (count <= 0) break;
}
offset = i;
return r;
}
var offset = serialized.match(/\d/).index;
var val = serialized[offset];
var left = getToken(serialized, offset + 1);
var right = getToken(serialized, offset + 1 + left.length );
return {val: val, left: left, right: right};
}

var serialized = serializeTree(root);
console.log('serialized: ' + serialized );

var copyNode = deserializeTree( serialized );
console.log( 'deserialized: ' + printTree(copyNode) );``````

Output:

``````"serialized: (1((2((3(4)))))((5(6))))"
"deserialized: 1,2,3,4,5,6"``````

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

@agrawal so bossy :P

Just kidding anyways I was hoping the code was clear enough. The idea is to go to each node and serialize the node with its left subtree or right subtree. For example with the current tree

``````2
1  3``````

the serialize algo transverse each node and wraps its pharenthesis with its children, for example in the above tree when we are at node with value 2, we do

``"(2 leftSubtree rightSubtree)``

, where leftSubTree is serialized result of node with value 1 and rightSubtree is the serialized result of node with value 3, which at end will all result in

``(2 (1)(3) )``

To deserialize we simple parse the token into three parts [ nodeValue, leftSubtreeToken, rightSubtreeToken] then we deserialize leftSubtreeToken and rightSubtreeToken and use that result as left/right children for the current node. For example with the above serialized token parsing at first iterations would result in [2, "(1)", "(3)"]. Now current node value is 2, and we pass (1) to the same deserialize function and use that result as the left tree and similar for right tree.

Best.

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

a
/\
c d
/\ /\
a d c b

can you explain this example

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

Traverse the tree in postorder and inorder. It's possible to reconstruct a tree given it's post and inorder traversal.

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

``````void Serialize(Node const *n, vector<int> &out)
{
if (n == NULL) {
out.push_back(numeric_limits<int>::min());
return;
}
out.push_back(n->val_);
Serialize(n->left_, out);
Serialize(n->right_, out);
}

Node *Deserialize(vector<int> const &in, int &idx)
{
if (idx >= in.size() ||
in[idx] == numeric_limits<int>::min())
{
++idx;
return NULL;
}
Node *n = new Node(in[idx++]);
n->left_ = Deserialize(in, idx);
n->right_ = Deserialize(in, idx);
return n;
}``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

Exaplain your approach too, I didn't want only code.

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.