Facebook Interview Question for Software Engineer Interns


Country: United States
Interview Type: Phone Interview




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

I think the other solutions do not handle usage of the same character twice. Below is the bug free solution.

def preProcessBoard(board):
    sz = len(board)
    boardMap = {}
    for i in xrange(sz):
        for j in xrange(sz):
            if board[i][j] in boardMap:
                boardMap[board[i][j]].append(i*sz+j)
            else:
                boardMap[board[i][j]] = [i*sz+j]
    return boardMap

def getNeighbors(index,sz):
    row = index/sz
    col = index % sz
    neigs = set()
    for i in xrange(row-1,row+2):
        for j in xrange(col-1,col+2):
            if i >=0 and i<sz and j>=0 and j<sz and not (i == row and j == col):
                neigs.add(i*sz+j)
    return neigs

def isOnBoard(boardMap,word,oldPos,posList):
    if len(word) == 0:
        return True
    if word[0] not in boardMap:
        return False
    else:
        if oldPos == None:
            for pos in boardMap[word[0]]:
                posList.add(pos)
                if isOnBoard(boardMap,word[1:],pos,posList):
                    return True
                else:
                    posList.remove(pos)
        else:
            for pos in boardMap[word[0]]:
                if pos in getNeighbors(oldPos,4) and pos not in posList:
                    posList.add(pos)
                    if isOnBoard(boardMap,word[1:],pos,posList):
                        return True
                    else:
                        posList.remove(pos)
    return False           

board = [['s','m','e','f'],['r','a','t','d'],['l','o','n','i'],['k','a','f','b']]
boardMap = preProcessBoard(board)
print isOnBoard(boardMap,'afna',None,set())

- Melih March 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Well written code. Here is a cake for c++ enthusiasts, which handles multiple starting points for a given search string.

#include <iostream>
#include <deque>
#include <map>
#include <list>
#include <string>

#define rep(i,m) for(int i=0;i<(int)(m);i++)
#define rep2(i,n,m) for(int i=n;i<(int)(m);i++)

using namespace std;
void PreprocessBoard(string boggleBoard, map<char, list<int> > &prePosMap) {

	rep(i,boggleBoard.size()) 
		prePosMap[boggleBoard[i]].push_back(i);
}

void GetNeighbours(string boggleBoard,int curPosDst, map<int,bool> &neighboursMap, map<int,bool> &resultPosMap, int wd, int ht) {
	neighboursMap.clear();
	int posx = curPosDst/wd, posy = curPosDst%ht;
	rep2(i,posx-1,posx+2)
		rep2(j,posy-1,posy+2) {			
			if( (i>=0) && (j>=0) && (i < wd) && (j < ht) && (resultPosMap.find(i*wd+j) == resultPosMap.end()) ) 	{
				neighboursMap[i*wd+j] = 1;
			}
		}
}
bool _SearchBoggle(string boggleBoard, string searchStr, map<int,bool> &resultPosMap ,deque<int> &resultPosQ, int curPosSrc, int wd, int ht )
{
	if( curPosSrc == searchStr.size() )
		return true;

	int prevPosDst = resultPosQ.back();
	map<int,bool> neighboursMap;

	GetNeighbours(boggleBoard, prevPosDst, neighboursMap, resultPosMap, wd, ht);

	for(map<int,bool>::iterator it = neighboursMap.begin(); it!=neighboursMap.end(); it++ ) {
		if( boggleBoard[it->first] == searchStr[curPosSrc] ) {
			resultPosMap[it->first] = 1;
			resultPosQ.push_back(it->first);
			if( _SearchBoggle(boggleBoard, searchStr, resultPosMap ,resultPosQ, curPosSrc+1, wd, ht ) ) {
				return true;
			}
			else {
				// Backtrack :)
				resultPosMap.erase(it->first);
				resultPosQ.pop_back();
			}
		}
	}

	return false;
}
bool SearchBoggle(string boggleBoard, map<char, list<int> > &prePosMap, string searchStr, deque<int> &resultPosQ, int wd, int ht) {
	// resultPos contains the positions of the result.
	if( searchStr.size() == 0 ) 
		return false;
	map<char, list<int> >::iterator it = prePosMap.find(searchStr[0]);
	if( it == prePosMap.end() )
		return false;
	list<int> startingPositions = it->second;

	for(list<int>::iterator it = startingPositions.begin(); it!=startingPositions.end(); it++ ) {
		resultPosQ.clear();
		map<int,bool> resultPosMap; resultPosMap.clear();

		resultPosMap[*it] = 1;
		resultPosQ.push_back(*it);

		if( _SearchBoggle(boggleBoard, searchStr, resultPosMap, resultPosQ, 1, wd, ht) )
			return true;
	}
	return false;
}
int main()
{
	string boggleBoard = "SMEFRATDLONIKAFB";
	int width = 4, height = 4;
	map<char, list<int> > prePosMap;
	deque<int> resultPos;
	PreprocessBoard(boggleBoard, prePosMap);
	bool isStringPresent;
	isStringPresent = SearchBoggle(boggleBoard, prePosMap, "STAR", resultPos, width, height);
	isStringPresent = SearchBoggle(boggleBoard, prePosMap, "TONE", resultPos, width, height);
	isStringPresent = SearchBoggle(boggleBoard, prePosMap, "NOTE", resultPos, width, height);
	isStringPresent = SearchBoggle(boggleBoard, prePosMap, "SAND", resultPos, width, height);

	return 0;
}

- chetan.j9 May 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@chetan.j9 well written code.

- Psycho June 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@melith, you might want to bound 2nd for loop over number of neighbors (always<=7)rather then on positions of certain element (max bound n2). let me know if i aam wrong or any other way to optimize that function any more

- lolcoder January 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Heres a DFS implementation with a hash lookup for the first letter written in objective-c

#import <Foundation/Foundation.h>
 
@interface Node : NSObject
@property (nonatomic, strong) NSString * letter;
@property (nonatomic, strong) NSMutableSet * adjacentNodes;
@end
 
@implementation Node
-(NSMutableSet *)adjacentNodes{
    if(_adjacentNodes){
        return _adjacentNodes;
    }
    _adjacentNodes = [[NSMutableSet alloc] init];
    return _adjacentNodes;
}
@end
 
 
@interface Graph : NSObject
@property (nonatomic, strong) NSSet * nodes;
@property (nonatomic, strong) NSDictionary * lookupDictionary;
 
+(instancetype)graphForBoggleBoard:(NSArray *)board;
 
-(BOOL)searchForWord:(NSString *)word;
@end
 
@implementation Graph
 
