亚马逊访谈|第53集（SDE-1版）

在每一轮面试中，他们都会问我为什么要加入亚马逊，为什么我要在这么短的时间内（大约2.5个月）离开之前的公司，以及为什么要做项目。 面试官非常友好。他们会一直解释到你完全不明白为止。即使在讨论方法和解决方案时，他们也会消除你的疑虑。

网上面试 1. 给定2个字符串，找出第2个是否是第1个的子字符串 （如果你能用KMP解决就好了） 2. 给定两个矩形，找出它们是否重叠。 3. 给出各种价值的硬币列表（每种类型的硬币数量不限），找出你可以通过多少种方式获得给定的价值。 （DP是预期的。）由于不能保证价值为1的硬币会出现，如果给定的价值不可能，我们必须返回-1。

所有回合都在同一天。

第一层f2f： 首先，我被要求自我介绍，并简要介绍我的项目。后来他让我解释我的任何一个项目，以及我完成的最艰巨的任务。 我们已经使用中缀对通用搜索表达式的求值进行了ix和postfix求值。在这里，我们就为什么需要从中缀到后期修复的对话进行了大量讨论。

1.给定字符串s和int r，首先按行填充每个字符，按列打印。 例如字符串s=“abcdefgh”和r=3 因此，按列填充将给出： a d g b e h c-f

最终的ans将是adgbehcf。 他只是想要准确的输出。在内部，我们处理字符串的方式并不重要。

2.给定字符串或数字。。例如，134现在与每个数字，根据手机的键盘，一些字母将被关联。 这里1->abc，3->ghi，4->jkl。所以我们应该打印所有的排列，这样我们从每个数字中取一个字符。 输入数字可以是任意长度。 假设每个数字都有m个相关数字，那么对于长度n的输入，我们需要生成n^m个可能的字符串。

拿了张地图 这将返回数字的所有字母。使用递归解决了这个问题。这与字符串的排列非常相似。 面试官在这里似乎印象深刻。

第二层f2f 1.求给定数的sqrt的整数部分。最初我给出了o（根（n））解。后来用二进制搜索（O（logn））解决了这个问题。

2 给定一个整数数组。将每个数字替换为右侧更高的数字，后者更靠近。 （如果不存在，则保持原样。） 例如输入–>3 4 6 1 输出->4 6 1

我建议我们可以从右边遍历，我们将获得额外的数组（这里是o（n）空间复杂度），在该数组中，我们将存储下一个更高的更接近的数的索引。 那就好像

if (a[i] < a[i+1]
  then store i+1;
else
   traverse using index stored in auxiliary array 

因为我们需要额外的空间来存储索引，他要求输入的是一个结构数组，该结构有数字和更高的索引，2个字段。这样我们就不需要额外的空间和额外的遍历。

class Node {
   int val;
   int higher;
}

他很想知道我是如何跟踪索引的，以及我是如何在它们之间遍历的。它是o（n）和o（1）空间复杂度。（当我们有一个[i]>a[i+1]时，我们不做线性搜索，但我们使用索引跳转，所以不是o（n^2）），很难说服他理解复杂性。

3. 给定一棵二叉树。在同一级别连接所有节点。 每个节点都有左、右和下一个标记指针。我们需要填补下一个空缺。 通过水平顺序遍历解决。类似于带队列的树上的BFS。只需要一种方法，这个方法没有代码。

第三层f2f（招聘经理） 1.这是一个设计问题。你必须设计一个游戏。它有不同类型的怪物和不同的武器。英雄会射杀怪物。每个怪物都会有一些初始生命值。每一种武器都会对怪物造成预先设定的伤害。当其生命值为0时，怪物将死亡/消失。而且会有多个层次。根据等级，怪物及其行为会发生变化。

2. 给定一个带有下一个指针和随机指针的只读链表，克隆该列表。 我告诉他我知道解决办法，并向他解释了方法。它使用了hashmap，占用了o（N）额外的空间。然后他问我是否知道o（1）空间解，因为我不知道，所以我被要求解这个。有了这个，他告诉我可以修改链接列表。 起初我很挣扎，但在他的帮助下，最终我想出了可行的代码。他在执行方面看起来不错。

在这里，我问一下亚马逊的工作文化和流程。我问了很多关于他们使用的工具和技术的问题。因为我研究过scrum模型，所以非常有趣。他似乎对这里印象深刻。

第四层f2f（开发经理） 1.给定2个排序链表，将它们合并为单个排序链表。更改指针，不要复制数据。（与SLL上mergesort的合并部分相同）

2.给定二叉树，连接同一列中的所有节点。需要注意的是，同一个节点可以有两个父节点。这里，如示例所示，节点7由2和6指向。 使用水平顺序遍历解决了这个问题。用地图 ：columNo，Node。它将存储该列最后访问的节点。所以，每当我们访问一个节点时，我们首先检查它对应的列是否存在于hashmap中。如果不是，则表示它是列的第一个节点，放入map。如果列存在，那么我们将获得存储在map中的节点，当前节点将是它的下一个同级节点。我们更新地图。 他用例子和代码进行了试运行，最终的方法他还行。

        1
       /   
      2     6
     /     / 
   3      7    8
   /           /  
  4         12 
 /                 
5  9           13
                 
     10           14
      
       11 

两天后，我终于接到人力资源部的电话，我被选中了

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