Facebook Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

Create a graph of all allowed edges using the consecutive letters of word.
Then run dfs like algo starting from first letter reaching the last letter using only allowed order. If not found use the other occurrence of first letter

- Tartar January 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. (optional syntactic sugar) since 4x4=16 only ~ half letters are allowed. before work, check if each letter is allowed. complexity O(n)

2. generate array of strings with all possible words. with n*(n-1)/2 complexity there are at most 120 combinations. this step is done once, uses little space and allows for step 4.

3. sort array.

4. lookup any word with binary search in O(log n) steps.

- Nils January 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using recursion to continue looking for the string and a 2D boolean array to track of the visited indices.

import java.util.Scanner;

class Ruzzle {
	public static void main(String [] args) {
		char [][] board = {{'S', 'T', 'F', 'M'}, {'R', 'U', 'N', 'G'}, {'T', 'A', 'M', 'N'}, {'E', 'O', 'N', 'I'}};
		Scanner s = new Scanner(System.in);
		String str = s.nextLine();

		boolean [][] tracker = new boolean[4][4];
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				tracker[i][j] = false;
			}
 		}

		boolean found = false;

		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				if (board[i][j] == str.charAt(0)) {
					tracker[i][j] = true;
					if (lookForNextCharacter(board, tracker, str, i, j, 1)) {
						found = true;
						break;
					}
					tracker[i][j] = false;
				}
			}
			if (found) {
				break;
			}
		}

		if (found) {
			System.out.println("String found");
		}
		else {
			System.out.println("String not found");
		}
	}

	public static boolean lookForNextCharacter(char[][] board, boolean[][] tracker, String str, int x, int y, int index) {
		if (index == str.length()) {
			return true;
		}
		for (int i = -1; i <= 1; i++) {
			for (int j = -1; j <= 1; j++) {
				if (i != 0 || j != 0) {
					// First check is that the index should exist
					if (isIndexValid(x + i, y + j, tracker, board, str.charAt(index))) {
						tracker[x + i][y + j] = true;
						if (lookForNextCharacter(board, tracker, str, x + i, y + j, index + 1)) {
							return true;
						}
						tracker[x + 1][y + 1] = false;
					}
				}
			}
		}
		return false;
	}

	public static boolean isIndexValid(int x, int y, boolean[][] tracker, char [][] board, char chr) {
		if (x >= 0 && x < 4 && y >= 0 && y < 4 && tracker[x][y] != true && board[x][y] == chr) {
			return true;
		}
		return false;
	}
}

- Sumeet Singhal January 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Not exactly one function but it is working

public class WordGame{
	public static void main(String args[]){
		char [][]mat = {{'r','a','z','f'},{'m','p','r','g'},{'k','a','t','a'},{'w','z','a','k'}};
		
		String s = "prrg";
		boolean isIt = false;
		for(int i =0;i<4;i++){
			for(int j =0;j<4;j++){
				if(s.charAt(0) == mat[i][j]){
					int visited[][] = new int[4][4];
					visited[i][j] = 1;
					if(check(mat,visited,s,mat[i][j]+"",i,j))
						isIt = true;
				}
			}
		}		
		System.out.println(isIt);

	}

	public static boolean check(char[][]mat,int[][] visited,String toCheck,String formed,int i ,int j){
			int left,up,right,down;			
			
				left = j-1>=0 ? j-1:j;
				right =j+1<4?j+1:j;
				up = i-1>=0?i-1:i;
				down =i+1 <4?i+1:i;

				for(int k=left;k<=right;k++){
					for(int l = up;l<=down;l++){
						if(visited[k][l] ==0){
							String n = formed+mat[k][l];
							//System.out.println("new string is "+n);
							if(n.equals(toCheck))
								return true;
							if(toCheck.contains(n)){
								visited[k][l] =1;
								if(check(mat,visited,toCheck,n,k,l))
									return true;			
							}
						}
					}
				}
		return false;
	}

}

