logo
Redian新闻
>未名空间
>gardening - 拈花惹草
>
我这样的黑手指还是买苗吧
avatar
我这样的黑手指还是买苗吧# gardening - 拈花惹草
l*c
1 楼
感恩节前去了趟amazon onsite，被面的是traffic组里的一个新成立的小team。以下是
我遇到的面试题，另外还附加了一些其他公司的面经。接下来几天就要出结果了，求祝
福。
1.写一段程序比较两棵树是否一样。
2.有一个奇怪的linkedlist,除了next pointer还有一个random pointer指向一个随机
的节点。问如何实现clone函数。
3.写一段代码，给一个字符串，例如"30*(5+10)",输出计算结果。
4.写一段代码，输入一个数组和一个数字，找两个数组元素和为给定数字。
5.输入一个linkedlist和一个数字例如：9->7->8->6->1->2 和 3，输出还是一个
linkedlist但是每三个数reverse一下，例如8->7->9->2->1->6。
6.如何求一个树的mirror（将所有节点的children节点反序排列）.
7.下面这道题目是吃饭的时候问的，题目比较长，大概的意思是,现在亚马逊希望通过
facebook寻找拥有共同爱好的用户，并推荐那些用户所购买的商品给这个用户。如果这
个新用户刚刚通过facebook连接到amazon的账户上，请设计一个算法和相应的数据结构
来给用户推荐商品。并列出时间复杂度和空间复杂度。
8.现在给定一个函数，f(x),x在某值之前是非递减的，在某值之后是非递增的。设计一
个算法快速查找这个值。我给出的算法最坏情况是O(n)，平均是O(lgn)，但是很可惜没
来得及写完。
amazon之前电面的时候有问:
1.现在有三种包，大，中，小，以及相应的locker，如何设计这样一个存包的系统。
2.如何寻找stack中的最大元素。
另外在面试jane street的时候还遇到一个比较有意思的题目：
现在有一个很长的linkedlist,要从中随机选取一个node，我回答先扫一遍求的长度，
然后在找那个node,他便又问能否给出一个只需要扫描一便linkedlist就可以找到那个
值的方法。
祝大家早日找到理想工作！
avatar
z*9
2 楼
今年是我种菜的第三年了。第一年我把地挖开就种上了西红柿西葫芦和豆角，结果一共
吃到了两根西葫芦和一顿豆角； 第二年我下本钱买了好些土啊牛粪啊混进地里，结果6
月时搬家了，当时西红柿都半人高了，黄瓜也开始爬藤了，只好含泪离开，还怕它们长
不好把架子全留下了。
今年是第三年，正好我妈也来了，我两摩拳擦掌准备大干一番，结果：下了20棵番茄籽
，一个没发；30棵黄瓜，发了4棵；辣椒茄子丝瓜更是全军覆没。老妈每天拉着脸叹气
：白挖了四厢地啊！白埋了那么多树叶啊！我实在受不了了，一拍大腿，咱买苗去！
先去的HD，刚过完black Friday , 只剩下歪瓜裂枣。转身就奔苗圃，哇塞，什么都有
啊，也不是那么贵嘛。我买了6棵大西红柿，6棵黄色金太阳，6棵辣椒，15棵豆角，6棵
日本茄子，2棵日本黄瓜，一下子把地都填的差不多了。每个品种才$3.99, 我觉得挺便
宜的。来年不浪费感情育苗了，还是直接买苗算了
avatar
O*i
3 楼
faint, 1和6是同一类型的题目也会重复考。
如果是普通树，递归reverse孩子节点是否用类似reverse字符串的方法（首尾指针交换
，然后向中间移动再交换直到指针相交)？
avatar
z*9
4 楼
我买的豆角是精华区里小裴推荐的Romano , 但是我买的这个是不爬藤的，希望也能高
产
avatar
O*i
5 楼
3)是否转为逆波兰30 5 10 ＋ ＊再用栈计算会比较好？
avatar
m*6
6 楼
恩，我一直建议新农民一开始还是买苗，以后有经验了，再育一些美国店没有的种子苗。
大路品种确实是店里买省事省心。
avatar
j*l
7 楼
bless
avatar
f*b
8 楼
Bless

