l*********c
发帖数: 29 | 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就可以找到那个
值的方法。
祝大家早日找到理想工作！ |
O******i
发帖数: 269 | 2 faint, 1和6是同一类型的题目也会重复考。
如果是普通树，递归reverse孩子节点是否用类似reverse字符串的方法（首尾指针交换
，然后向中间移动再交换直到指针相交)？ |
O******i
发帖数: 269 | 3 3)是否转为逆波兰30 5 10 ＋ ＊再用栈计算会比较好？ |
j*****l
发帖数: 1650 | |
f*******b
发帖数: 520 | 5 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。
|
n*******w
发帖数: 687 | 6 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。
|
f*******t
发帖数: 7549 | 7 赞面经
感觉这个题最难写：
3.写一段代码，给一个字符串，例如"30*(5+10)",输出计算结果。 |
O******i
发帖数: 269 | 8 不是brain teaser, 是编程珠玑和knuth都介绍的经典的蓄水池抽样(reservoir
sampling)
另外在面试jane street的时候还遇到一个比较有意思的题目：
现在有一个很长的linkedlist,要从中随机选取一个node，我回答先扫一遍求的长度，
然后在找那个node,他便又问能否给出一个只需要扫描一便linkedlist就可以找到那个
值的方法。
这题是brain teaser吧。答案是使用两个pointer。一个一直往前走，另一个指向结果。 |
d********t
发帖数: 9628 | 9 啥叫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。
|
O******i
发帖数: 269 | 10 总体说不太难，很多都是版上讨论过的题，拿不到offer好像说不过去。。。 |
|
|
s******n
发帖数: 3946 | 11 写计算器代码少于100行不太可能，只能大概写个伪码。
找数组random这种东西作为考试真没意思，看过的人马上知道怎么做，没看过的人能当
场30分钟内想的出来的太少了。至少得有点变化。
【在 n*******w 的大作中提到】
: bless！
: 1.写一段程序比较两棵树是否一样。
: 常见题。
: 2.有一个奇怪的linkedlist,除了next pointer还有一个random pointer指向一个随机
: 的节点。问如何实现clone函数。
: 最近版上刚讨论过。先creat big linkedlist然后split。
: 3.写一段代码，给一个字符串，例如"30*(5+10)",输出计算结果。
: 经典算法。两个stack，一个操作数，一个操作符。写代码其实不简单，要定义操作符
: 的优先级。
: 4.写一段代码，输入一个数组和一个数字，找两个数组元素和为给定数字。
|
s******n
发帖数: 3946 | 12 第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;
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;
} |
p*****2
发帖数: 21240 | 13
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;
|
p*****2
发帖数: 21240 | 14 我的想法是先变成
2 1 6 8 7 9 就是把linked list reverse
然后在n个，n个reverse
8 7 9 2 1 6 |
k***t
发帖数: 276 | 15 这个思路挺好。不过好像要double link list才比较方便适用。
【在 p*****2 的大作中提到】
: 我的想法是先变成
: 2 1 6 8 7 9 就是把linked list reverse
: 然后在n个，n个reverse
: 8 7 9 2 1 6
|
q****x
发帖数: 7404 | 16 第七题有意思。
【在 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。
|
c***8
发帖数: 188 | 17 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。
|
q******8
发帖数: 848 | 18 第七题，通过facebook推荐商品那个题有什么思路吗？ |
x*******7
发帖数: 223 | 19 编程珠玑 哪一章讲了reservoir sampling？
果。
【在 O******i 的大作中提到】
: 不是brain teaser, 是编程珠玑和knuth都介绍的经典的蓄水池抽样(reservoir
: sampling)
: 另外在面试jane street的时候还遇到一个比较有意思的题目：
: 现在有一个很长的linkedlist,要从中随机选取一个node，我回答先扫一遍求的长度，
: 然后在找那个node,他便又问能否给出一个只需要扫描一便linkedlist就可以找到那个
: 值的方法。
: 这题是brain teaser吧。答案是使用两个pointer。一个一直往前走，另一个指向结果。
|
r**********1
发帖数: 292 | |
|
|
l*********c
发帖数: 29 | 21 据说是用各种方式增加amazon网页的浏览次数。
【在 d********t 的大作中提到】
: 啥叫trafic组？
|
l*********c
发帖数: 29 | 22 我当时用了一个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
|
d********t
发帖数: 9628 | 23 该改成traffick组
【在 l*********c 的大作中提到】
: 据说是用各种方式增加amazon网页的浏览次数。
|
l*********c
发帖数: 29 | 24 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推荐商品那个题有什么思路吗？
|
l*********c
发帖数: 29 | 25 我觉得应该可以的。
【在 O******i 的大作中提到】
: faint, 1和6是同一类型的题目也会重复考。
: 如果是普通树，递归reverse孩子节点是否用类似reverse字符串的方法（首尾指针交换
: ，然后向中间移动再交换直到指针相交)？
|
l*********c
发帖数: 29 | 26 嗯。我当时是用栈做的。思路与逆波兰表达式类似。
【在 O******i 的大作中提到】
: 3)是否转为逆波兰30 5 10 ＋ ＊再用栈计算会比较好？
|
l*********c
发帖数: 29 | 27 第八题其实是离散的，可能我没说清楚。我感觉有点困难的是在某点之前是非递减的，
之后是非递增的，所以要处理相等的情况。
【在 n*******w 的大作中提到】
: bless！
: 1.写一段程序比较两棵树是否一样。
: 常见题。
: 2.有一个奇怪的linkedlist,除了next pointer还有一个random pointer指向一个随机
: 的节点。问如何实现clone函数。
: 最近版上刚讨论过。先creat big linkedlist然后split。
: 3.写一段代码，给一个字符串，例如"30*(5+10)",输出计算结果。
: 经典算法。两个stack，一个操作数，一个操作符。写代码其实不简单，要定义操作符
: 的优先级。
: 4.写一段代码，输入一个数组和一个数字，找两个数组元素和为给定数字。
|
i*******t
发帖数: 79 | 28 有些题简单，有些题很难，遇到难题可以说放弃吗？
是计分制吗？要是一道难题卡住了，后面简单题也没时间答怎么办？
第二题“先creat big linkedlist然后split。”能具体说说吗？ |
l*********c
发帖数: 29 | 29
我觉得如果遇到难题一定不能放弃，可以适当的问提示。
一道难题卡住了心态一定要调整。我当时就是吃了这个亏。
第二题那个create big linkedlist然后split的方法我也不太清楚。我当时建立了一个
hashmap用来map original的node与新的node。
【在 i*******t 的大作中提到】
: 有些题简单，有些题很难，遇到难题可以说放弃吗？
: 是计分制吗？要是一道难题卡住了，后面简单题也没时间答怎么办？
: 第二题“先creat big linkedlist然后split。”能具体说说吗？
|
q****x
发帖数: 7404 | 30 有消息吗？
【在 l*********c 的大作中提到】
:
: 我觉得如果遇到难题一定不能放弃，可以适当的问提示。
: 一道难题卡住了心态一定要调整。我当时就是吃了这个亏。
: 第二题那个create big linkedlist然后split的方法我也不太清楚。我当时建立了一个
: hashmap用来map original的node与新的node。
|
|
|
S**N
发帖数: 182 | 31 感恩节前面如果现在还没消息的话 肯定挂了吧
听说他们家很快
【在 q****x 的大作中提到】
: 有消息吗？
|
q****x
发帖数: 7404 | 32 楼主题难度不小。
【在 S**N 的大作中提到】
: 感恩节前面如果现在还没消息的话 肯定挂了吧
: 听说他们家很快
|
S**N
发帖数: 182 | 33 恩 要我面估计也挂
【在 q****x 的大作中提到】
: 楼主题难度不小。
|
p*****2
发帖数: 21240 | |
m*****k
发帖数: 731 | 35 这是数据结构严蔚敏上的例子吧。
【在 f*******t 的大作中提到】
: 赞面经
: 感觉这个题最难写：
: 3.写一段代码，给一个字符串，例如"30*(5+10)",输出计算结果。
|
q******8
发帖数: 848 | |
f********e
发帖数: 166 | |
Y**B
发帖数: 144 | 38 1.现在有三种包，大，中，小，以及相应的locker，如何设计这样一个存包的系统。
这个题怎么设计?说给说说 |
f*******t
发帖数: 7549 | 39 这帖又被顶上来了……不知道楼主现在怎样了，祝福一下~
发当时练手写的两题，3和5
http://115.com/file/e7smv89m |
l**********1
发帖数: 415 | 40 请给详细说说第2题，clone list的那个，没打看懂题目是啥意思。谁有讨论这个题的
链接？ |
|
|
L***Q
发帖数: 508 | 41 前面有人说建大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的那个，没打看懂题目是啥意思。谁有讨论这个题的
: 链接？
|
l*****a
发帖数: 14598 | 42 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+。
|
h*c
发帖数: 1859 | 43 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。
|
l*****a
发帖数: 14598 | 44 link能用吗？
【在 f*******t 的大作中提到】
: 这帖又被顶上来了……不知道楼主现在怎样了，祝福一下~
: 发当时练手写的两题，3和5
: http://115.com/file/e7smv89m
|
f*******t
发帖数: 7549 | 45 刚传的，应该不会下载不了吧？
【在 l*****a 的大作中提到】
: link能用吗？
|
e***s
发帖数: 799 | 46 没看懂. 这逻辑不对啊。
【在 l*****a 的大作中提到】
: why need map?
: A->random=B
: A->next->random=B->next
: so
: A->next->random=A->random->next
|
s*******f
发帖数: 1114 | 47 //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。
|
d*****d
发帖数: 180 | 48 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- |
x********3
发帖数: 160 | 49 我看到大家说第五题我震惊了，不是一遍遍历就完了么，当前第一个node和第三个node
数交换一下不就行了，需要这么复杂么？还是我sb了？求教 |
s*******f
发帖数: 1114 | 50 // 给一个字符串，例如"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。
|
|
|
i*******6
发帖数: 107 | 51 #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;i
if (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;i
if (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);
}
} |