- Bond January 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

const int MAX_ROWS = 4;
const int MAX_COLS = 4;

bool InRange(int x, int y)
{
	if ((x < 0 && x >= MAX_ROWS) || (y < 0 && y >= MAX_COLS))
	{
		return false;
	}
	else
	{
		return true;
	}
}

bool IsAdjacent(char board[][MAX_COLS], int x, int y, char key, int& x1, int& y1)
{
	if (board == NULL || !InRange(x, y))
	{
		x1 = y1 = -1;
		return false;
	}
	
	int startx = x - 1;
	int starty = y - 1;
	int endx = x + 1;
	int endy = y + 1;

	for (int i = startx; i <= endx; i++)
	{
		for (int j = starty; j <= endy; j++)
		{
			if (InRange(i, j) && !(i == x && j == y) && board[i][j] == key)
			{
				x1 = i; y1 = j;
				return true;
			}
		}
	}
	return false;
}

bool FirstFound(char board[][MAX_COLS], char key, int& x, int& y)
{
	for (int i = 0; i < MAX_ROWS; i++)
	{
		for (int j = 0; j < MAX_COLS; j++)
		{
			if (board[i][j] == key)
			{
				x = i; y = j;
				return true;
			}
		}
	}
	return false;
}

bool ContainsWord(char board[][MAX_COLS], char* word)
{
	bool alreadyused[MAX_ROWS][MAX_COLS] = { false };

	int x = -1, y = -1;
	if (FirstFound(board, word[0], x, y))
	{
		alreadyused[x][y] = true;
	}
	else
	{
		return false;
	}

	int x1 = -1, y1 = -1;
	char* start = word + 1;
	while (*start != '\0')
	{
		if (IsAdjacent(board, x, y, *start, x1, y1) &&
			alreadyused[x1][y1] == false)
		{
			start++;
			x = x1; y = y1;
			alreadyused[x][y] = true;
		}
		else
		{
			return false;
		}
	}

	return true;
}

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

using standard backtracing method to solve it.

- shichaotan January 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

using standard backtracing method to solve it.

- shichaotan January 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

boolean FindWord(char[][] keyboard, int N, String word) {
    	
    	boolean[][] isVisited = new boolean[N][N];
    	for (int r=0; r<N; r++) {
    		for (int c=0; c<N; c++) {
    			isVisited[r][c] = true;
    			boolean ret = FindWordRecursive(keyboard, isVisited, N, r, c, word, 1);
    			isVisited[r][c] = false;
    			if (ret) {
    				return true;
    			}
    		}
    	}
    	
    	return false;
    }
    
    boolean FindWordRecursive(char[][] keyboard, boolean[][] isVisited, int N, int r, int c, String word, int offset) {
    	
    	if (offset == word.length()) {
    		return true;
    	}
    	
    	for (int i=-1; i<=1; i++) {
    		for (int j=-1; j<=1; j++) {
    			
    			int r1 = r+i;
    			int c1 = c+j;
    			if (r1>=0 && r1<N && c1>=0 && c1<N && !isVisited[r1][c1]) {
    				isVisited[r1][c1] = true;
    				boolean ret = FindWordRecursive(keyboard, isVisited, N, r1, c1, word, offset+1);
    				isVisited[r1][c1] = false;
    				if (ret) {
    					return true;
    				}
    			}
    		}
    	}
    	
    	return false;

}

- pavel.kogan January 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a nice question because it allows you demonstrate not only your knowledge of data structures and algorithms, but of class design as well.

The way I would implement a solution to this problem is as follows.

Let's say we create a class called WordPuzzle. We'd have a static method "of" which takes in a 2-dimensional char[][], and generates a graph of the characters. The "of" builder method will be responsible for generating this graph, and the WordPuzzle will have an instance variable which holds a reference to such a graph.

