## Google Interview Question for Software Engineer / Developers

• 3

Country: Australia
Interview Type: Phone Interview

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

Java:

``````public class Solution {
public static void main(String... args){
char[][] map = {{ 'S', 'N', 'B', 'S', 'N' },
{ 'B', 'A', 'K', 'E', 'A' },
{ 'B', 'K', 'B', 'B', 'K' },
{ 'S', 'E', 'B', 'S', 'E' }};

System.out.println(findPath(map, "SNAKES"));
}

public static int findPath(char[][] map, String target){
int count = 0;
for(int i = 0; i < map.length ; i++){
for(int j = 0; j < map[i].length; j++){
count += findPath(map, target, i, j, 0);
}
}
return count;
}

public static int findPath(char[][] map, String target, int startX, int startY, int targetIndex){

if(startX < 0 || startY < 0 || startX >= map.length || startY >= map[startX].length){
return 0;
}

char original = map[startX][startY];

if(original != target.charAt(targetIndex))
return 0;

if(targetIndex == target.length() - 1)
return 1;

int count = 0;
map[startX][startY] = '\0';         // avoid return back to visited node

count += findPath(map, target, startX+1, startY, targetIndex+1);
count += findPath(map, target, startX, startY+1, targetIndex+1);
count += findPath(map, target, startX-1, startY, targetIndex+1);
count += findPath(map, target, startX, startY-1, targetIndex+1);

map[startX][startY] = original;
return count;
}
}``````

