亚马逊访谈|第三集

请在下面找到我在亚马逊采访的细节。

面谈日期： 2012年7月26日

轮数： 1个在线考试+4个PI

面试类型： 新生校园面试

在线测试（时间）：90分钟

20个客观问题： 能力和基本C目标问题。

2个主观问题： 我 给定一个包含每个节点中的字符的链表，将其节点分隔开来，使包含元音的所有节点都移动到链表的末尾。我们必须维持秩序。 二、 括号检查器。

第一轮面试（50分钟）

问题1： 您将获得两个链表，其节点包含一个数字作为数据成员。两个列表都代表一个数字。您必须添加它们并返回结果列表。 输入：9->9->3->4->5和8->9->1（代表99345和891） 输出：1->0->0->2->3->6 我的解决方案： 反转链接列表。创建新的金额列表，并将其反转。最后，反转结果列表。

问题2： 面试官要求在不改变原始列表的情况下解决上述问题。 我的解决方案： 计算两个列表中的节点数。如果相等，则简单地递归添加两个列表。如果没有，则前进一个temp ptr，它是一个指针，通过不同的节点指向较大列表的头部，然后添加temp和列表2所指向的列表。一定要记住随身携带的物品。递归地添加。传播较大列表中剩余元素的进位。被要求编写代码。编码了。

第二轮面试（60分钟）

问题1： 在一次扫描中删除链表末尾的第n个节点。

问题2： 在链表中，除了下一个ptr，还存在一个随机ptr。 克隆链接列表。 在O（n）中完成，但通过修改链接列表，然后恢复它。被要求在不修改原始列表的情况下执行此操作。是在O（n^2）中做的

问题3： 给出了BST的两个节点。打印从第一个节点到第二个节点的路径。除了正常的左指针和右指针之外，还提供了父指针 .

第三轮面试（1小时）

问题1： 这里有一个由n个整数组成的数组，其中元素的范围为n，即最大数和最小数之差为n。找到重复数。

问题2： 问题1的延伸。被要求找出每个数字重复的次数。

问题3： 每个数据元素有n帧m个。每个帧中的数据元素按递增顺序排列。我们为您提供了m*n空间，您必须在其中按递增顺序排列所有数据。

我的第一个解决方案是使用合并排序。他修改了这个问题，因为只有O（n）空间，你需要以最快的速度以递增的顺序发送数据。 我的第二个解决方案是使用min heap，并用所有n帧中的第一个元素构造它。Min heap还包含表示数据元素帧数的额外字段。这种数据结构可以满足需要。

第四轮面试（1小时）

问题1： 用O（n）中最大的下一个整数替换数组中的每个元素。 我做不到。我试过了，但没有成功。当你进入最后一轮时，这是意料不到的。

问题2： 反转链表中的每k个节点。

很好，但最终没有被选中……。

本文由 维奈·凯坦 我们很快会将Vinay对雅虎和微软的采访作为单独的帖子发布。Vinay被微软选中。很多人祝贺Vinay当选。

如果你喜欢Geeksforgek，并想贡献自己的力量，你也可以写一篇文章，然后把你的文章发到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。