沃吗送30的KINDLE不是TOUCH啊 - 未名空间MITBBS历史存档

沃吗送30的KINDLE不是TOUCH啊# PDA - 掌中宝

w*x2012-04-27 07:04

1 楼

刚拿到offer, 发面经回馈版面. (不知道怎么发包子, 会的人教一下, 一定散尽家财.)
一切起源于9月底, 发现facebook在西雅图开了office在招聘, 于是顺手投了个简历.
Recruiter很快回复, 要求做两个中等或者难的puzzle再开始面试. 那时候工作很忙,
也就耽搁了. 一直拖到thanksgiving假期才腾出点时间做了两个中等的puzzle交上去.
facebull也做了, 本地机器上运行都没问题, 但是评卷机器人老说不对, 估计running time太
慢了.
电话面试:
Puzzle做完了就开始电面. 加州office的人打电话过来, 信号不好break up无数次最后
干脆断掉了直接在网上聊:) 题目是实现int power(int x, int y), 先写最简单的那种, 然后
写个better running time, 然后写个只用constant memory的. 最后一个constant
memory有一点tricky, 提示是用bottom-up iteration.
西雅图Onsite:
赞FB的recruiter动作都很快, 电面完了第二天就邀请去西雅图office onsite. 这个
onsite只有一轮45分钟, 其实也就是个面对面的电话面试. 题目就是把一个JSON string打印
成人能看懂的格式. 比较tricky的地方就是escape character和quoted character.
Palo Alto Onsite:
西雅图Onsite完第二天就邀请去Palo Alto面试. 不过正好到了圣诞假期, 于是拖到一
月份. 话说他们包的那个Sheraton Palo Alto酒店实在不咋地, 后面就是Caltrain的铁轨,
噪音很大. 不过campus给人感觉不错, 遇上的人都nice, 而且看上去干劲十足. (和原来公司天
壤之别啊,呵呵) Onsite一共四轮, 每个45分钟, 面了两轮之后休息和HR共进午餐. 题目如下:
1. Generate next n strings according to the following pattern:
1 (this is the input string)
11 (1 one in the previous string)
21 (2 one's in the previous string)
1211 (1 two, 1 one)
111221 (1 one, 1 two, 2 one's)
312211 (3 one's, 2 two's, 1 one)
附加题: Proof whether there is an input string that can produce a
sequence that's strictly non-increasing in length.
2. BST每个level列印一行. 说几个test case.
3. Sort colors.
有个enum叫做Color {Red, White, Blue}, 一个神奇的method叫Color getColor(int)
能把int value对应到Color上. 然后给一个int array, 要求sort the array to the
order Red, White then Blue. 只能用constant memory. 如果两个数字都对应一种颜色,
这两个数字随便怎么排. 此题我觉得是整个面试中最tricky的一道了吧. 提示是如果只有两种颜色
如何sort.
4. 设计FB首页的news feed.
5. 两个sorted array, A里面有足够的剩余空间放B, merge A and B. Give test
cases.
6. 橄榄球每次得2分3分或者7分. 给一个总分, 打印出所有可能的composition. (其实
就是硬币找零)

i*u2012-04-27 07:04

2 楼

给的时间是上午9：00，是不是要9：00到那。我家离打指纹的地方有2个小时，不知道
同一天晚点可以否？thx

d*z2012-04-27 07:04

3 楼

看到广告了

i*92012-04-27 07:04

4 楼

waw, congratulations!

p*l2012-04-27 07:04

5 楼

你随便哪天去都可以.我们就是.不过得看放行的人的心情.你一进去,笑眯着眼说GOOD
MORNING HOW ARE YOU DOING TODAY.人家心情一好,就放你进去打了.
我提前十天打的,怕他不放我,媚笑着说HOW R U DOING SIR,此大哥的眉头皱了皱,还是
把我放进去了.
伸手不打笑脸人,这句管用

O*n2012-04-27 07:04

6 楼

不是才好。更轻更小更方便

【在 d****z 的大作中提到】

: 看到广告了

I*T2012-04-27 07:04

7 楼

3. Sort colors.
有个enum叫做Color {Red, White, Blue}, 一个神奇的method叫Color getColor(int)
能把int value对应到Color上. 然后给一个int array, 要求sort the array to the
order Red, White then Blue. 如果两个数字都对应一种颜色, 这两个数字随便怎么排
. 此
题我觉得是整个面试中最tricky的一道了吧. 提示是如果只有两种颜色如何sort.
这个题是counting sort？再建一个array来存储每个数对应什么颜色，然后遍历原
array得到对应的颜色和每个颜色有几个，最后建个新int array把原array中的各个数
填进去

p*l2012-04-27 07:04

8 楼

我答得这么好,发个包子吧

c*n2012-04-27 07:04

9 楼

我同意不是TOUCH更好，电子书阅读器要有很好的容错能力，摸一下就翻一下很麻烦
，而且多看不支持KINDLE TOUCH。
多看的确好啊，没想到背景一个小公司能做出这等好东西。

l*g2012-04-27 07:04

10 楼

cong

v*s2012-04-27 07:04

11 楼

Touch好，nook和T1上的实体键我基本不用

w*x2012-04-27 07:04

12 楼

忘了说明一个要求是constant memory. counting sort不是constant memory, 因为
input
是array, 不是linked list. 我来把原题更新一下.

【在 I********T 的大作中提到】

: 3. Sort colors.
: 有个enum叫做Color {Red, White, Blue}, 一个神奇的method叫Color getColor(int)
: 能把int value对应到Color上. 然后给一个int array, 要求sort the array to the
: order Red, White then Blue. 如果两个数字都对应一种颜色, 这两个数字随便怎么排
: . 此
: 题我觉得是整个面试中最tricky的一道了吧. 提示是如果只有两种颜色如何sort.
: 这个题是counting sort？再建一个array来存储每个数对应什么颜色，然后遍历原
: array得到对应的颜色和每个颜色有几个，最后建个新int array把原array中的各个数
: 填进去

s*G2012-04-27 07:04

13 楼

big cong big cong!!!!!!!!!
li4 hai4 a

y*a2012-04-27 07:04

14 楼

cong a

h*n2012-04-27 07:04

15 楼

就是partition把

【在 I********T 的大作中提到】

: 3. Sort colors.
: 有个enum叫做Color {Red, White, Blue}, 一个神奇的method叫Color getColor(int)
: 能把int value对应到Color上. 然后给一个int array, 要求sort the array to the
: order Red, White then Blue. 如果两个数字都对应一种颜色, 这两个数字随便怎么排
: . 此
: 题我觉得是整个面试中最tricky的一道了吧. 提示是如果只有两种颜色如何sort.
: 这个题是counting sort？再建一个array来存储每个数对应什么颜色，然后遍历原
: array得到对应的颜色和每个颜色有几个，最后建个新int array把原array中的各个数
: 填进去

w*x2012-04-27 07:04

16 楼

嗯, 就是in place swap. 当时想了半天脑子才转过弯来搞了个2-pass处理三种颜色.

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

: 就是partition把

w*x2012-04-27 07:04

17 楼

学会怎么发包子了, 但是只有六个, 已经全部奉上!

S*n2012-04-27 07:04

18 楼

恭喜了

一定散尽家财.)
顺手投了个简历.
那时候工作很忙,
的puzzle交上去.
对, 估计running time太
break up无数次最后
y), 先写最简单的那种, 然后
最后一个constant

