Amazon Interview Question SDE-2s
Country: United States
Interview Type: Written Test
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];
}
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
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;
}
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;
}
}
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;
}
}
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;
}
}
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,
}
/**
* 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";
}
}
}
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()
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();
}
}
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();
}
}
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;
}
}
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;
}
}
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