To compute the time complexity, we can consider the searching path a DFS 4-way tree traversal with the depth equal to the length of searched string k - 1 (root's depth is 0), so searching each tree takes O(4^(k-1)) = O(2^2(k-1)) = O(2^2k). Since each node can be a root, there will be m*n (dimension of the map) trees to search. Therefore, the general time complexity is O(m*n*2^2k). Since 2^2k grows much faster than m*n, simply O(2^2k).

If there is no turning back, it would be a 3-way tree search except that the root has 4 child nodes, but this would have little impact on the time complexity (O(4*3^(k-2)) = O(2^2k)).

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

I think, your analysis is nice, but I am pretty sure you cannot replace O(m*n*2^k ) by simply O(2^k) since. By definition, then you must be able find some constant c such that c*2^k > m*n*2^k for all n,m,k. But this is not possible since n and m are parameters that may scale up to infinity. Unless you state explicitly the correlation between k,m,n, you should not better make this kind of simplifications...

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

Using x, y is a little confusing here, perhaps better to just stay with row/col.
startRow, startCol. X most people assume would move left to right, which is really a column, and Y most people assume move top to bottom which is really a row.
Otherwise algorithm looks good.

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

``````//How many occurrences of a given search word can you find in a two-dimensional
// array of characters given that the word can go up, down, left, right,
//and around 90 degree bends?

//Ex:
//Count of occurrences of SNAKES
//S N B S N
//B A K E A
//B K B B K
//S E B S E

#include<iostream>
#include<stdlib.h>
using namespace std;

//Maximum movement allowed is equal to length of target word
int FoundWaysToMakeWord(int arr[],int i, int j,int m, int n,int index, int maxIndex,int curr[], int target[])
{
if(i == -1 || i == m)  //allowed index are upto m-1
{
return 0;
}
if(j == -1 || j == n)//allowed index are upto n-1
{
return 0;
}

if(index > maxIndex)//SNAKE max index = 4 we can fill char 0 1 2 3 4 position
{
return 0;
}

curr[index] = arr[i][j];

if(curr[index] != target[index])
{
return 0;//char mismatch found
}

if(index == maxIndex)//it mean last char also matched mean we done it
{
return 1;
}

return (FoundWaysToMakeWord(arr,i+1,j,m,n,index+1,maxIndex,curr,target) +
FoundWaysToMakeWord(arr,i-1,j,m,n,index+1,maxIndex,curr,target) +
FoundWaysToMakeWord(arr,i,j+1,m,n,index+1,maxIndex,curr,target) +
FoundWaysToMakeWord(arr,i,j-1,m,n,index+1,maxIndex,curr,target));

}

/*
//start point can be only (0,0),(m-1,0),(0,n-1),(m-1,n-1)
int FoundWaysToMakeWordUtil(int arr[],int target[], int m, int n,int length)
{
int *p = new int[length];

return FoundWaysToMakeWord(arr,0,0,m,n,0,length-1,p,target)+
FoundWaysToMakeWord(arr,0,n-1,m,n,0,length-1,p,target)+
FoundWaysToMakeWord(arr,m-1,n-1,m,n,0,length-1,p,target)+
FoundWaysToMakeWord(arr,m-1,0,m,n,0,length-1,p,target);
}
*/

int FoundWaysToMakeWordUtil(int arr[],int target[], int m, int n,int length)
{
int *p = new int[length];

int count = 0;

for(int i = 0; i < m;i++)
{
for(int j = 0; j < n; j++)
{
if(arr[i][j] == 'S')
{
count += FoundWaysToMakeWord(arr,i,j,m,n,0,length-1,p,target);
}
}
}

return count;
}

int main()
{
int p = {
{'S', 'N', 'B', 'S', 'N'},
{'B', 'A', 'K', 'E', 'A'},
{'B', 'K', 'B', 'B', 'K'},
{'S', 'E', 'B', 'S', 'E'}
};
int target[] = {'S','N','A','K','E','\0'};

cout<<FoundWaysToMakeWordUtil(p,target,4,5,5)<<endl;
}``````

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

What would be the worst case time complexity ?

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

I believe this solution doesn't work for search words that are palindromes.

Say You were searching for the word "SNAANS", and your 2D array looked
like this

SNA---
______
______

I believe your solution would find one path. This is because you are searching in
all directions regardless of the direction from which you came. If you are moving
RIGHT, you only want to move either RIGHT, UP, or DOWN, not LEFT. The case
for other directions is similar, you don't want to go back in the opposite direction.

Also, You should consider adding a table to store whether you can make the search word from a given index in p, if you were led to your index in p by a specific direction, and have seen particular number of correct characters so far. So
your map would be keyed like so

map[cur_row][cur_col][direction][curr_index]

This would greatly speed up the algorithm I believe, since you don't solve the same subproblems again.

Consider a 2D array like this

SSSSSS
SN
NAKES

There are 2 paths here
- -S
S and -N
NAKES -AKES

If you used a map as I said, once you found one of these paths, you
would store in the index corresponding to the K position that you found the string when you were heading to the LEFT and were at index 3, so once you got to
that index and checked the map, you would see a 1 stored there, and would just be able to return 1 right then and there. In this example the map is obviously not
going to give you much of a benefit, but consider if the search words were a lot
longer and you had a lot of cases of solving the same sub problems.

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

I jus want to give a brief explanation about this question since all the others just posted their code. The basic idea is to do search at each possible possition. In this example, we want to find "SNAKE", then the possible start positions are the positions where the character is "S", then you keep a visited array to avoid going back to the same position. The visited array is a little bit tricky. For example, if the matrix is :
S N B S N
B A K E A
B K B B K
S E B S E
Then you go from (0, 0) to (1, 0), to (2, 0), you visited array in these three positions are set as true, but when you discovered that (2, 0) is not a possible answer, you should reset the visited array at position (2, 0) to false immediately since you may go to it later.

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

``````#include<iostream>
using namespace std;

void RecursiveCount(int X, int Y, int Xhigh, int Yhigh, int it, char Search, int length,char Word, int *Count)
{
char c = Word[X][Y];

if( c == Search[it])
{
//cout<<X<<"--"<<Y<<"--it:"<<it<<"--length:"<<length<<endl;
if( it == length-1)
{
(*Count)++;
}
else if(it < length-1)
{
if(X-1 > -1)		RecursiveCount(X-1,Y,Xhigh,Yhigh, it+1,Search,length,Word,Count);
if(X+1 < Xhigh)		RecursiveCount(X+1,Y,Xhigh,Yhigh, it+1,Search,length,Word,Count);
if(Y-1 > -1)		RecursiveCount(X,Y-1,Xhigh,Yhigh, it+1,Search,length,Word,Count);
if(Y+1 < Xhigh)		RecursiveCount(X,Y+1,Xhigh,Yhigh, it+1,Search,length,Word,Count);

}

}

}

int main()
{
char Word = {"SNBSN","BAKEA","BKBBK","SEBSE"};
char Search = {"SNAKES"};
int length = 6;
int Count = 0;

for(int i=0;i<4;i++)
{
for(int j=0;j<5;j++)
{
if(Word[i][j] == Search[i])	RecursiveCount(i,j,5,5,0,Search,length,Word,&Count);
}
}
cout<<"No.of Occurences for the Search Word ="<<Count<<endl;

getchar();
return 0;
}``````

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

I think the complexity is O(2^N).

Can someone confirm this?

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

Confirmed working Java solution below. You also have to keep track of which nodes you've visited so far.

``````import java.util.ArrayList;

public class Boggle {

private static class Position {
public int row;
public int col;

public Position(int row, int col) {
this.row = row;
this.col = col;
}

public boolean equals(Object o) {
if (!(o instanceof Position)) return false;

Position other = (Position) o;
return (this.row == other.row) && (this.col == other.col);
}

public String toString() {
return "(" + row + "," + col + ")";
}
}

public static int wordCount(char[][] grid, String word) {
int count = 0;
Position p = new Position(0, 0);
ArrayList<Position> visited;

for (int row = 0; row < grid.length; row++) {
p.row = row;
for (int col = 0; col < grid.length; col++) {
p.col = col;

visited = new ArrayList<Position>();
count += wordCountHelper(grid, word, p, visited);
}
}
return count;
}

// number of rows = grid.length
// number of cols = grid.length

// returns the # of times we can find the word word starting at position p in the grid
public static int wordCountHelper(char[][] grid, String word, Position p, ArrayList<Position> visited) {
if (word.charAt(0) != grid[p.row][p.col]) return 0;

// if p is in the list visited, then return 0;
for (Position visited_pos : visited) {
if (p.equals(visited_pos)) return 0;
}

if (word.length() == 1) {
System.out.println(visited);
return 1;  // word.charAt(0) == grid[p.row][p.col]
}

int count = 0;
int n_visited = visited.size();

// check up
if (p.row != 0) {
Position p_next = new Position(p.row - 1, p.col);
count += wordCountHelper(grid, word.substring(1), p_next, visited);
}

// check down
if (p.row != grid.length - 1) {
Position p_next = new Position(p.row + 1, p.col);
keepFirstKPositions(visited, n_visited);
count += wordCountHelper(grid, word.substring(1), p_next, visited);
}

// check left
if (p.col != 0) {
Position p_next = new Position(p.row, p.col - 1);
keepFirstKPositions(visited, n_visited);
count += wordCountHelper(grid, word.substring(1), p_next, visited);
}

// check right
if (p.col != grid.length - 1) {
Position p_next = new Position(p.row, p.col + 1);
keepFirstKPositions(visited, n_visited);
count += wordCountHelper(grid, word.substring(1), p_next, visited);
}

return count;
}

public static void keepFirstKPositions(ArrayList<Position> list, int k) {
int size = list.size();
if (k >= size) return;

for (int i = 0; i < size - k; i++) {
int idx = size - 1 - i;
list.remove(idx);
}
}

public static void main(String[] args) {
char[][] grid = {
{'s', 'n', 'b', 's', 'n'},
{'b', 'a', 'k', 'e', 'a'},
{'b', 'k', 'b', 'b', 'k'},
{'s', 'e', 'b', 's', 'e'}
};

String word = "snakes";

System.out.println("The word " + word + " appears " + wordCount(grid, word) + " times.");
}
}``````

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

``````/*
* we need prevRow and preCol to stop going in the route we came from
*/
public static int findOccurence(char[][] a, int row, int col, String text,
int textIndex, int prevRow, int prevCol) {

//base condition
if (row < 0 || col < 0 || row >= a.length || col >= a[row].length)
return 0;
if (a[row][col] == text.charAt(textIndex) && textIndex == text.length()-1)
return 1;

int retValue = 0;

//if character matches then try to match next character by incrementing textIndex
if (a[row][col] == text.charAt(textIndex)) {
if (prevRow != row + 1 || prevCol != col)//This if condition prevents going in the route we came from
retValue += findOccurence(a, row + 1, col, text, textIndex + 1,	row, col);

if (prevRow != row || prevCol != col + 1)//This if condition prevents going in the route we came from
retValue += findOccurence(a, row, col + 1, text, textIndex + 1,row, col);

if (prevRow != row - 1 || prevCol != col)//This if condition prevents going in the route we came from
retValue += findOccurence(a, row - 1, col, text, textIndex + 1,row, col);

if (prevRow != row || prevCol != col - 1)//This if condition prevents going in the route we came from
retValue += findOccurence(a, row, col - 1, text, textIndex + 1,row, col);
}

return retValue;
}

public static void main(String[] args) {
char[][] a = { { 'S', 'N', 'B', 'S', 'N' },
{ 'B', 'A', 'K', 'E', 'A' },
{ 'B', 'K', 'B', 'B', 'K' },
{ 'S', 'E', 'B', 'S', 'E' } };

String str = "SNAKES";
int result = 0;

for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[i].length; j++)
result += findOccurence(a, i, j, str, 0, -1, -1);
}

