Amazon Interview Question SDE1s
Country: India
Interview Type: In-Person
There are 4 times.
public class FindWord {
public static void main(String[] args) {
char[][] ca = {{'w','s','r','t','g','g'},
{'a','a','c','h','i','n'},
{'k','c','h','u','j','j'},
{'o','h','i','n','y','q'}
};
String w = "sachin";
System.out.println(findWord(ca, w));
}
public static int findWord(char [][] ca, String w){
int c = 0;
for(int i = 0; i < ca.length; i++ ){
for(int j = 0; j < ca[0].length; j++ ){
if ( ca.length + ca[0].length - 1 - 1 - i - j >= w.length() )
c += find(ca, w, i, j, 0);
}
}
return c;
}
public static int find(char [][] ca, String w, int x, int y, int p){
int c = 0;
if ( ca[x][y] == w.charAt(p)){
if ( p == w.length() - 1)
return 1;
for(int i = 0; i < 3; i++ ){
switch (i){
case 0:
if( x + 1 < ca.length && p + 1 < w.length() ){
c += find(ca, w, x+1, y, p+1);
}
break;
case 1:
if( x + 1 < ca.length && y + 1 < ca[0].length && p + 1 < w.length()){
c += find(ca, w, x + 1, y + 1, p+1);
}
break;
case 2:
if( y + 1 < ca[0].length && p + 1 < w.length() ){
c += find(ca, w, x, y + 1, p+1);
}
break;
}
}
}
return c;
}
}
This is a nice and elegant solution, the only (potential) problem with it I think is that its running time might be exponential in the worst case (O(n^2*3^k) to be precise).
Think about the following case: an nxn matrix consisting only from a single character 'a'. You want to find the number of appearances of the sub-string a^k (k times 'a'). Denote by f(m) the number of operations performed with each call to DFS with the sub-string a^m (m times 'a'). Then, because there is always a character match (unless the array indices are out of bounds), for every call to DFS we go through all possible movement directions and thus the total number of operations is:
f(k) = 3*f(k-1) = 3^2 * f(k-2) = ... = 3^k
It follows that each call to DFS from the main loop is O(3^k) and the overall run-time complexity is O(n^2 * 3^k).
I guess it depends on the goal of the question. If the goal is to list all the appearances of a given word then this solution is great. But if the goal is to just count the total number of appearances without the need to list all of them then, I think it can be done more efficiently with the use of more space (dynamic programming).
FindWordCount(char *word, char **matrix, int curRow, int curCol, int rows, int cols)
{
if (curRow >= rows) return 0;
if (curCol >= cols) return 0;
if (*word != matrix[curRow][curCol]) return 0;
// goto next letter in the word.
word++;
// no more letters left. we got a match.
if (*word == NULL)
return 1;
int WordCount = 0;
// go right
WordCount += FindWordCount(word, matrix, curRow+1, curCol, rows, cols);
// go down
WordCount += FindWordCount(word, matrix, curRow, curCol+1, rows, cols);
// go diag
WordCount += FindWordCount(word, matrix, curRow+1, curCol+1, rows, cols);
return WordCount;
}
I'm more familiar with C. Following is my C code:
#include <stdio.h>
#include <string.h>
int find(int row, int col, const char** matrix, int R, int C, const char* target, int index)
{
if(row >= R || col >= C) return 0;
if(matrix[row][col] == target[index]){
if(target[index+1] == '\0') return 1;
return find(row, col+1, matrix, R, C, target, index+1) +
find(row+1, col, matrix, R, C, target, index+1) +
find(row+1, col+1, matrix, R, C, target, index+1);
}
return 0;
}
int findWord(const char** matrix, int R, int C, const char* target)
{
int i, j, count = 0;
for(i = 0; i < R; ++i){
for(j = 0; j < C; ++j){
if(matrix[i][j] == target[0]){
count += find(i, j, matrix, R, C, target, 0);
}
}
}
return count;
}
int main()
{
const char* matrix[] = {
"wsrtgg",
"aachin",
"kchujj",
"ohinyq"
};
const char* target = "sachin";
printf("%s occurs %d times in the matrix\n", target,
findWord(matrix, sizeof(matrix)/sizeof(char*), strlen(matrix[0]), target)
);
return 0;
}
DP is best approach for this because there are many overlapping sub-problems.
Approach should be.
1) At each cell find the index of that character in the string to match.
a) If found, look in three direction from where you can come to this cell. i) one before cell, ii) above cell , iii) diagonally before. Now if the index equals previous value +1 update the matrix with index otherwise zero.
b) If not found just move to next matrix.
Once whole of the matrix is filled, look for all the path which can be backtrack from the full length of the string.
//There are 4 answers for the above question
#include<stdio.h>
#include<string.h>
int dfs(char **mat, int R,int C, char *search,int r,int c, int index)
{
//printf("%d %d %d\n",r,c,index);
int answer=0;
if(index==strlen(search)-1)
return 1;
if(r>=R || c>=C)
return 0;
if(mat[r+1][c]==search[index+1])
answer+=dfs(mat,R,C,search,r+1,c,index+1);
if(mat[r][c+1]==search[index+1])
answer+=dfs(mat,R,C,search,r,c+1,index+1);
if(mat[r+1][c+1]==search[index+1])
answer+=dfs(mat,R,C,search,r+1,c+1,index+1);
return answer;
}
int find_1stLetter(char **mat,int R,int C,char *search)
{
int i,j, answer=0;
for(i=0;i<R;i++)
{
for(j=0;j<C;j++)
{
if(mat[i][j]==search[0])
{
//printf("%c %c--",mat[0][0],search[0]);
//printf(".%d %d.\n",i,j);
answer+=dfs(mat,R,C,search,i,j,0);
}
}
}
return answer;
}
int main()
{
int i,j;
char *mat[]={"wsrtgg","aachin","kchujj","ohinyq"};
char search[15]={'s','a','c','h','i','n','\0'};
int answer=find_1stLetter(mat,4,6,search);
printf("\nanswer=%d\n",answer);
return 0;
}
class Count{
static int num=0;
}
public class BFSsearch {
static String find="sachin";
static char [][] matrix={
{'w','s','r','t','g','g'},
{'a','a','c','h','i','n'},
{'k','c','h','u','j','j'},
{'o','h','i','n','y','q'},
};
public static void main(String []args){
boolean flag=false;
int i=0,j = 0;
for(i=0;i<matrix.length;i++){
for(j=0;j<matrix[0].length;j++){
if(matrix[i][j]==find.charAt(0)){
flag=true;
break;
}
}
if(flag)
break;
}
findSubString(j,i,0);
System.out.println(Count.num);
}
static void findSubString(int curX,int curY,int position){
if(position==find.length()-1){
Count.num++;
return;
}
if(matrix.length+matrix[0].length-1-1-curX-curY>=find.length()-position-1){
if(curX+1<=matrix[0].length-1&&matrix[curY][curX+1]==find.charAt(position+1))
findSubString(curX+1,curY,position+1);
if(curY+1<=matrix.length-1&&matrix[curY+1][curX]==find.charAt(position+1))
findSubString(curX,curY+1,position+1);
if(curX+1<=matrix[0].length-1&&curY+1<=matrix.length-1&&matrix[curY+1][curX+1]==find.charAt(position+1) )
findSubString(curX+1,curY+1,position+1);
}
}
}
public class MatrixWord {
public static void main(String[] args) {
char[][] x = {{'w','s','r','t','g','g'},
{'a','a','c','h','i','n'},
{'k','c','h','u','j','j'},
{'o','h','i','n','y','q'}
};
String word = "sachin";
int found = 0;
int wi=0;
System.out.println(x.length+" "+x[0].length);
for(int i =0;i<x.length;i++){
for(int j=0;j<x[0].length;j++){
if(x[i][j]==word.charAt(0)){
System.out.println("First char matched");
found=found+checkword(word,0,x,i,j,x.length,x[0].length);
}
}
}
System.out.println(found);
}
private static int checkword(String word,int wi, char[][] x,int i, int j, int limitfori, int limitforj) {
int found=0;
System.out.println("wi="+wi+" i="+i+" j="+j);
if(i >= limitfori || j >= limitforj) return 0;
if(word.charAt(wi)==x[i][j]){
if(wi==word.length()-1 ){
System.out.println("Found="+found);
return 1;
}
else{
found += checkword(word,wi+1,x, i+1, j, limitfori, limitforj);
found += checkword(word,wi+1,x, i, j+1, limitfori, limitforj);
found += checkword(word,wi+1,x, i+1, j+1, limitfori, limitforj);
}
}
return found;
}
}
#include<iostream>
#include<string>
#include<vector>
using namespace std;
class Occurence{
vector< vector<char> > matrix;
public:
Occurence();
int find_instances(string );
int bfs_find(string,int ,int ,int);
};
Occurence::Occurence()
:matrix{{'w','s','r','t','g','g'} ,{'a','a','c','h','i','n'} ,{'k','c','h','u','j','j'} , {'o','h','i','n','y','q'}}{}
int Occurence::find_instances(string name)
{
int c = 0;
for(int i = 0;i<matrix.size();i++)
{
for(int j=0;j<matrix[i].size();j++)
{
cout<<matrix[i][j]<<'\n';
if(name[0] == matrix[i][j])
{
c += bfs_find( name , i , j , 0 );
}
}
cout<<'\n';
}
return c;
}
int Occurence::bfs_find(string name ,int i,int j,int matched)
{
if(matched == name.size()-1)
return 1;
int c = 0;
cout<<i<<' '<<j<<'\n';
if( j+1 < matrix[i].size() && matrix[i][j+1] == name[matched+1] )
c+=bfs_find(name,i,j+1,matched+1);
if( i+1 < matrix.size() && matrix[i+1][j] == name[matched+1])
c+=bfs_find(name,i+1,j,matched+1);
if( j+1 < matrix[i].size() && i+2 < matrix.size() && matrix[i+1][j+1] == name[matched+1])
c+=bfs_find(name,i+1,j+1,matched+1);
return c;
}
int main()
{
Occurence a;
cout<<"Answer is: "<<a.find_instances("sachin")<<'\n';
}
#include<iostream>
#include<string>
#include<vector>
using namespace std;
class Occurence{
vector< vector<char> > matrix;
public:
Occurence();
int find_instances(string );
int bfs_find(string,int ,int ,int);
};
Occurence::Occurence():matrix{{'w','s','r','t','g','g'} ,
{'a','a','c','h','i','n'} ,
{'k','c','h','u','j','j'} ,
{'o','h','i','n','y','q'}}{}
int Occurence::find_instances(string name)
{
int c = 0;
for(int i = 0;i<matrix.size();i++)
{
for(int j=0;j<matrix[i].size();j++)
{
if(name[0] == matrix[i][j])
{
c += bfs_find( name , i , j , 0 );
}
}
}
return c;
}
int Occurence::bfs_find(string name ,int i,int j,int matched)
{
if(matched == name.size()-1)
return 1;
int c = 0;
if( j+1 < matrix[i].size() && matrix[i][j+1] == name[matched+1] )
c+=bfs_find(name,i,j+1,matched+1);
if( i+1 < matrix.size() && matrix[i+1][j] == name[matched+1])
c+=bfs_find(name,i+1,j,matched+1);
if( j+1 < matrix[i].size() && i+2 < matrix.size() && matrix[i+1][j+1] == name[matched+1])
c+=bfs_find(name,i+1,j+1,matched+1);
return c;
}
int main()
{
Occurence a;
cout<<"Answer is: "<<a.find_instances("sachin")<<'\n';
}
I tried to solve the problem by a DFS.
public class findWord {
static int n=4;
static int m=6;
static String[] matrix=new String[n];
static String word;
static int len;
static int ans=0;
static Step[] sa=new Step[100];
static Step step;
static void init(){
matrix[0]=new String("wsrtgg");
matrix[1]=new String("aachin");
matrix[2]=new String("kchujj");
matrix[3]=new String("ohinyq");
word=new String("sachin");
len=word.length();
System.out.println("The matrix is: ");
for(int i=0;i<n;i++) System.out.println(matrix[i]);
System.out.println("The word is: "+word);
}
static void dfs(int u,int v,int k){
if(matrix[u].charAt(v)!=word.charAt(k)) return;
step.add(v, u);
if(k==len-1){
sa[ans]=new Step(step);ans++;
step.remove();
return;
}
if(u+1<n) dfs(u+1,v,k+1);
if(v+1<m) dfs(u,v+1,k+1);
if(u+1<n&&v+1<m) dfs(u+1,v+1,k+1);
step.remove();
}
public static void main(String args[]){
init();
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
step=new Step();
dfs(i,j,0);
}
System.out.println("The number of same words is: "+ans);
for(int i=0;i<ans;i++) sa[i].out();
}
}
Dynamic program.
- initialize dp with 1 at the position where first character of the string is present
- search for every character in the matrix one by one and check i-1,j ,i,j-1 , i-1,j-1 are the character which preceeds it in the string to be searched, if yes then add its dp store. Do it for all three positions.
- At the end search whole matrix for for the last character and add the number present at corresponding position in the DP array. Complexity n^2+n^2 * L + n^2. How to optimize it
public static int findHelperDynamic(char c[][], String s) {
int dp[][] = new int[c.length][c[0].length];
int a = 1;
for (int i = 0; i < c.length; i++) {
for (int j = 0; j < c[0].length; j++) {
if (c[i][j] == s.charAt(0)) {
dp[i][j] = 1;
}
}
}
while (a < s.length()) {
System.out.println("s" + s);
for (int i = 0; i < c.length; i++) {
for (int j = 0; j < c[0].length; j++) {
if (c[i][j] == s.charAt(a)) {
if (i > 0 && c[i - 1][j] == s.charAt(a - 1)) {
dp[i][j] = dp[i][j] + dp[i - 1][j];
}
if (j > 0 && c[i][j - 1] == s.charAt(a - 1)) {
dp[i][j] = dp[i][j] + dp[i][j - 1];
}
if (i > 0 && j > 0 && c[i - 1][j - 1] == s.charAt(a - 1)) {
dp[i][j] = dp[i][j] + dp[i - 1][j - 1];
}
}
}
}
a++;
}
int count=0;
for (int i = 0; i < c.length; i++) {
for (int j = 0; j < c[0].length; j++) {
if(c[i][j]==s.charAt(s.length()-1)){
count=count+dp[i][j];
}
}
}
return count;
}
Actually, there are 4 matches for "sachin" and not 3 as the question says.
- whatevva' December 16, 2013def DFS(M, x, y, s, MatchSoFar): if x >= len(M) or y >= len(M[0]) or M[x][y] != s[0]: return 0 ## s[0] matched; if this is the only character in string ## then there is a word match if len(s) == 1: print MatchSoFar+[(x,y)] return 1 ## search in child nodes for rest of string match num_matches = 0 for (X, Y) in [(x, y+1), (x+1, y), (x+1, y+1)]: num_matches += DFS(M, X, Y, s[1:], MatchSoFar+[(x,y)]) return num_matches ## MAIN M = [ ['w' , 's' , 'r' , 't' , 'g' , 'g' ], ['a' , 'a' , 'c' , 'h' , 'i' , 'n' ], ['k' , 'c' , 'h' , 'u' , 'j' , 'j' ], ['o' , 'h' , 'i' , 'n' , 'y' , 'q' ], ] num_matches = 0 for x in range(len(M)): for y in range(len(M[0])): num_matches += DFS(M, x, y, "sachin", []) print num_matches ====== OUTPUT: [(0, 1), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5)] [(0, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 3)] [(0, 1), (1, 1), (2, 1), (2, 2), (3, 2), (3, 3)] [(0, 1), (1, 1), (2, 1), (3, 1), (3, 2), (3, 3)] 4