Amazon Interview Question SDE1s
Country: United States
Last sequence is wrong in this.
public static void main(String args[]) {
String [] [] matrix = {{"A","N", "L", "Y", "S"},{"I", "S", "D", "E", "S"},{"I", "G", "N", "D", "E"}};
printMatrixPaths(matrix, "DES");
}
public static void printMatrixPaths(String[][] matrix, String word)
{
for (int i=0; i < matrix.length; i++)
for (int j=0; j< matrix[0].length; j++)
printMatrixPaths(matrix, i, j, new ArrayList<String>(), word, null);
}
public static void printMatrixPaths(String[][] matrix, int row, int column, List<String> path, String word, String tempWord)
{
if (matrix == null || matrix.length == 0 ||row < 0 || column < 0 || row >= matrix.length || column >= matrix[0].length)
return;
if (tempWord == null)
{
if (!String.valueOf(word.charAt(0)).equals(matrix[row][column]))
{
return;
}
} else if (!String.valueOf(word.charAt(tempWord.length())).equals(matrix[row][column])){
return;
}
tempWord = (tempWord == null )? matrix[row][column] : (tempWord += matrix[row][column]);
path.add(matrix[row][column] +" is at : "+ row +", "+ column);
if (word.equals(tempWord))
{
printMatrixPath(path);
path.remove(path.size()-1);
return;
}
printMatrixPaths(matrix, row-1, column, path, word, tempWord);
printMatrixPaths(matrix, row-1, column+1, path, word, tempWord);
printMatrixPaths(matrix, row, column+1, path, word, tempWord);
printMatrixPaths(matrix, row+1, column, path, word, tempWord);
printMatrixPaths(matrix, row+1, column+1, path, word, tempWord);
}
public static void printMatrixPath(List<String> paths)
{
for(String path : paths)
{
System.out.println(path);
}
}
The obvious solutions to this problem is doing a recursive or non-recursive (using stack) DFS like everyone else has suggested. However I observed the performance of this the algorithm could be optimized by using this trick:
Assumption: All the characters in the input are ASCII characters.
1. Create a 256*256 neighbor matrix where there is one row for all possible characters and one column for all possible characters. Each row for a particular character will contain a true for all the characters that are its neighbor in the input matrix and false for all the characters that aren't its neighbor. (You could actually optimize the space used here since each character can have at most 8 neighbors.
2. Now if you have to lookup "DEF". Simply check if the neighbor matrix contains a true for ['D','E'] and ['E','F'] both of which would be O(1) operations. So you can actually check if a string exists given matrix in the time proportional to the length of the string.
3. Above method fails if there are repeated characters (it gives False positives). So if step 2 gives you True then fall back to traditional DFS approach, but if it gives you False, you can exit.
#include<stdio.h>
int printDESposition(char [][]matrix,char *word,int i,int j,int trackrow[3],int trackcol[3][3],int indexTrackrow,int indexTrackcol) {
if(i-1 >=0 && j-1>=0 && matrix[i-1][j-1]==word[0]) {
trackrow[indexTrackrow]=i-1;
trackrow[indexTrackcol]=j-1;
if(indexTrackrow==2) {
printPositions(trackrow,trackcol);
}
else {
printDESposition(matrix,++word,i-1,j-1,trackrow,trackcol,++indexTrackrow,++indexTrackcol);
--word;
--indexTrackrow;
--indexTrackcol;
}
// Similarly for the other 7 conditions code needs to be filled up..
}
}
int main() {
char matrix[][] = {{"A","N", "L", "Y", "S"},{"I", "S", "D", "E", "S"},{"I", "G", "N", "D", "E"}};
char *word="DES";
int trackrow[3];
int trackcol[3];
indexTrackrow=0;
indexTrackcol=0;
for(int i=0;i<5;i++) {
for(int j=0;j<5;j++) {
if(matrix[i][j]==word[0]) {
trackrow[indexTrackrow]=i;
trackcol[indexTrackcol]=j;
printDESposition(matrix,++tempWord,i,j,trackrow,trackcol,++indexTrackrow,++indexTrackcol);
}
--word;
--indexTrackrow;
--indexTrackcol;
}
}
}
Simple backtracking algorithm.
I have used a TRIE for storing the dictionary.
const int DIM = 3;
const int MAXNEIGHBOURS = 8;
int displacement[8][2] = {{-1,-1},{0,-1},{1,-1},{1,0},{-1,1},{0,1},{-1,1},{-1,0}};
char matrix[DIM][DIM] = {{'c','a','t'},{'a','j','i'},{'t','n','o'}};
bool solveMatrix(int row,int col, string word)
{
if(word.compare("*") ==0)
return false;
if(dictionary.search(word))
{
cout<<"\n"<<word;
matrix[row][col] = '*';
return true;
}
for(int i=0; i<MAXNEIGHBOURS ; i++)
{
int newRow = row + displacement[i][0];
int newCol = col + displacement[i][1];
char originalCharacter = matrix[row][col];
matrix[row][col] = '*';
if(isValid(newRow,newCol))
{
if(solveMatrix(newRow,newCol,word+matrix[newRow][newCol]))
return true;
}
matrix[row][col] = originalCharacter;
}
return false;
}
This code can be further optimized with little tweaks to search function of trie such that it can return 3 possible values.
0 - no sequence with current word as prefix.
1 - Sequence like current word is present in trie but it is not the complete word only the prefix.
2- It is complete word.
We can continue search only in case of 1, when 2 is returned word is found and when 0 is returned no use of searching further.
All we need to do is to search for the location of the "D" in the matrix and then check the possible combinations one-by-one. Based on the question, we do not need to worry about what is behind the location of the currently found "D". Hence, search goes forward in O(1). However, the entire program is O(mn) due to the search for the available "D"s. Here's the code:
#include<stdio.h>
#include<stdlib.h>
#define SIZE(A) (sizeof(A)/sizeof(A[0]))
#define ROW 3
#define COL 5
char m[ROW][COL] = {'A','N', 'L', 'Y', 'S',
'I', 'S', 'D', 'E', 'S',
'I', 'G', 'N', 'D', 'E'};
void SearchString(char *s, int row, int col)
{
try
{
if(!*s) throw "\nNULL Input\n";
}catch(const char *p)
{
puts(p);
return;
}
if(row-1>=0 && col+1<COL)
{
if(m[row-1][col]=='E' && m[row-1][col+1]=='S')
printf("[%d %d]\t[%d %d]\t[%d %d]\n",row,col,row-1,col,row-1,col+1);
if(m[row][col+1]=='E' && m[row-1][col+1]=='S')
printf("[%d %d]\t[%d %d]\t[%d %d]\n",row,col,row,col+1,row-1,col+1);
if(col+2<COL)
{
if (m[row-1][col+1]=='E' && m[row-1][col+2]=='S')
printf("[%d %d]\t[%d %d]\t[%d %d]\n",row,col,row-1,col+1,row-1,col+2);
if (m[row][col+1]=='E' && m[row-1][col+2]=='S')
printf("[%d %d]\t[%d %d]\t[%d %d]\n",row,col,row,col+1,row-1,col+2);
if(m[row][col+1]=='E' && m[row][col+2]=='S')
printf("[%d %d]\t[%d %d]\t[%d %d]\n",row,col,row,col+1,row,col+2);
}
if(row-2>=0)
{
if(m[row-1][col]=='E' && m[row-2][col+1]=='S')
printf("[%d %d]\t[%d %d]\t[%d %d]\n",row,col,row-1,col,row-2,col+1);
}
}
if(row+1<ROW && col+1<COL)
{
if(m[row+1][col]=='E' && m[row+1][col+1]=='S')
printf("[%d %d]\t[%d %d]\t[%d %d]\n",row,col,row+1,col,row+1,col+1);
if(m[row][col+1]=='E' && m[row+1][col+1]=='S')
printf("[%d %d]\t[%d %d]\t[%d %d]\n",row,col,row,col+1,row+1,col+1);
if(col+2<COL)
{
if(m[row][col+1]=='E' && m[row+1][col+2]=='S')
printf("[%d %d]\t[%d %d]\t[%d %d]\n",row,col,row,col+1,row+1,col+2);
if(m[row+1][col+1]=='E' && m[row+1][col+2]=='S')
printf("[%d %d]\t[%d %d]\t[%d %d]\n",row,col,row+1,col+1,row+1,col+2);
}
}
}
int main()
{
char *s="DES";
for(int i=0;i<ROW;i++)
{
for(int j=0;j<COL;j++)
{
if(m[i][j]=='D')
SearchString(s,i,j);
}
}
return 1;
}
- lei2.qin July 09, 2013public class MatrixWords { private char[][] matrix; private String word; public MatrixWords(char[][] matrix, String word) { this.matrix = matrix; this.word = word; } public void findWords() { for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[i].length; j++) { findNext(i, j, 0, ""); } } } private void findNext(int x, int y, int idx, String positions) { if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[x].length) return; if (matrix[x][y] != word.charAt(idx)) return; positions += (word.charAt(idx) + " - [" + x + ", " + y + "], "); if (idx < word.length() - 1) { findNext(x - 1, y - 1, idx + 1, positions); findNext(x, y - 1, idx + 1, positions); findNext(x + 1, y - 1, idx + 1, positions); findNext(x - 1, y + 1, idx + 1, positions); findNext(x, y + 1, idx + 1, positions); findNext(x + 1, y + 1, idx + 1, positions); findNext(x + 1, y, idx + 1, positions); findNext(x - 1, y, idx + 1, positions); } else { System.out.println(positions); } } public static void main(String[] args) { char[][] matrix = new char[][]{ {'A', 'N', 'L', 'Y', 'S'}, {'I', 'S', 'D', 'E', 'S'}, {'I', 'G', 'N', 'D', 'E'} }; String word = "DES"; MatrixWords mw = new MatrixWords(matrix, word); mw.findWords(); } }