Facebook Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
very high complexity and you cannot make visited nodes unusable unless they are starting position even then there is problem try "fhdfck", there are two similar characters in the word so you need to keep visited nodes into loop
adding to what Soundwave said
Get a list of all the nodes which are equal to the first letter of the word.
then go through each of these instances ( refer them by their co-ord not values)
and do a BFS keeping track of the path you took. Again the key here is to use Co-Ordinates to navigate and check for cycles and not values. Just use the values at the time you want to compare against the required ones.
use a method like getAdjNodes(i,j, matrix) which returns a list if i,j as neighbors of the node you passed in.
This is just brute force method. Should exist a more efficient way to do it.
public boolean isWordPresent(int i, int j, String target, boolean[][]visited, char[][]matrix){
if(i<0 || i>=matrix.length || j<0 || j>=matrix[0].length){
return false;
}
if(visited[i][j]){
return false;
}
if(matrix[i][j] != target.charAt(0)){
return false;
}else{
visited[i][j] = true;
//the last char matches
if(target.length()==1){
return true;
}else{
return isWordPresent(i-1,j-1,target.substring(1),visited,matrix)||
isWordPresent(i-1,j,target.substring(1),visited,matrix)||
isWordPresent(i-1,j+1,target.substring(1),visited,matrix)||
isWordPresent(i,j-1,target.substring(1),visited,matrix)||
isWordPresent(i,j+1,target.substring(1),visited,matrix)||
isWordPresent(i+1,j-1,target.substring(1),visited,matrix)||
isWordPresent(i+1,j,target.substring(1),visited,matrix)||
isWordPresent(i+1,j+1,target.substring(1),visited,matrix);
}
}
}
public boolean findWord(String target, char [][]matrix){
//first check valid word and matrix
if(target.equals("") || target==null){
return false;
}
if(matrix.length==0){
return false;
}
//loop
boolean flag = false;
for(int row =0; row<matrix.length;row++){
for(int column=0;column<matrix[0].length;column++){
boolean [][]visited = new boolean[matrix.length][matrix[0].length];
flag = isWordPresent(row,column,target,visited,matrix);
if(flag){
return true;
}
}
}
return false;
}
(1) Create a Coord class that represents a (row, col) pair
(2) Iterate through the matrix and store the occurrences of each character in a HashMap<Character, List<Coord>>
(3) Define a recursive method find(String word, HashSet<Coord> seen, int index, Coord prev). The HashSet<Coord> seen represents the coordinates we have seen already (null initially). The index is the current index of the word we want to find (0 initially). The Coord prev is the previous Coord (null initially). In each recursive call, we want to look up all possible coordinates for the character at current index. If no coordinates is found then return false. Otherwise iterate through the coordinates from the map and perform recursive call.
More details in the code below, but I doubt this is the proper solution as it requires too much code.
class FindWord {
static HashMap<Character, LinkedList<Coord>> map = new HashMap<Character, LinkedList<Coord>>();
public static boolean isPresent(String[] matrix, String word) {
int len = matrix[0].length();
for(int r=0; r<matrix.length; r++) {
for(int c=0; c<len; c++) {
char ch = matrix[r].charAt(c);
if(!map.containsKey(ch))
map.put(ch, new LinkedList<Coord>());
map.get(ch).add(new Coord(r, c));
}
}
return helper(word, new HashSet<Coord>(), 0, null);
}
public static boolean helper(String word, HashSet<Coord> seen, int index, Coord prev) {
if(index >= word.length())
return true;
char ch = word.charAt(index);
if(!map.containsKey(ch))
return false;
for(Coord coord : map.get(ch)) {
if(prev == null || prev.adjacent(coord)) {
if(seen.contains(coord))
continue;
seen.add(coord);
if(helper(word, seen, index+1, coord))
return true;
seen.remove(coord);
}
}
return false;
}
public static void main(String[] args) {
int len = args.length;
String[] matrix = new String[len-1];
System.arraycopy(args, 0, matrix, 0, len-1);
System.out.println(isPresent(matrix, args[len-1]));
}
static class Coord {
public int r;
public int c;
public Coord(int r, int c) {
this.r = r;
this.c = c;
}
public int hashCode() {
return r*c;
}
public boolean equals(Coord coord2) {
return r == coord2.r && c == coord2.c;
}
public boolean adjacent(Coord coord2) {
if(this.equals(coord2))
return false;
return (Math.abs(r - coord2.r) <= 1) &&
(Math.abs(c - coord2.c) <= 1);
}
}
}
I guess there is need to DFS but we can start at all letters and see if there exist a valid suffix with that letter as the starting point if its true we can search a valid prefix attached to it.. we can mark all the suffix letters as visited but not the prefix searched ones.. this will not invalidate other possible cases
here is my code ... hope it helps i have tested the given conditions
public class PatternMatch {
static boolean travasel[][];
public static boolean findPattern(char[][] arr,int[] cRows, int[] cColumns,int intRow, int intCol,char[] pattern)
{
travasel = new boolean[intRow][intCol];
for(int i = 0; i< intRow; i++)
{
for(int j = 0; j< intCol; j++)
{
travasel[i][j] = false;
}
}
for(int i = 0; i< intRow; i++)
{
for(int j = 0; j< intCol; j++)
{
if(arr[i][j] == pattern[0])
{
travasel[i][j] = true;
if(checkPattern(arr,cRows,cColumns,i,j,pattern,0))
return true;
}
}
}
return false;
}
public static boolean checkPattern(char[][] m,int[] cRows, int[] cColumns,int tRows,int tCol, char[] pattern,int index)
{
if (index == pattern.length - 1)
return true;
for(int i =0; i < cRows.length; i++)
{
if(tRows+cRows[i] >= 0 && tRows+cRows[i] <= m.length -1 && tCol+cColumns[i] >= 0 && tCol+cColumns[i] <= m[0].length -1 && travasel[tRows+cRows[i]][tCol+cColumns[i]] == false)
{
if(m[tRows+cRows[i]][tCol+cColumns[i]] == pattern[index +1])
{
travasel[tRows+cRows[i]][tCol+cColumns[i]] = true;
if(checkPattern(m,cRows,cColumns,tRows+cRows[i],tCol+cColumns[i],pattern,index + 1))
{
return true;
}
travasel[tRows+cRows[i]][tCol+cColumns[i]] = false;
}
}
}
return false;
}
public static void main(String[] args) {
int[] incRows = {-1,1,0,0,-1,-1,1,1};
int[] incColumns = {0,0,1,-1,-1,1,-1,1};
char[][] m = {{'a','b','c','d','e','f'},
{'z','n','a','b','c','f'}, // z n a b c f
{'f','g','f','a','b','c'}}; //f g f a b c
String pattern = "gng";
System.out.println(findPattern(m,incRows,incColumns,m.length,m[0].length,pattern.toCharArray()));
}
}
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);
}
}
Here is a solution which is very similar to one provided here. But still this is a brute-force solution.
public class AnyDirectionWordFinder {
public static void main(String[] args) {
String[][] letters = new String[][]{
{"a", "b", "c", "d", "e", "f"},
{"z", "n", "a", "b", "c", "f"},
{"f", "g", "f", "a", "b", "c"},
};
System.out.println(letters.length); // << NOTE THAT THIS IS "3"
System.out.println(letters[0].length); // << NOTE THAT THIS IS "6"
System.out.println(isWordFound(letters, "fnz")); // true
System.out.println(isWordFound(letters, "gng")); // false
System.out.println(isWordFound(letters, "fbz")); // false
}
private static boolean isWordFound(String[][] letters, String word) {
for (int x=0; x<letters.length; x++) {
for (int y=0; y<letters[0].length; y++) {
boolean[][] visited = new boolean[letters.length][letters[0].length];
if (traverse(word, letters, visited, x, y)) {
return true;
}
}
}
return false;
}
private static boolean traverse(String wordToMatch, String[][] letters, boolean[][] visited, int x, int y) {
if (wordToMatch.length() == 0) {
return true;
}
if (x >= letters.length || y >= letters[0].length
|| x < 0 || y < 0) {
return false;
}
String firstLetter = wordToMatch.substring(0,1);
if (!visited[x][y] && letters[x][y].equals(firstLetter)) {
visited[x][y] = true;
String newWordToMatch = wordToMatch.substring(1);
return
traverse(newWordToMatch, letters, visited, x+1, y) ||
traverse(newWordToMatch, letters, visited, x-1, y) ||
traverse(newWordToMatch, letters, visited, x+1, y+1) ||
traverse(newWordToMatch, letters, visited, x-1, y-1) ||
traverse(newWordToMatch, letters, visited, x, y+1) ||
traverse(newWordToMatch, letters, visited, x, y-1) ||
traverse(newWordToMatch, letters, visited, x-1, y+1) ||
traverse(newWordToMatch, letters, visited, x+1, y-1);
}
return false;
}
}
1. The entire alphabet set is of size 26 ( a-z) . Create a hash map of size 26 and parse through the matrix and store the frequency. Cost : O(row*col)
2. Iterate over the search string and subtract the freq. in the hash map as you iterate over each character. If at any point the frequency goes -ve, then the word doesn't exist.
Running time : O(row*col) Space: Constant
Doesn't include the constraint that consecutive characters must be neighbours in the matrix.
Just DFS from every starting position looking for a matching word along valid paths and as you visit nodes/letters, capitalize them ( c = c + 'A' - 'a') to mark them as visited, and decapitalize them when unwinding.
- S O U N D W A V E February 28, 2014