Amazon Interview Question for SDE-2s


Country: United States
Interview Type: Written Test




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

public static MatrixNode buildLinkedMatrix(int[][] m){
        MatrixNode[][] nodes = new MatrixNode[m.length][m[0].length];
        for (int i = 0; i < m.length; i++){
            for (int j = 0; j < m[0].length; j++){
                MatrixNode matrixNode = new MatrixNode(m[i][j]);
                nodes[i][j] = matrixNode;
                if (j - 1 >= 0){
                    nodes[i][j-1].right = matrixNode;
                }
                if (i-1>= 0){
                    nodes[i-1][j].down = matrixNode;
                }
            }
        }
        return nodes[0][0];

}

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

public static MatrixNode buildLinkedMatrix(int[][] m){
        MatrixNode[][] nodes = new MatrixNode[m.length][m[0].length];
        for (int i = 0; i < m.length; i++){
            for (int j = 0; j < m[0].length; j++){
                MatrixNode matrixNode = new MatrixNode(m[i][j]);
                nodes[i][j] = matrixNode;
                if (j - 1 >= 0){
                    nodes[i][j-1].right = matrixNode;
                }
                if (i-1>= 0){
                    nodes[i-1][j].down = matrixNode;
                }
            }
        }
        return nodes[0][0];
    }

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

your matrix looks right, but it has overheads:
- at recursion [0][0] you create [0][1], which will create [0][1], and [1][1] (among others)
- but at [0][0] you create as well [1][0], which leads to create [1][1] (the second time)
you have elements created multiple times, I guess if you count your LList instances it will be 9 instead of 6

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

I think the return value should be single node* which should be pointing to entry of data[0][0]. As all elements are reachable from there.

Here is my solution in C++

struct node{
    int data;
    node* next;
    node* down;
};
node* getLinkedList(int **data,int M,int N) {
   
    // Create a linked list for first row the normal way.
    node* parentNode = NULL;
    node* currentNode = new node();
    node* head = currentNode;
    
    for(int j = 0 ; j < M; j++) {
        currentNode->data = data[0][j];
        currentNode->next = currentNode->down = NULL;
        if ( parentNode) {
            parentNode->next = currentNode;
        }
        parentNode = currentNode;
    }
    
    // We will keep upper row pointer so that it can be updated with down row pointer.
    node* upperRowHead = head;

    //Iterate on rest of matrix and create list accordingly.
    for(int i = 1 ; i < N; i++) {
        node* currentParentNode = NULL;
        node* currentNode = new node();
        node* currentHead = currentNode;
        for(int j = 0 ; j < M; j++) {
            currentNode->data = data[i][j];
            currentNode->next = currentNode->down = NULL;
            if ( currentParentNode) {
                currentParentNode->next = currentNode;
            }
            currentParentNode = currentNode;
            upperRowHead->down = currentNode;
            upperRowHead = upperRowHead->next;
        }
        upperRowHead = head;
    }
    
    return head;
}

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

Node *create (int d) {
  auto N = new Node;
  N->data = d;
  N->next = N->below = nullptr;
}

Node *matrix2LL(vector<vector<int>> &M) {
  Node *head = nullptr , *first = nullptr, *second = nullptr;
  for (int i = 0; i < M.size() ; i++) {
    Node *N;
    for (int j = 0; j < M.front().size(); j++) {
      if (!second) {
        second = create(M[i][j]);
        if (!head)
          head = second;
        N = second;
      } else {
        N->next = create(M[i][j]);
        N = N->next;
      }
      if (first) {
        first->below = N;
        first = first->next;
      }
    }
    first = second;
    second = nullptr;
  }
  return head;
}

void printMatrix (Node *N) {
  Node *first = N;
  while (true) {
    Node *below = first ? first->below : nullptr;
    while (first) {
      cout << first->data << "  " ;
      first = first->next;
    }
    cout << "\n";
    if (below)
      first = below;
    else
      break;
  }
}

- A. coward August 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node *create (int d) {
  auto N = new Node;
  N->data = d;
  N->next = N->below = nullptr;
}

