亚马逊面试| 114场（校园实习）

最近亚马逊印度公司访问了我们的校园，进行了为期两个月的实习。一共有三轮

2个在线编码问题+20个MCQ

MCQ问题主要是关于数据结构的6-7个问题，7-8个C语言输出程序，4-5个关于一般能力倾向、概率、排列和组合的问题。

这两个问题是：

A. 给定一组区间，必须对重叠区间进行分组，并以非递减顺序显示所有区间。 例：（1,5）、（8,11）、（3,6）、（10,20） 产出：（1,6）、（8,20） 提示：虽然这是一个非常简单的问题，可以在许多在线门户网站上找到，但请记住，给定的输入是字符串形式的，需要仔细分析。 为此，不必将字符串转换为整数，您可以使用

while(scanf("(%d,%d),",&a,&b))
{
//store a and b as you wish to
}

B 给定一组负整数和非负整数，需要重新排列它们，使负整数和非负整数在交替位置。 约束条件：所有负整数和非负整数的顺序必须与之前相同。如果有更多的负整数，则超出的整数应出现在数组的末尾，如果非负整数的数量更多，则非负整数的顺序也应相同。

eg: -5,-2,5,2,4,7,1,8,0,-8
output: -5,5,-2,2,-8,4,7,1,8,0

同样，对于输入，您可以使用上述技术。

在这轮面试之后，150名学生中约有20人被选中进行个人面试。

以下是我们两人的面试经历。

人1： 第一轮：

1. 如果一个二叉树有三个指针，左、右和同级，其中所有的左、右子指针都已填充，则需要用同一级别上下一个节点的地址填充同级指针。如果它是级别的最后一个节点，请填充NULL。

我首先告诉他一种使用带队列的水平顺序遍历的方法。然后他让我不用排队，使用递归。我告诉他这个方法，当他满意时，他让我在纸上写一个代码，涵盖所有角落的案例。

2. 给定一个大小为2n+1的数组，其中n个整数重复两次，一个整数只出现一次，找到该整数。 我用异或告诉他。然后他把问题改为 给定一个大小为2n+2的数组，其中n个整数重复2次，2个整数只出现一次。找到他们两个。这也可以使用XOR实现。你可以在Geeks for Geeks的arrays部分找到解决方案

3.给定任何一个二叉树，其中所有的叶子的左指针和右指针在一个从左到右的双链表中连接，而不是指向NULL。此外，最左边的叶的左指针指向该节点本身，最右边的叶的右指针指向该叶本身，如果存在没有左或右子节点的内部节点，则该特定指针将指向该节点本身。 你需要 查找树的有序遍历。 我告诉他这个方法后，他又让我在纸上写一个代码。

4.他问我所知道的数据结构，然后开始用图表提问。我们如何代表他们？ 邻接矩阵和邻接列表哪个更好？ 然后他给出了一些情况，并问我应该使用这两种实现中的哪一种。

第二轮：

1.他花了大约15分钟详细询问了我的项目。

2.然后他问我在第三学期和第四学期学习的科目。 我忘了我学过的所有科目 经过深思熟虑后，我说出的第一个话题是Unix Linux编程。然后他让我在5分钟内写出所有我知道的命令。我列出了将近20个。他问我其中几个的功能以及它们之间的区别。

3.最后他问了我一个关于二叉树的问题，这个问题很简单。 将二叉搜索树中每个节点的数据替换为大于它的所有节点之和。 我给了他使用反向顺序遍历的方法。然后他让我在纸上写一个代码。我在代码中使用了指针。然后他让我写一个不使用指针、静态变量或全局变量的代码。 我写的。最后，他似乎很满意。

第二个人

第1轮： 1. 给定一个单链表和一个整数k，我必须编写代码，以成对的k反转列表，同时处理所有基本情况。 例如1->2->3->4->5->6->7->8K=3 o/p 3->2->1->6->5->4->8->7 她实际上在一些基本案例中尝试了我的代码，试图找到漏洞

2. 给定两个数组，一个大小为n，另一个大小为（n+k），但填充了k值，我被要求在不使用任何额外空间的情况下将这两个数组合并到第二个数组中。我很快给了她逻辑，然后我们接着问下一个问题。

3. 给定一个字符串，找到该字符串中第一个重复字符的索引。 abcba o/p:0（正如“a”最初出现在“b”之前，尽管两者都重复了两次）。 同样，需要无错误代码。

4.然后她问了我一些关于我目前正在进行的研究项目的问题。这又持续了10-15分钟。

第二轮： 1.这一轮从关于我的研究项目的问题开始。然后他问我喜欢哪种数据结构。我们就堆和相关的时间复杂性进行了长时间的讨论。

2. 给定一棵二叉树、树中的任何节点和一个整数k，打印距离给定节点k处的所有节点。 请注意，节点可能在上方或下方。我们首先讨论了一种方法，在他对我的解释感到满意后，他要求提供无错误代码。

3. 给定一个整数n，在n个节点的情况下可以生成多少个BST ? 我告诉他加泰罗尼亚数和直接公式-2^n–n。但他想要一个推导，所以我建立了一个循环，并向他展示了DP来评估它。

4.给定n个人，你会被告知属于同一个国家的所有成对的人。你要说出不属于同一个国家的人的数量， 我将其表示为一个图表，并应用dfs来获得连接组件的数量和每个组件的大小。然后这是一个简单的公式，没有任何成分。

之后，他开始讨论亚马逊的生活、公司对你的期望以及你应该在公司做什么。

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