【在 l*********c 的大作中提到】
: 感恩节前去了趟amazon onsite，被面的是traffic组里的一个新成立的小team。以下是
: 我遇到的面试题，另外还附加了一些其他公司的面经。接下来几天就要出结果了，求祝
: 福。
: 1.写一段程序比较两棵树是否一样。
: 2.有一个奇怪的linkedlist,除了next pointer还有一个random pointer指向一个随机
: 的节点。问如何实现clone函数。
: 3.写一段代码，给一个字符串，例如"30*(5+10)",输出计算结果。
: 4.写一段代码，输入一个数组和一个数字，找两个数组元素和为给定数字。
: 5.输入一个linkedlist和一个数字例如：9->7->8->6->1->2 和 3，输出还是一个
: linkedlist但是每三个数reverse一下，例如8->7->9->2->1->6。
avatar
n*w
9 楼
bless！
1.写一段程序比较两棵树是否一样。
常见题。
2.有一个奇怪的linkedlist,除了next pointer还有一个random pointer指向一个随机
的节点。问如何实现clone函数。
最近版上刚讨论过。先creat big linkedlist然后split。
3.写一段代码，给一个字符串，例如"30*(5+10)",输出计算结果。
经典算法。两个stack，一个操作数，一个操作符。写代码其实不简单，要定义操作符
的优先级。
4.写一段代码，输入一个数组和一个数字，找两个数组元素和为给定数字。
经典题。允许O(n)空间，hashtable。否则先sort，一前一后两个指针往中间找。
5.输入一个linkedlist和一个数字例如：9->7->8->6->1->2 和 3，输出还是一个
linkedlist但是每三个数reverse一下，例如8->7->9->2->1->6。
版上最近刚讨论过。递归或者iterative都有。
6.如何求一个树的mirror（将所有节点的children节点反序排列）.
跟遍历similar。
7.下面这道题目是吃饭的时候问的，题目比较长，大概的意思是,现在亚马逊希望通过
facebook寻找拥有共同爱好的用户，并推荐那些用户所购买的商品给这个用户。如果这
个新用户刚刚通过facebook连接到amazon的账户上，请设计一个算法和相应的数据结构
来给用户推荐商品。并列出时间复杂度和空间复杂度。
open question。不好答。
8.现在给定一个函数，f(x),x在某值之前是非递减的，在某值之后是非递增的。设计一
个算法快速查找这个值。我给出的算法最坏情况是O(n)，平均是O(lgn)，但是很可惜没
来得及写完。
跟离散的情况类似。比如一个数组n个元素，先递增然后递减。找到最大元素的index。
类似binary search。版上最近也讨论过。
连续的情况，给定x0，要比较f(x0)与f(x0+delta)的大小然后binary search。delta是
答案的精度。
amazon之前电面的时候有问:
1.现在有三种包，大，中，小，以及相应的locker，如何设计这样一个存包的系统。
2.如何寻找stack中的最大元素。
栈的每个entry增加一个变量，记录当前为止最大元素。
另外在面试jane street的时候还遇到一个比较有意思的题目：
现在有一个很长的linkedlist,要从中随机选取一个node，我回答先扫一遍求的长度，
然后在找那个node,他便又问能否给出一个只需要扫描一便linkedlist就可以找到那个
值的方法。
这题是brain teaser吧。答案是使用两个pointer。一个一直往前走，另一个指向结果。
比如指针为p1，p2.p1，p2指向第一个node。
p1指向下一个node，并以1/2的概率把p2指向p1.
p1指向下一个node，并以1/3的概率把p2指向p1.
。。。。。。
p1指向下一个node，并以1/n的概率把p2指向p1.
。。。。。。
直到p1为null，p2即是结果。

