c*********t
发帖数: 2921 | 1 ihasleetcode，
这个sodoku solver到底是什么个问题？
是说生成所有的sodoku的9*9矩阵？那样的组合可就太多了。
还是说给了一个没有填满的9*9矩阵，解决去填空缺的数字？
还是说给了一个填满的9*9矩阵，判断是不是个有效的solution?
到底是这三者中的哪一个？
谢谢！
试那么短的时间内是写不出来的。
isValid() 函数，检测这个 board 是否valid。然后，找出第一个空格内填 1-9，如果
isValid() 的话继续 DFS，直到没有空格为止（那就是找到答案了）。要注意函数返
回之前把空格还原。
int
8 }
>8 |
|
A***M
发帖数: 18 | 2 我的理解是sodoku solver应该包含如下两部分
1）生成一个合理的sodoku,使27个区(9行9列9个3*3)都满足条件
2）去掉一些number产生一个合理的puzzle, 不会产生多解的情况。
网上搜一下， 有很多这方面的讨论。 |
|
t*********l
发帖数: 566 | 3 攒rp，最近遇到的面试题。。。
C++：effective c++上的东西若干；exception相关；继承和子父类指针若干. 十五分
钟左右。
算法/编程：1. 大文件随机sample，one pass. 2. sodoku solver. 3. logn解x^y,
4. DP题 5. 1Billion query里选出时间最近5分钟内最frequent的1000个，one pass
（我以前在amazon见到过这题）。6.两个排序数组找共同中值。递归和非递归解法。7.
斐波那契数列。100层楼梯下楼，可以一步也可以两步，多少种下法？递归和非递归。
8 贝叶斯后验概率。9。多少人在一起，生日可能出现重复概率大于0.5？（算法导论原
题，我只记得个答案，直接说了。。。）10. 一个数组，找最大值比较次数？同时找最
大值和最小值比较次数？找最大值和次最大值比较次数？（他问我是否知道这题，我说
是作业题。后来和师兄聊说是这他常拿来用的面试题。）
系统设计和经验：1 设计一个库，提供timer的功能。deltalist/hash，或类似linux
kernal的 timer 设计。效率 |
|
e****e
发帖数: 25 | 4 谢谢！再好奇的请教一下：Sodoku的解算法是不是 CS的学生都学过啊？不好意思，我
不是 CS的 |
|
g*******y
发帖数: 1930 | 5 赞！
bless lz～
linkedlist那题，没有说空间限制的话，先想到hash很正常！
sodoku那题用bitwise做比较方便。
最后一个用trie比较好 |
|
|
|
|
l*****a
发帖数: 559 | 9 恩，网上曾经贴过详解的。
depth-first-search，现场写有点难度。 |
|
g**********y
发帖数: 14569 | 10 写了个最原始的，一点智能都没有的：
public class Sudoku {
private int[] t = new int[9];
public boolean solve(int[][] matrix) {
Point p = nextUnknown(matrix);
if (p == null) {
print(matrix);
return true;
}
for (int i=1; i<10; i++) {
matrix[p.x][p.y] = i;
if (pass(matrix) && solve(matrix)) return true;
}
matrix[p.x][p.y] = 0;
return false;
}
private Point nextUnknown(int[][] ma... 阅读全帖 |
|
i**********e
发帖数: 1145 | 11 这题作为面试题应该考察的就是基础 DFS 和 coding skills，如果要智能的话在面试那么短的时间内是写不出来的。
这题思路不难的，只是 coding 方面要注意，不要出错就行。基本思路就是先实现 isValid() 函数，检测这个 board 是否valid。然后，找出第一个空格内填 1-9，如果 isValid() 的话继续 DFS，直到没有空格为止（那就是找到答案了）。要注意函数返回之前把空格还原。
这个函数:
private boolean pass(int[][] matrix)
里面用了一些重复的代码，可以 refactor 成更简洁些，也可以减少错误发生的机率：
private boolean passHelper(int [][] matrix, int startRow, int startCol, int
endRow, int endCol)
这样你在 pass 函数里只要传叫 passHelper() 三次即可。
1）startRow = 0, startCol = col, endRow = 8, endCol = col { for col = 0... 阅读全帖 |
|
|
c*********t
发帖数: 2921 | 13 如果是2的话，
如果给定的数很少，就是说这个矩阵很稀疏，那么solution有可能会有很多种，答案不
是唯一的，对吧？ |
|
i**********e
发帖数: 1145 | 14 是填满空缺的数字.
>>如果给定的数很少，就是说这个矩阵很稀疏，那么solution有可能会有很多种，答案
不是唯一的，对吧？
假设只有唯一一个答案。
另外，如果有兴趣的话，可以参考 Peter Norvig 写的有关 sudoku solver 文章（里
面还介绍了怎么生成一个 sudoku puzzle，附有完整代码）。
从他那里转载：
What is the search algorithm? Simple: first make sure we haven't already
found a solution or a contradiction, and if not, choose one unfilled square
and consider all its possible values. One at a time, try assigning the
square each value, and searching from the resulting position. In other words
, we search for a value d such ... 阅读全帖 |
|
h**k
发帖数: 3368 | 15 说到唯一解，有这么个问题。
在给定的数满足什么条件下，sudoku有而且仅有一个解？
square |
|
s**x
发帖数: 7506 | 16 你那个 hint words and sodoku 是怎么答的？ 多谢分享。 |
|
|
l*n
发帖数: 529 | 18 prefix就是用来check viability的吧，楼上说的没错，还是sodoku的思路。
就是找个空位扔一个未用的字符进去，然后check每个方向是否有希望成为单词，也就
是看的当前字符构成的prefix。但凡判定有人不能延伸为单词，就backtrack。 |
|
l*n
发帖数: 529 | 19 prefix就是用来check viability的吧，楼上说的没错，还是sodoku的思路。
就是找个空位扔一个未用的字符进去，然后check每个方向是否有希望成为单词，也就
是看的当前字符构成的prefix。但凡判定有人不能延伸为单词，就backtrack。 |
|
l********e
发帖数: 1220 | 20 昨天amazon的闪电deal搞了两个玩具：一个汽车华容道，一个糖果sodoku。我总是在幻
想孩子有朝一日能自己坐那儿鼓捣玩具，让我解放一会儿。不过估计到了那个时候，我
又要抱怨他们不理我了。
walmart的黑五广告里有个木头画板，才14，感觉比塑料的强啊。 |
|
|
|
s****l
发帖数: 10462 | 23 我基本上没有打过游戏，更别说街机了。就是电脑上或者手机上也很少打（除了二十年
前玩过两个晚上的三国和前两年玩了比较长时间的sodoku）。从来没有着迷过。是不是
很极品？ |
|
s****l
发帖数: 10462 | 24 握个手。在那个街机帖子里回的。
我基本上没有打过游戏，更别说街机了。就是电脑上或者手机上也很少打（除了二十年
前玩过两个晚上的三国和前两年玩了比较长时间的sodoku）。从来没有着迷过。是不是
很极品？ |
|
t********e
发帖数: 1169 | 25 【 以下文字转载自 JobHunting 讨论区 】
发信人: mitbbs59 (bEQi), 信区: JobHunting
标 题: 本版1年以内的所有 面经题目，含帖子link [为大家方便]
发信站: BBS 未名空间站 (Fri Jan 29 14:20:44 2010, 美东)
不敢保证全部涵盖，大部分的都在。
我自己找了一遍，大家一起用着都方便。
不过只是含有题目的帖子 我才包含进来了，只分享经验没贴题目的 我都没有包含
进来。
大家复习着方便。
1. 一个sorted interger Array[1...N], 已知范围 1...N+1. 已知一个数字missing。
找该数字。
把原题改为unsorted，找missing数字。 performance。
2. 复制linked list。 已知每个节点有两个pointer，一个指向后一个节点，另一个指向
其他任意一节点。 O(n)时间内，无附加内存，复制该linked list。（存储不连续）
3. 一个party N个人，如果一个人不认识任何其他人，又被任何其他人认识，此人为
celeb... 阅读全帖 |
|
t********e
发帖数: 1169 | 26 【 以下文字转载自 JobHunting 讨论区 】
发信人: mitbbs59 (bEQi), 信区: JobHunting
标 题: 本版1年以内的所有 面经题目，含帖子link [为大家方便]
发信站: BBS 未名空间站 (Fri Jan 29 14:20:44 2010, 美东)
不敢保证全部涵盖，大部分的都在。
我自己找了一遍，大家一起用着都方便。
不过只是含有题目的帖子 我才包含进来了，只分享经验没贴题目的 我都没有包含
进来。
大家复习着方便。
1. 一个sorted interger Array[1...N], 已知范围 1...N+1. 已知一个数字missing。
找该数字。
把原题改为unsorted，找missing数字。 performance。
2. 复制linked list。 已知每个节点有两个pointer，一个指向后一个节点，另一个指向
其他任意一节点。 O(n)时间内，无附加内存，复制该linked list。（存储不连续）
3. 一个party N个人，如果一个人不认识任何其他人，又被任何其他人认识，此人为
celeb... 阅读全帖 |
|
|
r*******y
发帖数: 1729 | 28 学习了，真的是太好了，多谢多谢！
再加一个sodoku，也是一个不错的训练逻辑的游戏。
been |
|
E*********e
发帖数: 10297 | 29 sodoku土土的问，这个怎么玩？替我自己问的。 |
|
|
r*******y
发帖数: 1729 | 31 太牛了！还要送儿子么？4岁娃自己做完了一整本sodoku，太赞了！ |
|
|