Node *matrix2LL(vector<vector<int>> &M) {
  Node *head = nullptr , *first = nullptr, *second = nullptr;
  for (int i = 0; i < M.size() ; i++) {
    Node *N;
    for (int j = 0; j < M.front().size(); j++) {
      if (!second) {
        second = create(M[i][j]);
        if (!head)
          head = second;
        N = second;
      } else {
        N->next = create(M[i][j]);
        N = N->next;
      }
      if (first) {
        first->below = N;
        first = first->next;
      }
    }
    first = second;
    second = nullptr;
  }
  return head;
}

void printMatrix (Node *N) {
  Node *first = N;
  while (true) {
    Node *below = first ? first->below : nullptr;
    while (first) {
      cout << first->data << "  " ;
      first = first->next;
    }
    cout << "\n";
    if (below)
      first = below;
    else
      break;
  }
}

- A. coward August 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node *create (int d) {
  auto N = new Node;
  N->data = d;
  N->next = N->below = nullptr;
}

Node *matrix2LL(vector<vector<int>> &M) {
  Node *head = nullptr , *first = nullptr, *second = nullptr;
  for (int i = 0; i < M.size() ; i++) {
    Node *N;
    for (int j = 0; j < M.front().size(); j++) {
      if (!second) {
        second = create(M[i][j]);
        if (!head)
          head = second;
        N = second;
      } else {
        N->next = create(M[i][j]);
        N = N->next;
      }
      if (first) {
        first->below = N;
        first = first->next;
      }
    }
    first = second;
    second = nullptr;
  }
  return head;
}

void printMatrix (Node *N) {
  Node *first = N;
  while (true) {
    Node *below = first ? first->below : nullptr;
    while (first) {
      cout << first->data << "  " ;
      first = first->next;
    }
    cout << "\n";
    if (below)
      first = below;
    else
      break;
  }
}

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

C#

static void Main(string[] args)
        {
            int[,] arrMatrix11 = new int[3, 3]
                                    {
                                        {1, 2, 3},
                                        {4, 5, 6}, 
                                        {7, 8, 9}
                                    };
            ArrayQuestions.Node2DList node2dList11 = ArrayQuestions.Flatten(arrMatrix11);
            node2dList11.Display();
}

        public static Node2DList Flatten(int[,] arr)
        {
            if (arr.GetLength(0) >= 1 && arr.GetLength(1) >= 1)
            {
                Node2DList curr = new Node2DList(arr[0, 0]);
                Flatten(arr, 1, 0, curr, Direction.Right);
                Flatten(arr, 0, 1, curr, Direction.Down);
                return curr;
            }
            else
            {
                return null;
            }
        }

        private static void Flatten(int[,] arr, int i, int j, Node2DList prev, Direction direction)  // todo :: rename i = row and j = col
        {
            Node2DList curr = i <= arr.GetLength(0) - 1 && j <= arr.GetLength(1) - 1
                            ? new Node2DList(arr[i, j])
                            : null;

            if (direction == Direction.Right)
            {
                prev.right = curr;
            }
            else
            {
                prev.down = curr;
            }

            if (null != curr)
            {
                Flatten(arr, i + 1, j, curr, Direction.Right);
                Flatten(arr, i, j + 1, curr, Direction.Down);
            }
        }

        public class Node2DList
        {
            public int val { get; set; }
            public Node2DList right { get; set; }
            public Node2DList down { get; set; }

            public Node2DList(int val)
            {
                this.val = val;
            }

            public override string ToString()
            {
                string result = this.val + " , Right = " + this.right + ", Down = " + this.down;
                return result;
            }

            public void Display()
            {
                Node2DList row = this;
                while (row != null)
                {
                    Node2DList col = row;
                    while (col != null)
                    {
                        Console.Write(col.val + " ");
                        col = col.right;
                    }

                    Console.WriteLine();
                    row = row.down;
                }
            }
        }

        private enum Direction
        {
            Down,
            Right,
        }

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

/**
 * Declare a Node [][] of the same size of the matrix. Then next connect the nodes 
 * to each other. The Node struct will have a left pointer and a down pointer.
 * Bonus: There is a print routine to print the matrix of Nodes.
 */

