## Oracle Interview Question for SDE-2s

• 2

Country: India
Interview Type: In-Person

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

I think backtracking can be used here , start from the source and start visiting neighbouring vertices along some random path , marking the visited vertices , the point at which we get stuck according the rules , we backtrack until there is a different path possible . In this way we should be able to arrive at the solution.

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

If we consider the cells of the grid as vertices, I think, the problem is to find the 'Hamiltonian Cycle'.

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

In cycle, you reach back to the same cell. Here source and destination are different.

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

bfs solution, basically if seeing the end point, do not push it into stack

``````import java.util.*;
public class Traverse2DMatrix {
class Point{
int x;
int y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
}
public Point start = new Point(0, 0);
public Point end = new Point(1, 2);
public int [][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
public void traverse2D(){
int m = matrix.length;
int n = matrix[0].length;
boolean[][] visited = new boolean[m][n];
ArrayList<Point> res = new ArrayList<Point>();
Stack<Point> st = new Stack<Point>();
st.push(start);
while(st.isEmpty() == false) {
Point temp = st.pop();
if(visited[temp.x][temp.y] == false) {
visited[temp.x][temp.y] = true;
if(temp.x - 1 >= 0 && (temp.x - 1 != end.x || temp.y != end.y)) {
st.push(new Point(temp.x - 1, temp.y));
}
if(temp.x + 1 <= m - 1 && (temp.x + 1 != end.x || temp.y != end.y)) {
st.push(new Point(temp.x + 1, temp.y));
}
if(temp.y - 1 >= 0 && (temp.x != end.x || temp.y - 1 != end.y)) {
st.push(new Point(temp.x, temp.y - 1));
}
if(temp.y + 1 <= n - 1 && (temp.x != end.x || temp.y + 1 != end.y)) {
st.push(new Point(temp.x, temp.y + 1));
}
}
}
}
}``````

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

I am having few questions as above solution is wrong,

1. We should consider start and end point, as given in question.
2. Is travelling from any point to any point is posibble?

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

``````i think some more clarification need for this

any point to any point looks impossible to cover all and reach

if its a square matrix and souce is one corner and target is other diagonal corner
we can solve it easily....``````

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

If we consider the cells of the grid as vertices, I think, the problem is to find the 'Hamiltonian Cycle'.

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

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

void print(int *arr, int m, int n)
{
int i, j;
for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
printf("%d ", *((arr+i*n) + j));
}

void traverse(int * arr,int m, int n,int cur_x,int cur_y,int dest_x,int dest_y,int moves)
{
if(cur_x>=m||cur_y>=n||cur_x<0||cur_y<0)
return;

*((arr+cur_x*n) + cur_y)= moves;

if(moves==(m*n)&&cur_x==dest_x&&cur_y==dest_y)
{
print((int *)arr,m, n);
return;
}

traverse(arr,m,n,cur_x,cur_y+1,dest_x,dest_y,moves+1);
traverse(arr,m,n,cur_x+1,cur_y,dest_x,dest_y,moves+1);
traverse(arr,m,n,cur_x,cur_y-1,dest_x,dest_y,moves+1);
traverse(arr,m,n,cur_x-1,cur_y,dest_x,dest_y,moves+1);
}

int main()
{
int arr[3][3] = {{0,0,0}, {0,0,0}, {0,0,0}};
int m=3,n=3;
traverse((int *)arr,m,n,0,0,2,2,1);
return 0;``````

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

i have a different idea, please tell me if im wrong

if source is at (a,b) and dest at (x,y).
print A(a,b), goto (0,0) start printing entire matrix with condition
if((i==a&&j==b)||(i==x&&i==y))
continue; \\ donot print that element
and after printing entire array, print destination ie A(x,y)

again im not sure if that counts as visiting the element twice.

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

``````public class FindPath{
class Move{
int x;
int y;
Move(int y, int x){
this.y = y;
this.x = x;
}

public static Move[] findPath(int[][] field, Move start, move end){
if(field == null || move == null || end == null){
throw new NullPointerException();
}
int yMax = field.length;
if(yMax == 0){
throw new IllegalArgumentException();
}
int xMax = field[0].length;
if(xMax == 0){
throw new IllegalArgumentException();
}
if(start.y < 0 || start.y >= yMax || start.x < 0 || start.x >= xMax ||
end.y < 0 || end.y >= y || end.x < 0 || end.x >= xMax){
throw new IllegalArgumentException();
}
FindPath findPath = new FindPath(field, end, yMax, xMax);
return convertToArr(findPath.findPathRecur(start), yMax, xMax);
}

private static Move[] convertToArr(Stack<Move> moveStack, int yMax, int xMax){
if(moveStack == null){
return null;
}
int size = yMax * xMax;
Move[] results = new Move[size];
while(!moveStack.isEmpty()){
size--;
results[size] = moveStack.pop();
}
return results;
}

private int[][] field;
private Stack<Move> takenPath;
private int[][] positionState;
private Move start;
private Move end;
private int yMax;
private int xMax;
private int maxMoves;

private FindPath(int[][] field, Move end, int yMax, int xMax){
this.field = field;
takenPath = new Stack<Move>(yMax *xMax);
this.end = end;
positionState = new int[yMax][xMax];
this.yMax = yMax;
this.xMax = xMax;
this.maxMoved = yMax * xMax;
}

private ArrayList<Move> findPathRecur(Move move){
this.takenPath.push(move);
this.positionState[move.y][move.x] = EXPLORED;
if(this.takenPath.size() == this.maxMoved && move.x == this.end.x && move.y == this.end.y){
return takenPath;
}
Stack<Move> temp;
Move tempMove;
for(int moveIndex = 0; moveIndex < 4; moveIndex++){
tempMove = genMove(move, moveIndex);
if(tempMove != null){
temp = findPathRecur(tempMove);
if(temp != null){
return temp;
}
}
}
this.takenPath.pop();
this.positionState[move.y][move.x] = UNEXPLORED;
return null;
}

private Move genMove(Move src, int index){
switch(index) {
case 0: //left
if(src.x == 0){
return null;
}
return new Move(src.y, src.x -1);
case 1: //up
if(src.y == 0){
return null;
}
return new Move(src.y -1, src.x);
case 2: //right
if(src.x +1 >= xMax){
return null;
}
return new Move(src.y, src.x + 1);
case 3: //down
if(src.y + 1 >= yMax){
return null;
}
return new Move(src.y + 1, src.x);
return null;
}
}
}``````

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

Just realized that genMove needs to check the positionState too, so it should be

``````private Move genMove(Move src, int index){
Move move = null;
switch(index) {
case 0: //left
if(src.x == 0){
return null;
}
move = new Move(src.y, src.x -1);
break;
case 1: //up
if(src.y == 0){
return null;
}
move = new Move(src.y -1, src.x);
break;
case 2: //right
if(src.x +1 >= xMax){
return null;
}
move = new Move(src.y, src.x + 1);
break;
case 3: //down
if(src.y + 1 >= yMax){
return null;
}
move = new Move(src.y + 1, src.x);
break;
return null;
}
if(this.positionState[move.y][move.x] == EXPLORED){
return null;
}
return move;
}``````

and EXPLORED and UNEXPLORED need to be defined:

``````private static final int EXPLORED = 1;
private static final int UNEXPLORED = 0;``````

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

import java.io.*;
public class traverse_2d_matrix
{
public static void main(String args[]) throws IOException
{
int m,n;
System.out.println();

String s;
int mat[][]=new int[m][n];
for(int i=0;i<m;i++)
{
int num=0;
int k=0,j=0;
while(j<n)
{
//System.out.println(k);
if(k<s.length() && s.charAt(k)!=' ' )
{
num=num*10+(s.charAt(k)-'0');
k++;
}
else
{
mat[i][j]=num;
num=0;
j++;
k++;
}
}
}

int x[]={1,1,0,-1,-1,-1,0,1};
int y[]={0,1,1,1,0,-1,-1,-1};
int source_i=0;
int source_j=1;
int dest_i=2;
int dest_j=1;
boolean visited[][]=new boolean[m][n];
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
visited[i][j]=false;
}
dfsutil(mat,m,n,source_i,source_j,dest_i,dest_j,visited,x,y);
System.out.println(mat[dest_i][dest_j]);
}
public static void dfsutil(int mat[][],int m,int n,int i,int j,int d_x,int d_y,boolean visited[][],int x[],int y[])
{
if(i<0 || i>=m || j<0 || j>=n || visited[i][j])
return;
if(i==d_x && j==d_y)
return;
System.out.println(mat[i][j]);
visited[i][j]=true;
for(int k=0;k<8;k++)
{
dfsutil(mat,m,n,i+x[k],j+y[k],d_x,d_y,visited,x,y);
}

}

}

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

i think by triversing in forward and backbard direction from source to destination is suficient to triverce all nodes

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

``````#include<stdio.h>
#include<conio.h>
int n;
int i,j,k,l;

int main()
{
printf("enter n:");
scanf("%d",&n);
int a[n][n];
printf("enter source:");
scanf("%d",&i);scanf("%d",&j);
i--;j--;
printf("enter destination:");
scanf("%d",&k);scanf("%d",&l);
k--;l--;
int p,q;
for(p=0;p<n;p++)
{
for(q=0;q<n;q++)
{
a[p][q]=3;
}
printf("\n");
}

a[i][j]=0;
a[k][l]=1;

for(p=0;p<n;p++)
{
for(q=0;q<n;q++)
{
printf(" %d ",a[p][q]);
}
printf("\n");
}

printf("\n\n\n\n");

for(p=0;p<n;p++)
{
for(q=0;q<n;q++)
{
printf(" %u ",&a[p][q]);
}
printf("\n");
}

forword(a);
backword(a);

printf("\n\n\n\n");

for(p=0;p<n;p++)
{
for(q=0;q<n;q++)
{
printf(" %d ",a[p][q]);
}
printf("\n");
}

return 0;
}

forword(int *x)
{
int p,q;
for(p=i;p<=k;p++)
{
if(p==i)
{
for(q=j; q<n; q++)
{
*(x+(n*p+q))=2;
}

}
if(i<p && p<k)
{
for(q=0; q<n; q++)
{
*(x+(n*p+q))=2;
}
}
if(p==k)
{
for(q=0; q<l; q++)
{
*(x+(n*p+q))=2;
}

/* if(p==(n-1) && q==(n-1))
{
p=0;q=0;
}*/
}
}

}

backword(int *x)
{
int p,q;
for(p=i;p>=0;p--)
{
if(p==i)
{
for(q=j-1; q>=0; q--)
{
*(x+(n*p+q))=2;
}
}

if( (0<=p) && (p<i ) )
{
for(q=n-1; q>=0; q--)
{
*(x+(n*p+q))=2;
}
}

if(p==0 && q==0)
{
p=n-1;
q=n-1;
}
}

for(p=n-1;p>=k;p--)
{
if( k<p && p<n)
{
for(q=n-1; q>=0; q--)
{
*(x+(n*p+q))=2;
}
}

if(p==k)
{
for(q=n-1; q>k; q--)
{
*(x+(n*p+q))=2;
}
}
}
}``````

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

public class BacktrackingAlgorithm
{
private boolean visited[][] ;

public static void main(String arg[])
{
BacktrackingAlgorithm bta = new BacktrackingAlgorithm();
int[][] input = {{4,5,3} ,{8,6,2} , {9,7,1}};
MatrixLocation startLocation = new MatrixLocation(2, 1);
MatrixLocation endLocation = new MatrixLocation(1, 2);
bta.traverseMatrix(input, startLocation, endLocation);
}

public void traverseMatrix(int[][] input,MatrixLocation start, MatrixLocation end )
{
if(input == null || start == null || end == null)
{
throw new NullPointerException("Input cannot be Null");
}
visited = new boolean[input.length][input[0].length];
traverseRecursive(input, start, end);
printMatrixLocation(input, end);
visited[end.row][end.coloum] = true;
}

private void traverseRecursive(int[][] input,MatrixLocation currentlocation, MatrixLocation end)
{
if(isValidLocation(input, currentlocation) && !visited[currentlocation.row][currentlocation.coloum] && !currentlocation.equals(end) )
{
printMatrixLocation(input, currentlocation);
visited[currentlocation.row][currentlocation.coloum] = true;
MatrixLocation newLocation= new MatrixLocation(currentlocation.row, currentlocation.coloum+1) ;
traverseRecursive(input, newLocation, end);
newLocation= new MatrixLocation(currentlocation.row +1, currentlocation.coloum) ;
traverseRecursive(input, newLocation, end);
newLocation= new MatrixLocation(currentlocation.row, currentlocation.coloum -1) ;
traverseRecursive(input, newLocation, end);
newLocation= new MatrixLocation(currentlocation.row -1, currentlocation.coloum) ;
traverseRecursive(input, newLocation, end);

}

}

private boolean isValidLocation(int[][] input,MatrixLocation location)
{

if (location.row < input.length && location.row >= 0
&& location.coloum < input[0].length && location.coloum >= 0)
{
return true;
}
return false;
}

private void printMatrixLocation(int[][] data, MatrixLocation location)
{
System.out.println("ROW:" +location.row +" Coloum:"+location.coloum +" Value:" +data[location.row][location.coloum]);
}

static class MatrixLocation
{
int row;
int coloum;

MatrixLocation(int row , int coloum)
{
this.row = row;
this.coloum = coloum;
}

public boolean equals(Object obj)
{
MatrixLocation location = (MatrixLocation)obj;
return (location.row == this.row) && (location.coloum == this.coloum);
}

}
}

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

``````public class BacktrackingAlgorithm
{
private boolean visited[][] ;

public static void main(String arg[])
{
BacktrackingAlgorithm bta = new BacktrackingAlgorithm();
int[][] input = {{4,5,3} ,{8,6,2} , {9,7,1}};
MatrixLocation startLocation = new MatrixLocation(2, 1);
MatrixLocation endLocation = new MatrixLocation(1, 2);
bta.traverseMatrix(input, startLocation, endLocation);
}

public void traverseMatrix(int[][] input,MatrixLocation start, MatrixLocation end )
{
if(input == null || start == null || end == null)
{
throw new NullPointerException("Input cannot be Null");
}
visited = new boolean[input.length][input[0].length];
traverseRecursive(input, start, end);
printMatrixLocation(input, end);
visited[end.row][end.coloum] = true;
}

private void traverseRecursive(int[][] input,MatrixLocation currentlocation, MatrixLocation end)
{
if(isValidLocation(input, currentlocation) && !visited[currentlocation.row][currentlocation.coloum] && !currentlocation.equals(end) )
{
printMatrixLocation(input, currentlocation);
visited[currentlocation.row][currentlocation.coloum] = true;
MatrixLocation newLocation= new MatrixLocation(currentlocation.row, currentlocation.coloum+1) ;
traverseRecursive(input, newLocation, end);
newLocation= new MatrixLocation(currentlocation.row +1, currentlocation.coloum) ;
traverseRecursive(input, newLocation, end);
newLocation= new MatrixLocation(currentlocation.row, currentlocation.coloum -1) ;
traverseRecursive(input, newLocation, end);
newLocation= new MatrixLocation(currentlocation.row -1, currentlocation.coloum) ;
traverseRecursive(input, newLocation, end);

}

}

private boolean isValidLocation(int[][] input,MatrixLocation location)
{

if (location.row < input.length && location.row >= 0
&& location.coloum < input[0].length && location.coloum >= 0)
{
return true;
}
return false;
}

private void printMatrixLocation(int[][] data, MatrixLocation location)
{
System.out.println("ROW:" +location.row +"     Coloum:"+location.coloum +"     Value:" +data[location.row][location.coloum]);
}

static class MatrixLocation
{
int row;
int coloum;

MatrixLocation(int row , int coloum)
{
this.row = row;
this.coloum = coloum;
}

public boolean equals(Object obj)
{
MatrixLocation location = (MatrixLocation)obj;
return (location.row == this.row) && (location.coloum == this.coloum);
}

}
}``````

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

package com.careerCup.oracle;

/*Traverse a given 2D matrix from given source to destination in such way that every cell should be visited exactly one time
(we have to cover all cells of matrix exactly once and have to reach at destination).*/

public class TwodArray {

public void parseArray(int[][] myArray)
{
for(int i=0;i<myArray.length;i++)
{
for(int j=0;j<myArray.length;j++)
{
System.out.println("parsed element--->"+myArray[i][j]);
}
}

}

public static void main(String[] args) {
TwodArray a=new TwodArray();

int[][] myArray = { {0,1,2,3}, {3,2,1,0}, {3,5,6,1}, {3,8,3,4} };

a.parseArray(myArray);
}
}

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

This will just print the array. As far as I can see, we are provided with a matrix a[n][n] and are also given a starting point (i, j). We have to traverse the whole matrix without visiting a cell more than once.

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

But we need to start from the starting position and not the (0,0) index of the array.

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.