贡献今天facebook电面一道题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

贡献今天facebook电面一道题

贡献今天facebook电面一道题# JobHunting - 待字闺中

h*g2012-02-17 08:02

1 楼

输入一个矩阵：
ABCE
SFCS
ADEE
和一个string 比如 ABCCED
判断这个string 是否是矩阵的一个连续路径（可以上下左右移动，一次一格），矩阵
中用过的字母不能再用。
比如 ABCCED 可以。SEE 可以
但 ABCB 就不行因为B 已被用过不能往回走。

i*r2012-02-17 08:02

2 楼

照着走一遍好了

g*e2012-02-17 08:02

3 楼

这不就是zynga的scramble吗

i*e2012-02-17 08:02

4 楼

经典 dfs，boggle 题。
用一个二维table来记录visited cell就可以了。

m*a2012-02-17 08:02

5 楼

只能从top-left 开始吗

【在 h*****g 的大作中提到】

: 输入一个矩阵：
: ABCE
: SFCS
: ADEE
: 和一个string 比如 ABCCED
: 判断这个string 是否是矩阵的一个连续路径（可以上下左右移动，一次一格），矩阵
: 中用过的字母不能再用。
: 比如 ABCCED 可以。SEE 可以
: 但 ABCB 就不行因为B 已被用过不能往回走。

h*g2012-02-17 08:02

6 楼

任意位置都可以开始

【在 m*****a 的大作中提到】

: 只能从top-left 开始吗

i*e2012-02-17 08:02

7 楼

不一定，可以从任何格子当起点。

【在 m*****a 的大作中提到】

: 只能从top-left 开始吗

w*z2012-02-17 08:02

8 楼

要用Stack吧，每个点可以有多种可能的走法。是一个遍历

i*e2012-02-17 08:02

9 楼

请问 lz，SEE 可以代表可以 wrap around 对吧？

c*e2012-02-17 08:02

10 楼

好像蛮简单的么，就是一次取一个字母，看一下几种可能的情况保存一下，接着取下一
个，把走不通的结果踢出去，一直到走完。

h*g2012-02-17 08:02

11 楼

从第二行最后的一个S 开始，往下走，再往左走，就得到了。

【在 i**********e 的大作中提到】

: 请问 lz，SEE 可以代表可以 wrap around 对吧？

i*e2012-02-17 08:02

12 楼

恩，是的。我想多了 :)

【在 h*****g 的大作中提到】

: 从第二行最后的一个S 开始，往下走，再往左走，就得到了。

z*n2012-02-17 08:02

13 楼

思路并不很难，不过电面的时候直接coding写好也不容易，
Facebook电面就这一题，还是有几道coding题？

m*r2012-02-17 08:02

14 楼