The graph would be constructed such that the children of a node is all available options of letters that we can pick from. (Upon thinking about it, a tree-forest is probably a better option here).

Finally, we'll implement

WordPuzzle#contains(String)

which will DFS through the graph and return success if it finds the word we're looking for.

- Taylor January 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

class Point {
	int i; 
	int j;
	
	public Point(int i, int j) {
		this.i = i;
		this.j = j;
	}
}

public class Wordamint {

	public static void printWords(char[][] board, HashSet<String> dictionary) {

		int rows = board.length;
		int cols = board[0].length;

		int[][] visited = new int[rows][cols];
		clear(visited);

		for (int i = 0; i < rows; i++) {
			for (int j = 0; j < cols; j++) {
				clear(visited);
				StringBuffer sol = new StringBuffer();
				//System.out.println(board[i][j]);
				traverse(board, visited, i, j, dictionary, sol);

			}
		}

	}

	private static void traverse(char[][] board, int[][] visited, int i, int j,
			HashSet<String> dictionary, StringBuffer sol) {

		int rows = board.length;
		int cols = board[0].length;
		if(!isValidIndex(i,j, rows, cols)) return;
		if(visited[i][j] == 1) return;
		
		int index = sol.length();
		sol.append(board[i][j]); // add current to the solution
		// System.out.println(sol);
		visited[i][j] = 1;

		if(dictionary.contains(sol.toString())){ System.out.println(sol);}

		
		List<Point> p = getNextPositions(i,j, rows, cols );
		for (Point curr: p){
			traverse(board, visited, curr.i, curr.j, dictionary, sol);
		}
		
		// remove current letter from the solution
		sol.deleteCharAt(index);
		visited[i][j] = 0; // remove curr visited location since curr could come from some other prefix
	}

	private static boolean isValidIndex(int i, int j, int rows, int cols) {
		if(i < 0 ) return false;
		if(i >= rows) return false;
		
		if(j < 0 ) return false;
		if(j >= cols) return false;
				
		return true;
	}

	private static List<Point> getNextPositions(int i, int j, int rows,
			int cols) {
		List<Point> p = new ArrayList<Point>();
		
		//left + right
		if(j-1 >= 0) p.add(new Point(i, j-1));
		if(j+1 < cols) p.add(new Point(i, j+1));
		
		// top + bottom
		if(i-1 >= 0) p.add(new Point(i-1, j));
		if(i+1 < rows) p.add(new Point(i+1,j));
		
		// diagonals
		if(i-1 >= 0 && j-1 >= 0) p.add(new Point(i-1, j-1));
		if(i+1 < rows && j -1 >= 0 ) p.add(new Point(i+1,j-1));
		
		if(i-1 >= 0 && j+1 < cols) p.add(new Point(i-1, j+1));
		if(i+1 < rows && j+1 <cols ) p.add(new Point(i+1,j+1));
		
		return p;
	}

	private static void clear(int[][] visited) {
		for (int[] row: visited)
		    Arrays.fill(row, 0);
	}

}

- Simply January 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.LinkedList;
import java.util.List;

public class BoggleVariant {
	char[][] c;
	int n;
	boolean visited[][];
			
	public BoggleVariant(char[][] c, int n){
		this.c = c;
		this.n = n;
		visited = new boolean[n][n];
	}
	
	void resetVisits(){
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				visited[i][j] = false;
	}
	
