Amazon Interview Question for Production Engineers

• 0
of 0 votes

Team: kindle
Country: India
Interview Type: In-Person

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

``````//suppose Map is a <int,int> map that accepts negative numbers as keys
//col is initialized in 0
void verticalSum(Node n,Map map,int col){
if( n == null) return;
int temp = map.get(col);
map.put(col,temp + n->value);
verticalSum(n->left,map,col++);
verticalSum(n->right,map,col--);

}

// the results will be stored in the map``````

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

{{
static List<node1> listofnodes=new ArrayList<node1>();
void verticalSum(node1 p)
{
int verticalsum=0;
List<Integer> vertcalnodes =new ArrayList<Integer>();
if(listofnodes.contains(p)==false)
{
if(p!=null)
{
vertcalnodes.add(p.val);
if(p.left!=null)
{
node1 q=p.left;
boolean b=false;
while(q.right!=null)
{
q=q.right;
b=true;
}
if(b==true)
{
verticalsum+=q.val;
listofnodes.add(q);
vertcalnodes.add(q.val);
}
}
if(p.right!=null)
{
node1 q=p.right;
boolean b=false;
while(q.left!=null)
{
q=q.left;
b=true;
}
if(b==true)
{
verticalsum+=q.val;
listofnodes.add(q);
vertcalnodes.add(q.val);
}
}
verticalsum+=p.val;
System.out.println("Vertcal val for node :"+vertcalnodes+"is ="+verticalsum);
verticalSum(p.left);
verticalSum(p.right);
}
}
}
}}

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

@above explain the logic bro ?

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

@above explain the logic bro ?

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

i am just checking left or right child is there for the perticuler node or not.if its present then i am traversing to its at most oposite direction.
if(p.left!=null)
{//checking left child present or not
node1 q=p.left;
boolean b=false;
while(q.right!=null)
{//traversing to at most right successor
q=q.right;
b=true;
}
if(b==true)
{
/*if the right successor is present then i am just taking the sum and adding those node in the arraylist (listofnodes) to keep the previous recordand we are
adding vertical nodes(vertcalnodes.add(q.val);) only for showing those nodes for which we are going to calculate the vertical sum for that perticuler recursive call*/
verticalsum+=q.val;
listofnodes.add(q);
vertcalnodes.add(q.val);
}
}
/*and here listofnodes is used to see that the paerticuler node has been travased previously or not*/

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

``````public class BinaryTree {
private static class Node {
int key;
Node left;
Node right;
}
private Node root;
// Find left most dist
private int leftHorizontalDist() {
int dist = 0;
Node node = root;
while (node != null) {
++dist;
node = node.left;
}
return dist;
}
// Find right most dist
private int rightHorizontalDist() {
int dist = 0;
Node node = root;
while (node != null) {
++dist;
node = node.right;
}
return dist;
}
// index - horizontal dist of the node relative to the left most node.
private void fillVerticalDist(Node node, int index, int[] dist) {
if (node == null) {
return;
}
dist[index] += node.key;
fillVerticalDist(node.left, index - 1, dist);
fillVerticalDist(node.right, index + 1, dist);
}
public int[] getVerticalDist() {
if (root == null) {
return null;
}
int leftDist = leftHorizontalDist();
int rightDist = rightHorizontalDist();
int dist[] = new int[leftDist + rightDist + 1];
fillVerticalDist(root, leftDist, dist);
return dist;
}
}``````

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

It should work

``````void print_vert_sum(treeptr head) {
if(!head)
return;
if(head->leftchild)
printf("%d ", leftmost(head->leftchild));
move_inorder(head);
if(head->rightchild)
printf("%d ", rightmost(head));
}

void move_inorder(treeptr ptr) {
if(ptr) {
move_inorder(ptr->leftchild);
if(ptr->leftchild || ptr->rightchild)
vertical_sum(ptr);
move_inorder(ptr->rightchild);
}
}

int leftmost(treeptr ptr) {
while(ptr->leftchild)
ptr = ptr->leftchild;
return ptr->data;
}

int rightmost(treeptr ptr) {
while(ptr->rightchild)
ptr = ptr->rightchild;
return ptr->data;
}

void vertical_sum(treeptr ptr) {
int left = left_rightmost(ptr->leftchild);
int right = right_leftmost(ptr->rightchild);
printf("%d ", ptr->data + left + right);
}

int left_rightmost(treeptr ptr) {
if(!(ptr && ptr->rightchild))
return 0;
while(ptr->rightchild)
ptr = ptr->rightchild;
return ptr->data;
}

int right_leftmost(treeptr ptr) {
if(!(ptr && ptr->leftchild))
return 0;
while(ptr->leftchild)
ptr = ptr->leftchild;
return ptr->data;
}``````

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

Sorry, I can't catch the meaning.
who can help to explain how to get the vertical sum?
"vertical sum is 04 02 12 03 07"

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