import java.util.Objects;

public class MatrixLinks {

    public static void main(String[] args) {

        MatrixLinks work = new MatrixLinks();
        int [] [] m = {{1,2,3}, {4,5,6}, {7,8,9}};
        Node n = work.matrixLink (m);
        work.print (n);
    }

    private void print(Node n) {
        Node node = Objects.requireNonNull(n);
        while ( node !=null)  {
            Node  c= node;
            while ( c!=null) {
                System.out.print(c);
                c=c.right;
            }
            node= node.down;
            System.out.println();
        }
    }

    private Node matrixLink(int[][] m) {
        int max_row = m.length;
        int max_col= m[0].length;
        Node [] [] mt = new Node [max_row] [max_col];
        for (int i = 0; i < max_row ; i++) {
            for (int j = 0; j <max_col ; j++) {
                mt [i][j] = new Node(m [i][j]);
            }
        }
        for (int i = 0; i < max_row ; i++) {
            for (int j = 0; j <max_col; j++) {
                Node n = mt [i][j];
                if ( j+1< max_col)n.right (mt [i][j+1]);
                if (i+1 <max_row) n.down (mt [i+1][j]);
                System.out.println("connected " +n);
            }
        }

        return mt [0][0];
    }

    class Node {
        private int d; Node right, down ;
        Node (int d){ this.d =d;}
        Node right () { return this.right;}
        Node down () {return  this.down;};
        Node right (Node n) { this.right = n; return this;}
        Node down (Node n) { this.down= n; return this;}

        @Override
        public String toString() {
            return "Node{" +
                    "d=" + d + ", " +
                    "r=" + (this.right () ==null ? "NUL": this.right().d) + ", "+
                    "d=" + (this.down () ==null ? "NUL": this.down().d) + ""+
                    "}\t";
        }
    }
}

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

def get_matrix():
    matrix = [
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9],
    ]

    return matrix


class Node(object):
    data = None
    right_node = None
    bottom_node = None

    def __init__(self, data=None):
        if data:
            self.data = data


def convert_to_linked_list(matrix):
    node = Node()
    start = node

    for i in range(len(matrix)):
        vertical_node = node

        for j in range(len(matrix[i])):
            node.data = matrix[i][j]

            if i < len(matrix) - 1:
                node.bottom_node = Node()

            if j < len(matrix[i]) - 1:
                node.right_node = Node()
                node = node.right_node

        node = vertical_node.bottom_node

    return start


def print_linked_list(linked_list):

    bottom_node = linked_list
    while bottom_node:
        right_node = bottom_node
        while right_node:
            print right_node.data,
            right_node = right_node.right_node

        bottom_node = bottom_node.bottom_node
        print


def main():
    matrix = get_matrix()
    linked_list = convert_to_linked_list(matrix)

    print_linked_list(linked_list)


main()

- Souradeep De August 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Scanner;
class dlink{
public int data;
public dlink down;
public dlink next;

public dlink(int value){
data=value;
down=null;
next=null;
}

public void display_link(){
System.out.println(data);
}
}

class linked_matrix{
private dlink start,temp1,temp2;
private int row,col;

public linked_matrix(int x,int y){
start=null;
temp1=null;
temp2=null;
row=x;
col=y;
}

public void initialization(){

dlink newl= new dlink(0);
start=newl;
temp1=start;
temp2=start;
for(int j=0;j<row;j++){
for( int i=1;i<col;i++){
temp1.next=new dlink(0);
temp1=temp1.next;
}

temp2.down=new dlink(0);
temp2=temp2.down;
temp1=temp2;
}

}
public void insert(int value,int r_no,int c_no){
temp1=start;
int i;
for( i=0;i<r_no;i++){
temp1=temp1.down;
}
for(i=0;i<c_no;i++){
temp1=temp1.next;
}
temp1.data=value;
}
public void display(){
temp1=start;
temp2=start;
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
System.out.print(temp1.data+" ");
temp1=temp1.next;
}
temp2=temp2.down;
temp1=temp2;
System.out.println("\n");
}
}
}
class project6{
public static void main(String args[]){
linked_matrix ob;
Scanner sc=new Scanner(System.in);
System.out.print("Enter no. of rows: ");
int r=sc.nextInt();
System.out.print("Enter no. of columns: ");
int c=sc.nextInt();
System.out.println("\n");
ob=new linked_matrix(r,c);
ob.initialization();
ob.display();
System.out.println("\n\n");
ob.insert(2,0,0);
ob.insert(3,0,1);
ob.insert(4,0,2);
ob.insert(5,0,3);
ob.insert(6,1,0);
ob.insert(7,1,1);
ob.insert(8,1,2);
ob.insert(9,1,3);
ob.insert(10,2,1);
ob.insert(11,2,2);
ob.display();
}
}