+(instancetype)graphForBoggleBoard:(NSArray *)board{
    NSMutableSet * nodes = [[NSMutableSet alloc] init];
    NSMutableDictionary * dictionary = [NSMutableDictionary dictionary];
 
    NSMutableArray * nodeBoard = [[NSMutableArray alloc] initWithCapacity:board.count];
    for (NSArray * row in board){
        NSMutableArray * nodeRow = [[NSMutableArray alloc] initWithCapacity:row.count];
        for (NSString * letter in row){
            Node * node = [[Node alloc] init];
            node.letter = letter;
            
            [nodeRow addObject:node];
            [nodes addObject:node];
            if (dictionary[node.letter]){
                [dictionary[node.letter] addObject:node];
            }else{
                dictionary[node.letter] = @[node].mutableCopy;
            }
        }
        [nodeBoard addObject:nodeRow];
    }
 
 
    NSArray * previousRow = nil;
    for (NSInteger row = 0; row < nodeBoard.count; row++){
        NSArray * nodeRow = nodeBoard[row];
        for (NSInteger col = 0; col < nodeRow.count; col ++){
            Node * currentNode = nodeBoard[row][col];
            for (Node * node in previousRow){
                [currentNode.adjacentNodes addObject:node];
                [node.adjacentNodes addObject:currentNode];
            }
            if (col > 0){
                Node * node = nodeBoard[row][col - 1];
                [currentNode.adjacentNodes addObject:node];
                [node.adjacentNodes addObject:currentNode];
            }
        }
        previousRow = nodeRow;
    }
 
 
    Graph * graph = [[Graph alloc] init];
    graph.lookupDictionary = dictionary;
    graph.nodes = nodes;
    return graph;
}
 
BOOL depthFirstSearch(Node * node, NSString * word, NSInteger depth, NSMutableSet * visitedNodes){
 
    unichar nodeLetter = [node.letter characterAtIndex:0];
    unichar wordLetter = [word characterAtIndex:depth];
 
    [visitedNodes addObject:node];
 
    if (nodeLetter == wordLetter){
        if (depth < word.length - 1) {
            for (Node * adjacentNode in node.adjacentNodes){
                if ([visitedNodes containsObject:adjacentNode]) continue;
                BOOL found = depthFirstSearch(adjacentNode, word, depth + 1, visitedNodes);
                if (found == YES) return found;
            }
        }
        else return YES;
    }
 
    [visitedNodes removeObject:node];
    return NO;
}
 
-(BOOL)searchForWord:(NSString *)word{
    NSString * firstLetter = [NSString stringWithFormat:@"%c",[word characterAtIndex:0]];
    NSSet * firstNodes = self.lookupDictionary[firstLetter];
    for (Node * node in firstNodes){
        NSMutableSet * visitedNodes = [[NSMutableSet alloc] initWithCapacity:word.length];
        BOOL found = depthFirstSearch(node, word, 0, visitedNodes);
        if (found == YES) return YES;
    }
 
    return NO;
}
@end
 
 
int main(int argc, char *argv[]) {
    @autoreleasepool {
        NSArray * boggleBoard = @[
                                  @[@"a", @"b", @"c"],
                                  @[@"d", @"d", @"h"],
                                  @[@"e", @"i", @"u"]
                                  ];
 
        Graph * graph = [Graph graphForBoggleBoard:boggleBoard];
        NSLog (@"Word %@", [graph searchForWord:@"chuddd"] ? @"exists" : @"doesnt exist");
    }
    return 0;
}

- Joel May 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We need to build a hash for each character in the boggle board, and make a recursive search on each character of the string:

bbr1=['S', 'M', 'E','F'];
bbr2=['R', 'A', 'T','D'];
bbr3=['L', 'O', 'N','I'];
bbr4=['K', 'A', 'F','B'];

bb=[bbr1, bbr2, bbr3,bbr4];
rowmax=len(bb);
colmax=len(bb[0]);
wordPos={};
for row in range(4):
  for col in range(4):
    if bb[row][col] in wordPos.keys():
      wordPos[bb[row][col]].append([row, col]);
    else:
      wordPos[bb[row][col]]=[[row,col]];
print wordPos;
print range(-1,1);
def searchWord(pos, curPos, wordList):
  print curPos, wordList;
  if len(wordList)==0:
    return 0;
  if curPos == None:
    if wordList[0] in pos.keys():
      return searchWord(wordPos, pos[wordList[0]], wordList[1:]);
    else:
      return -1;
  else:
    for onePos in curPos:
      for h in range(-1,2):
        for v in range(-1,2):
          if h==0 and v==0:
            continue;
          row=onePos[0]+v;
          col=onePos[1]+h;
          if row < 0 or row > rowmax-1:
            continue;
          if col < 0 or col > colmax-1:
            continue;
          if bb[row][col] == wordList[0]:
            if 0==searchWord(pos,[[row, col]], wordList[1:]):
              return 0;
  return -1;


print searchWord(wordPos, None, "STAR");
print searchWord(wordPos, None, "TONE");
print searchWord(wordPos, None, "NOTE");
print searchWord(wordPos, None, "SAND");
print searchWord(wordPos, None, "AFB");
print searchWord(wordPos, None, "UU");
print searchWord(wordPos, None, "");

- chenlc626 March 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No need to build a hash for each character in the boggle board, dumb!

- Anonymous April 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@anonymous, it'll help in first search, you should not useit after that

- lolcoder January 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this is the same idea as chenic626, but I couldn't understand their code very well, so I did it myself.

import collections

def pathExists(current_coordinate, coordinates_available, letters):
   # This is our base case. If there are no letters left to check, then we
   # have successfully matched all the ones we wanted.
   if not letters:
      return True

   current_letter = letters[0]
   if current_letter not in coordinates_available:
      return False

   (current_row, current_col) = current_coordinate
   for (row_index, col_index) in coordinates_available[current_letter]:
      # If the next letter has a co-ordinate within one cells radius, continue
      # our search through it.
      if ( abs(row_index - current_row) <= 1
           and abs(col_index - current_col) <= 1 ):

         if pathExists((row_index, col_index),
                       coordinates_available,
                       letters[1:]):
            return True

   return False

def isWordInMatrix(matrix, word):
   # Create a map of letter => co-ordinate positions, noting that any given
   # letter may be in more than one cell in our grid.
   coordinates = collections.defaultdict(list)
   for row_index, row in enumerate(matrix):
      for col_index, letter in enumerate(row):
         coordinates[letter].append( (row_index, col_index) )

   # For each letter, pull up all the co-ordinates needed to construct it
   # (they're the ones we have to work with, so we call them the available
   # ones.)
   coordinates_available = {}
   for letter in word:
      coordinates_available[letter] = coordinates[letter]

   # We start our search with the first letter of the word.
   startingCoordinates = coordinates_available[word[0]]
   for coordinate in startingCoordinates:
      if pathExists(coordinate, coordinates_available, word[1:]):
         return True

   return False


# Tests.
matrix = [ [ 'S', 'M', 'E', 'F' ],
           [ 'R', 'A', 'T', 'D' ],
           [ 'L', 'O', 'N', 'I' ],
           [ 'K', 'A', 'F', 'S' ] ]

assert isWordInMatrix(matrix, 'SAND')
assert isWordInMatrix(matrix, 'NOTE')
assert not isWordInMatrix(matrix, 'STAR')
assert not isWordInMatrix(matrix, 'TONE')

assert isWordInMatrix(matrix, 'S')
assert isWordInMatrix(matrix, 'SRLKAFSIDFEMATNO')
assert not isWordInMatrix(matrix, 'SANSFAKFDI')

- jay March 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Well done, but not fully correct. The following assertions should hold, but don't with your code. You would have to implement steps that letters cant be reused.

assert not isWordInMatrix(matrix, 'FDID')
assert not isWordInMatrix(matrix, 'FFFF')

- Anonymous October 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Build a hash map keyed on position. For every letter of the word you have to find, search every adjacent position of the previous letter. For the first letter, you will have to search all positions.
This does it in O(n). Please correct me if I am wrong.