System.out.println(result);
}
}

/**
* Time complexity: O(N^3)
* Space complexity: O(1)
*/``````

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

``````import java.util.ArrayList;
import java.util.List;

public class FindOccurences
{
private int count;
private boolean[][] visited;
private int[] dx = {0,0 ,1, -1};
private int[] dy = {1,-1,0,0 };
private String key;
private char[][] input;
private int rowCount;
private int colCount;

class Location
{
int x;
int y;
Location(int x, int y)
{
this.x = x;
this.y = y;
}
}

public int find(char[][] input, String key)
{
List<Location> locationList = findLocations(input, key.charAt(0));
visited = new boolean[input.length][input.length];
this.input = input;
this.key = key;
this.rowCount = input.length;
this.colCount = input.length;
for(Location loc : locationList)
{
List<Character> list = new ArrayList<Character>();
search(loc.x, loc.y, list, 0);
}
return count;
}

private void search(int x, int y, List<Character> arrayList, int index)
{
if (index == this.key.length()-1)
{
StringBuffer sb = new StringBuffer();
for(int i = 0 ; i < arrayList.size() ; i++)
{
sb.append(arrayList.get(i));
}
if (sb.toString().intern().equals(this.key))
{
count++;
}
return;
}
else
{
if (arrayList.get(arrayList.size()-1) != this.key.charAt(index))
{
return;
}
}

for(int i = 0 ; i < 4 ; i++)
{
if (valid(x+dx[i], y+dy[i]))
{
visited[x+dx[i]][y+dy[i]] = true;
search(x+dx[i], y+dy[i], arrayList, index+1);
visited[x+dx[i]][y+dy[i]] = false;
arrayList.remove(arrayList.size()-1);
}
}
}

private boolean valid(int i, int j)
{
return (i>= 0 && i < rowCount && j >=0 && j < colCount && visited[i][j] == false);

}

private List<Location> findLocations(char[][] input, char key)
{
List<Location> retVal = new ArrayList<Location>();
for(int i = 0 ; i < input.length ; i++)
{
for(int j = 0 ; j < input.length ; j++)
{
if (input[i][j] == key)
{
}
}
}
return retVal;
}

/**
* @param args
*/
public static void main(String[] args)
{
char[][] a = { { 'S', 'N', 'B', 'S', 'N' },
{ 'B', 'A', 'K', 'E', 'A' },
{ 'B', 'K', 'B', 'B', 'K' },
{ 'S', 'E', 'B', 'S', 'E' } };

String str = "SNAKES";
int result = new FindOccurences().find(a, str);
System.out.println(result);
}

}``````

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

