## Samsung Interview Question for Developer Program Engineers

Country: India
Interview Type: Written Test

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

There's a bunch of ways to solve this.

Some artificial intelligence algorithms:
- Backtracking with branch-and-bound
- Genetic algorithm
- Ant colony optimization

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

Convert to a graph:
- Each element that's not a block is a new vertex.
- Each vertex shall be connected to its Moore neighborhood's vertices.

Apply Dijkstra's algorithm on graph (each edge has a weight of 1).

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

It's easy to think of converting it to a graph and apply single source shortest path, just note that this is a sparse graph so building the graph requires O(N) time where N = m*n and a Dijkstra solution with heap requires O(NlogN) time since |E| <= 8N.

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

You can use Dynamic Programming to solve this.
Time Complexity : O(n*m)
Space Complexity : O(n*m)

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

BFS approach. Didn't really test the code.

``````import java.util.*;

class MinSteps {
static class Position {
int r;
int c;
public Position(int r, int c) {
this.r = r;
this.c = c;
}
}

static int minSteps(int[][] map) {
int m = map.length;
int n = map[0].length;
int steps = 0;
while(steps < m+n) {
for(Position p : curr) {
int r = p.r;
int c = p.c;
if(r == m-1 && c == n-1)
return steps;
check(r+1, c, map, next);
check(r, c+1, map,  next);
check(r+1, c+1, map, next);
curr = next;
}
steps++;
}
// we shouldn't reach here
return Integer.MAX_VALUE;
}

static void check(int r, int c, int[][] map, LinkedList<Position> next) {
int m = map.length;
int n = map[0].length;
if(r < m && c < n && map[r][c] == 1) {
map[r][c] = -1;
}
}

public static void main(String[] args) {
}
}``````

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

You have assumed that movement can happen only on the direction of goal which is not necessary.

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

``````#include<iostream>
//#define max 2147483647
using namespace std;

bool safe(int i,int j,int m,int n){
if(i>=0 && i<m && j>=0 && j<n){
return true;
}
else{
return false;
}
}

void pop(int *front,int *rear){
if(*rear == *front){
*rear=-1;
*front=-1;
}
else{
*front= *front+1;
}
}

int main(){
int t;
cin>>t;
while(t--){
int m,n;
cin>>m>>n;
int A[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
cin>>A[i][j];
}
}
int T[m][n]; int Q[m*n][2];
/* int A[7][5]={  {1,0,1,1,1},
{1,1,0,0,1},
{1,0,0,1,0},
{0,1,1,0,0},
{0,0,1,0,1},
{1,0,0,1,1},
{0,1,1,0,1}};*/
int rear=-1,front=-1;

for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
T[i][j]=2147483647;
//  cout<<T[i][j]<<" ";
}
// cout<<endl;
}

T[0][0]=0;int i=0,j=0;
rear=0;front=0;
Q[rear][0]=0;Q[rear][1]=0;
while(i<m-1 || j<n-1){

if(safe(i+1,j+1,m,n) && A[i+1][j+1]==1 && T[i+1][j+1]>1+T[i][j]){
T[i+1][j+1]=1+T[i][j];
if(rear==-1 && front ==-1){
front++;
}
rear++;
Q[rear][0]=i+1;
Q[rear][1]=j+1;
if(i+1 == m-1 && j+1 == n-1){
cout<<"min path length: "<<T[m-1][n-1]<<endl;
break;
}
}
else if(safe(i,j+1,m,n) && A[i][j+1]==1 && T[i][j+1]>1+T[i][j]){
T[i][j+1]=1+T[i][j];
if(rear==-1 && front ==-1)
front++;
rear++;
Q[rear][0]=i;
Q[rear][1]=j+1;
if(i == m-1 && j+1 == n-1){
cout<<"min path length: "<<T[m-1][n-1]<<endl;
break;
}
}
else if(safe(i+1,j,m,n) && A[i+1][j]==1 && T[i+1][j]>1+T[i][j]){
T[i+1][j]=1+T[i][j];
if(rear==-1 && front ==-1)
front++;
rear++;
Q[rear][0]=i+1;
Q[rear][1]=j;
if(i+1 == m-1 && j == n-1){
cout<<"min path length: "<<T[m-1][n-1]<<endl;
break;
}
}
else if(safe(i-1,j+1,m,n) && A[i-1][j+1]==1 && T[i-1][j+1]>1+T[i][j]){
T[i-1][j+1]=1+T[i][j];
if(rear==-1 && front ==-1)
front++;
rear++;
Q[rear][0]=i-1;
Q[rear][1]=j+1;
if(i-1 == m-1 && j+1 == n-1){
cout<<"min path length: "<<T[m-1][n-1]<<endl;
break;
}
}
else if(safe(i-1,j,m,n) && A[i-1][j]==1 && T[i-1][j]>1+T[i][j]){
T[i-1][j]=1+T[i][j];
if(rear==-1 && front ==-1)
front++;
rear++;
Q[rear][0]=i-1;
Q[rear][1]=j;
if(i-1 == m-1 && j == n-1){
cout<<"min path length: "<<T[m-1][n-1]<<endl;
break;
}
}
else if(safe(i+1,j-1,m,n) && A[i+1][j-1]==1 && T[i+1][j-1]>1+T[i][j]){
T[i+1][j-1]=1+T[i][j];
if(rear==-1 && front ==-1)
front++;
rear++;
Q[rear][0]=i+1;
Q[rear][1]=j-1;
if(i+1 == m-1 && j-1 == n-1){
cout<<"min path length: "<<T[m-1][n-1]<<endl;
break;
}
}
else if(safe(i,j-1,m,n) && A[i][j-1]==1 && T[i][j-1]>1+T[i][j]){
T[i][j-1]=1+T[i][j];
if(rear==-1 && front ==-1)
front++;
rear++;
Q[rear][0]=i;
Q[rear][1]=j-1;
if(i == m-1 && j-1 == n-1){
cout<<"min path length: "<<T[m-1][n-1]<<endl;
break;
}
}
else if(safe(i-1,j-1,m,n) && A[i-1][j-1]==1 && T[i-1][j-1]>1+T[i][j]){
T[i-1][j-1]=1+T[i][j];
if(rear==-1 && front ==-1)
front++;
rear++;
Q[rear][0]=i-1;
Q[rear][1]=j-1;
if(i-1 == m-1 && j-1 == n-1){
cout<<"min path length: "<<T[m-1][n-1]<<endl;
break;
}
}
else{

pop(&front,&rear);
i=Q[front][0];
j=Q[front][1];
if(front== -1 && rear== -1){
cout<<"NO Path"<< endl;
break;

}
}
/*   cout<<"i= "<<i<<" j= "<< j<<endl;
for(int k=front;k<=rear;k++){

cout<<Q[k][0]<<" "<<Q[k][1]<<endl;
}*/
}

}
return 0;
}``````

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.