- alex March 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

For an nxn grid, it's not possible to do it in O(n), O(n^2) is minimal.

I don't understand why you're building a hashmap? Arrays are O(1) anyway, which is what your input grid will be.

- jay March 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

HashMap is the best solution, having O(n). Add all the characters as keys. Now get the string, take each letter from string and search in HashMap.

- Prashanth March 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

All you have managed to do is verify all the letters are in the word in O(n). You have *not* shown that there is a path (by traversing adjacent cells).

Your idea would say "TONE" is OK because all the letters are in the HashMap, which is incorrect, "TONE" is not a valid word (as given in the question).

- jay March 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@rfaccone
Can you please clarify how is NOTE - Yes and TONE - No as I could see all the four chars in the two words same?

- Expressions March 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

As I get it a word is in the table only if it can be created by combination of adjacent letters.
and we don't have any 'E' near 'N' to get word "TONE'

- J. March 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Words can be constructed from the letters of sequentially adjacent cubes, where "adjacent" cubes are those horizontally, vertically, and diagonally neighboring

- @Expressions March 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This doesn't handle the duplicate characters.If someone can suggest a way to handle that ?

#include <stdio.h>
#include <string.h>
#define SIZE 4
#define CHAR_SIZE 256

struct co{
	int i;
	int j;
};

struct c_r{
	struct co s[CHAR_SIZE];
	char track[CHAR_SIZE];
};
struct c_r main_;

int search(char mat[SIZE][SIZE], char c, int i, int j)
{
	/* search in top if it exists */
	if(i-1 >= 0)
		if(mat[i-1][j] == c)
			return 1;
	/* search in top right if it exists */
	if(i-1 >= 0 && j+1 < SIZE)
		if(mat[i-1][j+1] == c)
			return 1;
	/* search in top left if it exists */
	if(i-1 >= 0 && j-1 >= 0)
		if(mat[i-1][j-1] == c)
			return 1;
	/* search in current down if it exists */
	if(i+1 < SIZE)
		if(mat[i+1][j] == c)
			return 1;
	/* search in current left if it exists */
	if(j-1 >= 0)
		if(mat[i][j-1] == c)
			return 1;

	/* search in current right if it exists */
	if(j+1 < SIZE)
		if(mat[i][j+1] == c)
			return 1;
	/* search in down left if it exists */
	if(i+1 < SIZE && j-1 >= 0)
		if(mat[i+1][j-1] == c)
			return 1;
	/* search in down right if it exists */
	if(i+1 < SIZE && j+1 < SIZE)
		if(mat[i+1][j+1] == c)
			return 1;
	return 0;
}

int find_word(char mat[SIZE][SIZE], char *word, int i, int size)
{
	if(i >= size)
		return 1;
	if(main_.track[word[i] -'0'] == word[i]){
		if(i+1 >= size)
			return 1;
		if(search(mat, word[i+1], main_.s[main_.track[word[i] -'0'] - '0'].i, main_.s[main_.track[word[i] -'0'] - '0'].j)) {			
			find_word(mat, word, i+1, size);
		} else {
			return 0;			
		}
	} else {
		return 0;
	}
}

int main()
{	
	int i, j;
	char *word = {"TDIN"};
	char mat[SIZE][SIZE] = {
			       'S', 'M', 'E', 'F',
			       'R', 'A', 'T', 'D',
			       'L', 'O', 'N', 'I',
			       'K', 'Z', 'P', 'B',
				};
	for(i=0;i<SIZE;i++) {
		for(j=0;j<SIZE;j++) {
			main_.track[mat[i][j] - '0'] = mat[i][j];
			main_.s[mat[i][j] - '0'].i = i;
			main_.s[mat[i][j] - '0'].j = j;			
		}
	}	
	if(find_word(mat, word, 0, strlen(word)))
		printf("found\n");
	else
		printf("not found\n");
	return 0;
}

- aka March 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

findWord(int[][] data,char[] word){
	int k=0;//position of character in checking word.
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			if(data[i][j]==word[k]){
				if(checkWord(i,j,k++,data,words){
					System.out.println("word exists");
					break;
				}
			}
		}
	}
}
public boolean checkWord(int i,int j,int k,int[][] data,char[] word){
	if(k==words.length) return true;
	char letter=words[k];
	if(j!=3 && data[i][j+1]==letter) return checkWord(i,j++,k++,data,word);
	if(i!=3 && data[i+1][j]==letter) return checkWord(i++,j,k++,data,word);
	if(i!=3 && j!=3 && data[i+1][j+1]==letter) return checkWord(i++,j++,k++,data,word);
	if(i!=0 && data[i-1][j]==letter) return checkWord(i--,j,k++,data,word);
	if(j!=0 && data[i][j-1]==letter) return checkWord(i,j--,k++,data,word);
	if(i!=0 && j!=0 && data[i-1][j-1]==letter) return checkWord(i--,j--,k++,data,word);
	if(i!=3 && j!=0 && data[i+1][j-1]==letter) return checkWord(i++,j--,k++,data,word);
	if(i!=0 && j!=3 && data[i-1][j+1]==letter) return checkWord(i--,j++,k++,data,word);
}
time complexiy is O(N*M*K) in worst case, where N is number of rows, M is number of columns and K is length of word for which we are searching.  Please let me know for improvements since I used brute force technique here

- ajit March 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry about code formatting

- ajit March 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Time complexity is rather N*8^W where N is the number of cells (rows*columns) and W is the word length; because at every cell you have 8 options to continue and you will continue W times. You can start at N positions.

- Safi November 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public String verifyWords(String word){


char[] a={'S','M','E','F'};
char[] b={'R','A','T','D'};
char[] c={'L','O','N','I'};
char[] d={'K','A','F','B'};

int count=0;

for (int i = 0; i < word.length(); i++) {

char my=word.charAt(i);

for (int j = 0; j < a.length; j++) {

if(my==a[j]){

count=count+1;
}
}
for (int k = 0; k < b.length; k++) {

if(my==b[k]){

count=count+1;
}

} for (int L = 0; L < c.length; L++) {

if(my==c[L]){

count=count+1;
}
}
for (int M = 0; M < d.length; M++) {

if(my==d[M]){

count=count+1;
}

}
}


System.out.println("count is--->"+count);


if(count>=4){
return "Yes";
}
else{
return "NO";
}

}

- Ranjista March 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the answer in C#. This generalize into any size word and and size board (dimension mxn)