Here is the code in C :)

``````#include <stdio.h>
#include <conio.h>
#include <string.h>

int row=4,col=5;

int occur(char a[],int x,int y,char targ[],int index,int n)
{
if(x<0||y<0||x>=row||y>=col)
return 0;
if(index>n)
return 0;
if(a[x][y]!=targ[index])
{
return 0;
}
if(index==strlen(targ)-1)
{
return 1;
}
return (occur(a,x,y+1,targ,index+1,n)
+occur(a,x+1,y,targ,index+1,n)
+occur(a,x-1,y,targ,index+1,n)
+occur(a,x,y-1,targ,index+1,n));

}
int count(char a[],char targ[])
{
int d=0;
for(int i=0;i<row;i++)
{
for(int j=0;j<col;j++)
{
if(a[i][j]=='S')
d+=occur(a,i,j,targ,0,strlen(targ)-1);
}
}
return d;
}

int main()
{
char a[]={{'S','N','B','S','N'},{'B','A','K','E','A'},{'B','K','B','B','K'},{'S','E','B','S','E'}};
char c[]={"SNAKES"};
printf("No of occurences are %d ",count(a,c));

}``````

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

#include "stdafx.h"
#include <iostream>

using namespace std;
int moveAndCheckRemainingString(char a[],char* c, int starttingIndex , int length, int i , int j, int arrayH, int Dir);
bool isMoveValid(int i, int j , int arrayH, int arrayL);
bool isRightBan(int Dir);
bool isLeftBan(int Dir);
bool isUpBan(int Dir);
bool isDownBan(int Dir);

int main()
{
char a[]={{'S','N','B','S','N'},{'B','A','K','E','A'},{'B','K','B','B','K'},{'S','E','B','S','E'}};
char c[]={"SNAKES"};
int i = 0;
int j = 0;
int occurance = 0;
for(;i< 4 ; i++)
for(; j< 5 ; j++)
{
if(a[i][j] == 'S')
{
occurance += moveAndCheckRemainingString(a, c, 1, 6, i, j, 4 ,-1);
}

}
cout << "occurance : " << occurance;
return 0;
}

int moveAndCheckRemainingString(char a[],char* c, int starttingIndex , int length, int i , int j, int arrayH, int Dir)
{
int occ = 0;
if(starttingIndex == length-1)
{
return 1;
}

// check right move
if(isMoveValid(i, j+1, arrayH, 5) && !isRightBan(Dir) && a[i][j+1] == c[starttingIndex])
{
occ += moveAndCheckRemainingString(a, c, starttingIndex+1, length, i, j+1, arrayH, 2);
}

// check left
if(isMoveValid(i, j-1, arrayH, 5) && !isLeftBan(Dir) && a[i][j-1] == c[starttingIndex])
{
occ += moveAndCheckRemainingString(a, c, starttingIndex+1, length, i, j+1, arrayH, 1);
}

// check Up
if(isMoveValid(i+1, j, arrayH, 5) && !isUpBan(Dir) && a[i+1][j] == c[starttingIndex])
{
occ += moveAndCheckRemainingString(a, c, starttingIndex+1, length, i+1, j, arrayH, 3);
}

// Check down
if(isMoveValid(i, j-1, arrayH, 5) && !isDownBan(Dir) &&a[i-1][j] == c[starttingIndex])
{
occ += moveAndCheckRemainingString(a, c, starttingIndex+1, length, i-1, j, arrayH, 4);
}

return occ;
}

bool isMoveValid(int i, int j , int arrayH, int arrayL)
{
return (i<arrayH) && (j < arrayL);
}

// 1 = left
// 2 = right
// 3 = up
// 4 = down
bool isRightBan(int Dir)
{
if(Dir == 1)
{
return true;
}

return false;
}

bool isLeftBan(int Dir)
{

if(Dir == 2)
{
return true;
}

return false;
}

bool isUpBan(int Dir)
{
if(Dir == 4)
{
return true;
}

return false;

}

bool isDownBan(int Dir)
{
if(Dir == 3)
{
return true;
}

return false;
}

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

