CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Amazon Interview Question for SDE-2s


Country: United States
Interview Type: In-Person
More Questions from This Interview



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

// package whatever; // don't place package name!

import java.io.*;  
import java.util.*;
import java.lang.*;

class myCode
{
    static class TreeNode{
        int val;
        TreeNode left,right;
        TreeNode(int val){
            this.val = val;
        }
    }
    public static void main (String[] args) throws java.lang.Exception
    {
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(1);
        root.right = new TreeNode(2);
        TreeNode node1 = new TreeNode(3);
        root.left.right=node1;
        
        root.right.left = new TreeNode(4);
        TreeNode node2 = new TreeNode(5);
        
        root.right.left.left = node2;
        
        System.out.println(numRouteChange(node1,node2,root));
    }
    
    public static int numRouteChange(TreeNode node1,TreeNode node2,TreeNode root){
        TreeNode parent= findParent(node1,node2,root);
        int num1 = numRouteChangeHelper(parent,node1,null,0);
        int num2 = numRouteChangeHelper(parent,node2,null,0);
        
        return num1+num2+1;
    }
    
    public static int numRouteChangeHelper(TreeNode parent,TreeNode node,String pre_dir,int change){
        if(parent == null){
            return -1;
        }
        if(parent==node){
            return change;
        }
        int count = -1;
        if(pre_dir == null || pre_dir.equals("left")){
            count = numRouteChangeHelper(parent.left,node,"left",change);
        }else if(pre_dir.equals("right")){
            count = numRouteChangeHelper(parent.left,node,"left",change+1);
        }
        if(count>=0){
            return count;
        }
        
        if(pre_dir == null || pre_dir.equals("right")){
            count = numRouteChangeHelper(parent.right,node,"right",change);
        }else if(pre_dir.equals("left")){
            count = numRouteChangeHelper(parent.right,node,"right",change+1);
        }
        
        return count;
    }
    
    public static TreeNode findParent(TreeNode node1,TreeNode node2,TreeNode root){
        if(root == null){
            return null;
        }
        
        if(root==node1 || root==node2){
            return root==node1?node1:node2;
        }
        
        TreeNode left = findParent(node1,node2,root.left);
        TreeNode right = findParent(node1,node2,root.right);
        if(left!=null && right!=null){
            return root;
        }
        return left==null?right:left;
    }
}

- Anonymous August 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// package whatever; // don't place package name!

import java.io.*;  
import java.util.*;
import java.lang.*;

class myCode
{
    static class TreeNode{
        int val;
        TreeNode left,right;
        TreeNode(int val){
            this.val = val;
        }
    }
    public static void main (String[] args) throws java.lang.Exception
    {
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(1);
        root.right = new TreeNode(2);
        TreeNode node1 = new TreeNode(3);
        root.left.right=node1;
        
        root.right.left = new TreeNode(4);
        TreeNode node2 = new TreeNode(5);
        
        root.right.left.left = node2;
        
        System.out.println(numRouteChange(node1,node2,root));
    }
    
    public static int numRouteChange(TreeNode node1,TreeNode node2,TreeNode root){
        TreeNode parent= findParent(node1,node2,root);
        int num1 = numRouteChangeHelper(parent,node1,null,0);
        int num2 = numRouteChangeHelper(parent,node2,null,0);
        
        return num1+num2+1;
    }
    
    public static int numRouteChangeHelper(TreeNode parent,TreeNode node,String pre_dir,int change){
        if(parent == null){
            return -1;
        }
        if(parent==node){
            return change;
        }
        int count = -1;
        if(pre_dir == null || pre_dir.equals("left")){
            count = numRouteChangeHelper(parent.left,node,"left",change);
        }else if(pre_dir.equals("right")){
            count = numRouteChangeHelper(parent.left,node,"left",change+1);
        }
        if(count>=0){
            return count;
        }
        
        if(pre_dir == null || pre_dir.equals("right")){
            count = numRouteChangeHelper(parent.right,node,"right",change);
        }else if(pre_dir.equals("left")){
            count = numRouteChangeHelper(parent.right,node,"right",change+1);
        }
        
        return count;
    }
    