sealed class Program
    {

        static void Main(string[] args)
        {

            //S M E F 
            //R A T D 
            //L O N I 
            //K A F B 
            char[,] board = new char[4, 4];
            board[0, 0] = 's'; board[0, 1] = 'm'; board[0, 2] = 'e'; board[0, 3] = 'f';
            board[1, 0] = 'r'; board[1, 1] = 'a'; board[1, 2] = 't'; board[1, 3] = 'd';
            board[2, 0] = 'l'; board[2, 1] = 'o'; board[2, 2] = 'n'; board[2, 3] = 'i';
            board[3, 0] = 'k'; board[3, 1] = 'a'; board[3, 2] = 'f'; board[3, 3] = 'b';

            string word = "sand";
            bool value = search(board, word);
        }

       static bool search(char[,] board, string word)
        {
            for (int i = 0; i < board.GetLength(0); i++)
            {
                for (int j = 0; j < board.GetLength(1); j++)
                {
                    if (find(i, j, board, word))
                    {
                        return true;
                    }
                }
            }
            return false;
        }

        static bool find(int i, int j, char[,] board, string word)
        {
            if (word.Length == 1)
            {
                return board[i, j] == word[0];
            }

            bool v0=false,v1=false, v2=false, v3=false, v4=false, v5=false, v6=false, v7=false, v8=false;
            int m = board.GetLength(0);
            int n = board.GetLength(1);
            string part = word.Substring(1, word.Length - 1);

            v0 = board[i, j] == word[0];

            // Search the neighbourhood
            if (i > 0) { v1 = find(i - 1, j, board, part); }
            if (i > 0 && j < n - 1) { v2 = find(i - 1, j + 1, board, part); }
            if (j < n - 1) { v3 = find(i, j + 1, board, part); }
            if (i < m - 1 && j < n - 1) { v4 = find(i + 1, j + 1, board, part); }
            if (i < m - 1) { v5 = find(i + 1, j, board, part); }
            if (i < m - 1 && j > 0) { v6 = find(i + 1, j - 1, board, part); }
            if (j > 0) { v7 = find(i, j - 1, board, part); }
            if (i > 0 && j > 0) { v8 = find(i - 1, j - 1, board, part); }


            return v0 &&( v1 || v2 || v3||v4||v5||v6||v7||v8);
        }


    }

- sriwantha March 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 6 vote

Make a graph of 26 vertices and the edges representing the 8 neighbors. Note that some of the vertices would have more than 8 neighbors because the vertex character may be appearing multiple times.
Now perform BFS upto level 4 and stop when the word is found.

- manish bajpai March 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this is the best approach too, I think it's a Graph problem

- beldar.cat March 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice!

- Anonymous April 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Why would a vertex have more than 8 neighbors?

- Epic_coder May 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 votes

Wouldn't this lead to false positives? For example the word "FAME" would be found in such a graph, but it is not in the board.

How about representing the board as a graph (sixteen nodes with up to eight neighbours each), then searching for word by searching for the first letter, then doing a DFS from there. We could speed up the first letter search by constructing a MultiMap of letter->Nodes as we construct the graph.

- Andy May 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

To clarify, can we use one alphabet repeatedly? If so, LOLO is yes, otherwise LOLO is no.

- zxx714 March 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<?php
$block = array('S', 'M', 'E', 'F',
               'R', 'A', 'T', 'D',
               'L', 'O', 'N', 'I',
               'K', 'A', 'F', 'B');

$given_array = array("STAR", "TONE", "NOTE", "SAND");



foreach ($given_array as $given_str) {
    echo '<br>';
    $to_continue = FALSE;
    $pos = NULL;
    for ($j = 0; $j < strlen($given_str); $j++) {
        if (isset($pos) && $to_continue === TRUE) {
            $to_continue = false;

            $l = $pos - 1;
            $tl = $pos - 5;
            $bl = $pos + 3;

            $r = $pos + 1;
            $tr = $pos - 3;
            $br = $pos + 5;

            $t = $pos - 4;
            $b = $pos + 4;

            $places = array('l' => $l, 'tl' => $tl, 'bl' => $bl, 'r' => $r, 'tr' => $tr, 'br' => $br, 't' => $t, 'b' => $b);
            foreach ($places as $key => $place) {
                if ($block[$place] == $given_str[$j]) {
                    $pos = $place;
                    $to_continue = TRUE;
                    break;
                } else {
                    $to_continue = FALSE;
                }
            }
        } else {
            if ($j == 0) {
                for ($i = 0; $i < count($block); $i++) {
                    if ($block[$i] == $given_str[$j]) {
                        $to_continue = TRUE;
                        $pos = $i;
                        break;
                    }
                }
            } else {
                echo "$given_str: NOT FOUND";
                break;
            }
        }

        if ($j == (strlen($given_str) - 1 )) {
            if ($to_continue) {
                echo "$given_str: FOUND";
            } else {
                echo "$given_str: NOT FOUND";
            }
        }
    }
}

- nadarangel April 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we can build a trie from the board in o(n^4) which will make the search in o(n) for each query.
What do u think?

- Hitman April 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

improving this...we will get a graph data structure. Which is much better in space utilization.

- Anonymous April 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

just use a hash-map:

#include<iostream.h>
#include<conio.h>
#include<string.h>

char hash[200], a[100][100], x[10];

void create_hash(char a)
{
 if(hash[a]=='\0')
  hash[a]=a;
}

void find_match()
{
 int i, present=1;
 for(i=0;i<strlen(x);i++)
 {
  if(x[i]!=hash[x[i]])
  {
   present=0;
   break;
  }
 }
 if(present==1)
  cout<<"pattern present"<<endl;
 else
  cout<<"pattern not present"<<endl;
}

void create()
{
 int r, c, i, j;
 for(i=0;i<200;i++)
  hash[i]=NULL;
 cout<<"how many rows ? ";
 cin>>r;
 cout<<"how many cols ? ";
 cin>>c;
 cout<<"enter matrix:"<<endl;
 for(i=0;i<r;i++)
 {
  for(j=0;j<c;j++)
  {
   cin>>a[i][j];
   create_hash(a[i][j]);
  }
 }
 cout<<"enter pattern: ";
 cin>>x;
 find_match();
}

main()
{
 clrscr();
 create();
 getch();
}

- Devang Sinha April 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

not the efficient one.

- Anonymous April 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a solution, precompiling the boggle with a Trie and then doing the search in O(n).

import java.util.*;
import java.lang.*;

class Main
{
	static String[]boggle=new String []{
          "SMEF",
	  "RATD",
          "LONI",
	  "KAFB"};
	static String[]search=new String[]{
		"STAR",
		"TONE",
		"NOTE",
		"SAND"};
	public static void main (String[] args) throws java.lang.Exception
	{
		
		Trie t = processBoggle(boggle);
		for(String w: search){
			System.out.println(w+":"+t.contains(w));
		}
	}
	static Trie processBoggle(String[]boggle){
		Trie t = new Trie();
		for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			dfs(i,j,boggle,"",t);
		}
		}
		return t;
	}
	static boolean inBoard(int i,int j){
		return i>=0 && i < 4 && j >= 0 && j < 4;
	}
	static void dfs(int i,int j, String[]boggle, String curr, Trie t){
		if (!inBoard(i,j)) return;
		if (visited[i][j]) return;
                visited[i][j]=true;
		curr = curr+boggle[i].charAt(j);
		if (curr.length()==4){
			t.insert(curr);
		} else {
			for(int d=0;d<8;d++){
				dfs(i+dx[d],j+dy[d],boggle, curr, t);
			}
		}
                visited[i][j]=false;
	}
	static boolean [][]visited=new boolean[4][4];
	static int [] dx = new int[]{-1,-1,-1, 0,0, 1,1,1};
	static int [] dy = new int[]{-1, 0, 1,-1,1,-1,0,1};
}
class Trie{
	boolean isWord = false;
        Trie [] children = new Trie[26];
	boolean contains(String s){
		if (s.length()==0){
			return isWord;
		} else {
			int p = s.charAt(0)-'A';
			return children[p]!=null && children[p].contains(s.substring(1));
		}
	}
	void insert(String s){
		if (s.length()==0){
			isWord = true;
		} else {
			int p = s.charAt(0)-'A';
			if (children[p]==null){
				children[p] = new Trie();
			}
			children[p].insert(s.substring(1));
		}
	}

}

