Amazon Interview Question for SDE1s


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[1] == null ? '' : $.children[1].s_rep()
    l_str = $.children[0] == null ? '' : $.children[0].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 ) )

- NoOne August 23, 2017 | Flag Reply
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.

- Arpit August 23, 2017 | Flag Reply
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"

- tnutty2k8 August 24, 2017 | Flag Reply
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.

Your best best is to step through code if you want to learn more or ask specific question.

Best.

- tnutty2k8 August 26, 2017 | Flag Reply
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

- agrawal.arpit35 August 26, 2017 | Flag Reply
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.

- hasan.iqbal.anik October 23, 2017 | Flag Reply
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;
}

- Alex November 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

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

- agrawal.arpit35 August 25, 2017 | Flag Reply


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