## Samsung Interview Question for Software Engineer / Developers

• -3

Country: India
Interview Type: In-Person

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

First place question should be "Given if the element is 1 we can move Right or down, if it is 0 we can only proceed downward".
Then find the working code.......
Plz give any comment....

``````#include<stdio.h>

#define ROW 3
#define COL 3
#define MAX ROW*COL

int NextDistance(int, int);

int arr[3][3] = {1, 1, 0, 0, 0, 0, 1, 0, 0};

int main(void)
{
int i, j, dist;
printf("\nOrigina Array......\n");
for(i=0; i<ROW; i++)
{
for(j=0; j<COL; j++)
printf("\t%d", arr[i][j]);
printf("\n");
}

dist = NextDistance(0, 0);
if(dist < MAX)
printf("\nShortest Distance : %d\n\n", dist);
else
printf("\nThere is no path exist from start element to end element....\n\n");

return 0;
}

int NextDistance(int i, int j)
{
int slen=MAX, slen1=MAX, slen2=MAX;
if(i==ROW-1 && j==COL-1)
return 0;
else if(i==ROW-1 && arr[i][j]==0)
return MAX;
else if(arr[i][j] == 0)
{
if(i < ROW-1)
slen = 1 + NextDistance(i+1, j);
}
else
{
if(j < COL-1)
slen1 = 1 + NextDistance(i, j+1);
if(i < ROW-1)
slen2 = 1 + NextDistance(i+1, j);
slen = slen1<slen2 ? slen1 : slen2;
}
return slen;
}``````

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

it is correct with some unnecessary steps like there is an unrequired if condition.and there was no need to init slens to max.

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

flood fill algorithm

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

a little insight, on how flood fill applies here, would be nice.

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

just do bfs to find out the shortest path.

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

for an array of size MxN, does the first element mean element at 0,0 and last element mean the element at M-1,N-1 (assuming 0 based indexing) ?

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

shortest distance between the first and the last element in a two dimension:

Case 1: first element = a[0][0] & last element a[M][N]
Sol: you can never move from a[0][0] to a[M][N] with only possible action left and down. Right move is required unless left move from a[0][0] is not a[0][N]

Case 2: first element = a[0][0] & last element a[M][index] (bottom row)
Sol: no matter what matrix is given made up with o and 1. ans will always M down moves.

Case 3: first element = a[0][0] & last element a[M][N] (right most column) and we have move down or right for each 1
Sol: when ever you got 1 go right and down for 0...once reached rightmost column go down for all elements (0 or 1)

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

There seems to be a problem with the mechanics of the question.
- You want to start at (0,0) and go to (m-1,n-1) in a m by n grid.
- As per your question, on seeing a 1 you can move left or down and on seeing a 0 you can move only down.
- The problem with this is that you are never able to move right and you may never reach (m-1, n-1).

So , the second part of your question ought to be something like this :

Given, if the element is 1, we can move LEFT or DOWN, if it is 0 we can move RIGHT or UPWARDS.

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

yeah Rahul you are correct, the question was if the element was 1 , we can move right or downwards and if it was 0, we can proceed downwards only. Also, we have to find whether the route from the (0,0) to (m-1,n-1) exists.

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

Dynamic programming approach if 1 leads to right/down and 0 leads to down.

s(0,0) = 0
s(i,j) = min{s(i-1,j) , s(i,j-1)} +1

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

1.Go right if the value of the array[i][j] is 1 and j!=N-1, if j is N-1 then move down and you are done.

2. go right if array[i][j] is 1 ,and go left if array[i][j]=0
3. Loop till i<M and j<N

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

``````#include<stdio.h>
int findPath(int arr[][4],int posx, int posy, int maxx, int maxy)
{
int pathFound = 0;
printf("x:%d and y:%d\n",posx,posy);
if(posx < maxx && posy < maxy-1)
{
if(arr[posx][posy] == 1)
{
pathFound = findPath(arr,posx,posy+1,maxx,maxy);
}
if( pathFound == 0)
{
pathFound = findPath(arr,posx+1,posy,maxx,maxy);
}
}
else if(posy == maxx-1)
{
pathFound = 1;
}
return pathFound;
}
int main()
{
int arr[4][4] = {{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,1,1,0}};
printf("%d",findPath(arr,0,0,4,4));
}``````

i think this works fine

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

Consider the matrix to represent a graph where zero means presence of an edge and one implies absence of an edge. Then run BFS to find the shortest path between given indices i, and j.

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

Create a Graph from the given conditions, where each cell in the Matrix is a Node. Give each cell a number and when value is 0 it connects to two other cell through graph edge. When value is 1, it connects to only one cell.

After that run Graph Shortest path algorithm with same weight for each edge.

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

yr only in few cases we can solve this because in most of the cases you will come in the last row with 0 and you can't move down after that ..
is this questions is correct or rahul is correct

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

Since each move is either right or down.
Total moves required = (N-1)DOWN MOVES + (M-1) right moves == N+M-2 (always)
so problem reduces to:

if(there_is_a_path)return N+M-2;
else INT_MAX;

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.

### 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.

### 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.

### 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.