- Anonymous April 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it consumes too much space.

- Anonymous April 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a javascript solution that's a bit more readable and extensible, however it is slower than some of the other solutions.

var alphabet = 'smefratdlonikafb';
var BOARD = [];
var BOARD_ROWS = 4;
var BOARD_COLS = 4;
for(var i = 0; i < BOARD_COLS; i++) {
  BOARD[i] = [];
  for(var j = 0; j < BOARD_ROWS; j++) {
    BOARD[i][j] = alphabet[0];
    alphabet = alphabet.substring(1);
  }
}

function getNearbyCells(x, y) {
  var result = [];
  if( x < BOARD_COLS-1) {
    result.push({ x: x+1, y: y });
    if( y < BOARD_ROWS-1 ) {
      result.push({ x: x+1, y: y+1 });
    }
    if( y > 0 ) {
      result.push({ x: x+1, y: y-1 });
    }
  }

  if( x > 0 ) {
    if( y < BOARD_ROWS-1) {
      result.push({ x: x-1, y: y+1 });
    }
    result.push({ x: x-1, y: y });
    if( y > 0 ) {
      result.push({ x: x-1, y: y-1 });
    }
  }

  if( y < BOARD_ROWS-1 ) {
    result.push({ x: x, y: y+1 });
  }
  if( y > 0 ) {
    result.push({ x: x, y: y-1 });
  }

  return result;
}

// Returns the location of the letter or false if it could not be found
function findLetter(x, y, l) {
  var nearbyCells = getNearbyCells(x, y)
  for( var i = 0; i < nearbyCells.length; i++ ) {
    var position = nearbyCells[i];
    if( BOARD[position.x][position.y] === l ) {
      return {
        x: position.x,
        y: position.y
      };
    }
  }
  return false;
}

function searchForWord(x, y, word) {
  var l = {x:x, y:y};
  for( var i = 0; i < word.length; i++ ) {
    var letter = word[i];
    l = findLetter(l.x, l.y, letter);

    if( !l ) {
      return false;
    }
  }
  return true;
}

function hasWord(word) {
  // See if the first letter exists by searching the entire board
  var firstLetter = word[0];
  word = word.substring(1);
  var possibleStartLocations = [];
  for(var i = 0; i < BOARD_COLS; i++) {
    for(var j = 0; j < BOARD_ROWS; j++) {
      if(BOARD[i][j] === firstLetter) {
        possibleStartLocations.push({
          x: i,
          y: j
        });
      }
    }
  }

  // Starting from all the possible start locations, find the word
  for( var i = 0; i < possibleStartLocations.length; i++ ) {
    var p = possibleStartLocations[i];
    var canFindWord = searchForWord(p.x, p.y, word);
    if(canFindWord) {
      return true;
    }
  }
  return false;
}

- overload119 May 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Working PHP code

function boggle($word)
{
	$bb = array(array('s', 'm', 'e', 'f'),
				array('r', 'a', 't', 'd'),
				array('l', 'o', 'n', 'i'),
				array('k', 'a', 'f', 'b'));

	$warr = str_split($word);
	$k = 0;
	for($i = 0; $i < count($bb[0]); $i++)
		for($j = 0; $j < count($bb); $j++)
	 {
	 	if($warr[0] == $bb[$i][$j])
	 	{
	 		$visited[$i][$j] = true;
	 		return check($bb, $i, $j, $warr,0, $visited );
	 	}
	 }
}

function check($bb,$i, $j, $warr, $curIndex, $visited)
{
	print "$i, $j\n";
	$n = 4;
	$dx = array(0, 1, 1, 1, 0, -1, -1, -1);
	$dy = array(1, 1, 0, -1, -1, -1, 0, 1);
	
	if($curIndex == 3)
	{
		return true;
	}
	
	for($d = 0; $d<8; $d++)
	{
		$newi = $i + $dx[$d];
		$newj = $j + $dy[$d];
		
		if($newi >= 0 && $newi < $n && $newj >=0 && $newj < $n && !$visited[$newi][$newj]
				&& $warr[$curIndex + 1]  == $bb[$newi][$newj])
		{
			++$curIndex;
			$visited[$newi][$newj] = true;
			
			$ret = check($bb, $newi, $newj, $warr, $curIndex, $visited);
			if($ret)
				break;
			
			--$curIndex;
			$visited[$newi][$newj] = false;
			print $curIndex;
			print $warr[$curIndex];
			print_r ($visited);
		}
		
	}
}

print boggle("smef);

- Jack Harper May 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Most solutions proposed here are overly complicated. This is just a simple recursion question. write a top down solution. if a character matches then try to match the next character in the 8 characters around.. here's a simple approch

char board[4][4] = { 'S', 'M', 'E', 'F',
'R', 'A', 'T', 'D',
'L', 'O', 'N', 'I',
'K', 'A', 'F', 'B' } ;

bool matchword(char*in, int x, int y)
{
bool match = false;
if (*in == '\0')
return true;

int newX;
int newY;
for ( int i = -1; i <=1; i++)
{
for (int j = -1; j <=1; j++)
{
newX = x+i;
newY = y+j;
if (newX < 0 || newX > 4) newX = x;
if (newY < 0 || newY > 4) newY = y;

if (board[newX][newY] == *in)
match = matchword(in+1, newX, newY);
}
}
return match;
}

bool matchword(char* in)
{
bool match = false;
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
if (board[i][j] == *in)
match = matchword(in+1, i, j);
}
}
return match;
}

void main (int argc, char** argv)
{
char* array[]={ "STAR", "TONE", "NOTE", "SAND" };
for (int i = 0; i < 4; i++)
{
char* res;
if (matchword(array[i]))
res = "YES";
else
res = "NO";
cout<<array[i]<<"-"<<res<<endl;
}
_getch();
}

- Sameep June 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

looking for BANANA with

BANQ
QQQQ
QQQQ
QQQQ

will yield true, while it should not.

- Anonymous June 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we can use BST to solve this problem by having another one variable to keep the count of each character.
Since the word contains only four characters.so we can use four variables to keep track of the count while searching for given word..

For eg:

when we search for the word STARS
let us assume BST contains count for S-1,T-3,A-2,R-1.
first we will check S in BST and store the count in a variable by decrementing one.now the count will become zero.when we search for S at the end of the string ,before that we search the count variable..Now count for char S will be 0..So the given word doest exist..
Its enough to form a BST with 26 different letters[a-z] at the maximum..if each char occurs at any no of time we can have count variable..

- Baladhandapani June 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I found another one solution to this problem.The idea is take each character from 4*4 matrix and compare it with the all character of the given word to search.

if matches then replace that char in the given word to 0 0r some other special char.
and also have a count variable which incremented by one for each char matches..
If the count be 4 and all the char in the given word is replaced by 0.
then given word found in the matrix.

- Baladhandapani June 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's a recursive solution in Java :

public class Board {
	static char [] word;
	static char [][] board;
	public static boolean inBoard(char [][] inBoard, String inWord){
		board = inBoard;
		word = inWord.toCharArray();
		for(int i=0;i<4;i++)
			for(int j=0;j<4;j++)
				if(inBoardAux(i,j,0))
					return true;
		return false;
	}
	
