Oracle Interview Question
SDE-2sCountry: India
Interview Type: In-Person
If we consider the cells of the grid as vertices, I think, the problem is to find the 'Hamiltonian Cycle'.
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) {
res.add(temp);
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));
}
}
}
res.add(end);
}
}
#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;
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.
How about this DFS Backtracking approach:
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);
default: //bad
return null;
}
}
}
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;
default: //bad
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;
import java.io.*;
public class traverse_2d_matrix
{
public static void main(String args[]) throws IOException
{
int m,n;
System.out.println();
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String s;
m=Integer.parseInt(br.readLine());
n=Integer.parseInt(br.readLine());
int mat[][]=new int[m][n];
for(int i=0;i<m;i++)
{
s=br.readLine();
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);
}
}
}
i think by triversing in forward and backbard direction from source to destination is suficient to triverce all nodes
#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;
}
}
}
}
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);
}
}
}
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);
}
}
}
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);
}
}
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.
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.
- praveenkcs28 July 14, 2014