【在 w*****x 的大作中提到】

: 刚拿到offer, 发面经回馈版面. (不知道怎么发包子, 会的人教一下, 一定散尽家财.)
: 一切起源于9月底, 发现facebook在西雅图开了office在招聘, 于是顺手投了个简历.
: Recruiter很快回复, 要求做两个中等或者难的puzzle再开始面试. 那时候工作很忙,
: 也就耽搁了. 一直拖到thanksgiving假期才腾出点时间做了两个中等的puzzle交上去.
: facebull也做了, 本地机器上运行都没问题, 但是评卷机器人老说不对, 估计running time太
: 慢了.
: 电话面试:
: Puzzle做完了就开始电面. 加州office的人打电话过来, 信号不好break up无数次最后
: 干脆断掉了直接在网上聊:) 题目是实现int power(int x, int y), 先写最简单的那种, 然后
: 写个better running time, 然后写个只用constant memory的. 最后一个constant

W*F2012-04-27 07:04

19 楼

什么是puzzle，弱问一下

c*o2012-04-27 07:04

20 楼

恭喜楼主啦！！

.)
.
running time太
种, 然后

【在 w*****x 的大作中提到】

: 刚拿到offer, 发面经回馈版面. (不知道怎么发包子, 会的人教一下, 一定散尽家财.)
: 一切起源于9月底, 发现facebook在西雅图开了office在招聘, 于是顺手投了个简历.
: Recruiter很快回复, 要求做两个中等或者难的puzzle再开始面试. 那时候工作很忙,
: 也就耽搁了. 一直拖到thanksgiving假期才腾出点时间做了两个中等的puzzle交上去.
: facebull也做了, 本地机器上运行都没问题, 但是评卷机器人老说不对, 估计running time太
: 慢了.
: 电话面试:
: Puzzle做完了就开始电面. 加州office的人打电话过来, 信号不好break up无数次最后
: 干脆断掉了直接在网上聊:) 题目是实现int power(int x, int y), 先写最简单的那种, 然后
: 写个better running time, 然后写个只用constant memory的. 最后一个constant