【在 l*********c 的大作中提到】
: 感恩节前去了趟amazon onsite，被面的是traffic组里的一个新成立的小team。以下是
: 我遇到的面试题，另外还附加了一些其他公司的面经。接下来几天就要出结果了，求祝
: 福。
: 1.写一段程序比较两棵树是否一样。
: 2.有一个奇怪的linkedlist,除了next pointer还有一个random pointer指向一个随机
: 的节点。问如何实现clone函数。
: 3.写一段代码，给一个字符串，例如"30*(5+10)",输出计算结果。
: 4.写一段代码，输入一个数组和一个数字，找两个数组元素和为给定数字。
: 5.输入一个linkedlist和一个数字例如：9->7->8->6->1->2 和 3，输出还是一个
: linkedlist但是每三个数reverse一下，例如8->7->9->2->1->6。
avatar
f*t
10 楼
赞面经
感觉这个题最难写：
3.写一段代码，给一个字符串，例如"30*(5+10)",输出计算结果。
avatar
O*i
11 楼
不是brain teaser, 是编程珠玑和knuth都介绍的经典的蓄水池抽样(reservoir
sampling)
另外在面试jane street的时候还遇到一个比较有意思的题目：
现在有一个很长的linkedlist,要从中随机选取一个node，我回答先扫一遍求的长度，
然后在找那个node,他便又问能否给出一个只需要扫描一便linkedlist就可以找到那个
值的方法。
这题是brain teaser吧。答案是使用两个pointer。一个一直往前走，另一个指向结果。
avatar
d*t
12 楼
啥叫trafic组？

【在 l*********c 的大作中提到】
: 感恩节前去了趟amazon onsite，被面的是traffic组里的一个新成立的小team。以下是
: 我遇到的面试题，另外还附加了一些其他公司的面经。接下来几天就要出结果了，求祝
: 福。
: 1.写一段程序比较两棵树是否一样。
: 2.有一个奇怪的linkedlist,除了next pointer还有一个random pointer指向一个随机
: 的节点。问如何实现clone函数。
: 3.写一段代码，给一个字符串，例如"30*(5+10)",输出计算结果。
: 4.写一段代码，输入一个数组和一个数字，找两个数组元素和为给定数字。
: 5.输入一个linkedlist和一个数字例如：9->7->8->6->1->2 和 3，输出还是一个
: linkedlist但是每三个数reverse一下，例如8->7->9->2->1->6。
avatar
O*i
13 楼
总体说不太难，很多都是版上讨论过的题，拿不到offer好像说不过去。。。
avatar
s*n
14 楼
写计算器代码少于100行不太可能，只能大概写个伪码。
找数组random这种东西作为考试真没意思，看过的人马上知道怎么做，没看过的人能当
场30分钟内想的出来的太少了。至少得有点变化。

【在 n*******w 的大作中提到】
: bless！
: 1.写一段程序比较两棵树是否一样。
: 常见题。
: 2.有一个奇怪的linkedlist,除了next pointer还有一个random pointer指向一个随机
: 的节点。问如何实现clone函数。
: 最近版上刚讨论过。先creat big linkedlist然后split。
: 3.写一段代码，给一个字符串，例如"30*(5+10)",输出计算结果。
: 经典算法。两个stack，一个操作数，一个操作符。写代码其实不简单，要定义操作符
: 的优先级。
: 4.写一段代码，输入一个数组和一个数字，找两个数组元素和为给定数字。
avatar
s*n
15 楼
第5题我来写一个吧，每段称为一个chunk
Node* reorder(Node* head, int n) {
Node* newHead = NULL;
Node* chunk_prev=NULL;
Node* chunk_head = head;
while (chunk_head!=NULL) {
Node* saved_chunk_head = chunk_head;
Node* chunk_tail = chunk_head->next;
for (int i=0; iNode* tmp = chunk_tail->next;
chunk_tail->next=chunk_head;
chunk_head = chunk_tail;
chunk_tail = tmp;
}
if (chunk_prev!=NULL) chunk_prev->next = chunk_head;
else newHead = chunk_head;
chunk_prev = saved_chunk_head;
chunk_head = chunk_tail;
}
if (chunk_prev) chunk_prev->next = NULL;
return newHead;
}
avatar
p*2
16 楼

API这样定义是不是更好？
int reorder(Node** head, int n)