	public static boolean inBoardAux(int i, int j, int start){
		if(board[i][j]!=word[start])
			return false;
		else if(start==word.length-1)
			return true;
		
		for(int k=i-1;k<=i+1;k++)
			for(int l=j-1;l<=j+1;l++)
				if((k!=i || l!=j) && 0<=k && k<4 && 0<=l && l<4 ){
					if(inBoardAux(k,l,start+1))
						return true;
				}
		return false;
	}
	
	public static void main(String [] args){
		char [][] tBoard = {{'s','m','e','f'},{'r','a','t','d'},{'l','o','n','i'},{'s','m','e','f'}};
		System.out.println(inBoard(tBoard, "sand"));
	}
}

- TonyStack June 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I you don't want to be able to use the same cell of the board twice, you can give as a parameter to inBoardAux a matrix of boolean values representing the already visited cells. The algorithm can also be improved with memoization or dynamic programming easily.

- TonyStack June 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
 * Given an virtual 4x4 boggle board, and some 4 letter words, determine if the words are in the board 
 * ex. 
 * 
 * S M E F 
 * R A T D 
 * L O N I 
 * K A F B 
 * 
 * STAR- no 
 * TONE- no 
 * NOTE- yes 
 * SAND- yes 
 * etc.
 * @author patrick
 *
 */
public class Board {


	
	public static void main(String[] args) {
		char[][] board = new char[][]{
				{'S','M','E','F'},
				{'R','A','T','D'},
				{'L','O','N','I'},
				{'K','A','F','B'}
		};
		
		String[] words = new String[] {"STAR", "TONE", "NOTE", "SAND"};
		
		for(String word : words) {
			char[] letters = word.toCharArray();
			Coordinate[] starters = find(board, letters[0]);
			boolean found = false;
			for(Coordinate starter : starters) {
				if(boggleHelper(board, letters, 1, starter, null)) {
					System.out.println(word + " - YES");
					found = true;
					break;
				}
			}
			
			if(!found) {
				System.out.println(word + " - NO");
			}
			
			
		}
	}
	
	private static boolean boggleHelper(char[][] board, char[] word, int index, Coordinate current, Coordinate origin) {
		if(index >= word.length) {
			return true;
		}
		Coordinate[] neighbors = findNeighbors(board, current, origin);
		for(Coordinate neighbor : neighbors) {
			if(board[neighbor.y][neighbor.x] == word[index]) {
				if(boggleHelper(board, word, index+1, neighbor, current)) {
					return true;
				}
			}
		}
		
		return false;
	}
	
	public static Coordinate[] findNeighbors(char[][] board, Coordinate current, Coordinate origin) {
		
		Coordinate[] all = new Coordinate[] {
			new Coordinate(current.y+1, current.x-1),
			new Coordinate(current.y+1, current.x),
			new Coordinate(current.y+1, current.x+1),
			new Coordinate(current.y, current.x-1),
			new Coordinate(current.y, current.x+1),
			new Coordinate(current.y-1, current.x-1),
			new Coordinate(current.y-1, current.x),
			new Coordinate(current.y-1, current.x+1)
			};
		
		List<Coordinate> result = new ArrayList<Coordinate>(all.length);
		
		for(Coordinate c : all) {
			if(c.y >=0 && c.y<4 && c.x>=0 && c.x<4 && !c.equals(origin)) {
				result.add(c);
			}
		}
		
		return result.toArray(new Coordinate[result.size()]);
	}
	
	private static Coordinate[] find(char[][] board, char c) {
		List<Coordinate> results = new LinkedList<Coordinate>();
		for(int y=0; y<4; y++) {
			for(int x=0; x<4;x++) {
				if(board[y][x] == c) {
					results.add(new Coordinate(y, x));
				}
			}
		}
		return results.toArray(new Coordinate[results.size()]);
	}
}

public class Coordinate {
	public int x;
	public int y;
	
	public Coordinate() {}
	public Coordinate(int y, int x) {
		this.x = x;
		this.y = y;
	}
	
	@Override
	public boolean equals(Object obj) {
		if(obj instanceof Coordinate) {
			Coordinate c = (Coordinate)obj;
			return this.x == c.x && this.y == c.y;
		}
		return false;
	}
	
	@Override
	public int hashCode() {
		return y*10 + x;
	}
}

- diloreto.p June 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

using System;
using System.IO;
using System.Collections.Generic;

class FaceBook
{
public static void Main(){
char[][] board=new char[][]{
new char[]{'S','M','E','F'},
new char[]{'R','A','T','D'},
new char[]{'L','O','N','I'},
new char[]{'K','A','F','B'}
};


BoggleBoard _4x4Board=new BoggleBoard(board);


Console.WriteLine("STAR:{0}", _4x4Board.Match("STAR"));
Console.WriteLine("TONE:{0}", _4x4Board.Match("TONE"));
Console.WriteLine("NOTE:{0}", _4x4Board.Match("NOTE"));
Console.WriteLine("SAND:{0}", _4x4Board.Match("SAND"));

}

public class BoggleBoard
{
public Dictionary<int,char> listBorad=new Dictionary<int,char>();

List<List<int>> foundList=new List<List<int>>();
HashSet<int> setOKLoc =new HashSet<int>();
HashSet<int> foundLoc =new HashSet<int>();

private char[][] board;

public BoggleBoard(char[][] board1)
{
this.board=board1;
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
{
listBorad.Add((i*4)+j+1,board[i][j]);

}

}

public bool Match(string input){
setOKLoc.Clear();
foundList.Clear();
foundLoc.Clear();
for(int i=0;i<input.Length;i++)
{

int loc=0;
if(Find(input[i],out loc))
{
generateNighbure(loc);
if(i!=0 && !IsNighbour(loc))
return false;

}
}

return true;
}

private bool Find(char chr,out int loc){
loc=-1;
foreach(var pair in listBorad)
{
if(pair.Value==chr){

if(foundLoc.Add(pair.Key))
{
loc=pair.Key;
return true;
}

}
}

return false;
}

private void generateNighbure(int loc)
{
int[] nighbours={1,4};
int temp=0;
for(int i=0;i<=1;i++)
{
temp=loc+nighbours[i];
if(temp>0 && temp<=16)
{
setOKLoc.Add(temp);
}
temp=loc-nighbours[i];
if(temp>0 && temp<=16)
{
setOKLoc.Add(temp);
}
}

}

private bool IsInFoundList(int i,int j)
{
foreach(var l in foundList)
{
if (l[0]==i && l[1]==j )
return true;

}
return false;
}



private bool IsNighbour(int newLoc)
{
foreach(var item in setOKLoc){
if(item==newLoc)
return true;

}
return false;

}
}

}

- Mohammad July 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>

using namespace std;


bool check(vector<vector<char> > v,string str){

for(int i=0;i<v.size();i++){
for(int j=0;j<v[i].size();j++){
int index=0;
stack<int> stkx;
stack<int> stky;

stkx.push(i);
stky.push(j);

while(!stkx.empty()){
int x = stkx.top();
int y = stky.top();

stkx.pop();
stky.pop();
// cout<<i<<" "<<j<<endl;
if(v[x][y]==str[index]){
//cout<<v[x][y]<<endl;
index++;
//we got out letter..lets apply dfs here
for(int k=-1;k<2;k++){
for(int l=-1;l<2;l++){
if(k==0 && l==0){}
else{
if(x+k>=0 && x+k<4 && y+l>=0 && y+l<4 && v[x+k][y+l]==str[index]){
stkx.push(x+k);
stky.push(y+l);
}
}
}
}

if(index == str.length())
return true;
}
}
}
}

return false;
}