g*s2012-04-27 07:04

21 楼

intermediate = meal, hard = buffet? two meals or one buffet?

.)
.
running time太
种, 然后

【在 w*****x 的大作中提到】

: 刚拿到offer, 发面经回馈版面. (不知道怎么发包子, 会的人教一下, 一定散尽家财.)
: 一切起源于9月底, 发现facebook在西雅图开了office在招聘, 于是顺手投了个简历.
: Recruiter很快回复, 要求做两个中等或者难的puzzle再开始面试. 那时候工作很忙,
: 也就耽搁了. 一直拖到thanksgiving假期才腾出点时间做了两个中等的puzzle交上去.
: facebull也做了, 本地机器上运行都没问题, 但是评卷机器人老说不对, 估计running time太
: 慢了.
: 电话面试:
: Puzzle做完了就开始电面. 加州office的人打电话过来, 信号不好break up无数次最后
: 干脆断掉了直接在网上聊:) 题目是实现int power(int x, int y), 先写最简单的那种, 然后
: 写个better running time, 然后写个只用constant memory的. 最后一个constant

g*s2012-04-27 07:04

22 楼

1. Generate next n strings according to the following pattern:
1 (this is the input string)
11 (1 one in the previous string)
21 (2 one's in the previous string)
1211 (1 two, 1 one)
111221 (1 one, 1 two, 2 one's)
312211 (3 one's, 2 two's, 1 one)
can u explain more about the rule? i'm lost.

.)
.
running time
太
种,
然后

【在 w*****x 的大作中提到】

: 刚拿到offer, 发面经回馈版面. (不知道怎么发包子, 会的人教一下, 一定散尽家财.)
: 一切起源于9月底, 发现facebook在西雅图开了office在招聘, 于是顺手投了个简历.
: Recruiter很快回复, 要求做两个中等或者难的puzzle再开始面试. 那时候工作很忙,
: 也就耽搁了. 一直拖到thanksgiving假期才腾出点时间做了两个中等的puzzle交上去.
: facebull也做了, 本地机器上运行都没问题, 但是评卷机器人老说不对, 估计running time太
: 慢了.
: 电话面试:
: Puzzle做完了就开始电面. 加州office的人打电话过来, 信号不好break up无数次最后
: 干脆断掉了直接在网上聊:) 题目是实现int power(int x, int y), 先写最简单的那种, 然后
: 写个better running time, 然后写个只用constant memory的. 最后一个constant

w*x2012-04-27 07:04

23 楼

嗯. 做了两个meal. Buffet没pass

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

: intermediate = meal, hard = buffet? two meals or one buffet?
:
: .)
: .
: running time太
: 种, 然后

g*s2012-04-27 07:04

24 楼

