Google Interview Question for Software Engineer / Developers


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)).

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

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...

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

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.

- Farooq September 30, 2015 | Flag
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

//The answer is 3. 

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

//Maximum movement allowed is equal to length of target word
int FoundWaysToMakeWord(int arr[][5],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[][5],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[][5],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[4][5] = {
                   {'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;
}

- Kavita June 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What would be the worst case time complexity ?

- Nomad June 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- zach June 21, 2014 | Flag
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.

- ravio June 07, 2014 | Flag Reply
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[7], int length,char Word[4][6], 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[4][6] = {"SNBSN","BAKEA","BKBBK","SEBSE"};
	char Search[7] = {"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;
    }

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

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

Can someone confirm this?

- deepak_gta June 13, 2014 | Flag
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[0].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[0].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;
        }
        visited.add(p);

        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[0].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.");
    }
}

- Siddharth D. January 23, 2015 | Flag Reply
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)
*/

- Snigda June 07, 2014 | Flag Reply
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[0].length];
		this.input = input;
		this.key = key;
		this.rowCount = input.length;
		this.colCount = input[0].length;
		for(Location loc : locationList)
		{
			List<Character> list = new ArrayList<Character>();
			list.add(key.charAt(0));
			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]))
	    	 {
	             arrayList.add(input[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[0].length ; j++)
	    	{
	    		if (input[i][j] == key)
	    		{
	    			retVal.add(new Location(i,j));
	    		}
	    	}
	    }
        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);
	}

}

- Suman June 07, 2014 | Flag Reply
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[][5],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[][5],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[][5]={{'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));

}

- vgeek June 07, 2014 | Flag Reply
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[][5],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[][5]={{'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[][5],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;
}

- Anonymous June 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<string.h>
int count,len;
char a[100][100],s[50],cc;
int m,n;
int vis[100][100];
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[0]){
				see=1;
				dfs(i,j);
			}
		}
	}
	printf("%d\n",count);
	return 0;
}

Input :
4 5
snbsn
bakea
bkbbk
sebse
snakes

Output :
3

- for.the.sake.92 June 08, 2014 | Flag Reply
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.

- Eduardo Morales June 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int EightDMove[8][2] = { { 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[4][5], 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][0];
	    int b =i+EightDMove[k][1];
		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[4][5] = {
                   {'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);
}

- dutta.dipankar08 June 09, 2014 | Flag Reply
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[0].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[0]) {
					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;
	}

}

- Phoenix June 09, 2014 | Flag Reply
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[4][5], 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;
    }

    // base case: already visited
    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[4][5] = {{'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;
}

- allenylzhou June 11, 2014 | Flag Reply
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[1]<inputArray[col].length && wordToSearch[startChar]==inputArray[col][newIndex[1]]) {
				result += findWord(inputArray, wordToSearch, newIndex[0], newIndex[1], startChar+1);
			}
			//Try bottom to up
			newIndex[1] = row-1;
			if (newIndex[1]>=0 && wordToSearch[startChar]==inputArray[col][newIndex[1]]) {
				result+= findWord(inputArray, wordToSearch, newIndex[0], newIndex[1], startChar+1);
			}
			//Reset the row
			newIndex[1] = row;
			//Try right to left
			newIndex[0] = col-1;
			if (newIndex[0]>=0 && wordToSearch[startChar]==inputArray[newIndex[0]][row]) {
				result+= findWord(inputArray, wordToSearch, newIndex[0], newIndex[1], startChar+1);
			}
			//Try left to right
			newIndex[0] = col+1;
			if (newIndex[0]<inputArray.length && wordToSearch[startChar]==inputArray[newIndex[0]][row]) {
				result+= findWord(inputArray, wordToSearch, newIndex[0], newIndex[1], startChar+1);
			}
			return result;
		} else {
			return 1;
		}
	}

- Vitali (Germany) June 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int countWordsInMatrix(char[][] matrix, char[] inputString) {
		int col = matrix[0].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;
		}

}

- fang-l10 June 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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[0].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[0].length)
				numOccurances += findNewOccurance(remainingString, row, col+1);
			if(col - 1 >= 0)
				numOccurances += findNewOccurance(remainingString, row, col-1);
		}
		return numOccurances;
	}
}

- Nagamanoj June 15, 2014 | Flag
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?

- soodongStudying June 27, 2014 | Flag Reply
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[0])
    { // proceed
        if (search[1] == 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;
        
        return totalCount;
    }
    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);
        }
    }

    return totalCount;
}

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

    if (argc > 1)
    {
        M = atoi(argv[1]);
    }
    if (argc > 2)
    {
        N = atoi(argv[2]);
    }
    
    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;
}

- Gokul Subramanian July 16, 2014 | Flag Reply
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[0])
				counter += checkNeighbor(arr, i, j, str, 1);

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

- AndrewRadkovich July 17, 2014 | Flag Reply
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;
}

- kevseb1993 July 18, 2014 | Flag Reply
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[0].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[0].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);
    }
}

- mbyta August 13, 2014 | Flag Reply
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[0].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;
	}

- aviundefined September 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Instead of

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

- aviundefined September 14, 2014 | Flag
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.

- Anonymous October 18, 2014 | Flag Reply
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.

- Vinay December 17, 2014 | Flag Reply
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.

- Snap Dragon June 19, 2015 | Flag Reply


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