int main(){
vector<vector<char> > v;

for(int i=0;i<4;i++){
vector<char> temp;
for(int j=0;j<4;j++){
char x;
cin>>x;
temp.push_back(x);
}
v.push_back(temp);
}

int n;
do{
string str;
cin>>str;

if(check(v,str))
cout<<"This word is in board"<<endl;
else
cout<<"This word is not in board"<<endl;
}while(1);
return 0;
}

- Rohit July 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Ruby implementation:

#!/usr/bin/ruby
#
require 'pp'

# Find a character on the boggle board
#
# ==== Attributes
#
# boggle: the board
# char: The char we want to find
# 
# ==== Return
#
# Returns a hash with the position or nil if it is not found
#
# { :x => 0, :y => 0 } 

def find_char boggle, char 

  boggle.each_with_index do |row,row_num|

    if (column = row.index(char)) != nil

      return {
        :y => column,
        :x => row_num
      }

    end

  end

  return nil

end

# In two chars return true if char_a is neightbor of char_b
#
# ==== Attributes
#
# char_a,char_b: the two chars to evaluate
# 
# ==== Return
#
# true,false
# 
def are_neighbor? boggle,char_a,char_b
  pos_a = find_char boggle,char_a
  pos_b = find_char boggle,char_b

  if pos_a == nil or pos_b == nil
    return false
  end

  if pos_a[:x].between?(pos_b[:x]-1,pos_b[:x]+1) and pos_a[:y].between?(pos_b[:y]-1,pos_b[:y]+1)
    return true
  end

  return false

end

def validate_word boggle, word

    
    if find_char boggle,char == nil
      return false
    end

    if index != 0
      if not are_neighbor? boggle, word[index], word[index-1]
        return false
      end
    end
  end
  
  return true 

end

boggle = [
  ['S','M','E','F'],
  ['R','A','T','D'],
  ['L','O','N','I'],
  ['K','A','F','B'],
]

pp validate_word boggle, "STAR"
pp validate_word boggle, "TONE"
pp validate_word boggle, "NOTE"
pp validate_word boggle, "SAND"

- Anonymous August 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

By me : -)

- Juan Brein August 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

C# - iI think is the most efficient way:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication2
{
    class FindWordInBoard
    {
        public static void MainFunc()
        {
            char[][] newBoard = new char[4][];

            newBoard[0]=  new char[4]{'S','M','E','F'};
            newBoard[1] = new char[4] { 'R', 'A', 'T', 'D' };
            newBoard[2] = new char[4] { 'L', 'O', 'N', 'I' };
            newBoard[3] = new char[4] { 'K', 'A', 'F', 'B' };

            Console.WriteLine(findWordOnBoard(newBoard, "STAR"));
            Console.WriteLine(findWordOnBoard(newBoard, "TONE"));
            Console.WriteLine(findWordOnBoard(newBoard, "NOTE"));
            Console.WriteLine(findWordOnBoard(newBoard, "SAND"));

            Console.Read();
        }

        static bool findWordOnBoard(char[][] inBoard, string word)
        {
            int n = 4;
            int m = 4;
            var board=AddEdges(inBoard, n + 1, m + 1);


            char currChar = word[0];
            for (int i = 1; i < n + 1; i++)
            {
                for (int j = 1; j < m + 1; j++)
                {
                    if (currChar == board[i][j])
                    {
                        bool isFound = FindPathOnBoard(board, word.Substring(1), i, j);
                        if (isFound)
                        {
                            return true;
                        }
                    }
                }
            }
            return false;
        }

        static bool FindPathOnBoard(char[][] board, string currWord, int start_i, int start_j)
        {
            if (currWord.Length == 0)
            {
                return true;
            }
            char currChar = currWord[0];
            for (int i = -1; i < 2; i++)
            {
                for (int j = -1; j < 2; j++)
                {
                    if (board[start_i + i][start_j + j] == currChar)
                    {
                        bool isFound = FindPathOnBoard(board, currWord.Substring(1), start_i + i, start_j + j);
                        if (isFound)
                        {
                            return true;
                        }
                    }
                }
            }
            return false;

        }
        static char[][]  AddEdges(char[][] board, int n, int m)
        {
            char[][] newBoard = new char[n + 1][];
            for (int i = 0; i < n+1; ++i)
                newBoard[i] = new char[m+1];


            for (int i = 0; i < n + 1; i++)
            {
                for (int j = 0; j < m + 1; j++)
                {
                    if (j < 1 || j > m - 1 || i < 1 || i > n - 1)
                    {
                        newBoard[i][j] = '1';
                    }
                    else
                    {
                        newBoard[i][j] = board[i - 1][j - 1];
                    }
                }
            }

           return newBoard;

        }
    }
}

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

public static boolean scan(String wordToCheck) {
	    boolean flag = true;
	    int count = 0;
	    for (char character: wordToCheck.toCharArray()) {
	        for (int j=0; j<4; j++) {
	            for (int k=0; k<4; k++) {
	                if (array[j][k] == character) {
	                	count++;
	                	if (count == wordToCheck.length()) {return true;}
	                }
	            }
	        }  
	    }
	    return false;
	}

- Munsh January 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

storing the boggle board in a 2D character array.
not handling double letter words but simple enough, right?

- Munsh January 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

DFS-like solution, in which you erase the wrong path when going back the recursive calls.

public class BoggleBoard {
    public static boolean hasWord(String word, char[][] board) {
        int n = board.length;
        boolean[][] currentPath = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (findWord(word, 0, board, i, j, currentPath)) {
                    return true;
                }
            }
        }
        return false;
    }

    // If find, returns true and the path altered. Else return false, and path unaltered
    // Handles empty string cases
    private static boolean findWord(String word, int init, char[][] board, int i, int j, boolean[][] currentPath) {
        if (init == word.length()-1)
            return (board[i][j] == word.charAt(init));
        if (init >= word.length() || board[i][j] != word.charAt(init))
            return false;

        currentPath[i][j] = true;
        for (int x = i - 1; x <= i + 1; x++) {
            for (int y = j - 1; y <= j + 1; y++) {
                if (x >= 0 && x < board.length &&
                        y >= 0 && y < board.length &&
                        !currentPath[x][y] &&
                        findWord(word, init + 1, board, x, y, currentPath)) {
                    return true;
                }
            }
        }
        currentPath[i][j] = false;
        return false;
    }

    public static void main(String[] args) {
        char[][] board = {{'s','m','e','f'},{'r','a','t','d'},{'l','o','n','i'},{'k','a','f','b'}};

        System.out.println(hasWord("star", board));
        System.out.println(hasWord("tone", board));
        System.out.println(hasWord("note", board));
        System.out.println(hasWord("sand", board));
        System.out.println(hasWord("", board));
    }
}

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

public class Main
{