the problem in the phone is dp, just like Fibonacci?
2, 5, 6 are all classical.
4, i know little about web, so no comments. :)
1, i'm not sure about what rule the pattern follows. can u elaborate it?
3, in case of 2-color only, partition() in quicksort()? so for 3-color
case, u treat two colors as the same first, then distinguish them in the
2nd pass. avg time is O(N) while space O(1). is this good enough?

.)
.
running time
太
种,
然后

【在 w*****x 的大作中提到】

: 刚拿到offer, 发面经回馈版面. (不知道怎么发包子, 会的人教一下, 一定散尽家财.)
: 一切起源于9月底, 发现facebook在西雅图开了office在招聘, 于是顺手投了个简历.
: Recruiter很快回复, 要求做两个中等或者难的puzzle再开始面试. 那时候工作很忙,
: 也就耽搁了. 一直拖到thanksgiving假期才腾出点时间做了两个中等的puzzle交上去.
: facebull也做了, 本地机器上运行都没问题, 但是评卷机器人老说不对, 估计running time太
: 慢了.
: 电话面试:
: Puzzle做完了就开始电面. 加州office的人打电话过来, 信号不好break up无数次最后
: 干脆断掉了直接在网上聊:) 题目是实现int power(int x, int y), 先写最简单的那种, 然后
: 写个better running time, 然后写个只用constant memory的. 最后一个constant

w*x2012-04-27 07:04

25 楼

1 (这个是initial string)
11 (表示上一个string里面有一个1)
21 (上一个string里面有两个1)
1211 (一个2，两个1)
111221 (一个1，一个2，两个1)
312211 (三个1，两个2，一个1)
就是把连续的相同的数字归纳到一起.

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

: 1. Generate next n strings according to the following pattern:
: 1 (this is the input string)
: 11 (1 one in the previous string)
: 21 (2 one's in the previous string)
: 1211 (1 two, 1 one)
: 111221 (1 one, 1 two, 2 one's)
: 312211 (3 one's, 2 two's, 1 one)
: can u explain more about the rule? i'm lost.
:
: .)

g*s2012-04-27 07:04

26 楼

two "1" -> 21
one "2", one "1", not two "1". u have a typo here and that's why i get
lost. :) now i think i know the pattern. thx.

【在 w*****x 的大作中提到】

:
: 1 (这个是initial string)
: 11 (表示上一个string里面有一个1)
: 21 (上一个string里面有两个1)
: 1211 (一个2，两个1)
: 111221 (一个1，一个2，两个1)
: 312211 (三个1，两个2，一个1)
: 就是把连续的相同的数字归纳到一起.

g*s2012-04-27 07:04

27 楼

btw, what's the solution to the extra question? it seems the input "1"
satisfies this property. is this related to np complexity/turing machine,
about the problem encoding?

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

:
: two "1" -> 21
: one "2", one "1", not two "1". u have a typo here and that's why i get
: lost. :) now i think i know the pattern. thx.

j*u2012-04-27 07:04

28 楼

lz power怎么算的：
最简单的是y--每次乘x？
better running time的是recursion + DP？
const space的是每次乘方？比如x^15=x^8 * x^4 * x^2 * x^1，但是有重复运算。
sort color的不算tricky，如果你看到过dutch flag的话，你看interviewer连flag的
颜色都没改:P

.)
.
running time太
种, 然后

【在 w*****x 的大作中提到】

: 刚拿到offer, 发面经回馈版面. (不知道怎么发包子, 会的人教一下, 一定散尽家财.)
: 一切起源于9月底, 发现facebook在西雅图开了office在招聘, 于是顺手投了个简历.
: Recruiter很快回复, 要求做两个中等或者难的puzzle再开始面试. 那时候工作很忙,
: 也就耽搁了. 一直拖到thanksgiving假期才腾出点时间做了两个中等的puzzle交上去.
: facebull也做了, 本地机器上运行都没问题, 但是评卷机器人老说不对, 估计running time太
: 慢了.
: 电话面试:
: Puzzle做完了就开始电面. 加州office的人打电话过来, 信号不好break up无数次最后
: 干脆断掉了直接在网上聊:) 题目是实现int power(int x, int y), 先写最简单的那种, 然后
: 写个better running time, 然后写个只用constant memory的. 最后一个constant

