日元跌了，日本的出口企业财报纷纷超过预期，人民币跌了，联想表示利润下滑要涨价 - 未名空间MITBBS历史存档

日元跌了，日本的出口企业财报纷纷超过预期，人民币跌了，联想表示利润下滑要涨价# Hardware - 计算机硬件

c*t2015-08-24 07:08

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！

c*m2015-08-24 07:08

2 楼

也是一景。
据台湾《电子时报》援引上游供应链的消息称，由于人民币近期大幅度贬值，联想计划
于8月底提高其PC电脑产品在中国区的售价，然后在东南亚市场也会提价。
而联想并不是唯一一个准备这么干的，华硕、宏碁都打算随后在9月份跟进。其他厂商
不详，但肯定也会有所动作。
联想方面对此拒绝发表任何评论，但并未直接否认。
消息称，联想的企业级和消费级桌面电脑、笔记本都会涨价，但是平板机、智能手机不
会涨价，因为这些市场竞争太激烈了。
联想有40％的收入来自中国区，而随着人民币贬值，一些市场观察人士预计，联想的利
润将会出现大幅度滑坡。
联想方面此前曾表示，汇率问题不会对其有太大影响，因为其交易主要使用美元，但如
果涨价成真，人民币贬值的影响远超预期。
消息来源预计，联想需要至少一年的时间才能满血复活，而华硕、宏碁等将趁机对中国
、欧洲PC市场发动更猛烈的攻势。

M*u2015-08-24 07:08

3 楼

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实现这种批量

R*a2015-08-24 07:08

4 楼

说明联想主要市场在国内，并且联想的主要元件提供商在国外。

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

: 也是一景。
: 据台湾《电子时报》援引上游供应链的消息称，由于人民币近期大幅度贬值，联想计划
: 于8月底提高其PC电脑产品在中国区的售价，然后在东南亚市场也会提价。
: 而联想并不是唯一一个准备这么干的，华硕、宏碁都打算随后在9月份跟进。其他厂商
: 不详，但肯定也会有所动作。
: 联想方面对此拒绝发表任何评论，但并未直接否认。
: 消息称，联想的企业级和消费级桌面电脑、笔记本都会涨价，但是平板机、智能手机不
: 会涨价，因为这些市场竞争太激烈了。
: 联想有40％的收入来自中国区，而随着人民币贬值，一些市场观察人士预计，联想的利
: 润将会出现大幅度滑坡。

c*t2015-08-24 07:08

5 楼

呵呵，我应该在公司前面加个‘小’字。
不是暴雪那一类的，是一个专做手机游戏和桌面小游戏的公司。

【在 M**u 的大作中提到】

: con
: 有没有暴雪的面经？
:
: combination
: 3,
: tools

g*e2015-08-24 07:08

6 楼

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*t2015-08-24 07:08

7 楼

sed是stream editor吧，学习了。
另外如果用6进制的话，进位以后的0怎么排除掉呢？而且还得写一个6进制数的实现？

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

: 1. n位6进制数，挨个加一，从n个1加到n个6就完了
: 2. use sed
:
: combination
: 3,

o*e2015-08-24 07:08

8 楼

1. f(n) 用来输出n个组合. 用recursive 输出 f(n-1) 一直到 f(1)
但是不知道怎么把输出的格式弄好.

g*y2015-08-24 07:08

9 楼

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; iSystem.out.print(a[i]);
}
System.out.println();
return;
}

for (int i=1; i<7; i++) {
a[k] = i;
permute(a, k+1);
}
}

f*42015-08-24 07:08

10 楼

2个筛子的话
1 2和2 1不算是同样的点数？

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

: 1. n位6进制数，挨个加一，从n个1加到n个6就完了
: 2. use sed
:
: combination
: 3,

c*t2015-08-24 07:08

11 楼

是分开算的，因为相当于每个骰子有一个序号，所以认为不算是同样的点数

【在 f****4 的大作中提到】

: 2个筛子的话
: 1 2和2 1不算是同样的点数？

f*42015-08-24 07:08

12 楼

哦，没注意你有写共6^n种

【在 c******t 的大作中提到】

: 是分开算的，因为相当于每个骰子有一个序号，所以认为不算是同样的点数

o*e2015-08-24 07:08

13 楼

高.

【在 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*12015-08-24 07:08

14 楼

Big Fish

【在 c******t 的大作中提到】

: 呵呵，我应该在公司前面加个‘小’字。
: 不是暴雪那一类的，是一个专做手机游戏和桌面小游戏的公司。

r*n2015-08-24 07:08

15 楼

看来楼主跟我面到一起去了，我这题当时也没答出来，事后写的：
//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*t2015-08-24 07:08

16 楼

第一题不就是那个经典的电话面板上给定一个电话号码，返回所有对应字母组合

c*t2015-08-24 07:08

17 楼

赞！你的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*n2015-08-24 07:08

18 楼

是为了在递归树里退回到上一个分叉点。。。

【在 c******t 的大作中提到】

: 赞！你的resize()是为了去掉末尾的'\0'?

k*d2015-08-24 07:08

19 楼

#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*e2015-08-24 07:08

20 楼

鸡蛋里挑骨头。
大家做算法题的时候，会考虑异常情况吗？
譬如函数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*d2015-08-24 07:08

21 楼

我写的那个code，如果输入非法（N<1)，就什么都不输出（除了一个回车）。

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

: 鸡蛋里挑骨头。
: 大家做算法题的时候，会考虑异常情况吗？
: 譬如函数throwDice中的参数问题：如果输入dnum

c*t2015-08-24 07:08

22 楼

没有理解这里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*d2015-08-24 07:08

23 楼

就是到了递归树的叶节点了，输出结果。

【在 c******t 的大作中提到】

: 没有理解这里else的作用是什么，能不能解释一下？ thx

r*n2015-08-24 07:08

24 楼

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*i2015-08-24 07:08

25 楼

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*32015-08-24 07:08

26 楼

thx

a*32015-08-24 07:08

27 楼

zynga

g*a2015-08-24 07:08

28 楼

Thanks for sharing

C*U2015-08-24 07:08

29 楼

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*e2015-08-24 07:08

30 楼

面一家游戏公司让我做两个三维的球交面的 profile~~ 都没听过的东西。

g*y2015-08-24 07:08

31 楼

骰子那题就是两个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*42015-08-24 07:08

32 楼

古老的挖坟
骰子这题可以对<=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*e2015-08-24 07:08

33 楼

骰子问题
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*e2015-08-24 07:08

34 楼

做3D的portfolio

b*e2015-08-24 07:08

35 楼

这些都是高中信息学竞赛的题目。

【在 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*x2015-08-24 07:08

36 楼

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*e2015-08-24 07:08

37 楼

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) {