	/**
	 * use backtracking
	 * @param probe
	 * @return
	 */
	boolean containsString(String probe){
		char[] probeC = probe.toCharArray();
		
		boolean found = false;
		// string can start anywhere
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				resetVisits();
				found = containsString(probeC, i, j , 0);
				if(found){
					return true;
				}
			}
		}
		
		return found;
	}
	/**
	 * assume k < probeC.length
	 * also start location !visited
	 */ 
	boolean containsString(char[] probeC , int loci , int locj , int k){
		if(k >= probeC.length){
			return true;
		}
		
		//System.out.println("DEBUG " + k + " (" + loci + "," + locj + ") "+ c[loci][locj] + " " + probeC[k]);
		
		boolean solvable = false;
		
		if(c[loci][locj] == probeC[k]){
			visited[loci][locj] = true;
			
			// pre
			List<List<Integer>> next = new LinkedList<List<Integer>>();
			// valid moves (i,j) -> (i+-1,j+-1)
			if(loci+1<n && !visited[loci+1][locj]){
				List<Integer> pos = new LinkedList<Integer>();
				pos.add(loci+1); pos.add(locj);
				next.add(pos);
			}
			if(loci-1>=0 && !visited[loci-1][locj]){
				List<Integer> pos = new LinkedList<Integer>();
				pos.add(loci-1); pos.add(locj);
				next.add(pos);
			}
			if(locj+1 < n && !visited[loci][locj+1]){
				List<Integer> pos = new LinkedList<Integer>();
				pos.add(loci); pos.add(locj+1);
				next.add(pos);
			}
			if(locj-1 >= 0 && !visited[loci][locj-1]){
				List<Integer> pos = new LinkedList<Integer>();
				pos.add(loci); pos.add(locj-1);
				next.add(pos);
			}
			
			if(loci+1<n && locj+1 < n && !visited[loci+1][locj+1]){
				List<Integer> pos = new LinkedList<Integer>();
				pos.add(loci+1); pos.add(locj+1);
				next.add(pos);
			}
			if(loci+1<n && locj-1 >=0 && !visited[loci+1][locj-1]){
				List<Integer> pos = new LinkedList<Integer>();
				pos.add(loci+1); pos.add(locj-1);
				next.add(pos);
			}
			if(loci-1>=0 && locj+1 < n && !visited[loci-1][locj+1]){
				List<Integer> pos = new LinkedList<Integer>();
				pos.add(loci-1); pos.add(locj+1);
				next.add(pos);
			}
			if(loci-1>=0 && locj-1 >=0 && !visited[loci-1][locj-1]){
				List<Integer> pos = new LinkedList<Integer>();
				pos.add(loci-1); pos.add(locj-1);
				next.add(pos);
			}
			
			//System.out.println("remaining " + (probeC.length-1-k));
			
			// base
			if(k == (probeC.length-1)){
				return true;
			}
			
			if(next.size() == 0){
				return false;
			}
			
			// DFS
			for(List<Integer> neighbor : next){
				boolean canExtend = containsString(probeC, neighbor.get(0), neighbor.get(1) , k+1);
				solvable |= canExtend;
				//System.out.println("canExtend (" + loci + "," + locj + ")? " + canExtend);
				if(solvable){
					return true;
				} else {
					visited[neighbor.get(0)][neighbor.get(1)] = false;
				}
			}
			
		} else {
			return false;
		}
		
		return solvable;
	}	
	   
	   public static void main(String[] args){
		   char[][] testcase = { { 'd' , 'e' , 't' , 'e' }, 
				   { 'i', 'm', 'e', 'r' },
				   { 'n' , 'b' , 'r' , 'n' },
				   { 'a' , 't' , 'i' , 'o' }
		   	};
		   
		   BoggleVariant wrapper = new BoggleVariant(testcase, 4);
		   String probe = "determination";
		   boolean res = wrapper.containsString(probe);
		   for(int i = 0; i < 4; i++)
			   System.out.println(new String(testcase[i]));
		   System.out.println("\t" + probe + "\t" + res);
		   
	   }

}