``````#include<stdio.h>
#include<string.h>
int count,len;
char a,s,cc;
int m,n;
int vis;
int see;
void dfs(int i,int j){
vis[i][j]=1;
if(see==len){
count++;
return;
}
if(i-1>=0 && j>=0){
if(s[see]==a[i-1][j] && vis[i-1][j]==0){
see++;
dfs(i-1,j);
vis[i-1][j]=0;
see--;
}
}
if(i>=0 && j-1>=0){
if(s[see]==a[i][j-1] && vis[i][j-1]==0){
see++;
dfs(i,j-1);
vis[i][j-1]=0;
see--;
}
}
if(i+1>=0 && j>=0){
if(s[see]==a[i+1][j] && vis[i+1][j]==0){
see++;
dfs(i+1,j);
vis[i+1][j]=0;
see--;
}
}
if(i>=0 && j+1>=0){
if(s[see]==a[i][j+1] && vis[i][j+1]==0){
see++;
dfs(i,j+1);
vis[i][j+1]=0;
see--;
}
}
}
int main(){
scanf("%d %d",&m,&n);
count=0;
for(int i=0;i<m;i++){
scanf("%c",&cc);
for(int j=0;j<n;j++){
scanf("%c",&a[i][j]);
vis[i][j]=0;
}
}
scanf("%c",&cc);
scanf("%s",s);
len=strlen(s);
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(a[i][j]==s){
see=1;
dfs(i,j);
}
}
}
printf("%d\n",count);
return 0;
}``````

Input :
4 5
snbsn
bakea
bkbbk
sebse
snakes

Output :
3

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

Would it be easier to look for the string backwards? like.. "EKANS", that way you dont have to remember if you found "AKE" from "SNAKE" along the way if there is another "SN" next to the "A" later on.. just go from right to left till you hit every letter you want.

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

``````int EightDMove = { { 0,1},{1,0},{1,1},{0,-1},{-1,0},{-1,-1},{1,-1},{-1,1} };
#define IS_VALID_MOVE(i,j) ( i>=0 && i<4 && j>=0 && j<5 )

int countOccZigZag(char maze, int i, int j, char *in)
{
/* Yes Match found and ends here */
if(*in == '\0')
return 1;

/* yet to match something */
int sum =0;
for (int k =0 ;k<8;k++)
{   int a = i+EightDMove[k];
int b =i+EightDMove[k];
if(IS_VALID_MOVE(a,b) && maze[a][b] == *in)
{
sum += countOccZigZag(maze,a,b,in+1);
}
}
return sum;
}

void test()
{
/* Initilaize the board and text */
char p = {
{'S', 'N', 'B', 'S', 'N'},
{'B', 'A', 'K', 'E', 'A'},
{'B', 'K', 'B', 'B', 'K'},
{'S', 'E', 'B', 'S', 'E'}
};
char target[] = {'S','N','A','K','E','\0'};

/* Call the util when there is a match */
int sum =0;
for (int i=0 ;i<4;i++)
for (int j=0;j<5;j++)
if (p[i][j] == *target )
sum += countOccZigZag(p,i,j,target+1);
printf ("Count : %d",sum);
}``````

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

A bruteforce recursion based solution in java without any optimization

``````public class SnakeFinder {
public static char board[][];
public static char[] tstr;
public static int maxr, maxc;

public static void main(String args[]) {
String str[] = { "SNBSN", "BAKEA", "BKBBK", "SEBSE" };
maxr = str.length;
maxc = str.length();
board = new char[maxr][maxc];
for (int s = 0; s < str.length; s++)
board[s] = str[s].toCharArray();
tstr = "SNAKES".toCharArray();
int count = 0;
for (int r = 0; r < maxr; r++) {
for (int c = 0; c < maxc; c++) {
if (board[r][c] == tstr) {
count += find(r, c, 1);
}// if end
}// for c end
}// for r end
System.out.println(count);
}// end of main

//searches for the character targetString[i] from r, c
public static int find(int r, int c, int i) {
if (i == tstr.length)
return 1;

int count = 0;
if (r - 1 > -1 && board[r-1][c] == tstr[i])
count += find(r - 1, c, i + 1);
if (r + 1 < maxr  && board[r+1][c] == tstr[i])
count += find(r + 1, c, i + 1);
if (c - 1 > -1 && board[r][c-1] == tstr[i])
count += find(r, c - 1, i + 1);
if (c + 1 < maxc && board[r][c+1] == tstr[i])
count += find(r, c + 1, i + 1);
return count;
}

}``````

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