import java.util.Scanner;
class dlink{
       public int data;
       public dlink down;
       public dlink next;

       public dlink(int value){
               data=value;
               down=null;
               next=null;
       }
  
       public void display_link(){
               System.out.println(data);
       }
 }
 
 class linked_matrix{
       private dlink start,temp1,temp2;
       private int row,col;

       public linked_matrix(int x,int y){
              start=null;
              temp1=null;
              temp2=null;
              row=x;
              col=y;
       }

      public void initialization(){
             
                    dlink newl= new dlink(0);
                    start=newl;
                    temp1=start;
                    temp2=start;
             for(int j=0;j<row;j++){
             for( int i=1;i<col;i++){
                    temp1.next=new dlink(0);
                    temp1=temp1.next;
             }
             
                    temp2.down=new dlink(0);
                    temp2=temp2.down;
                    temp1=temp2;
            }
            
     }
     public void insert(int value,int r_no,int c_no){
            temp1=start;
            int i;
            for( i=0;i<r_no;i++){
                   temp1=temp1.down;
            }
            for(i=0;i<c_no;i++){
                   temp1=temp1.next;
            }
            temp1.data=value;
   }
   public void display(){
            temp1=start;
            temp2=start;
            for(int i=0;i<row;i++){
                for(int j=0;j<col;j++){
                     System.out.print(temp1.data+" ");
                     temp1=temp1.next;
                }
                temp2=temp2.down;
                temp1=temp2;
                System.out.println("\n");
            }
  }
}
class project6{
         public static void main(String args[]){
                    linked_matrix ob;
                    Scanner sc=new Scanner(System.in);
                    System.out.print("Enter no. of rows: ");
                    int r=sc.nextInt();
                    System.out.print("Enter no. of columns: ");
                    int c=sc.nextInt();
                    System.out.println("\n");
                    ob=new linked_matrix(r,c);
                    ob.initialization();
                    ob.display();
                    System.out.println("\n\n");
                    ob.insert(2,0,0);
                    ob.insert(3,0,1);
                    ob.insert(4,0,2);
                    ob.insert(5,0,3);
                    ob.insert(6,1,0);
                    ob.insert(7,1,1);
                    ob.insert(8,1,2);
                    ob.insert(9,1,3);
                    ob.insert(10,2,1);
                    ob.insert(11,2,2);
                    ob.display();
         }
}

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

import java.util.Scanner;
class dlink{
       public int data;
       public dlink down;
       public dlink next;

       public dlink(int value){
               data=value;
               down=null;
               next=null;
       }
  