g*s2012-04-27 07:04

29 楼

我孤陋寡闻了。不错。不过反过来按quicksort的partition应该也能得个80分吧？

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

: lz power怎么算的：
: 最简单的是y--每次乘x？
: better running time的是recursion + DP？
: const space的是每次乘方？比如x^15=x^8 * x^4 * x^2 * x^1，但是有重复运算。
: sort color的不算tricky，如果你看到过dutch flag的话，你看interviewer连flag的
: 颜色都没改:P
:
: .)
: .
: running time太

i*e2012-04-27 07:04

30 楼

For number 1, the problem of proving the statement sounds MORE interesting..
. hmm..
My solution using character pointer manipulation.
#include
using namespace std;
void printCharCounts(const char *in, char out[]) {
int count = 1;
char *pOut = out;
const char *pIn = in;
while (*pIn) {
if (*pIn == *(pIn+1)) {
count++;
} else {
*pOut++ = '0' + count;
*pOut++ = *pIn;
count = 1;
}
pIn++;
}
*pOut = '\0';
}
int main() {
char str[100] = "1";
char next[100];
int n = 10;
cout << "Initial string: " << str << endl;
for (int i = 0; i < n; i++) {
printCharCounts(str, next);
cout << next << endl;
strcpy(str, next);
}
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

i*e2012-04-27 07:04

31 楼

>>Proof whether there is an input string that can produce a
sequence that's strictly non-increasing in length.
One example of an input that produces sequence non-increasing in length is:
22,
since it will produce the next output of 22 infinitely.
Also, you can prove that for any k groups of numbers (a group consists only
the same consecutive numbers).
Assume group = { a1, a2, ... ak },
then the next group = { m1a1 m2a2 ... mkak }, a total of 2k length.
Since a1 != a2, a2 != a1 && a2 != a3, ... ak-1 != ak-2 && ak-1 != ak,
Then the minimum possible of numbers of the next next group must also yield
a total of k groups of numbers, which the length is also 2k, which is in non
-increasing order in length.
But, I doubt such sequence exists besides the input "22", anyone can verify?
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

s*t2012-04-27 07:04

32 楼

I don't think your proof is correct.
For example, "123" -> "111213" ->"31121113".

only
yield

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

: >>Proof whether there is an input string that can produce a
: sequence that's strictly non-increasing in length.
: One example of an input that produces sequence non-increasing in length is:
: 22,
: since it will produce the next output of 22 infinitely.
: Also, you can prove that for any k groups of numbers (a group consists only
: the same consecutive numbers).
: Assume group = { a1, a2, ... ak },
: then the next group = { m1a1 m2a2 ... mkak }, a total of 2k length.
: Since a1 != a2, a2 != a1 && a2 != a3, ... ak-1 != ak-2 && ak-1 != ak,

J*n2012-04-27 07:04

33 楼

congs，能不能报一下offer的情况？

i*e2012-04-27 07:04

34 楼

"Then the minimum possible of numbers of the next next group must also yield
a total of k groups of numbers, which the length is also 2k, which is in
non-increasing order in length."
The proof is for the case which yields the "minimum" possible of number
where the minimum length = 2*k can produce sequence length's in non-
increasing order. It doesn't mean the next sequence's length must be non-
increasing.
I might still be wrong though, correct me if I'm wrong.
Can LZ please share how to answer: "Proof whether there is an input string
that can produce a sequence that's strictly non-increasing in length.",
thanks!
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

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

: I don't think your proof is correct.
: For example, "123" -> "111213" ->"31121113".
:
: only
: yield

Z*Z2012-04-27 07:04

35 楼

what does "strictly non-increasing" mean anyway?

yield

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

: "Then the minimum possible of numbers of the next next group must also yield
: a total of k groups of numbers, which the length is also 2k, which is in
: non-increasing order in length."
: The proof is for the case which yields the "minimum" possible of number
: where the minimum length = 2*k can produce sequence length's in non-
: increasing order. It doesn't mean the next sequence's length must be non-
: increasing.
: I might still be wrong though, correct me if I'm wrong.
: Can LZ please share how to answer: "Proof whether there is an input string
: that can produce a sequence that's strictly non-increasing in length.",

i*e2012-04-27 07:04

36 楼

Means the next sequence's length is less than or equal to current sequence's
length?
Hope I understand this right.

【在 Z*****Z 的大作中提到】

: what does "strictly non-increasing" mean anyway?
:
: yield

f*o2012-04-27 07:04

37 楼

恭喜, 谢谢详细的面经

w*x2012-04-27 07:04

38 楼

对, 但是可以利用binary representation避免重复运算实现constant space.
呵呵, 就是因为没看过dutch flag, 所以想了半天, 最后忽然开窍 :D

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

: lz power怎么算的：
: 最简单的是y--每次乘x？
: better running time的是recursion + DP？
: const space的是每次乘方？比如x^15=x^8 * x^4 * x^2 * x^1，但是有重复运算。
: sort color的不算tricky，如果你看到过dutch flag的话，你看interviewer连flag的
: 颜色都没改:P
:
: .)
: .
: running time太