- just_do_it February 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isWordExists(String word) {
		char[] str = word.toCharArray();
		for(int i=0; i<size; i++) {
			for(int j=0; j<size; j++) {
				if(board[i][j] == str[0]) {
					if(isWordExists(str, 0, i, j))
						return true;
				}
			}
		}
		return false;
	}
	
	private boolean isWordExists(char[] arr, int currIndex, int row, int col) {
		
		if(currIndex >= arr.length)
			return true;
		
		if(row < 0 || row >= size || col < 0 || col >=size)
			return false; 
		
		if(arr[currIndex] == board[row][col]) {
				
			// next char can be above, below, left, right, diag
			return isWordExists(arr, currIndex+1, row-1, col) || isWordExists(arr, currIndex+1, row+1, col) || isWordExists(arr, currIndex+1, row, col-1)
					|| isWordExists(arr, currIndex+1, row, col+1) || isWordExists(arr, currIndex+1, row-1, col-1) || isWordExists(arr, currIndex+1, row+1, col+1)
					|| isWordExists(arr, currIndex+1, row+1, col-1) || isWordExists(arr, currIndex+1, row-1, col+1);
			
		}
		
		return false;
	}

- Rohan February 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Similar implementation in golang:

func main() {
	arr := [4][4]uint8 { 
		{'a', 's','f', 's'},
		{'h', 'w','i', 't'},
		{'c', 't','a', 'g'},
		{'e', 'r','i', 'n'},
	}

	fmt.Println(wordExists(arr, "waits"))
	fmt.Println(wordExists(arr, "waiter"))
	fmt.Println(wordExists(arr, "swift"))
	fmt.Println(wordExists(arr, "waiting"))
}

func wordExists(arr [4][4]uint8, word string) bool {
	index := 0
	var visited [4][4]bool
	
	for i := 0 ; i < 4; i++ {
		for j := 0 ; j < 4; j++ {
			if arr[i][j] == word[index] {
				visited[i][j] = true
				if lookupNextChar(i, j, word, index + 1, visited, arr) {
					return true
				} 
				
				visited[i][j] = false
			}
		}
	}

	return false
}

func lookupNextChar(x, y int, word string, index int, visited [4][4]bool, arr [4][4]uint8) bool {
	if index == len(word) {
		return true
	}
	
	for i := x-1; i <= x+1; i++ {
		for j := y-1; j <= y+1; j++ {
			if isValidIndex(i, j) && visited[i][j] == false && arr[i][j] == word[index] {
				visited[i][j] = true
				if lookupNextChar(i, j, word, index + 1, visited, arr) {
					return true
				} 
				visited[i][j] = false
			}
		}
	}

	return false
}

func isValidIndex( i, j int) bool {
	return i >= 0 &&  i < 4 && j >= 0 && j < 4
}

- DP February 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>

bool canFormWord(char gameSlot[4][4], std::string input, int startRow, int startCol, int usedArray[4][4]) 
{
	if(input.length() == 1)
		return true;
	
	for(int i = -1; i <= 1; ++i) 
	{
		if(startRow + i < 0 || startRow + i > 3) continue;
		for (int j = -1; j <= 1; ++j) 
		{
			if(startCol + j < 0 || startCol + j > 3 || (i  == 0 && j == 0)) continue;
			if(usedArray[startRow + i][startCol + j] == 0 && gameSlot[startRow + i][startCol + j] == input[1]) 
			{
				usedArray[startRow + i][startCol + j] == 1;
				if(!canFormWord(gameSlot, input.substr(1), startRow + i, startCol + j, usedArray))
					usedArray[startRow + i][startCol + j] == 0;
				else
					return true;
			}
		}
	}
	return false;
}

int main () 
{
	char gameSlot[4][4] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p'};
	std::string input = "abcdhlpokgfjnmie";
	int usedArray [4][4] = {0};
	for(int i = 0; i < 4; ++i) 
	{
		for (int j = 0; j < 4; ++j) 
		{
			if(gameSlot[i][j] == input[0]) 
			{
				usedArray[i][j] = 1;
				if(canFormWord(gameSlot, input, i, j, usedArray))
				{
					std::cout << "Found" << std::endl;
					return 0;
				}
				else
					usedArray[i][j] = 0;
			}
		}
	}
	std::cout << "Not Found" << std::endl;

}