       public void display_link(){
               System.out.println(data);
       }
 }
 
 class linked_matrix{
       private dlink start,temp1,temp2;
       private int row,col;

       public linked_matrix(int x,int y){
              start=null;
              temp1=null;
              temp2=null;
              row=x;
              col=y;
       }

      public void initialization(){
             
                    dlink newl= new dlink(0);
                    start=newl;
                    temp1=start;
                    temp2=start;
             for(int j=0;j<row;j++){
             for( int i=1;i<col;i++){
                    temp1.next=new dlink(0);
                    temp1=temp1.next;
             }
             
                    temp2.down=new dlink(0);
                    temp2=temp2.down;
                    temp1=temp2;
            }
            
     }
     public void insert(int value,int r_no,int c_no){
            temp1=start;
            int i;
            for( i=0;i<r_no;i++){
                   temp1=temp1.down;
            }
            for(i=0;i<c_no;i++){
                   temp1=temp1.next;
            }
            temp1.data=value;
   }
   public void display(){
            temp1=start;
            temp2=start;
            for(int i=0;i<row;i++){
                for(int j=0;j<col;j++){
                     System.out.print(temp1.data+" ");
                     temp1=temp1.next;
                }
                temp2=temp2.down;
                temp1=temp2;
                System.out.println("\n");
            }
  }
}
class project6{
         public static void main(String args[]){
                    linked_matrix ob;
                    Scanner sc=new Scanner(System.in);
                    System.out.print("Enter no. of rows: ");
                    int r=sc.nextInt();
                    System.out.print("Enter no. of columns: ");
                    int c=sc.nextInt();
                    System.out.println("\n");
                    ob=new linked_matrix(r,c);
                    ob.initialization();
                    ob.display();
                    System.out.println("\n\n");
                    ob.insert(2,0,0);
                    ob.insert(3,0,1);
                    ob.insert(4,0,2);
                    ob.insert(5,0,3);
                    ob.insert(6,1,0);
                    ob.insert(7,1,1);
                    ob.insert(8,1,2);
                    ob.insert(9,1,3);
                    ob.insert(10,2,1);
                    ob.insert(11,2,2);
                    ob.display();
         }
}

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

C#:

using System;


namespace Rextester
{
    public class Program
    {
        public static void Main(string[] args)
        {
            //Your code goes here
            int[,] mat = new int[,] { { 1,2,3 }, { 4,5,6 }, { 7,8,9 }};
            Node n = ConvertMat2LL(mat,0,0);
            printList(n);
            
        }
        
        public static Node ConvertMat2LL(int [,] mat, int r, int c)
        {
            Node n = new Node();
            n.data = mat[r,c];
            Console.WriteLine("r: " + r.ToString() + " c: " + c.ToString() + " mat[r,c]: " + mat[r,c].ToString() );
            if(r < mat.GetLength(0) - 1 && n.down == null)
            {
                Console.WriteLine("r: " + r.ToString() + " c: " + c.ToString());
                n.down = ConvertMat2LL(mat , r + 1, c);
            }
            if(c < mat.GetLength(1) - 1 && n.right == null)
            {
                Console.WriteLine("r: " + r.ToString() + " c: " + c.ToString());
                n.right = ConvertMat2LL(mat , r, c + 1);
            }
            return n;            
        }
        
        public static void printList(Node n)
        {
            Node temp = n;
            while(temp != null)
            {
                while(temp != null)
                {
                    System.Console.Write(temp.data.ToString() + " ");
                    temp = temp.right;
                }
                System.Console.WriteLine("");
                n = n.down;
                temp = n;
            }
        }
        
    }
    
    public class Node
    {
        public Node right;
        public Node down;
        public int data;
    }
}

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

public class MatrixToLinkedList
{
	public static void main(String[] args)
	{
		int[][] mat = { { 1, 2, 3 }, 
				        { 4, 5, 6 },
				        { 7, 8, 9 } };

		MatrixToLinkedList m = new MatrixToLinkedList();
		Node node = m.createLinkedList(mat);

		System.out.println(node.val+" : "+node.right.val+" : "+node.down.val+" : "+ node.right.right.val);
	}

	public Node createLinkedList(int[][] mat)
	{
		return helper(mat, 0, 0);
	}

	private Node helper(int[][] mat, int i, int j)
	{
		if(isSafe(mat, i, j))
		{
			Node node = new Node(mat[i][j]);
			node.right = helper(mat, i, j+1);
			node.down = helper(mat, i+1, j);
			return node;
		}
		return null;
		
	}

	public boolean isSafe(int[][] mat, int row, int col)
	{
		if(row < 0|| row >= mat.length || col<0 || col>= mat[row].length)
			return false;
		return true;
	}


}

class Node
{
	int val;
	Node down;
	Node right;

	Node(int val)
	{
		this.val = val;
	}
}

- noob September 27, 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