w*x2012-04-27 07:04

39 楼

我感觉是我把题目记错了, interviewer问的应该是proof whether there is a string
that can produce a sequence strictly decreasing in length. 不是non-
increasing.
如果是non-increasing我也觉得除了"22"之外就没有了. 当时没有严格的证明strictly
decreasing不存在, 只是举了两个例子:
比如"111", 后面是"31", 然后是"1311". "31"就是最小的length.
"1111"(之前是"一百一十一个1", 之前是更多的1), 之后是"41", 然后"1411". 长度还是
在"41"是达到最小, 然后开始增加.
所以就算从无穷多的1开始, 最后会达到一个"xxxx1"的情况, 这时候长度最短, 然后就
开始增加
了.
还要感谢1337coder大侠, 你的网站真的对我帮助很大. 11月份去面google的时候有一
题就是大
侠解过的, 不过可惜我后面在其他题目上犯了低级错误没拿到offer...

length is:
only

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

: >>Proof whether there is an input string that can produce a
: sequence that's strictly non-increasing in length.
: One example of an input that produces sequence non-increasing in length is:
: 22,
: since it will produce the next output of 22 infinitely.
: Also, you can prove that for any k groups of numbers (a group consists only
: the same consecutive numbers).
: Assume group = { a1, a2, ... ak },
: then the next group = { m1a1 m2a2 ... mkak }, a total of 2k length.
: Since a1 != a2, a2 != a1 && a2 != a3, ... ak-1 != ak-2 && ak-1 != ak,

f*r2012-04-27 07:04

40 楼

cong! thanks for sharing.

.)
.
running time太
种, 然后

【在 w*****x 的大作中提到】

: 刚拿到offer, 发面经回馈版面. (不知道怎么发包子, 会的人教一下, 一定散尽家财.)
: 一切起源于9月底, 发现facebook在西雅图开了office在招聘, 于是顺手投了个简历.
: Recruiter很快回复, 要求做两个中等或者难的puzzle再开始面试. 那时候工作很忙,
: 也就耽搁了. 一直拖到thanksgiving假期才腾出点时间做了两个中等的puzzle交上去.
: facebull也做了, 本地机器上运行都没问题, 但是评卷机器人老说不对, 估计running time太
: 慢了.
: 电话面试:
: Puzzle做完了就开始电面. 加州office的人打电话过来, 信号不好break up无数次最后
: 干脆断掉了直接在网上聊:) 题目是实现int power(int x, int y), 先写最简单的那种, 然后
: 写个better running time, 然后写个只用constant memory的. 最后一个constant

t*02012-04-27 07:04

41 楼

cong

g*s2012-04-27 07:04

42 楼

hi, why ur site name is "ihas1337code". does that mean "i has 1337 code"?
why not "i have"?

yield
in
non-
string

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

