锐客网

  1. 首页 > 睿知 > it技术 > >

亚马逊专题面试及其经验分享|S8

IT知识算法数据结构面试经验

我最近面试了亚马逊, 了解SDE1在其TRMS团队中的位置。面试程序极为严格。
这是详细信息
第0回合：书面回合
面试测试– 2小时内要完成2个问题
Q1：计算表达式(2 + 3)* 5 ..问题刚刚说了这一点..我想我们必须做出自己的假设才能解决问题
Q2:如果两棵树具有相似的结构, 并且它们之间的唯一区别可能是它们的子节点可以交换或不交换, 则可以称为同构。.
例如
——4
—-2—6
–1–3–5–7
和
——4
—-6—2
–1–3–7–5
是同构的..树是相似的, 几个节点的左, 右子节点互换了…
给定两棵树, 确定它们是否同构…
即使我的第一个问题行之有效, 受访者也将我的第一个问题的解决方案标记为错误。当我告诉HR情况时, 她让一些亚马逊家伙对它进行了检查, 他们对此表示满意。
我清除了笔试。
电话面试1
Q1:在二分搜索树中找到第K个最大整数。当我告诉她像极客上的极客那样的解决方案时, 她让我使用递归来解决。
Q2:给定正整数数组, 找到可以通过该排列的任何排列形成的最大值。我告诉她一个逻辑。然后, 她让我只写比较函数, 以选择一个数字放在另一个数字之前。
当我给面试官一个直截了当的答案时, 她把问题弄得更糟了。也许他们想看看我如何思考和解决问题。
电话面试2
Q1:给出了一个二叉搜索树, 它的两个节点互换了。我必须找到两个节点。
Q2:确定给定数组中的所有毕达哥三胞胎。
我清理了这一回合。人力资源部告诉我, 我必须去班加罗尔进行面对面面试。 (所有旅行安排均由亚马逊自行制定)
个人面试1
Q1：找到一维数字数组中连续子数组的总和, 该数组的总和最大。.我不知道一个解决方案(卡丹的算法), 但我以某种方式能够在面试中解决问题。面试官喜欢我的接触方式, 并确实有所帮助
Q2:如何最好地使用堆栈来实现队列。时间的复杂度是多少？
能够很快做到这一点。
个人面试2
Q1： 查找给定字符串中的非唯一字符。我告诉她一个O(n ^ 2)[蛮力], 一个O(n logn)[排序然后比较相邻元素], 和一个O(n)[将字符计数存储在数组中]。然后, 她要求我在O(n)中不使用数组进行操作。
一无所知, 她终于告诉我她要我使用BIT Vector。我与Bit Vectors交谈得不太好, 我告诉了她。.她仍然问我要多想些。最终, 她告诉我一种使用相同解决方案的解决方案, 仅在面试中是无法想到的, 尤其是当一个人不知道什么是BIT Vectors时。当我提出要点并接受我以前的O(n)解决方案时, 她同意了, 然后我们继续下一个问题。
Q2：给定一个整数数组, 使用当前索引元素以外的第一个数组元素的乘积填充另一个数组。
在这里, 当我给她一个O(n)解[查找乘积并将其与当前元素相除以获得该索引位置的数字]时, 她要求我在不使用除法运算符的情况下进行操作。给她一个O(n ^ 2)解。但是我想的更好。最终, 当她开始告诉我一种O(n)方法时, 我想起了lsbin解决问题的方法并将其交给了她。可能她没有考虑。 (不确定)
个人面试3
这次面试是与亚马逊的招聘经理进行的。他首先问我一些人力资源问题, 例如"为什么选择亚马逊"？我们为什么应该录用你？项目, 实习等..？你将如何处理与队友之间的分歧？等等
然后他问我一个编程问题。
问：他在黑板上画了一个圆圈, 并在上面画了一点。分别命名为X1, X2, X3 ..
然后他说这些是加油站, 你必须找到正确的加油站, 汽车应从该位置开始在循环中循环, 以使汽车在完成一回合之前永远不会耗尽汽油。然后他坐在桌子上。
(对不起, 但是我将不得不对其进行详细描述, 以告诉你它是如何向我展示的。以及偏离路线以使问题本身更清晰。)
我不清楚我到底要做什么以及可以得到什么信息, 所以我问了他几个问题。
假设第一个加油站加油后, 为什么汽车会用完汽油？
他说, 每个加油站的汽油数量有限(假设为X1), 从该加油站加油后, 甚至可以在到达下一个加油站之前用尽汽油(可能发生的任何事情, 它都可以穿越下一个加油站但仍可以运行)在完成回合之前退出。)。所以我必须找到一个加油站, 汽车应该从这个循环开始, 这样它在完成循环之前永远不会耗尽汽油。
那么, 如果有能力的话, 汽车可以在下一个可用的加油站加油吗？
是
我们是否掌握从一个汽油泵到另一个汽油泵所需的汽油量的信息？
是
我假设汽车油箱足够大, 可以填充尽可能多的汽油。
然后, 我绘制了两个阵列, 一个阵列容纳每个工作站具有的天然气量, 另一个阵列容纳从该工作站到下一个工作站所需的天然气量。
可用燃油：X1, X2, X3, X4, X5
到达下一个站点所需的燃料：Y1, Y2, Y3, Y4, Y5
他说好, 请我继续。
然后我求出差(Y1-X1), (Y2-X2)..并将其存储在数组中..然后突然让我震惊的是, 这变成了在数组中查找连续子数组的最大和的简单问题。 (圆)。他喜欢我的方法, 并要求我进行编程。做到了, 并向他展示了我编写的代码的所有内容。他对此表示满意。
(面试后我感觉很好, 因为在那里我一点也没有绊脚..)
个人面试4
【亚马逊专题面试及其经验分享|S8】Q1：我们有一个带大括号'()'的大文件[只是一种类型..]查找它们是否平衡..(堆栈在这里不起作用, 因为你可能会用完存储堆栈的内存..)当我给他另一种解决方案, 他要求我使用并行过程来完成。我告诉他要详细说明..(老实说我对并行处理不熟悉)..最后我告诉了他..然后他让我仍然考虑一下。
我们讨论了大约20分钟。没有到达任何地方, 他继续问我下一个问题。
Q2:查找包含主字符串所有字符的最小子字符串。我再次对此有解决方案。我给了他O(n ^ 2)的方法。他要求我再想一想, 因为我的处事方式就是解决之道, 而且我可以利用最后获得的子解决方案来提高我的复杂性。什么都没想到, 我们终于转到了第三个问题。
Q3：给定分数的分子和分母, 无需使用除法和mod('/', '％')运算符即可找到商和余数。这很简单。我做的。然后, 他要求写出我的解的不变式, 即分母*商+余数=分子。
然后, 他让我考虑一下分子和分母中的一个或两个都为负的情况。我们快没时间了, 所以他没有给我时间思考和结束面试。他要我写一个不变的变量, 不管输入如何。现在我想到了, 我应该说|分母| *商+余数= |分子|
晚上飞回了家。
2天后, HR告诉我我没有参加。make
这可能是我进行过的所有面试中最困难的一次。
希望它能对你有所帮助。

    推荐阅读


    上一篇：算法（在先增加然后减少的数组中找到最大元素）

    下一篇：PHP如何使用gmp_divexact()函数（用法示例）