Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
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.
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;
}
}
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;
}
}
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;
}
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;
}
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.
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);
}
}
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);
}
}
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;
}
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
}
#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;
}
/*
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;
}
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;
}
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'))
// 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') )
Create a graph of all allowed edges using the consecutive letters of word.
- Tartar January 17, 2015Then 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