c******t
发帖数: 391 | 1 今天下午电面了一家WA的游戏公司， 整个过程大约45分钟。除了一些常规概念例如多
态、hash table，问了如下一道编程题，
1. 有n个六面骰子，点数均为1到6，编写一个函数，按行输出所有可能的combination
， 比如n=1, 输出为1, 2, 3, 4, 5, 6; n=2, 输出为1 1, 1 2, ..., 6 5, 6 6; n=3,
输出为...(共6^n种)
当时感觉和word permutation相似，但想了想似乎不对，给了递归的思路但没能立刻给
出code。 不知道这题大家有没有什么idea。
2. 又考了一个替换电话号码的题，有一堆网页文件(包括html, php, xml等)，需要替
换其中出现的一个指定格式电话号码。 我说了用grep+regular expression查找， 或
者用c++的boost库来匹配替换，但似乎对方不太满意，问我用什么tools实现这种批量
替换，我想了一会没答上来……
3. 之后又问了自己用过的3种设计模式
特来版上请教大家，那个骰子题有没有好的思路，另外电话号码批量替换用什么tools
比较好呢？ thx！ | M**u
发帖数: 10158 | 2 con
有没有暴雪的面经？
combination
3,
tools
【在 c******t 的大作中提到】
: 今天下午电面了一家WA的游戏公司， 整个过程大约45分钟。除了一些常规概念例如多
: 态、hash table，问了如下一道编程题，
: 1. 有n个六面骰子，点数均为1到6，编写一个函数，按行输出所有可能的combination
: ， 比如n=1, 输出为1, 2, 3, 4, 5, 6; n=2, 输出为1 1, 1 2, ..., 6 5, 6 6; n=3,
: 输出为...(共6^n种)
: 当时感觉和word permutation相似，但想了想似乎不对，给了递归的思路但没能立刻给
: 出code。 不知道这题大家有没有什么idea。
: 2. 又考了一个替换电话号码的题，有一堆网页文件(包括html, php, xml等)，需要替
: 换其中出现的一个指定格式电话号码。 我说了用grep+regular expression查找， 或
: 者用c++的boost库来匹配替换，但似乎对方不太满意，问我用什么tools实现这种批量
| c******t
发帖数: 391 | 3 呵呵，我应该在公司前面加个‘小’字。
不是暴雪那一类的，是一个专做手机游戏和桌面小游戏的公司。
【在 M**u 的大作中提到】
: con
: 有没有暴雪的面经？
:
: combination
: 3,
: tools
| g**e
发帖数: 6127 | 4 1. n位6进制数，挨个加一，从n个1加到n个6就完了
2. use sed
combination
3,
【在 c******t 的大作中提到】
: 今天下午电面了一家WA的游戏公司， 整个过程大约45分钟。除了一些常规概念例如多
: 态、hash table，问了如下一道编程题，
: 1. 有n个六面骰子，点数均为1到6，编写一个函数，按行输出所有可能的combination
: ， 比如n=1, 输出为1, 2, 3, 4, 5, 6; n=2, 输出为1 1, 1 2, ..., 6 5, 6 6; n=3,
: 输出为...(共6^n种)
: 当时感觉和word permutation相似，但想了想似乎不对，给了递归的思路但没能立刻给
: 出code。 不知道这题大家有没有什么idea。
: 2. 又考了一个替换电话号码的题，有一堆网页文件(包括html, php, xml等)，需要替
: 换其中出现的一个指定格式电话号码。 我说了用grep+regular expression查找， 或
: 者用c++的boost库来匹配替换，但似乎对方不太满意，问我用什么tools实现这种批量
| c******t
发帖数: 391 | 5 sed是stream editor吧，学习了。
另外如果用6进制的话，进位以后的0怎么排除掉呢？而且还得写一个6进制数的实现？
【在 g**e 的大作中提到】
: 1. n位6进制数，挨个加一，从n个1加到n个6就完了
: 2. use sed
:
: combination
: 3,
| o******e
发帖数: 74 | 6 1. f(n) 用来输出n个组合. 用recursive 输出 f(n-1) 一直到 f(1)
但是不知道怎么把输出的格式弄好. | g**********y
发帖数: 14569 | 7 public void run(int N) {
int[] a = new int[N];
permute(a, 0);
}
private void permute(int[] a, int k) {
if (k==a.length) {
for (int i=0; i
System.out.print(a[i]);
}
System.out.println();
return;
}
for (int i=1; i<7; i++) {
a[k] = i;
permute(a, k+1);
}
} | f****4
发帖数: 1359 | 8 2个筛子的话
1 2和2 1不算是同样的点数？
【在 g**e 的大作中提到】
: 1. n位6进制数，挨个加一，从n个1加到n个6就完了
: 2. use sed
:
: combination
: 3,
| c******t
发帖数: 391 | 9 是分开算的，因为相当于每个骰子有一个序号，所以认为不算是同样的点数
【在 f****4 的大作中提到】
: 2个筛子的话
: 1 2和2 1不算是同样的点数？
| f****4
发帖数: 1359 | 10 哦，没注意你有写 共6^n种
【在 c******t 的大作中提到】
: 是分开算的，因为相当于每个骰子有一个序号，所以认为不算是同样的点数
| | | o******e
发帖数: 74 | 11 高.
【在 g**********y 的大作中提到】
: public void run(int N) {
: int[] a = new int[N];
: permute(a, 0);
: }
:
: private void permute(int[] a, int k) {
: if (k==a.length) {
: for (int i=0; i: System.out.print(a[i]);
: }
| i***1
发帖数: 147 | 12
Big Fish
【在 c******t 的大作中提到】
: 呵呵，我应该在公司前面加个‘小’字。
: 不是暴雪那一类的，是一个专做手机游戏和桌面小游戏的公司。
| r******n
发帖数: 170 | 13 看来楼主跟我面到一起去了，我这题当时也没答出来，事后写的：
//output dnum dices permutation as a string
#include
#include
using namespace std;
void throwDice(int dnum, string out_str, int level)
{
if (level == dnum)
{
cout<
return;
}
for (int i=1; i<7;i++)
{
out_str+=(char)(i+'0');
throwDice(dnum,out_str, level+1);
out_str.resize(out_str.size()-1);
}
}
int main()
{
string out_str;
throwDice(6, out_str, 0);
return 1;
} | m****t
发帖数: 555 | 14 第一题不就是那个经典的电话面板上给定一个电话号码，返回所有对应字母组合 | c******t
发帖数: 391 | 15 赞！ 你的resize()是为了去掉末尾的'\0'?
【在 r******n 的大作中提到】
: 看来楼主跟我面到一起去了，我这题当时也没答出来，事后写的：
: //output dnum dices permutation as a string
: #include
: #include
: using namespace std;
: void throwDice(int dnum, string out_str, int level)
: {
: if (level == dnum)
: {
: cout<
| h*********n
发帖数: 11319 | 16 是为了在递归树里退回到上一个分叉点。。。
【在 c******t 的大作中提到】
: 赞！ 你的resize()是为了去掉末尾的'\0'?
| k***d
发帖数: 4 | 17 #include
#define N 3
#define MAXN 10
void gen(int level){
int i, j;
static int dice[MAXN]; /* global array also works */
if(level <= N){
for(i = 1; i <= 6; i++){
dice[level] = i;
gen(level+1);
}
}else{
for(j = 1; j <= N; j++){
printf("%d", dice[j]);
}
printf("\n");
}
}
int main(){
gen(1);
return 0;
} | n*****e
发帖数: 115 | 18 鸡蛋里挑骨头。
大家做算法题的时候，会考虑异常情况吗？
譬如函数throwDice中的参数问题：如果输入dnum
【在 r******n 的大作中提到】
: 看来楼主跟我面到一起去了，我这题当时也没答出来，事后写的：
: //output dnum dices permutation as a string
: #include
: #include
: using namespace std;
: void throwDice(int dnum, string out_str, int level)
: {
: if (level == dnum)
: {
: cout<
| k***d
发帖数: 4 | 19 我写的那个code，如果输入非法（N<1)，就什么都不输出（除了一个回车）。
【在 n*****e 的大作中提到】
: 鸡蛋里挑骨头。
: 大家做算法题的时候，会考虑异常情况吗？
: 譬如函数throwDice中的参数问题：如果输入dnum
| c******t
发帖数: 391 | 20 没有理解这里else的作用是什么，能不能解释一下？ thx
【在 k***d 的大作中提到】
: #include
: #define N 3
: #define MAXN 10
: void gen(int level){
: int i, j;
: static int dice[MAXN]; /* global array also works */
:
: if(level <= N){
: for(i = 1; i <= 6; i++){
: dice[level] = i;
| | | k***d
发帖数: 4 | 21 就是到了递归树的叶节点了，输出结果。
【在 c******t 的大作中提到】
: 没有理解这里else的作用是什么，能不能解释一下？ thx
| r******n
发帖数: 170 | 22 follow up 一下这家的面试，很快给了我2电面,最近告诉我悲剧。
2面是个senior SDE
问了4题，都是常见题：
1.如何design vending machine? 我大概说的key class为product, payment, machine
。follow up的questions如，如何知道还剩多少coke之类的
2. 如何design chess game? 如何知道谁赢了？board是否该为个class等。
3. find common longest substring in two strings.似乎是个DP经典问题。
http://en.wikipedia.org/wiki/Longest_common_substring_problem
我当时只说了brute force的方法，被要求优化
4.如何搜索遍历一个棋盘，假设只能走4领域。要求:不能重复访问已经走过的node.我说的遍历，通过visited flag防止重复。结果要求不能做visited flag，他给了提示后，原来算是mark previous node，然后不往回走。事后想想认为这样子后面还是有可能会转回原位置的说。
估计还是栽在design上, move on了
combination
3,
【在 c******t 的大作中提到】
: 今天下午电面了一家WA的游戏公司， 整个过程大约45分钟。除了一些常规概念例如多
: 态、hash table，问了如下一道编程题，
: 1. 有n个六面骰子，点数均为1到6，编写一个函数，按行输出所有可能的combination
: ， 比如n=1, 输出为1, 2, 3, 4, 5, 6; n=2, 输出为1 1, 1 2, ..., 6 5, 6 6; n=3,
: 输出为...(共6^n种)
: 当时感觉和word permutation相似，但想了想似乎不对，给了递归的思路但没能立刻给
: 出code。 不知道这题大家有没有什么idea。
: 2. 又考了一个替换电话号码的题，有一堆网页文件(包括html, php, xml等)，需要替
: 换其中出现的一个指定格式电话号码。 我说了用grep+regular expression查找， 或
: 者用c++的boost库来匹配替换，但似乎对方不太满意，问我用什么tools实现这种批量
| g*****i
发帖数: 2162 | 23 longest common substring用suffix tree做似乎比dp好.
第四题mark previous node什么意思?我感觉和visited flag差别不大吧
machine
我说的遍历，通过visited flag防止重复。结果要求不能做visited flag，他给了提示
后，原来算是mark previous node，然后不往回走。事后想想认为这样子后面还是有可
能会转回原位置的说。
【在 r******n 的大作中提到】
: follow up 一下这家的面试，很快给了我2电面,最近告诉我悲剧。
: 2面是个senior SDE
: 问了4题，都是常见题：
: 1.如何design vending machine? 我大概说的key class为product, payment, machine
: 。follow up的questions如，如何知道还剩多少coke之类的
: 2. 如何design chess game? 如何知道谁赢了？board是否该为个class等。
: 3. find common longest substring in two strings.似乎是个DP经典问题。
: http://en.wikipedia.org/wiki/Longest_common_substring_problem
: 我当时只说了brute force的方法，被要求优化
: 4.如何搜索遍历一个棋盘，假设只能走4领域。要求:不能重复访问已经走过的node.我说的遍历，通过visited flag防止重复。结果要求不能做visited flag，他给了提示后，原来算是mark previous node，然后不往回走。事后想想认为这样子后面还是有可能会转回原位置的说。
| w*****3
发帖数: 101 | | a*******3
发帖数: 15 | | g*******a
发帖数: 149 | | C***U
发帖数: 2406 | 27 1. 有n个六面骰子，点数均为1到6，编写一个函数，按行输出所有可能的combination
， 比如n=1, 输出为1, 2, 3, 4, 5, 6; n=2, 输出为1 1, 1 2, ..., 6 5, 6 6; n=3,
输出为...(共6^n种)
====================================================================
这个题目的思路和all combination的思路是一样的。
首先把第一个骰子可能的情况都放进去，也就是说你有
1 2 3 4 5 6
然后把第六个骰子的可能放进去，你就得到
1 1 | 2 1 | 3 1 | 4 1 | 5 1 |6 1
...
1 6 | 2 6 | 3 6 | 4 6 | 5 6 | 6 6
以此类推，其实就是DP | h*******e
发帖数: 1377 | 28 面一家游戏公司让我做两个三维的球交面的 profile~~ 都没听过的东西。 | g****y
发帖数: 240 | 29 骰子那题就是两个vector叉乘吧。base = [[1],[2],[3],[4],[5],[6]]
n的combination = （n-1）的combination 叉乘 base
def print_combination_by_line(n):
base = [[1],[2],[3],[4],[5],[6]]
last = [[]]
i = 1
while i <= n:
result = [x + y for x in base for y in last] #cross product
print("n=", i, result)
last = result[:]
i += 1 | f*******4
发帖数: 64 | 30 古老的挖坟
骰子这题可以对<=6^n-1进行6进制位表示
combination
3,
【在 C***U 的大作中提到】
: 1. 有n个六面骰子，点数均为1到6，编写一个函数，按行输出所有可能的combination
: ， 比如n=1, 输出为1, 2, 3, 4, 5, 6; n=2, 输出为1 1, 1 2, ..., 6 5, 6 6; n=3,
: 输出为...(共6^n种)
: ====================================================================
: 这个题目的思路和all combination的思路是一样的。
: 首先把第一个骰子可能的情况都放进去，也就是说你有
: 1 2 3 4 5 6
: 然后把第六个骰子的可能放进去，你就得到
: 1 1 | 2 1 | 3 1 | 4 1 | 5 1 |6 1
: ...
| | | b***e
发帖数: 383 | 31 骰子问题
public class NDices {
/**
* @param length : current digit's length
* @param n: number of dices
* @param stack: stack is used to save the result
*/
public static void ndices(int length, int n, Stack stack) {
if (length == n) {
System.out.println(stack.toString());
return ;
}
for (int i = 1; i <= 6; i++ ) {
stack.push(i);
ndices(length + 1, n, stack);
stack.pop();
}
}
public static void main(String[] args) {
Stack stack = new Stack();
ndices(0, 3, stack);
}
} | h*******e
发帖数: 1377 | | b*******e
发帖数: 6389 | 33 这些都是高中信息学竞赛的题目。
【在 c******t 的大作中提到】
: 今天下午电面了一家WA的游戏公司， 整个过程大约45分钟。除了一些常规概念例如多
: 态、hash table，问了如下一道编程题，
: 1. 有n个六面骰子，点数均为1到6，编写一个函数，按行输出所有可能的combination
: ， 比如n=1, 输出为1, 2, 3, 4, 5, 6; n=2, 输出为1 1, 1 2, ..., 6 5, 6 6; n=3,
: 输出为...(共6^n种)
: 当时感觉和word permutation相似，但想了想似乎不对，给了递归的思路但没能立刻给
: 出code。 不知道这题大家有没有什么idea。
: 2. 又考了一个替换电话号码的题，有一堆网页文件(包括html, php, xml等)，需要替
: 换其中出现的一个指定格式电话号码。 我说了用grep+regular expression查找， 或
: 者用c++的boost库来匹配替换，但似乎对方不太满意，问我用什么tools实现这种批量
| q****x
发帖数: 7404 | 34 2. sed
combination
3,
【在 c******t 的大作中提到】
: 今天下午电面了一家WA的游戏公司， 整个过程大约45分钟。除了一些常规概念例如多
: 态、hash table，问了如下一道编程题，
: 1. 有n个六面骰子，点数均为1到6，编写一个函数，按行输出所有可能的combination
: ， 比如n=1, 输出为1, 2, 3, 4, 5, 6; n=2, 输出为1 1, 1 2, ..., 6 5, 6 6; n=3,
: 输出为...(共6^n种)
: 当时感觉和word permutation相似，但想了想似乎不对，给了递归的思路但没能立刻给
: 出code。 不知道这题大家有没有什么idea。
: 2. 又考了一个替换电话号码的题，有一堆网页文件(包括html, php, xml等)，需要替
: 换其中出现的一个指定格式电话号码。 我说了用grep+regular expression查找， 或
: 者用c++的boost库来匹配替换，但似乎对方不太满意，问我用什么tools实现这种批量
| e****e
发帖数: 418 | 35 Nice work.
Since length = stack.size(), the parameter length on method is not needed.
So it can be
public static void ndices(int n, Stack stack){
...
}
{
【在 b***e 的大作中提到】
: 骰子问题
: public class NDices {
:
: /**
: * @param length : current digit's length
: * @param n: number of dices
: * @param stack: stack is used to save the result
: */
: public static void ndices(int length, int n, Stack stack) {
: if (length == n) {
|
|