- c++Coder March 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*

        Find a word in matrix of letters. Use each instance of a letter only once.

        usage:
        ./a.out row1 row2 row3 row4 word

        where a1 a2 a3 a4 are four letter sequences to put in the rows of the matrix and
        "word" is th eword to search for.

        The matrix for the examples below would be:

        abcd
        efgh
        ijkl
        mnop

        e.g.

        % ./a.out abcd efgh ijkl mnop pkfa
        % search: pkfa
        % found : pkfa


        % ./a.out abcd efgh ijkl mnop pkfd
        % search: pkfd
        % not found

        Pretty straightforward.  Spread out from each letter to the surrounding letters, if you
        find something mark it as visited in a bit string and continue for as long as there are
        letters left in "word" or you can't find the next letter. Uses only counters and a 16-bit
        short on the stack.

        Compile with _trace set to follow all the action.

        It CAN be done with one routine, you just have to initially call it four times
        for all possible starting letters to work.

*/

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

int _trace = 0;

main(int argc, char **argv) {
        char *word, *start;
        unsigned short visited = 0;
        int i,j,msize;
        int col, row;
        int found = 0;
        char matrix[4][4];

       if (argc < 6) {
                printf("Not enough arguments.\n");
                exit(1);
        }
        memset(&matrix[0][0],0x00,16);
        for (i=0; i<4; i++) {
                strncpy(&matrix[i][0], argv[i+1],4);
        }
        word = argv[5];
        msize = 4;
        start = word;
        printf("search: %s\n",word);
        for (col=1; col<msize; col+=2) {
                for (row=1; row<msize; row+=2) {
                        if (_trace) {
                                printf("starting at %d %d\n",row,col);
                        }
                        found = find_word(start,matrix,row,col,msize,&visited);
                        if (found) break;
                        start = word;
                        visited = 0;
                }
                if (found) break;
        }
        if (found) {
                printf("found : %s\n",word);
        } else {
                printf("not found\n");
        }
        exit(!found);
}

int find_word(char *word, char matrix[4][4], int arg_col, int arg_row, int msize, unsigned short *visited) {
        int row,col;
        unsigned short bits = 0;
        char *start;
        if (*word == 0x00) {
                return 1;
        }
        for (col=arg_col-1; col<=arg_col+1; col++) {
                if ((col < 0) || (col >= msize)) continue;
                for (row=arg_row-1; row<=arg_row+1; row++) {
                        if ((row < 0) || (row >= msize)) continue;
                        bits = (0x01<<((col<<2)+row));
                        if (_trace) {
                                printf("%d %d %c %c %u\n",col,row,matrix[col][row],*word,!(bits & *visited));
                        }
                        if ((matrix[col][row] == *word) && !(bits & *visited) ) {
                                start = ++word;                                *visited |= bits;
                                return find_word(start, matrix, col, row, msize, visited);
                        }
                }
        }
        *visited = 0;
        return 0;
}

- commodius_vicus March 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is C++ version of solution.
This algorithm first search the location of the first character of the keyword within the board and start the DFS to find the keyword. DFS stops at the depth equal to the length of keyword.

#include<iostream>
using namespace std;

int x_move[8] = {-1,0,1,-1,1,-1,0,1};
int y_move[8] = {-1,-1,-1,0,0,1,1,1};


bool dfs(char** board, string keyword, string& cur, int len, int x, int y)
{
  bool found = false;
  if (cur.length() == keyword.length())
  {
    return (cur==keyword);
  }

  for (int i = 0; i < 8; i++)
  {
    int nx = x+ x_move[i];
    int ny = y+ y_move[i];
    if (nx>=0 && nx <len&& ny>=0 && ny<len&& cur.find(board[ny][nx])== string::npos)
    {
      cur.push_back(board[ny][nx]);
      found = dfs(board, keyword, cur, len, nx, ny);
      if (found)
        break;
      //back tracking
      cur.pop_back();
    }
  }
  return found;
}