    public static void main(String[] args)
    {	
	char [][] board = {{'S','M','E','F'}, {'R', 'A', 'T', 'D'}, {'L', 'O', 'N', 'I'}, {'K', 'A', 'F', 'B'}};
	
	System.out.println(boardContainsWord(board, "STAR"));
	System.out.println(boardContainsWord(board, "TONE"));
	System.out.println(boardContainsWord(board, "NOTE"));
	System.out.println(boardContainsWord(board, "SAND"));
    }

    public static boolean boardContainsWord(char [][] board, String word)
    {
      HashMap<Character, Integer> map = new HashMap<Character, Integer>();
      
      for(int i = 0; i < board.length; i++)
      {
        for(int j = 0; j < board[0].length; j++)
        {
          map.put(board[i][j], i * board.length + j);
        }
      }
      
      for(int i = 0; i < word.length() - 1; i++)
      {
        Integer index = map.get(word.charAt(i));
        if(index == null || !getNeighbors(board, index).contains(word.charAt(i + 1)))
        {
          return false;
        }
      }  
      return true;
    }

    public static HashSet<Character> getNeighbors(char [][] board, int index)
    {
      final int size = board.length;
      final int row = index / size;
      final int col = index % size;
      
      HashSet<Character> set = new HashSet<Character>();
      for(int i = row - 1; i <= row + 1; i++)
      {
        for(int j = col - 1; j <= col + 1; j++)
        {
          if((i == row && j == col) || i < 0 || j < 0 || i > size - 1 || j > size - 1)
          {
            continue;
          }
          set.add(board[i][j]);
        }
      }
      return set;
    }    
}

- miro November 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I implemented this as a graph problem following a BFS scheme but not entirely BFS, here is my code in Java -

import java.io.File;
import java.util.HashMap;
import java.io.FileReader;
import java.util.ArrayList;
import java.io.IOException;
import java.io.BufferedReader;

/* this class is used to form a graph out of the input boggle matrix characters */
class BoggleGraph{
	
	// the number of vertices in the graph
	int nVertices;
	// this boolean variable holds the kind of graph one wants, directed or undirected */
	boolean isDirected;
	// this hashmap holds the adjacency list of the graph data structure
	HashMap<Character, ArrayList<Character>> adjacencyList;
	
	// this is the constructor for the class, which constructs a graph object
	public BoggleGraph(int nVertices, boolean isDirected){
		this.nVertices = nVertices;
		this.isDirected =  isDirected;
		this.adjacencyList = new HashMap<Character, ArrayList<Character>>();
	}
	
	// these functions help retrieve the fields of the graph data structure
	public int getVertices(){
		return this.nVertices;
	}
	public boolean getIsDirected(){
		return this.isDirected;
	}
	public HashMap<Character, ArrayList<Character>> getAdjacencyList(){
		return this.adjacencyList;
	}
	
	// this function helps insert an edge in a graph
	public void insertEdge(char vertex1, char vertex2, boolean isDirected){
		if(isDirected){
			if(adjacencyList.containsKey(vertex1)){
				if(!adjacencyList.get(vertex1).contains(vertex2))
					adjacencyList.get(vertex1).add(vertex2);
			}
			else{
				adjacencyList.put(vertex1, new ArrayList<Character>());
				adjacencyList.get(vertex1).add(vertex2);
			}
		}else{
			if(adjacencyList.containsKey(vertex1))
				adjacencyList.get(vertex1).add(vertex2);
			else{
				adjacencyList.put(vertex1, new ArrayList<Character>());
				adjacencyList.get(vertex1).add(vertex2);
			}
			
			insertEdge(vertex2, vertex1, true);
		}
	}
	
	// this function is used to display the graph
	public void displayGraph(){
		for(Character vertex : adjacencyList.keySet()){
			System.out.print(vertex + " : ");
			for(Character adj : adjacencyList.get(vertex))
			System.out.print(adj + " ");
			System.out.println();
		}
	}
}
public class Problem1_BoggleGameQuestion {
	
	// this function checks if a word can be formed out of the input Boggle Matrix
	public static boolean checkWord(BoggleGraph bgraph, String word){
		
		HashMap<Character, Boolean> visitedMap = new HashMap<Character, Boolean>();
		for(Character c : bgraph.getAdjacencyList().keySet())
			visitedMap.put(c, false);
		
		visitedMap.put(word.charAt(0), true);
		
		ArrayList<Character> frontier = bgraph.getAdjacencyList().get(word.charAt(0));
		
		for(int i = 1; i < word.length(); ++i){
			if(frontier.contains(word.charAt(i)) && !visitedMap.get(word.charAt(i))){
				visitedMap.put(word.charAt(i), true);
				frontier = bgraph.getAdjacencyList().get(word.charAt(i));
			}else{
				return false;
			}
		}
		
		return true;
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException{
		
		BufferedReader br = new BufferedReader(new FileReader(new File("C:/Users/ankitsablok89/Desktop/MS in Computer Science Classes/Competitive Programming/Interview Problems/BoggleGame.txt")));
		int dimensions = Integer.parseInt(br.readLine());
		char[][] boggleBoard = new char[dimensions][dimensions];
		for(int i = 0; i < dimensions; ++i){
			for(int j = 0; j < dimensions; ++j){
				boggleBoard[i][j] = br.readLine().charAt(0);
			}
		}
		
		BoggleGraph bgraph = new BoggleGraph(dimensions*dimensions, true);
		for(int i = 0; i < dimensions; ++i){
			for(int j = 0; j < dimensions; ++j){
				if(i-1 >= 0)
					bgraph.insertEdge(boggleBoard[i][j], boggleBoard[i-1][j], bgraph.isDirected);
				if(i+1 < dimensions)
					bgraph.insertEdge(boggleBoard[i][j], boggleBoard[i+1][j], bgraph.isDirected);
				if(j-1 >= 0)
					bgraph.insertEdge(boggleBoard[i][j], boggleBoard[i][j-1], bgraph.isDirected);
				if(j+1 < dimensions)
					bgraph.insertEdge(boggleBoard[i][j], boggleBoard[i][j+1], bgraph.isDirected);
				if(i-1 >= 0 && j-1 >= 0)
					bgraph.insertEdge(boggleBoard[i][j], boggleBoard[i-1][j-1], bgraph.isDirected);
				if(i+1 < dimensions && j-1 >= 0)
					bgraph.insertEdge(boggleBoard[i][j], boggleBoard[i+1][j-1], bgraph.isDirected);
				if(i-1 >= 0 && j+1 < dimensions)
					bgraph.insertEdge(boggleBoard[i][j], boggleBoard[i-1][j+1], bgraph.isDirected);
				if(i+1 < dimensions && j+1 < dimensions)
					bgraph.insertEdge(boggleBoard[i][j], boggleBoard[i+1][j+1], bgraph.isDirected);
			}
		}
		
		System.out.println(checkWord(bgraph, "STAR"));
		System.out.println(checkWord(bgraph, "TONE"));
		System.out.println(checkWord(bgraph, "NOTE"));
		System.out.println(checkWord(bgraph, "SAND"));
	}
}

- AnkitSablok19091989 February 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

This problem can be solved using recursion.
For each a[i][j] check if a[i][j] == word[k]
if(yes) {
go to eight neighbors and check if any of them is equal word[k+1]
} else {
return false;
}
Additionally keep track of the visited elements to avoid faulting results

- thelineofcode July 23, 2013 | 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