亚马逊浦那泳池校园面试介绍

本文概述

• 在线回合
• 技术面试1
• 技术面试2
• 技术面试3
• 技术暨酒吧筹款回合

亚马逊泳池校园安置活动于2019年3月进行。总共进行了五轮, 第一轮是在Hackerearth进行的在线编码轮次, 然后进行了三场技术面试和一次筹款活动暨技术轮回。

在线回合

存在2个与操作系统和DBMS有关的编码问题和10个MCQ。

技术面试1

问题1

给出两个整数n, k和一个数组一种大小为n。找出数组a中k的频率。

解

我的第一个解决方案是散列数组h中整个数组的频率, 然后打印h [k]。在这种情况下, 时间和空间复杂度均为O(n)。面试官要求我改善空间的复杂性。

在我的下一个解决方案中, 我只是对整数变量进行了计数, 并在遍历数组a时每发生一次k, 就将其递增。该空间复杂度降低为O(1), 时间复杂度仍为O(n)。

他告诉我, 如果对数组进行排序, 那么现在我还必须降低时间复杂度。我可以简单地使用C ++中的lower_bound()和upper_bound()函数来查找数组a中k的第一个和最后一个出现。现在, 空间复杂度为O(1), 时间复杂度为O(log(n))。他叫我写代码。

我认为与其直接使用upper_bound()和lower_bound(), 不如将其实现。因此, 我写了两个二进制搜索代码, 一个用于lower_bound(), 另一个用于upper_bound()。他感到满意, 并转到下一个问题。

问题2

从排序的链接中创建一个二叉搜索树。

解

我的第一个解决方案是一棵明显倾斜的树。他印象深刻, 并被告知这确实是一个非常简单的解决方案, 但是现在他想要一棵高度平衡的树。这个解。他告诉我写完整的代码, 在他的帮助下我做得有些正确。

技术面试2

我的第二轮比赛是由一位非常漂亮和聪明的小姐主持的。她通过提供建议和想法来改善我的解决方案, 对我有很大帮助。

问题1

给你一个二叉树和两个整数k和d。打印所有节点, 距离k距离d。

解

我的第一个解决方案是使用LCA查找每个节点到节点k的距离, 然后仅打印距离为d的那些节点。这是我的

理念

。我的解决方案的时间复杂度为O(nlog(n))。她想要它

上)。她帮助我建立了所有逻辑, 最后我被告知编写代码。

问题2

给你一个仅由0、1和2组成的数组a。你必须对数组进行排序。

解

我的第一个解决方案是在一次遍历中哈希数组的频率, 然后填充0s, 然后在第二次遍历中填充1, 再填充2s。她很满意, 但是想要一次遍历。这是解。我被告知要编写代码。

技术面试3

这更多是关于计算机科学各个领域的一般性讨论, 而不是问题解决方案。

问题1

你有两个文件a.txt和b.txt, 其中包含两个数字(最多十亿位)。你必须计算两个数字的和。

解

我的解决方案是首先移动两个文件的文件指针, 然后开始添加数字并携带, 然后向后移动并将结果存储到新文件中。最后创建另一个文件, 并保存上一个结果文件的反向内容。他感到满意, 但随后限制了向后遍历。我告诉我们可以使用递归返回进位。他问是否有任何数据结构可用于此问题。我回答了链表, 因为无法分配大量的连续内存, 但是链表不使用连续内存。

问题2

你将获得一个字母网格。你必须打印所有可以形成单词" AMAZON"的起点的坐标。你可以上下左右移动。

解

我提供了使用DFS和DP的解决方案。很难解释, 但我尽了全力。我想他期待更简单解但是他很满意他告诉我写出我的想法的代码。

技术暨酒吧筹款回合

有人告诉我关于我自己和我的项目的简短描述。他问我在该项目中的角色。之后, 他提出了两个要解决的问题。

问题1

给你一个二叉树和一个节点k。找出k的左子树是否是右子树的镜像。

解

这个想法是对这个.

问题2

你将得到一个字符数组。你必须返回一个字符数组, 其中每个字母x都存在min(frequency(x), x的字母顺序)。

解

这是一个简单的实现问题。我被告知要在课堂上正确编写代码。

最后, 总共选择了9个人。其中6个来自

浦那陆军技术学院

。我很幸运地成为其中一员。