【在 s******n 的大作中提到】
: 第5题我来写一个吧，每段称为一个chunk
: Node* reorder(Node* head, int n) {
: Node* newHead = NULL;
: Node* chunk_prev=NULL;
: Node* chunk_head = head;
: while (chunk_head!=NULL) {
: Node* saved_chunk_head = chunk_head;
: Node* chunk_tail = chunk_head->next;
: for (int i=0; i: Node* tmp = chunk_tail->next;
avatar
p*2
17 楼
我的想法是先变成
2 1 6 8 7 9 就是把linked list reverse
然后在n个，n个reverse
8 7 9 2 1 6
avatar
k*t
18 楼
这个思路挺好。不过好像要double link list才比较方便适用。

【在 p*****2 的大作中提到】
: 我的想法是先变成
: 2 1 6 8 7 9 就是把linked list reverse
: 然后在n个，n个reverse
: 8 7 9 2 1 6
avatar
q*x
19 楼
第七题有意思。

【在 l*********c 的大作中提到】
: 感恩节前去了趟amazon onsite，被面的是traffic组里的一个新成立的小team。以下是
: 我遇到的面试题，另外还附加了一些其他公司的面经。接下来几天就要出结果了，求祝
: 福。
: 1.写一段程序比较两棵树是否一样。
: 2.有一个奇怪的linkedlist,除了next pointer还有一个random pointer指向一个随机
: 的节点。问如何实现clone函数。
: 3.写一段代码，给一个字符串，例如"30*(5+10)",输出计算结果。
: 4.写一段代码，输入一个数组和一个数字，找两个数组元素和为给定数字。
: 5.输入一个linkedlist和一个数字例如：9->7->8->6->1->2 和 3，输出还是一个
: linkedlist但是每三个数reverse一下，例如8->7->9->2->1->6。
avatar
c*8
20 楼
bless

【在 l*********c 的大作中提到】
: 感恩节前去了趟amazon onsite，被面的是traffic组里的一个新成立的小team。以下是
: 我遇到的面试题，另外还附加了一些其他公司的面经。接下来几天就要出结果了，求祝
: 福。
: 1.写一段程序比较两棵树是否一样。
: 2.有一个奇怪的linkedlist,除了next pointer还有一个random pointer指向一个随机
: 的节点。问如何实现clone函数。
: 3.写一段代码，给一个字符串，例如"30*(5+10)",输出计算结果。
: 4.写一段代码，输入一个数组和一个数字，找两个数组元素和为给定数字。
: 5.输入一个linkedlist和一个数字例如：9->7->8->6->1->2 和 3，输出还是一个
: linkedlist但是每三个数reverse一下，例如8->7->9->2->1->6。
avatar
q*8
21 楼
第七题，通过facebook推荐商品那个题有什么思路吗？
avatar
x*7
22 楼
编程珠玑 哪一章讲了reservoir sampling？

果。

【在 O******i 的大作中提到】
: 不是brain teaser, 是编程珠玑和knuth都介绍的经典的蓄水池抽样(reservoir
: sampling)
: 另外在面试jane street的时候还遇到一个比较有意思的题目：
: 现在有一个很长的linkedlist,要从中随机选取一个node，我回答先扫一遍求的长度，
: 然后在找那个node,他便又问能否给出一个只需要扫描一便linkedlist就可以找到那个
: 值的方法。
: 这题是brain teaser吧。答案是使用两个pointer。一个一直往前走，另一个指向结果。
avatar
r*1
23 楼
bless la
avatar
l*c
24 楼
据说是用各种方式增加amazon网页的浏览次数。

【在 d********t 的大作中提到】
: 啥叫trafic组？
avatar
l*c
25 楼
我当时用了一个stack，从linkedlist 的头部开始，removeFirst 然后push进 stack。
放进n个以后，pop所有元素到linkedlist队尾。

【在 p*****2 的大作中提到】
: 我的想法是先变成
: 2 1 6 8 7 9 就是把linked list reverse
: 然后在n个，n个reverse
: 8 7 9 2 1 6
avatar
d*t
26 楼
该改成traffick组

【在 l*********c 的大作中提到】
: 据说是用各种方式增加amazon网页的浏览次数。
avatar
l*c
27 楼
I created an inverted file at that time。key is interesting area, value is a
linkedlist of users. If a user is interested in x1, x2, x3 interesting area
, then we will use the users in the three linkedlist as a neighborhood of
the current user. Find the users shared the same interested areas, for
example share at least two same interest area, then find their shopping
history from Amazon, then give recommendation.

【在 q******8 的大作中提到】
: 第七题，通过facebook推荐商品那个题有什么思路吗？
avatar
l*c
28 楼
我觉得应该可以的。

【在 O******i 的大作中提到】
: faint, 1和6是同一类型的题目也会重复考。
: 如果是普通树，递归reverse孩子节点是否用类似reverse字符串的方法（首尾指针交换
: ，然后向中间移动再交换直到指针相交)？
avatar
l*c
29 楼
嗯。我当时是用栈做的。思路与逆波兰表达式类似。

【在 O******i 的大作中提到】
: 3)是否转为逆波兰30 5 10 ＋ ＊再用栈计算会比较好？
avatar
l*c
30 楼
第八题其实是离散的，可能我没说清楚。我感觉有点困难的是在某点之前是非递减的，
之后是非递增的，所以要处理相等的情况。

【在 n*******w 的大作中提到】
: bless！
: 1.写一段程序比较两棵树是否一样。
: 常见题。
: 2.有一个奇怪的linkedlist,除了next pointer还有一个random pointer指向一个随机
: 的节点。问如何实现clone函数。
: 最近版上刚讨论过。先creat big linkedlist然后split。
: 3.写一段代码，给一个字符串，例如"30*(5+10)",输出计算结果。
: 经典算法。两个stack，一个操作数，一个操作符。写代码其实不简单，要定义操作符
: 的优先级。
: 4.写一段代码，输入一个数组和一个数字，找两个数组元素和为给定数字。
avatar
i*t
31 楼
有些题简单，有些题很难，遇到难题可以说放弃吗？
是计分制吗？要是一道难题卡住了，后面简单题也没时间答怎么办？
第二题“先creat big linkedlist然后split。”能具体说说吗？
avatar
l*c
32 楼

我觉得如果遇到难题一定不能放弃，可以适当的问提示。
一道难题卡住了心态一定要调整。我当时就是吃了这个亏。
第二题那个create big linkedlist然后split的方法我也不太清楚。我当时建立了一个
hashmap用来map original的node与新的node。

【在 i*******t 的大作中提到】
: 有些题简单，有些题很难，遇到难题可以说放弃吗？
: 是计分制吗？要是一道难题卡住了，后面简单题也没时间答怎么办？
: 第二题“先creat big linkedlist然后split。”能具体说说吗？
avatar
q*x
33 楼
有消息吗？

【在 l*********c 的大作中提到】
:
: 我觉得如果遇到难题一定不能放弃，可以适当的问提示。
: 一道难题卡住了心态一定要调整。我当时就是吃了这个亏。
: 第二题那个create big linkedlist然后split的方法我也不太清楚。我当时建立了一个
: hashmap用来map original的node与新的node。
avatar
S*N
34 楼
感恩节前面如果现在还没消息的话 肯定挂了吧
听说他们家很快

【在 q****x 的大作中提到】
: 有消息吗？
avatar
q*x
35 楼
楼主题难度不小。

【在 S**N 的大作中提到】
: 感恩节前面如果现在还没消息的话 肯定挂了吧
: 听说他们家很快
avatar
S*N
36 楼
恩 要我面估计也挂

【在 q****x 的大作中提到】
: 楼主题难度不小。
avatar
p*2
37 楼
还是挺难的。
avatar
m*k
38 楼
这是数据结构严蔚敏上的例子吧。

【在 f*******t 的大作中提到】
: 赞面经
: 感觉这个题最难写：
: 3.写一段代码，给一个字符串，例如"30*(5+10)",输出计算结果。
avatar
q*8
39 楼
楼主难度不小，是fresh grad吗
avatar
f*e
40 楼
bless
avatar
Y*B
41 楼
1.现在有三种包，大，中，小，以及相应的locker，如何设计这样一个存包的系统。
这个题怎么设计?说给说说
avatar
f*t
42 楼
这帖又被顶上来了……不知道楼主现在怎样了，祝福一下~
发当时练手写的两题，3和5
http://115.com/file/e7smv89m
avatar
l*1
43 楼
请给详细说说第2题，clone list的那个，没打看懂题目是啥意思。谁有讨论这个题的
链接？
avatar
L*Q
44 楼
前面有人说建大linked list然后split，不过俺不知道具体啥意思。
俺有另外一个思路，如果是用C++写，可以用map。扫描原链表两遍。
step 1：copy链表，暂不初始化每个node的random指着。copy的同时，把原链表每个
node的地址和cloned链表每个node的地址一一对应，用map建立对应。
step 2：再次扫描原链表，假设当前扫描原链表node A，在clone链表中对应node A+。
可以得到node A random指针指向的node B的地址，然后在map中得到node B对应在
clone链表中的node B+的地址。把node A+的random指针设为node B+。

【在 l**********1 的大作中提到】
: 请给详细说说第2题，clone list的那个，没打看懂题目是啥意思。谁有讨论这个题的
: 链接？
avatar
l*a
45 楼
why need map?
A->random=B
A->next->random=B->next
so
A->next->random=A->random->next

【在 L***Q 的大作中提到】
: 前面有人说建大linked list然后split，不过俺不知道具体啥意思。
: 俺有另外一个思路，如果是用C++写，可以用map。扫描原链表两遍。
: step 1：copy链表，暂不初始化每个node的random指着。copy的同时，把原链表每个
: node的地址和cloned链表每个node的地址一一对应，用map建立对应。
: step 2：再次扫描原链表，假设当前扫描原链表node A，在clone链表中对应node A+。
: 可以得到node A random指针指向的node B的地址，然后在map中得到node B对应在
: clone链表中的node B+的地址。把node A+的random指针设为node B+。
avatar
h*c
46 楼
no.2是一个经典踢...

【在 l*********c 的大作中提到】
: 感恩节前去了趟amazon onsite，被面的是traffic组里的一个新成立的小team。以下是
: 我遇到的面试题，另外还附加了一些其他公司的面经。接下来几天就要出结果了，求祝
: 福。
: 1.写一段程序比较两棵树是否一样。
: 2.有一个奇怪的linkedlist,除了next pointer还有一个random pointer指向一个随机
: 的节点。问如何实现clone函数。
: 3.写一段代码，给一个字符串，例如"30*(5+10)",输出计算结果。
: 4.写一段代码，输入一个数组和一个数字，找两个数组元素和为给定数字。
: 5.输入一个linkedlist和一个数字例如：9->7->8->6->1->2 和 3，输出还是一个
: linkedlist但是每三个数reverse一下，例如8->7->9->2->1->6。
avatar
l*a
47 楼
link能用吗？

【在 f*******t 的大作中提到】
: 这帖又被顶上来了……不知道楼主现在怎样了，祝福一下~
: 发当时练手写的两题，3和5
: http://115.com/file/e7smv89m
avatar
f*t
48 楼
刚传的，应该不会下载不了吧？

【在 l*****a 的大作中提到】
: link能用吗？
avatar
e*s
49 楼
没看懂. 这逻辑不对啊。

【在 l*****a 的大作中提到】
: why need map?
: A->random=B
: A->next->random=B->next
: so
: A->next->random=A->random->next
avatar
s*f
50 楼
//2.有一个奇怪的linkedlist,除了next pointer还有一个random pointer指向一个随机
//的节点。问如何实现clone函数。
struct LNode{
LNode *next, *random;
};
LNode* CloneList(LNode *head){
if (!head)
return NULL;
map mp;
LNode *h = new LNode;
mp[head] = h;
mp[NULL] = NULL;
LNode *p = h;
LNode *q = head;
head = head->next;
while (head){
p->next = new LNode;
p = p->next;
mp[head] = p;
head = head->next;
}
p->next = NULL;
p = h;
while (q){
p->random = mp[q->random];
p = p->next;
q = q->next;
}
}

【在 l*********c 的大作中提到】
: 感恩节前去了趟amazon onsite，被面的是traffic组里的一个新成立的小team。以下是
: 我遇到的面试题，另外还附加了一些其他公司的面经。接下来几天就要出结果了，求祝
: 福。
: 1.写一段程序比较两棵树是否一样。
: 2.有一个奇怪的linkedlist,除了next pointer还有一个random pointer指向一个随机
: 的节点。问如何实现clone函数。
: 3.写一段代码，给一个字符串，例如"30*(5+10)",输出计算结果。
: 4.写一段代码，输入一个数组和一个数字，找两个数组元素和为给定数字。
: 5.输入一个linkedlist和一个数字例如：9->7->8->6->1->2 和 3，输出还是一个
: linkedlist但是每三个数reverse一下，例如8->7->9->2->1->6。
avatar
d*d
51 楼
If original list is A->B->C->D...
Insert A',B',C',D' into the orignal list
we get
A->A'->B->B'->C->C'->D->D'......
then we have
original->next->random = original->random->next;
for example
assume A.random --> C
we will have:
A' == A.next
A.random==C
C.next=C'
A'.random=A.next.random=A.random.next=C.next=C'
once done, split it out.
http://tech-queries.blogspot.com/2011/04/copy-linked-list-with-
avatar
x*3
52 楼
我看到大家说第五题我震惊了，不是一遍遍历就完了么，当前第一个node和第三个node
数交换一下不就行了，需要这么复杂么？还是我sb了？求教
avatar
s*f
53 楼
// 给一个字符串，例如"30*(5+10)",输出计算结果。
double GetValue(double b1, double b2, char op){
switch(op){
case '+':
return b1 + b2;
case '-':
return b1 - b2;
case '*':
return b1 * b2;
case '/':
if (b2 < 0.00000001)
return 0;
return b1 / b2;
default:
return 0;
}
}
bool OpPriority(char op1, char op2){
if (op1 == '*' || op1 == '/'){
return true;
}else if ((op1 == '+' || op1 == '-') && (op2 != '*' && op2 != '/')){
return true;
}else{
return false;
}
}
double CalStr(char *str){
stack snum;
stack sop;
while (*str){
char *end;
double a = strtod(str, &end);
if (str == end){
while (isspace(*str)){
++str;
}
if (*str == '('){
sop.push('(');
++str;
continue;
}else{
break;
}
}
snum.push(a);
str = end;
while (isspace(*str)){
++str;
}
if (!*str){
break;
}
if (!strchr("+-/*)", *str)){
break;
}
if (!sop.empty() && OpPriority(sop.top(), *str)){
if (snum.size() < 2){
return 0; // illegal
}
double b1 = snum.top();
snum.pop();
double value = GetValue(b1, snum.top(), sop.top());
snum.pop();
snum.push(value);
sop.pop();
}
if (*str == ')'){
if (!sop.empty() && sop.top() == '('){
sop.pop();
}else{
return 0;
}
}else{
sop.push(*str);
}
++str;
}//while
if (!sop.empty()){
if (snum.size() < 2){
return 0; // illegal
}
double b1 = snum.top();
snum.pop();
double value = GetValue(b1, snum.top(), sop.top());
snum.pop();
snum.push(value);
sop.pop();
}
if (snum.empty()){
return 0;
}else{
return snum.top();
}
}
void TestCalStr(){
double a = CalStr("30*(5+10)");
double b = CalStr(" 30*(5+10)");
double c = CalStr(" +30*(5+10)");
double d = CalStr("30 *(5+10)");
double e = CalStr("30 * (5 + 10)");
double f = CalStr("30*(5+10))");
double g = CalStr("30*(5+10)+");
// double a = CalStr();
// double a = CalStr();
// double a = CalStr();
// double a = CalStr();
// double a = CalStr();
// double a = CalStr();
}

【在 l*********c 的大作中提到】
: 感恩节前去了趟amazon onsite，被面的是traffic组里的一个新成立的小team。以下是
: 我遇到的面试题，另外还附加了一些其他公司的面经。接下来几天就要出结果了，求祝
: 福。
: 1.写一段程序比较两棵树是否一样。
: 2.有一个奇怪的linkedlist,除了next pointer还有一个random pointer指向一个随机
: 的节点。问如何实现clone函数。
: 3.写一段代码，给一个字符串，例如"30*(5+10)",输出计算结果。
: 4.写一段代码，输入一个数组和一个数字，找两个数组元素和为给定数字。
: 5.输入一个linkedlist和一个数字例如：9->7->8->6->1->2 和 3，输出还是一个
: linkedlist但是每三个数reverse一下，例如8->7->9->2->1->6。
avatar
i*6
54 楼
#5.输入一个linkedlist和一个数字例如：9->7->8->6->1->2 和 3，输出还是一个
linkedlist但是每三个数reverse一下，例如8->7->9->2->1->6。
扩展了这道题，写成可以自己设置每几个数reverse一下。
思路大概是这样,一个原始链表为
0->1->2->3->4->5->6
如果每3个数反转一下的话，那么先把5指向0,6指向3,2指向null （换言之则是把第kn
个节点指向(k-2)*n+1个节点，再把第n个节点指向null），可以得到
6->3->4->5->0->1->2
然后把整个链表反转就是我们要的结果：
2->1->0->5->4->3->6
附上java代码和数据结构，以及测试用例，在netbeans5.5测试通过：
class ListElement{
public ListElement next;
public int data;
public ListElement(){

}
public ListElement(int data){
this.data = data;
}
public void print(){
if (next == null){
System.out.println(data);
} else
System.out.print(data+" -> ");
}
}
public class Main {
/**
* @param args the command line arguments
*/
public static void printlist(ListElement head){
ListElement previous = head;
while (previous!=null){
previous.print();
previous = previous.next;
}
}
public static ListElement reverseList(ListElement head){
if (head == null) return null;
ListElement next2 = null,pos=head;
ListElement next = pos.next;
pos.next = null;
while (next != null){
next2 = next.next;
next.next = pos;
pos = next;
next = next2;
}
printlist(pos);
return pos;

}
public static ListElement reversePart(ListElement head, int n){
// check input
if (head == null || n<=0) return null;
// initialization
ListElement head1,head2,head3,tail1,tail2; //1,2,3 means the 1st
,2nd,3rd part of n-range linkedlist
boolean isfirstpart = true;
head1 = head; tail1=head;
// generate the answer on the basis of situation
// in case of n=1, according to this algorithm,
// if n=1, the linkedlist will reverse when it is finished
building
// so there is no need to reverse it again
if (n==1) return reverseList(head);
for (int i=1;iif (tail1.next !=null) tail1=tail1.next;
else{ // there is less than n nodes in the list, just
keep the head then reverse the whole list
return reverseList(head);
}
}
if (tail1.next == null){ //there is just n nodes in the list,
reverse it.
return reverseList(head);
}
head2 = tail1.next; tail2=head2;
if (isfirstpart) {
tail1.next = null;
isfirstpart = false;
}
while (true){
// try to find tail2
for (int i=1;iif (tail2.next != null) tail2=tail2.next;
else{ //there is less than 2n nodes in the list,
point the last one to head1, then reverse linkedlist from head2
tail2.next = head1;
return reverseList(head2);
}
}
if (tail2.next == null){ // there is just 2n nodes in
the list, point the last one to head1, reverse from head2
tail2.next = head1;
return reverseList(head2);
}
head3 = tail2.next; tail2.next = head1;
head1 = head2; head2 = head3; tail2 = head2;
}
}
public static void main(String[] args) {
// TODO code application logic here
//set linkedlist
ListElement head = new ListElement(0);
ListElement previous = head;
ListElement next;
for (int i=1;i<21;i++){
next = new ListElement(i);
previous.next = next;
previous = next;
}
printlist(head);
//reverseList(head);
reversePart(head,3);
}
}
相关阅读
求推荐好用的草籽西瓜要育苗吗怎么能种空心菜？有人买过KMart的玫瑰和果树吗？去年店里买的番茄，草莓 in pot今年还会发芽生长吗？heirloom（也叫heritage）和杂交（也叫F1）区别 (转载)请问下发豆芽的豆子在哪里买？还有豌豆苗的那个豌豆种子在哪里买？sprinkler system会埋多深，翻地会不会弄断它前门口种什么菜，看起来像植物，不像菜?请大家帮忙推荐草种!!求购草头（黄花菜/南苜蓿）种子让爬藤玫瑰爬正面一侧扶手是好主意吗？求助:我家茶花怎么了?（BSSD）快来排队，发包子咯！【申请】沾花惹草(Gardening)版,版副 (转载)救命啊！bare root rose长的新芽都枯了美国有没有类似中国农业电视台之类的视频？【计划1】中间那个新的她，象太阳？我的茶花还有救吗?新农民请教哪个牌子mower好用？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。