``````/*
How many occurrences of a given search word can you find in a two-dimensional array
of characters given that the word can go up, down, left, right, and around 90 degree bends?
*/
int findSnake(char board, int x, int y, string word, int index,
vector<pair<int,int> > path) {

int back = (int)word.size() - 1;
char letter = word[index];

// base case: out of bounds
if(x < 0 || y < 0 || x > 3 || y > 4) {
return 0;
}

if(find(path.begin(), path.end(), pair<int,int>(x,y)) != path.end()) {
return 0;
}
path.push_back(pair<int,int>(x,y));
cout << "Visit (" << x << "," << y << ")" << endl;

// base case: snake chain broken
if(board[x][y] != letter) {
return 0;
}

// base case: snake chain succeeded
if(index == back) {
return 1;
}

int count = 0;
count += findSnake(board, x+1, y, word, index+1, path);
count += findSnake(board, x, y+1, word, index+1, path);
count += findSnake(board, x-1, y, word, index+1, path);
count += findSnake(board, x, y-1, word, index+1, path);
return count;
}

int countSnakes() {
char board = {{'S','N','B','S','N'},
{'B','A','K','E','A'},
{'B','K','B','B','K'},
{'S','E','B','S','E'}};

int count = 0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 5; j++) {
vector<pair<int,int> > path;
if (board[i][j] == 'S') {
path.clear();
count += findSnake(board, i, j, "SNAKE", 0, path);
cout << "Found " << count << " snakes" << endl;
}
}
}

return count;
}``````

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

Recursion based solution in Java, that searches given word in all directions starting from every char in the input array. Tested with all possible combination, I hope it helps.

``````public static void main(String[] args) {
char inputArray[][] =
{{'S','N','B','S','N'},
{'B','A','K','E','A'},
{'B','K','B','B','K'},
{'S','E','B','S','E'}};
String wordToSearch = "SNAKE";
findWord(inputArray, wordToSearch);
}

private static void findWord(char[][] inputArray, String wordToSearch) {
//split given word to the char array
char[] givenWord = wordToSearch.toCharArray();
int countOfMatches = 0;
//find all possible word, with the same length as provided
for (int col = 0; col<inputArray.length; col++) {
for (int row = 0; row<inputArray[col].length; row++) {
//If the first chat matches the array element, start to search
int startChar = 0;
if (givenWord[startChar]==inputArray[col][row]) {
countOfMatches += findWord(inputArray, givenWord, col, row, startChar+1);
}
}
}
System.out.println(String.format("Found the word: %s %d times",
wordToSearch, countOfMatches));
}
private static int findWord(char[][] inputArray, char[] wordToSearch,
int col, int row, int startChar) {
//Check if the end of the word is reached
if(startChar<wordToSearch.length) {
int result = 0;
int[] newIndex = new int []{col,row+1};
//Try up to bottom
if (newIndex<inputArray[col].length && wordToSearch[startChar]==inputArray[col][newIndex]) {
result += findWord(inputArray, wordToSearch, newIndex, newIndex, startChar+1);
}
//Try bottom to up
newIndex = row-1;
if (newIndex>=0 && wordToSearch[startChar]==inputArray[col][newIndex]) {
result+= findWord(inputArray, wordToSearch, newIndex, newIndex, startChar+1);
}
//Reset the row
newIndex = row;
//Try right to left
newIndex = col-1;
if (newIndex>=0 && wordToSearch[startChar]==inputArray[newIndex][row]) {
result+= findWord(inputArray, wordToSearch, newIndex, newIndex, startChar+1);
}
//Try left to right
newIndex = col+1;
if (newIndex<inputArray.length && wordToSearch[startChar]==inputArray[newIndex][row]) {
result+= findWord(inputArray, wordToSearch, newIndex, newIndex, startChar+1);
}
return result;
} else {
return 1;
}
}``````

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

``````public static int countWordsInMatrix(char[][] matrix, char[] inputString) {
int col = matrix.length;
int row = matrix.length;
int count = 0;
for (int i = 0; i < row - 1; i++) {
for (int j = 0; j < col - 1; j++) {
int find = search(matrix, row, col, i, j, inputString, 0);
count += find;
}
}
return count;
}

public static int search(char[][] matrix, int row, int col, int i, int j,
char[] inputString, int matchIndex) {
if (matchIndex == inputString.length)
return 1;
if (matrix[i][j] != inputString[matchIndex])
return 0;
else {
int count = 0;
if (i + 1 < row)
count += search(matrix, row, col, i + 1, j, inputString,
matchIndex + 1);
if (j + 1 < col)
count += search(matrix, row, col, i, j + 1, inputString,
matchIndex + 1);
if (i > 1)
count += search(matrix, row, col, i - 1, j, inputString,
matchIndex + 1);
if (j > 1)
count += search(matrix, row, col, i, j - 1, inputString,
matchIndex + 1);
return count;
}``````

}

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

Since nothing is mentioned in the question, I'm assuming that each character can repeat in array can be counted multiple times for a single occurrence of a string since characters can be repeated in the string itself.

My version of code in Java