    public static TreeNode findParent(TreeNode node1,TreeNode node2,TreeNode root){
        if(root == null){
            return null;
        }
        
        if(root==node1 || root==node2){
            return root==node1?node1:node2;
        }
        
        TreeNode left = findParent(node1,node2,root.left);
        TreeNode right = findParent(node1,node2,root.right);
        if(left!=null && right!=null){
            return root;
        }
        return left==null?right:left;
    }
}

- tiandiao123 August 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.home.careercup;
/**
 * The problem essentially boils down to finding the lowest common ancestor (LCA)
 * node. Now we need to find the number of turns on the path leading from
 * one node to the LCA and then to the other node. Note, there is  a possibility
 * that the LCA node for a pair of nodes can be one among the pair itself
 */

import java.util.*;

/*

        _______3______
           /                        \
    ___5__               ___1__
   /            \             /             \
   6           2            0            8
              /    \
              7   4


*/
public class FindTurnsOnPathBetweenTwoNodes {
    final Node root = Node.of(3);

    public static void main(String[] args) {
        FindTurnsOnPathBetweenTwoNodes g = new FindTurnsOnPathBetweenTwoNodes();
        int turns = g.turns(Node.of(6), Node.of(7));
        System.out.println("turns =" + turns);
    }


    int turns(Node a, Node b) {

        List<Edge> an = findPath(root, a);
        List<Edge> bn = findPath(root, b);

        ListIterator<Edge> ai = an.listIterator();
        ListIterator<Edge> bi = bn.listIterator();

        while (ai.hasNext() && bi.hasNext()) {
            Edge t1 = ai.next();
            Edge t2 = bi.next();
            if (t1.equals(t2)) {
                ai.remove();
                bi.remove();
            } else {
                ai.previous();
                bi.previous();
                break;
            }
        }
        // construct path ( node list)
        List<Node> path = new ArrayList<>();
        for (int i = 0; i < an.size(); i++) {
            path.add(an.get(i).start);
            if (i == an.size() - 1)
                path.add(an.get(i).end);
        }
        Collections.reverse(path);
        for (int i = 1; i < bn.size(); i++) {
            path.add(bn.get(i).start);
            if (i == bn.size() - 1)
                path.add(bn.get(i).end);
        }
        //print path
        for (Node n : path) {
            System.out.println(n.v);
        }

        Edge.Direction earlier = Edge.Direction.NONE;
        int turns = 0;

        while (ai.hasNext() || bi.hasNext()) {
            Iterator<Edge> itr = ai.hasNext() ? ai : bi;
            if (!itr.hasNext()) break;
            Edge e = itr.next();
            turns = e.d == earlier ? turns : ++turns;
            earlier = e.d;
        }
        return --turns; /* disregard first turn */


    }
// return mock paths for this example

    private List<Edge> findPath(Node root, Node b) {
        if (root.v == 3 && b.v == 6)
            return new ArrayList<>(Arrays.asList(Edge.of(3, 5, Edge.Direction.LEFT),
                    Edge.of(5, 6, Edge.Direction.LEFT)));
        if (root.v == 3 && b.v == 7)
            return new ArrayList<>(Arrays.asList(
                    Edge.of(3, 5, Edge.Direction.LEFT),
                    Edge.of(5, 2, Edge.Direction.RIGHT),
                    Edge.of(2, 7, Edge.Direction.LEFT)

            ));
        return Collections.emptyList();
    }

    // boiler plate Node and Edge declarations
    static class Node {
        Node(int v) {
            this.v = v;
        }

        static Node of(int v) {
            return new Node(v);
        }

        @Override
        public boolean equals(Object obj) {
            Node other = (Node) obj;
            return this.v == other.v;
        }

        int v;
        Node left, right;

    }

    static class Edge {
        enum Direction {LEFT, RIGHT, NONE}

        Node start, end;
        Direction d;

        static Edge of(int start, int end, Direction d) {
            Edge e = new Edge();
            e.start = Node.of(start);
            e.end = Node.of(end);
            e.d = d;
            return e;
        }