我练练手，试着写了下：
public class StringPath {
public static boolean stringMatch(char[][] m, String s) {
StringBuffer sb = new StringBuffer();
boolean visited[][] = new boolean[m.length][m[0].length];
boolean found = false;
for (int i=0;ifor (int j=0;jif (searchDFS(m, i, j, s, 0, visited, sb)) found = true;
}
}
return found;
}
public static boolean searchDFS(char[][] m, int x, int y, String s, int pos, boolean[][] v, StringBuffer sb) {
if (pos==s.length()) return true;
if (m[x][y]!=s.charAt(pos)) return false;
sb.append(m[x][y]);
v[x][y]=true;
boolean valid=false;
if (x>0 && !v[x-1][y] && searchDFS(m, x - 1, y, s, pos + 1, v, sb)) valid=true;
if (y>0 && !v[x][y-1]&& searchDFS(m, x, y - 1, s, pos + 1, v, sb)) valid=true;
if (xif (ysb.setLength(sb.length()-1);
v[x][y]=false;
return valid;
}
public static void main(String args[]) {
char[][] m = new char[][]{
{'A','B','C','E'},
{'S','F','C','S'},
{'A','D','E','E'}
};
System.out.println("ABCCED in matrix="+ stringMatch(m, "ABCCED"));
System.out.println("ABCB in matrix="+ stringMatch(m, "ABCB"));
System.out.println("SEE in matrix="+ stringMatch(m, "SEE"));
}
}

f*82012-02-17 08:02

15 楼

这个和我本周二intern oncampus的a家的题一模一样。。。
要简化的话可以加个function，比如提供一个字头，看字典里有没有这个字头开始的单
词没有的话就不用继续走了。可以节约时间。
四个递归和我的思路一样。得到了面试官的认可。不过我却是把四个递归写进for loop
里面了。。。郁闷。
顺便我本科，楼主是？

p*22012-02-17 08:02

16 楼

如果要判断很多字符串的话，用trie更好吧？遍历一次建好trie，以后查找就容易了。

z*t2012-02-17 08:02

17 楼

基于回归算法做了一下，
解法放在博客里，
http://codercareer.blogspot.com/2012/02/no-34-string-path-in-ma
欢迎在博客评论中告知您的意见和建议。多谢:)

【在 h*****g 的大作中提到】

f*l2012-02-17 08:02

18 楼

#include
#include
using namespace std;
bool isValid( char currentChar,int x, int y, int columnSize, int
rowSize,
char desiredChar, bitset <20> mybitset )
{
if(x < 0 || x > columnSize || y < 0 || y > rowSize )
{
return false ;
}
if ( mybitset[x*columnSize+y] == 1 )
{
return false;
}
if ( currentChar != desiredChar)
{
return false ;
}
return true ;
}
bool moveforward( int rowSize, int columnSize, char Array[][4], int x,
int y, char desired[], int stringSize, int currentLoc, bitset <20>
mybitset)
{
if ( currentLoc == (stringSize - 1)
&& desired[currentLoc] == Array[x][y])
{
return true ;
}
if ( currentLoc == (stringSize -1 ) && desired[currentLoc] !=
Array[x][y] )
{
return false ;
}
bool value = false;
mybitset.set(x*columnSize + y, 1);
if ( isValid( Array[x+1][y], x+1, y, columnSize, rowSize, desired[
currentLoc+1], mybitset ) == true )
{
value = moveforward(rowSize,columnSize, Array, x+1 , y,
desired,stringSize, currentLoc +1 , mybitset) ;
}
if ( value == false && isValid( Array[x-1][y], x-1, y,columnSize,
rowSize, desired[currentLoc+1], mybitset ) == true )
{
value = moveforward(rowSize, columnSize, Array, x-1 , y,
desired, stringSize, currentLoc +1 , mybitset) ;
}
if ( value == false && isValid( Array[x][y+1], x, y+1, columnSize,
rowSize, desired[currentLoc+1], mybitset ) == true )
{
value = moveforward(rowSize, columnSize, Array, x , y+1,
desired, stringSize, currentLoc +1 , mybitset) ;
}
if ( value == false && isValid( Array[x][y-1], x, y-1, columnSize,
rowSize, desired[currentLoc+1], mybitset ) == true )
{
value = moveforward(rowSize, columnSize, Array, x , y-1,
desired, stringSize, currentLoc +1 , mybitset) ;
}
if( value == false )
{
mybitset.set(x*columnSize + y, 0);
return false ;
}
else
{
return true ;
}
}
bool checkstring( char array[][4], int columnSize, int rowSize , char
desired[], int stringSize)
{
// search
for(int i = 0 ; i < rowSize ; i++)
for ( int j = 0 ; j < columnSize ; j++)
{
// set up initial state
bitset <20> visited(0) ;
if( array[i][j] == desired[0])
{
visited.set( i*columnSize + j, 1) ;
bool value = moveforward( rowSize, columnSize, array, i
, j, desired, stringSize, 0, visited) ;
if ( value == true)
{
return true ;
}
}
}
return false ;
}

【在 m*******r 的大作中提到】

: 我练练手，试着写了下：
: public class StringPath {
: public static boolean stringMatch(char[][] m, String s) {
: StringBuffer sb = new StringBuffer();
: boolean visited[][] = new boolean[m.length][m[0].length];
: boolean found = false;
: for (int i=0;i: for (int j=0;j: if (searchDFS(m, i, j, s, 0, visited, sb)) found = true;
: }

z*w2012-02-17 08:02

19 楼

用dfs的方法实现了一下，dfs有些改动，需要记录当前栈内已经访问的节点，发现当前点和路
径不符立即返回false，否则递归处理相邻的元素。一旦发现路径走完立即返回true
-----------------------------
import java.util.HashSet;
import java.util.Set;
public class FindPath {
public boolean findPath(String[] m, String path) {
if (path.length() == 0) return true;
for (int i = 0; i < m.length; i ++) {
for (int j = 0; j < m[0].length(); j ++) {
Set set = new HashSet();
if (dfs(m, i, j, path, 0, set))
return true;
}
}
return false;
}
private boolean dfs(String[] m, int i, int j, String path, int k,
Set set) {
if (m[i].charAt(j) == path.charAt(k)) {
set.add(i+":"+j);
if (k == path.length() - 1) {
return true;
}
int[] x = new int[]{i-1, i+1, i, i};
int[] y = new int[]{j, j, j+1, j-1};
for (int n = 0; n < x.length; n ++) {
if (x[n] < 0 || x[n] >= m.length || y[n] < 0 ||
y[n] >= m[0].length()) {
continue;
} else {
if (set.contains(x[n]+":"+y[n])) continue;
set.add(x[n]+":"+y[n]);
if (dfs(m, x[n], y[n], path, k+1, set)) {
return true;
}
set.remove(x[n]+":"+y[n]);
}
}
}
return false;
}
}