: "Then the minimum possible of numbers of the next next group must also yield
: a total of k groups of numbers, which the length is also 2k, which is in
: non-increasing order in length."
: The proof is for the case which yields the "minimum" possible of number
: where the minimum length = 2*k can produce sequence length's in non-
: increasing order. It doesn't mean the next sequence's length must be non-
: increasing.
: I might still be wrong though, correct me if I'm wrong.
: Can LZ please share how to answer: "Proof whether there is an input string
: that can produce a sequence that's strictly non-increasing in length.",

g*s2012-04-27 07:04

43 楼

if strictly decreasing, then finally it would hit to a single digit and
then start to increasing.
so u sure the interviewer asks "strictly decreasing"?

string
strictly
还是

【在 w*****x 的大作中提到】

: 我感觉是我把题目记错了, interviewer问的应该是proof whether there is a string
: that can produce a sequence strictly decreasing in length. 不是non-
: increasing.
: 如果是non-increasing我也觉得除了"22"之外就没有了. 当时没有严格的证明strictly
: decreasing不存在, 只是举了两个例子:
: 比如"111", 后面是"31", 然后是"1311". "31"就是最小的length.
: "1111"(之前是"一百一十一个1", 之前是更多的1), 之后是"41", 然后"1411". 长度还是
: 在"41"是达到最小, 然后开始增加.
: 所以就算从无穷多的1开始, 最后会达到一个"xxxx1"的情况, 这时候长度最短, 然后就
: 开始增加

Z*Z2012-04-27 07:04

44 楼

you raised two good points

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

: if strictly decreasing, then finally it would hit to a single digit and
: then start to increasing.
: so u sure the interviewer asks "strictly decreasing"?
:
: string
: strictly
: 还是

i*e2012-04-27 07:04

45 楼

谢谢，不敢当.
还有要谢谢你分享的面试题
以后要招人请别忘了 referral 我哦... （开玩笑的嘻嘻） :)
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

string
strictly
还是

【在 w*****x 的大作中提到】

: 我感觉是我把题目记错了, interviewer问的应该是proof whether there is a string
: that can produce a sequence strictly decreasing in length. 不是non-
: increasing.
: 如果是non-increasing我也觉得除了"22"之外就没有了. 当时没有严格的证明strictly
: decreasing不存在, 只是举了两个例子:
: 比如"111", 后面是"31", 然后是"1311". "31"就是最小的length.
: "1111"(之前是"一百一十一个1", 之前是更多的1), 之后是"41", 然后"1411". 长度还是
: 在"41"是达到最小, 然后开始增加.
: 所以就算从无穷多的1开始, 最后会达到一个"xxxx1"的情况, 这时候长度最短, 然后就
: 开始增加

i*e2012-04-27 07:04

46 楼

@grandjmitbbs:
I decided to name my site as "i has 1337 code" because of the lolcats
internet culture hehe. See here:
http://en.wikipedia.org/wiki/Lol_cats
@grandjmitbbs & ZhangBZ:
It seemed obvious (based on our intuitions) that it would never have such
inputs which produce sequences decreasing in length, but maybe the
interviewer wants LZ to prove it (remember, it's easy to follow your
intuition, but not necessarily easy to construct a correct proof).
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

g*y2012-04-27 07:04

47 楼

cong

j*u2012-04-27 07:04

48 楼

明白了，类似这样：
// assume x > 0, y > 0
int Power(int x, int y)
{
int pow = 1;
while (y > 0)
{
if ((y & 1) != 0) pow *= x;
x *= x;
y >>= 1;
}
return pow;
}

【在 w*****x 的大作中提到】

: 我感觉是我把题目记错了, interviewer问的应该是proof whether there is a string
: that can produce a sequence strictly decreasing in length. 不是non-
: increasing.
: 如果是non-increasing我也觉得除了"22"之外就没有了. 当时没有严格的证明strictly
: decreasing不存在, 只是举了两个例子:
: 比如"111", 后面是"31", 然后是"1311". "31"就是最小的length.
: "1111"(之前是"一百一十一个1", 之前是更多的1), 之后是"41", 然后"1411". 长度还是
: 在"41"是达到最小, 然后开始增加.
: 所以就算从无穷多的1开始, 最后会达到一个"xxxx1"的情况, 这时候长度最短, 然后就
: 开始增加

n*s2012-04-27 07:04

49 楼

mark