亚马逊面试体验（针对SDE-1的校园内体验） _亚马逊

亚马逊于2019年访问了JIIT Noida进行校园课程。
第1轮(在线编码回合-HackerEarth上的90分钟)：
这一轮包括2个编码问题和20个MCQ。编码问题的难度很容易, MCQ测试了CS基础知识(OS, DBMS, CN, OOPS等)。
编码问题是：

给定整数N。你有3、5和10个面额硬币的数量不限。打印使用硬币面额以形成N之和的任何方式。 Soln：标准DP硬币找零问题.
给定一家公司N天和Q个查询的利润。每个查询包含两个整数L和R。对于每个查询, 请打印获利大于或等于L且小于或等于R的天数。Soln：对利润进行排序, 对于每个查询, 请使用二进制搜索以找到R的上限和L的下限。时间复杂度：O(nlogn + Qlogn)

我记得一些MCQ：

T(n)= 4T(n / 2)+ n ^ 2的时间复杂度(选项：O(n ^ 2), O(nlogn)等)
给定：前缀表达式。以下哪个是对应的后缀表达式。
计算给定的页面错误数：给定：OS使用FIFO进行页面替换, 每帧没有页面数。并且系统以特定顺序使用x页, 然后以相反顺序使用y页。
Ping在网络中的目的。
有关SQL命令的一些问题(将列添加到表等)
在OOP中, 以下哪一项用于实现运行时多态。选项：Friend函数, 运算符重载, 函数重载等)
如果机器在y秒内对x个条目进行排序, 则它将在z秒内对多少个条目进行排序。给定：冒泡排序用于排序。
给定的树的后序遍历, 以下顺序中的哪一个。
有关死锁, 信号量等的问题
具有N个叶子的完整二??叉树中的节点数没有。
尽管问题很容易, 但临界值很高。在约400名学生中, 有30名能够完成本轮比赛。

第二回合(面试-1小时)：
面试官非常友好, 从"告诉我你的项目"开始。听起来像是一种形式, 我给了一个非常简短的答案, 然后他开始了这些问题。
Q1：打印一个数组中所有总计为给定数k的三元组。这里的要点是必须打印所有这样的三胞胎。例如如果给定的数组为{1, 1, 1, 1, 2, 0}且k = 3, 则输出应为：{(1, 1, 1), (1, 1, 1), (1, 1, 1), (1、1、1), (1、2、0), (1、2、0), (1、2、0), (1、2、0), (1、2、0) }
我开始思考, 并在向思考者解释我的思考过程。首先, 我讨论了对给定数组进行排序的问题, 然后针对数组中的每个元素A [i], 我发现了所有对总和为k-A [i]的对。为了找到对, 我将一个指针固定在A [i + 1]上, 将一个指针固定在A [n-1](如果n是数组的大小)。我必须修改解决方案, 以便所有可能的对都被打印出来, 而访调员本人为此提供了2-3条提示。
时间复杂度：O(nlogn + n ^ 2)= O(n ^ 2)
额外空间：O(1)
然后他要求我编写解决方案的代码, 然后我进行了试运行, 然后提交了解决方案。面试官告诉我重新检查我的代码。我对其进行了分析, 发现缺少一个案例, 我对此进行了补充, 然后他被说服了。
Q2：给定一个数组, 其中所有i均为A [i + 1] = A [i] + 1或A [i] –1。在这样的数组中, 找到一个数字k。
回答：可以使用线性搜索在O(n)中完成。但是可以通过执行跳转来优化它。例如, 如果k = 10并且第一个元素是5, 我们可以跳过4个元素, 因为这4个元素th元素最大可以为9。依此类推...
然后, 面试官修改了问题。现在, A [i + 1] =在{A [i] –t, A [i] + t}范围内。
回答：跳转的大小将被修改。
然后他让我编写解决方案。
每个问题大约花了30分钟, 在采访者的提示下, 我逐渐达到了解决方案。这听起来可能违反直觉, 但是面试官给出的提示是一个积极的信号(只要你能够抓住这些提示并提供他希望你提供的解决方案)。
第三回合(面对面采访-45分钟)：
问题：实现拆分应用程序算法(算法, 不是系统设计)。给定的交易格式为：A-> B 45, 这意味着A欠B的卢比为45卢比。
我首先绘制了一个事务图, 然后发现如果检测到图中的所有周期, 那么每个周期可以减少一个事务。面试官要我编码, 我开始这样做。然后, 他在中间停住了我, 并告诉我想出另一种解决方案。他给了我一个提示, 以考虑每个人应欠/被欠的净额是多少。使用该提示, 我能够提出一个贪婪的解决方案：组成两组人, 即那些欠一些净额的人和那些所欠的人。然后从欠债者中选择一个, 并从欠债者中给与一个。但是我不确定必须从这两个集合中选择元素的顺序。他暗示我选择了价值最大的产品。我试图用数学方法证明它, 然后继续进行求解。然后, 我使用max-heaps从这两个集合中提取元素。
时间复杂度：O(nlogn)
【亚马逊面试体验（针对SDE-1的校园内体验）】额外空间：O(n)
然后他让我编写解决方案的代码。在解决方案中, 我使用了heapify和percolate-up作为堆的函数, 他也让我对其进行了编码。
第4轮(面对面访谈-1小时)：
题：
给定一个BST, 找到第k个最大元素。没有给出BST的大小。
回答：使用逆序遍历。保留计数器以跟踪未访问的元素。
然后其余的面试仅基于项目和我的实习。我还被问到一些主观问题, 例如"你从事的最具挑战性的项目是什么？为什么？", "你最喜欢哪种技术"等。
面试官对我的项目提出了深入的问题, 但是由于我只提到了我自己制定的简单项目, 所以我自信地回答了所有问题。
第5轮(面对面访谈-1小时)：
这一轮有两名面试官。在这一轮中, 他们提出了许多CS基础知识的理论问题。我对理论科目不好, 只能部分回答问题。
其中的一些问题是：讨论信号量以及它们如何工作, 关键部分是什么, 竞争条件是什么, 线程与进程之间的区别是什么, 调度是什么, 讨论一些调度算法, 解释循环机制的工作。排程。什么是事务的原子属性, 讨论规范化, 1NF, 2NF等, 什么是DNS服务器, 两个DNS服务器可以相互通信, 当我们键入Web URL时会发生什么。
在一个问题中, 我在JAVA中获得了一个代码段, 并询问是否会违反关键部分。
我不知道亚马逊希望获得多少基本知识, 但是我仅回答了其中一些问题。我能够自信地回答一些问题。对于某些问题, 我给出了部分答案, 我回想起了很多。对于某些问题, 例如轮循机制, 原子性质等, 我根本无法回答。
到现在为止, 这一回合进行得并不顺利, 但是由于面试官非常友好, 我要求他们在DS / Algo上问我一些问题。然后他们要求我检查两个BST是否相同(即元素完全相同, 结构可能不同)。
Soln：将两个树的有序遍历存储在数组中, 并检查两个数组是否相同。
时间复杂度：O(m + n), 空间复杂度：O(m + n)
面试官告诉我优化空间, 并暗示了一些其他方法来进行有序遍历。然后, 我使用堆栈而不是递归来执行有序遍历。我保留了两个堆栈, 并在它们同时出现时从两个堆栈中删除了相同的元素。而且此堆栈最多包含O(logn)个元素(或O(height)个元素), 因此降低了空间复杂度。然后, 我被要求编写解决方案。
意见建议：