Oracle Interview Question for SDE-2s


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.

- praveenkcs28 July 14, 2014 | Flag Reply
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'.

- Hari Prasad Perabattula July 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- alex July 15, 2014 | Flag
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) {
                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);
    }
}

- dapeng2014 July 26, 2014 | Flag Reply
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?

- nav July 13, 2014 | Flag Reply
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....

- Kavita July 14, 2014 | Flag Reply
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'.

- Hari Prasad Perabattula July 15, 2014 | Flag Reply
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;

- gdg August 01, 2014 | Flag Reply
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.

- kartika August 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Zortlord October 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;

- Zortlord October 08, 2014 | Flag
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();
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);
}

}

}

- Anonymous November 16, 2014 | Flag Reply
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

- deep November 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- deep November 23, 2014 | Flag
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);
}

}
}

- Mathu June 11, 2015 | Flag Reply
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);
		}
		
	}
}

- Mathu June 11, 2015 | Flag Reply
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);
}
}

- sushantgadi July 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- _rahulg July 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Dhruv August 05, 2014 | Flag


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