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;
LinkedList<Position> curr = new LinkedList<Position>();
curr.add(new Position(0, 0));
int steps = 0;
while(steps < m+n) {
LinkedList<Position> next = new LinkedList<Position>();
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) {
next.add(new Position(r, c));
map[r][c] = -1;
}
}

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

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

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;
}``````

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