``````public class Test{
static char[][] inpArray = {{'S','N','B','S','N'},
{'B','A','K','E','A'},
{'B','K','B','B','K'},
{'S','E','B','S','E'}};

public static void main(String args[]){
String inpString = "SNAKES";
int numOccurances = 0;
for(int i = 0; i < inpArray.length; i++)
{
for(int j = 0; j < inpArray.length; j++)
{
if(inpArray[i][j] == inpString.charAt(0))
numOccurances += findNewOccurance(inpString, i, j);
}
}
System.out.println("Number of occurances of "+inpString+" is "+numOccurances);
}

public static int findNewOccurance(String inpString, int row, int col)
{
int numOccurances = 0;

if(inpString.length() == 0)
return 0;
if(inpString.length() == 1 && inpString.charAt(0) == inpArray[row][col])
return 1;
if(inpString.charAt(0) != inpArray[row][col])
return 0;
else
{
String remainingString = inpString.substring(1, inpString.length());
System.out.println(remainingString);
if(row + 1 < inpArray.length)
numOccurances += findNewOccurance(remainingString, row+1, col);
if(row - 1 >= 0)
numOccurances += findNewOccurance(remainingString, row-1, col);
if(col + 1 < inpArray.length)
numOccurances += findNewOccurance(remainingString, row, col+1);
if(col - 1 >= 0)
numOccurances += findNewOccurance(remainingString, row, col-1);
}
return numOccurances;
}
}``````

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

Is palindrome can be a compared string?

So, KOK, or LOL can be a string?

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

My implementation below in C++ allows for reusing already visited characters. It allows users to specify a matrix size, then creates and randomly populates the matrix, then asks the user for a search string, and then runs DFS without any notion of explored nodes.

As FrederichCheng mentioned, the runtime would be O(M*N*8^(k-1)) for a large matrix of size (M, N) and a search string of length k. (Imagine for example what happens when the matrix is all A's and the search string is AA... (k times).)

``````#include <iostream>
#include <stack>
#include <set>

#include <string.h>
#include <stdlib.h>
#include <time.h>

typedef std::pair<int, int> Pair;
typedef std::set<Pair> NeighborSet;

int find_wordcount_from_index(char ** arr, int M, int N, int i, int j, char const * search, NeighborSet ** neighbors)
{
if (arr[i][j] == search)
{ // proceed
if (search == 0)
{
std::cout << "Search successfully terminated at: (" << i << "," << j << ") " << std::endl;
return 1;
}

std::cout << "Exploring: (" << i << "," << j << ")" << std::endl;

int totalCount = 0;

NeighborSet n = neighbors[i][j];
typename NeighborSet::iterator it = n.begin();
std::cout << "Neighbors are: ";
for (; it != n.end(); ++it)
{
std::cout << "(" << it->first << "," << it->second << ") ";
}
std::cout << std::endl;

++search;
for (it = n.begin(); it != n.end(); ++it)
{
totalCount += find_wordcount_from_index(arr, M, N, it->first, it->second, search, neighbors);
}
--search;

}
else
{
// std::cout << "Search failure at: (" << i << "," << j << ") " << std::endl;
return 0;
}
}

int find_wordcount_in_matrix(char ** arr, int M, int N, char const * search)
{
// memoize all neighbors
NeighborSet ** neighbors = new NeighborSet*[M];
for (int i = 0; i < M; ++i)
{
neighbors[i] = new NeighborSet[N];

for (int j = 0; j < N; ++j)
{
int neighborsRows[] = {i-1, i, i+1};
int neighborsCols[] = {j-1, j, j+1};
for (int k = 0; k < 3; ++k)
{
for (int l = 0; l < 3; ++l)
{
int row = neighborsRows[k], col = neighborsCols[l];
if (row >= 0 && row < M && col >= 0 && col < N)
{
if (row == i && col == j)
{
continue;
}
neighbors[i][j].insert(std::make_pair(row, col));
}
}
}
}
}

int totalCount = 0;
for (int i = 0; i < M; ++i)
{
for (int j = 0; j < N; ++j)
{
totalCount += find_wordcount_from_index(arr, M, N, i, j, search, neighbors);
}
}

}

int main(int argc, char ** argv)
{
int M = 4;
int N = 5;

if (argc > 1)
{
M = atoi(argv);
}
if (argc > 2)
{
N = atoi(argv);
}

srand(time(NULL));

char ** arr = new char*[M];
for (int i = 0; i < M; ++i)
{
arr[i] = new char[N];
for (int j = 0; j < N; ++j)
{
char r = 'A' + rand() % 26;
arr[i][j] = r;
std::cout << r << " ";
}
std::cout << std::endl;
}

while (true)
{
std::string search;
while (search.size() == 0)
{
std::cout << "Enter search string: ";
std::cin >> search;
}

std::cout << "Searching for: " << search << std::endl;

int totalCount = find_wordcount_in_matrix(arr, M, N, search.c_str());
std::cout << "Total count is: " << totalCount << std::endl << std::endl;
}
return 0;
}``````

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

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

const int N = 5,
M = 4;

int checkNeighbor(char arr[M][N], int i, int j, char str[], int next)
{
if(next == strlen(str)) return 1;
int counter = 0;

if(arr[i - 1][j] == str[next] && i - 1 >= 0)
counter += checkNeighbor(arr, i - 1, j, str, next + 1);

if(arr[i + 1][j] == str[next] && i + 1 < M)
counter += checkNeighbor(arr, i + 1, j, str, next + 1);

if(arr[i][j - 1] == str[next] && j - 1 >= 0)
counter += checkNeighbor(arr, i, j - 1, str, next + 1);

if(arr[i][j + 1] == str[next] && j + 1 < N)
counter += checkNeighbor(arr, i, j + 1, str, next + 1);

return counter;
}

int main()
{
char arr[M][N] = {'S', 'N', 'B', 'S', 'N',
'B', 'A', 'K', 'E', 'A',
'B', 'K', 'B', 'B', 'K',
'S', 'E', 'B', 'S', 'E'},
str[] = "SNAKES";
int counter = 0;
for(int i = 0; i < M; i++)
for(int j = 0; j < N; j++)
if(arr[i][j] == str)
counter += checkNeighbor(arr, i, j, str, 1);

printf("%d\n", counter);
return 0;
}``````

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

simple dfs whenever the letter 'S' is encountered.

``````//pat is the pattern to be searched.
//m is size of pattern,n1 & n2 dimensions of the 2-D array
void dfs(int x,int y,int index)
{
if(x<0 || y<0 || x>=n1 || y>=n2){return;}
if(vis[x][y]){return;}
vis[x][y]=1;
if(v[x][y]!=pat[index] && index==m-1){return;}
if(v[x][y]==pat[index] && index==m-1){ans++;}
dfs(x+1,y,index+1);
dfs(x-1,y,index+1);
dfs(x,y+1,index+1);
dfs(x,y-1,index+1);
return;
}``````

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

// java solution

``````public class WordCounter
{
private static class Result
{
int occurrences;

public Result(int n)
{
occurrences = n;
}
}

public static int count(char[][] matrix, String s)
{
int pos;
Result r = new Result(0);

for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
pos = 0;
count(matrix, s, i, j, pos, r);
}
}

return r.occurrences;
}