        @Override
        public boolean equals(Object obj) {
            Edge other = (Edge) obj;
            return other.start.equals(this.start) &&
                    other.end.equals(this.end) &&
                    other.d == this.d;
        }
    }
}

- Makarand August 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

using System;

// To execute C#, please define "static void Main" on a class
// named Solution.

// ----------------------------------------------------------------------
class Solution
{
    
    // ------------------------------------------------------------------
    class Node
    {
        public int Value;
        public Node Left;
        public Node Right;
        public Node( int value ) { Value = value; }
    };
    
    // ------------------------------------------------------------------
    static void Main(string[] args)
    {
        
        int numNodes;
        Node root = buildTree( out numNodes );
        for (int i = 0; i < numNodes + 1; ++i)
        {
            runTest( root, i + 1 );
        }
        
    }
    
    // ------------------------------------------------------------------
    static void runTest( Node root, int value )
    {
        
        Console.WriteLine( "\nRunning test, searching for '{0}'", value );
        int numLeft = 0;
        int numRight = 0;
        bool found = findPath( root, value, ref numLeft, ref numRight );
        if (found)
        {
            bool isStraight = numLeft == 0 || numRight == 0;
            Console.WriteLine( "Value {0} found tree. Straight Path: {1}, Left Turns: {2}, Right Turns: {3}", 
                               value, isStraight ? "Yes" : "No", numLeft, numRight );
        }
        else
        {
            Console.WriteLine( "Value {0} was not found in the tree", value );
        }
        
    }
    
    // ------------------------------------------------------------------
    static bool findPath( Node node, int value, ref int numLeft, ref int numRight )
    {
        if (node == null)
        {
            return false;
        }
        if (node.Value == value)
        {
            return true;
        }
        if (findPath( node.Left, value, ref numLeft, ref numRight ))
        {
            numLeft++;
            return true;
        }
        else if (findPath( node.Right, value, ref numLeft, ref numRight ))
        {
            numRight++;
            return true;
        }
        return false;
    }
    
    // ------------------------------------------------------------------
    static Node buildTree( out int numNodes )
    {
        //                        1
        //               /               \
        //           2                      3 
        //        /      \              /       \
        //      4         5           6          7
        //     / \       / \        /  \        /  \
        //    8   9    10   11    12    13    14    15
        numNodes = 0;
        Node one = new Node( ++numNodes );
        Node two = new Node( ++numNodes );
        Node three = new Node( ++numNodes );
        one.Left = two;
        one.Right = three;
        Node four = new Node( ++numNodes );
        Node five = new Node( ++numNodes );
        two.Left = four;
        two.Right = five;
        Node six = new Node( ++numNodes );
        Node seven = new Node( ++numNodes );
        three.Left = six;
        three.Right = seven;
        Node eight = new Node( ++numNodes );
        Node nine = new Node( ++numNodes );
        four.Left = eight;
        four.Right = nine;
        Node ten = new Node( ++numNodes );
        Node eleven = new Node( ++numNodes );
        five.Left = ten;
        five.Right = eleven;
        Node twelve = new Node( ++numNodes );
        Node thirteen = new Node( ++numNodes );
        six.Left = twelve;
        six.Right = thirteen;
        Node fourteen = new Node( ++numNodes );
        Node fifteen = new Node( ++numNodes );
        seven.Left = fourteen;
        seven.Right = fifteen;
        return one;
    }
    
}

