亚马逊面试体验|第174组（SDE）

最近，我在钦奈亚马逊发展中心接受了SDE职位的面试。以下是我的采访经历：

电话回合： 1) 给定一个长度为的数组，你必须为一个三角形选择3个长度（a、b和c），以使其满足条件a+b>c、b+c>a、a+c>b。找出可以从给定数组创建的可能三角形的数量。 例：356910 (3,9,10), (3 5 6), (5 6 10), (5 9 10), (5 6 9), (6 9 10) 所以可能的三角形数是6

2) 数组中的倒计时 数组的反转计数表示数组距离排序的距离（或距离）。如果数组已排序，则反转计数为0。如果数组按相反顺序排序，则反转计数为最大值。 从形式上讲，如果a[i]>a[j]和i 内部访谈1（F2F）： 3) 下一个更大的元素 给定一个数组，为每个元素打印下一个较大元素（NGE）。元素x的下一个较大元素是数组中x右侧的第一个较大元素。没有较大元素的元素，考虑下一个更大的元素为-1。 例如： a） 对于任何数组，最右边的元素总是有下一个较大的元素-1。 b） 对于按降序排序的数组，所有元素的下一个较大元素为-1。 c） 对于输入数组[4,5,2,25}，每个元素的下一个较大元素如下所示。

Element       NGE
   4      -->   5
   5      -->   25
   2      -->   25
   25     -->   -1

d） 对于输入数组[13,7,6,12}，每个元素的下一个较大元素如下所示。

  Element        NGE
   13      -->    -1
   7       -->     12
   6       -->     12
   12     -->     -1

4) 排序数组到平衡BST 给定一个排序数组。编写一个函数，使用数组元素创建一个平衡的二进制搜索树。 例如：

Input:  Array {1, 2, 3}
Output: A Balanced BST
     2
   /  
  1    3

Input: Array {1, 2, 3, 4}
Output: A Balanced BST
      3
    /  
   2    4
 /
1

内部面试2（F2F）： 5) 有向图中的圈检测 给定一个有向图，检查该图是否包含循环。如果给定的图形至少包含一个循环，则函数应返回true，否则返回false。例如，下图包含三个循环0->2->0、0->1->2->0和3->3，因此函数必须返回true。

6) 将BST转换为已排序的循环双链接列表 .

与招聘经理进行电话交流： 关于我的介绍。 然后他问起我的大学项目。我们讨论了该项目的OO设计。 然后他问我目前公司的最新发明 然后他问我关于虚拟内存的问题，并就此进行了深入讨论。 然后他来到我目前正在做的项目 然后他问我你为什么要离开我现在的公司？？ 然后他提出了一个要解决的问题。 7) 给定一个数组A[]和一个数字x，检查A[]中的对，总和为x 给定一个由n个数和另一个数x组成的数组A[]，确定S中是否存在两个和正好为x的元素。 他询问了上述问题的各种可能解决方案。

钢筋提升机轮（F2F）： 8) 给定一棵二叉树，求其直径。 树的直径（有时称为宽度）是树中两片叶子之间最长路径上的节点数。

在解决了上述问题后，他对上述问题增加了一个约束条件：（即）在一圈内找到树的直径 树上的转弯示例： 在树1->从1开始，在根部2向右转弯， 在树2->从3开始向左走，在1处向右转弯， 在树3中->从1开始向右，在3处向左转弯，

     2                 3                 1
    /                /                   
   1   3             1                     3
                                          /
                       2                  2

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