private static void count(char[][] matrix, String s, int i, int j, int pos, Result r)
{
if (pos >= s.length()) return;

char c = s.charAt(pos);

if (matrix[i][j] != c) return;

if ((matrix[i][j] == c) && (pos == matrix.length - 1)) {
r.occurrences++;
return;
}

if (i < matrix.length - 1)      	count(matrix, s, i + 1, j, pos + 1, r);
if (i > 0)                      		count(matrix, s, i - 1, j, pos + 1, r);
if (j < matrix.length - 1)   	count(matrix, s, i, j + 1, pos + 1, r);
if (j > 0)					count(matrix, s, i, j - 1, pos + 1, r);
}

public static void main(String[] args)
{
char[][] matrix =   	{
{'S', 'N', 'B', 'S', 'N'},
{'B', 'A', 'K', 'E', 'A'},
{'B', 'K', 'B', 'B', 'K'},
{'S', 'E', 'B', 'S', 'E'}
};

String s = "SNAKE";
int n = count(matrix, s);

System.out.println("n = " + n);
}
}``````

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

1) Count word by using DFS from each cell
2) Java implementation of above approach

``````public static int countWord(char[][] a, String word)
{
int wordLength = word.length();
char[] current = new char[wordLength];
int row = a.length;
int col = a.length;
boolean[][] visited = new boolean[row][col];

int count = 0;

for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
if (!visited[i][j])
{
count += countWord(a, i, j, current, 0, visited, word, row, col);
}
}
}
return count;
}

private static int countWord(char[][] a, int i, int j, char[] current, int index, boolean[][] visited, String word,
int row, int col)
{
int count = 0;

if (isSafe(a, visited, i, j, row, col, index, word))
{
current[index] = a[i][j];

if (current[index] != word.charAt(index))
{
return 0;
}

if (index == word.length() - 1)
{
return 1;
}

visited[i][j] = true;

index++;

count += countWord(a, i + 1, j, current, index, visited, word, row, col);
count += countWord(a, i - 1, j, current, index, visited, word, row, col);
count += countWord(a, i, j + 1, current, index, visited, word, row, col);
count += countWord(a, i, j - 1, current, index, visited, word, row, col);

visited[i][j] = false;
}

return count;
}

private static boolean isSafe(char[][] a, boolean[][] visited, int i, int j, int row, int col, int index, String word)
{
if ((i >= 0 && i < row) && (j >= 0 && j < col) && (!visited[i][j]) && (index < word.length()))
{
return true;
}
return false;
}``````

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

``````if (!visited[i][j])
{
count += countWord(a, i, j, current, 0, visited, word, row, col);
}``````

Use this, it's more optimal

``````if (!visited[i][j] && a[i][j] == word.charAt(0))
{
count += countWord(a, i, j, current, 0, visited, word, row, col);
}``````

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

WE can use DFS here.
First Note down all the first letter position i.e. positions of 'S'. And do DFS for every S.

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

There are 4 possible paths if we can bend 90 degree, If the Matrix starts from (1,1) to (5,4), Then S(4,1) N(5,1) A(5,2) K(5,3) E(5,4) S(1,4) is also a path.

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

I guess, This can be solved in O(m*n*k) space and time using dynamic programming approach.

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.