- Anonymous August 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Tree {
	
	static int getTurn(Node n1,Node n2){
		int turnleft = getTurnHelper(n1.left,n2,true,false,0);
		int turnright = getTurnHelper(n1.right,n2,false,true,0);
		if(turnleft == -1 && turnright==-1)
			return -1;
		else if(turnleft >=0)
			return turnleft;
		else
			return turnright;
	}
	
	static int getTurnHelper(Node n1,Node n2,boolean left,boolean right,int turn){
		if(n1==null)
			return -1;
		if(n1==n2)
			return turn;
		boolean isLeft = left;
		boolean isRight = right;
		
		int turnleft = getTurnHelper(n1.left,n2,left?left:!left,right?!right:right,left?turn:turn+1);
		int turnright = getTurnHelper(n1.right,n2,left?!left:left,right?right:!right,right?turn:turn+1);
		if(turnleft == -1 && turnright==-1)
			return -1;
		else if(turnleft >=0)
			return turnleft;
		else
			return turnright;
	}
	

	public static void main(String args[]){
		Node node8 = new Node(8);
		Node node2 = new Node(2);
		Node node10 = new Node(10);
		Node node1 = new Node(1);
		Node node13 = new Node(13);
		Node node20 = new Node(20);
		Node node21 = new Node(21);
		Node node6 = new Node(6);
		Node node9 = new Node(9);
		node8.setLeftChild(node2);
		node8.setRightChild(node10);
		node2.setLeftChild(node1);
		node2.setRightChild(node13);
		node13.setLeftChild(node20);
		node13.setRightChild(node21);
		node10.setLeftChild(node6);
		node10.setRightChild(node9);
		System.out.println(getTurn(node8,node20));
		
		
	}
}

- Anonymous October 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <vector>

using namespace std;

class Node {
	public:
		Node(int val)
		{
			val_ = val;
			left_ = right_ = NULL;
		}
		int val_;
		Node *left_, *right_;
};

pair<vector<Node *> *, vector<Node *> *> Path(Node *n, Node *n1, Node *n2, vector<Node *> &path)
{
	if (!n ||
		!n1 ||
		!n2 ||
		n1 == n2 ||
		!path.empty())
	{
		return pair<vector<Node *> *, vector<Node *> *>(NULL, NULL);
	}
	vector<Node *> *p1 = NULL;
	vector<Node *> *p2 = NULL;
	if (n == n1) {
		p1 = new vector<Node *>();
	}
	if (n == n2) {
		p2 = new vector<Node *>();
	}
	if (!p1 ||
		!p2)
	{
		auto l = Path(n->left_, n1, n2, path);
		if (l.first) {
			p1 = l.first;
		}
		if (l.second) {
			p2 = l.second;
		}
	}
	if (!p1 ||
		!p2)
	{
		auto r = Path(n->right_, n1, n2, path);
		if (r.first) {
			p1 = r.first;
		}
		if (r.second) {
			p2 = r.second;
		}
	}
	if (path.empty()) {
		if (p1) {
			p1->push_back(n);
		}
		if (p2) {
			p2->push_back(n);
		}
		if (p1 &&
			p2)
		{
			path = *p1;
			for (int i = p2->size() - 2; i >= 0; --i) {
				path.push_back((*p2)[i]);
			}
		}
	}
	return pair<vector<Node *> *, vector<Node *> *>(p1, p2);
}

int TurnsCount(vector<Node *> const &path)
{
	int count = 0;
	int prev_dir = 0;
	for (int i = 0; i + 1 < path.size(); ++i) {
		Node *n = path[i];
		Node *parent = path[i + 1];
		if (n->left_ == parent ||
			n->right_ == parent)
		{
			swap(n, parent);
		}
		int dir = parent->left_ == n ? 1 : 2;
		if (prev_dir != 0 &&
			prev_dir != dir)
		{
			++count;
		}
		prev_dir = dir;
	}
	return count;
}

int main()
{
/*
      (1)
    /    \
  (2)    (5)
  /\     /\
(3)(4) (6)(7)
         \
         (8)
*/
	Node n1(1), n2(2), n3(3), n4(4), n5(5), n6(6), n7(7), n8(8);
	n1.left_ = &n2;
	n1.right_ = &n5;
	n2.left_ = &n3;
	n2.right_ = &n4;
	n5.left_ = &n6;
	n5.right_ = &n7;
	n6.right_ = &n8;

	vector<Node *> path;
	Path(&n1, &n3, &n8, path);
	cout << TurnsCount(path) << "\n";
	for (auto n : path) {
		cout << n->val_ << "->";
	}
	cout << "\n";
	return 0;
}

- Alex November 17, 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