bool find_word(char **board, string keyword, int len)
{
  bool found = false;
  for (int y = 0; y<len; y++)
  {
    for (int x = 0; x<len; x++)
    {
      if (board[y][x] == keyword[0])
      {
        string cur ="";
        cur.push_back(board[y][x]);
        if ((found = dfs(board, keyword, cur, len, x, y)))
            break;
      }
    }
 }
  return found;
}

- hankm2004 July 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Trie would be best suitable here.
Performance O(m) where m is length of string.
The only penalty here is the storage required for constructing Trie.
But I think with company like Facebook, using an extra space would not be a problem when we can get best performance.

- Ket August 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming that inputs are only alphabets. O(9*n^2) => O(n^2) solution.

class CheckWordInMatrix:

    def check(self, aMatrix:list, aWord:str):
        self.conMap = [[False for x in range(26)] for y in range(26)]
        self.containList = [False for x in range(26)]
        lenMatrix = len(aMatrix)
        for i in range(lenMatrix):
            for j in range(lenMatrix):
                idx1 = ord(aMatrix[i][j]) - ord('a')
                self.containList[idx1] = True
                for di in range(i-1,i+1+1):
                    for dj in range(j-1,j+1+1):
                        if(di >= 0 and di < lenMatrix and dj >= 0 and dj < lenMatrix):
                            idx2 = ord(aMatrix[di][dj]) - ord('a')
                            self.conMap[idx1][idx2] = True

        find = True
        preIdx = ord(aWord[0]) - ord('a')
        if self.containList[preIdx]:            
            for nextCh in aWord[1:]:
                nextIdx = ord(nextCh) - ord('a')
                if(self.conMap[preIdx][nextIdx] == False):
                    find = False
                    break
                preIdx = nextIdx
        else:
            find = False

        return find
           
    
C = CheckWordInMatrix()

aMatrix = [
    [ 'h', 'i', 'c', 'f'],
    [ 'g', 's', 'b', 'k'],
    [ 't', 'z', 't', 'v'],
    [ 'n', 'e', 'd', 'u'],
]

print(C.check(aMatrix, 'student'))
print(C.check(aMatrix, 'sick'))
print(C.check(aMatrix, 'sickn'))
print(C.check(aMatrix, 'hicfkbsgtztvuden'))

- dgsquare82 October 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// ZoomBA : Much better optimised code.
board = [ [ 'h', 'i', 'c', 'f'],
          [ 'g', 's', 'b', 'k'],
          [ 't', 'z', 't', 'v'],
          [ 'n', 'e', 'd', 'u'] ]

map = fold ( board , dict() ) -> {
  row = $.item ; row_index = $.index 
  $.partial |= dict( row ) -> { 
    [ board[row_index][$.index] , [ row_index , $.index ] ] }
}
def is_found( positions ){
    fold ( [1: #|positions| ] , [ true, true, true ] ) :: {
        #(p_r, p_c) = positions[ $.item - 1]
        #(r, c) = positions[ $.item ]
        #(h,v,d) = $.partial
        // horizontal 
        h &= ( (p_r == r ) && ( c - p_c == 1 ) ) 
        // vertical 
        v &= ( ( r - p_r == 1 ) && ( c == p_c ) ) 
        // diagonal  
        d &= ( ( r - p_r == 1 ) && ( c  - p_c == 1 ) )
        [ h, v, d] 
    } 
}

def word_exists( word ){
  if ( empty(word) ) return false
  #(positions ? e )  = list ( word.value ) -> { map[str($.item)] }
  if ( empty(positions) ) return false 
  #(h,v,d) = is_found( positions )
  ( h || v || d ) 
}
println( word_exists ( 'hi') )
println( word_exists ( 'is') )

- NoOne October 20, 2016 | 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