我通过员工推荐来申请SDET-1职位。我在Amazon Chennai(SP Infocity)接受了面试, 我面对了5个面对面的回合。
10月11日, 我面临着第一轮比赛, 该比赛主要与问题解决和编码有关。
第一回合：问题解决和编码回合(1小时)
面试官首先提出一个自我介绍的正式问题, 然后问我关于我的最后一年的项目的问题, 我将其清楚地解释并画在了董事会上。
然后她问了我两个编码问题。
- 模拟一个Android模式锁。
- 生成可以使用给定模式形成的所有单词。键盘规格是手机键盘, 我会清楚解释
如果给定输入为2 3 6。
2对应于abc。 3对应于def。 6对应于mno。
假设如果我们必须生成2, 3, 6的所有组合, 则输出应该是一组字符串
adm, adn, ad0, bdm, bdn, bd0, .....
我给出了一个递归和迭代的解决方案来打印组合。
然后面试官稍微修改了这个问题, 她让我用字典验证生成的字符串。
我给出了两种维护字典的方法。首先, 我提出了一种哈希表方法, 该方法对插入删除和搜索操作的平均时间复杂度为O(1)。
然后, 由于生成的字符串具有通用前缀, 因此我建议对字典使用trie方法。
面试官对我的解决方案感到满意, 并要求我对解决方案进行完全编码。
几天后, 我进行了2次面对面的比赛。
第二回合：测试和自动化回合(1小时)
面试官刚开始时询问我是否对测试和测试环境有所了解, 然后回答了有关问题, 然后我们讨论了测试的类型以及与之相关的不同阶段和测试程序。然后她问了我两个简单的测试用例生成问题。
- 为将两个字符串作为输入的add函数生成所有可能的测试用例, 并返回一个整数, 该整数是作为字符串输入给出的两个数字之和.
我给出了大约10个问题的测试案例, 因为它非常简单。我使用JUnit测试编写了一些简单的代码。
2.给定编辑器中的打开文件模块, 在什么情况下打开文件模块可能会出错。
我列出了一些案例, 我们就每个案例的来龙去脉清楚地进行了讨论。
由于我在前一天准备了测试部分, 因此这一轮非常容易。
第三轮：数据结构和算法第一轮(1小时15分钟)
这轮有两个人面试了我。我们只是从正式介绍开始, 然后他们问了我两个问题。
- 骑士步行问题.
给定一个n * n棋盘和一个放置在任意角落的骑士, 请生成所有可能的路径, 然后骑士可以覆盖所有正方形。
我从使用BFS的方法开始。但是我的方法存在一个缺陷, 那就是如果先前已经探究过骑士可以从给定点经过的所有可能点, 那么骑士就不会从牢房逃脱。
然后, 我提供了使用回溯的解决方案。
从一个角开始。对于每个可能的点, 骑士都可以使用简单的for循环对那些点进行递归调用。一旦计数达到n * n(以8 * 8棋盘为例, 如果计数为64), 则打印找出可以轻松维护在数组中的遍历路径。这解决了我以前的方法中的缺陷, 因为如果到达一条死路, 我们可以回到另一种可能性。
面试官对我的方法感到满意, 并要求我编写解决方案的代码。我进行了编码, 然后我们转到下一个问题。
2.给定一个链表, 找到在一个公共点收敛的两个链表的交点.
我先给出了蛮力O(n ^ 2)方法, 然后将其优化为O(n)时间和O(n)空间方法, 然后我通过找到O(n)时间O(1)空间解决方案这两个列表的长度是绝对不同的。然后他们要求我编写解决方案, 这非常简单。
之后, 我在10月31日进行了最后两轮比赛。
第四回合：招聘经理回合(1小时)
面试官让我简要介绍一下自己, 然后在开始的几分钟里解决了我的项目, 然后面试官询问了我之前参加的面试以及整个过程如何进行。然后他开始询问测试以及与某些给定场景相对应的测试的使用。经过几分钟的讨论, 他问了两个有关数据结构的问题。
- 给定一个整数数组, 可打印成对的总和。
首先, 我给出了O(nlogn)方法来查找对并打印它们。该方法是对数组进行排序, 并在左右分别保留两个索引, 并找出是否将对总和等于给定总和的对进行打印, 直到左右指针交叉为止。
然后他问我是否可以进一步优化它。我使用散列提供了O(n)方法。我维护了一个整数散列集。将第一个数字放入哈希集中, 从第二个元素开始, 对于数组中的每个数字, 检查哈希集中是否存在(给出总和–当前元素)。如果是这样, 请打印该对。
2.给定一个二叉树, 打印它的底视图.
经过几分钟的思考, 我想出了一种方法, 它使用节点到根的水平距离。在使用级别顺序遍历进行遍历时, 我们必须注意特定水平距离处的最后一个节点。我使用哈希表在每个水平距离存储最后访问的节点。
这种方法使用O(n)时间和O(n)空间。
然后他问了一个难题。
在一个有30人的房间里, 要确定一个唯一的握手次数, 条件是房间里的每个人都应该与所有人握手。
我只是使用了简单的逻辑。在两个人的房间中, 只有一个唯一的握手(第一个人只有一个唯一的握手, 而第二个则没有一个)。如果我们考虑三个人, n = 3(A, B, C)
A有两个独特的握手B, C。(n-1个握手)
B有1个唯一的握手C。(n-2次握手)
C没有任何独特的握手。
握手总数= n-1 + n-2 = 2n-3 = 3(这是前两个自然数的总和)
同样, 对于n个人, 唯一的握手将是前n-1个自然数的总和。
对于n = 30, 唯一握手的总数为29 * 30/2 = 29 * 15 = 435。
这是一个包装。他对我解决问题的方式感到满意。
他问我是否对他有任何疑问。我询问了亚马逊的文化和工作环境。
第五回合：酒吧加赛回合(1小时)
两名成员进入会议室并作了自我介绍, 我们从介绍和项目开始。
他们问我在当前一轮之前进行了几轮。他们最初只是问了几个有关测试的问题, 然后又问了两个编码问题。
- 给定二叉树, 在其中打印第K个最大元素.
我只是通过查找树的有序遍历立即开始使用蛮力解决方案。然后对数组进行排序, 并在排序后的数组中找到第k个最大数组, 该数组中第k个元素是数组起始索引的第n个元素, 其中n为树中的节点总数, 使用O(nlogn)时间和O(n)空间。
他们要求我进一步优化它。
通过将二叉树转换为双向链表, 然后在双向链表中找到第k个最大的对象, 可以给出O(nlogn)时间和O(1)空间解, 这可以在O(nlogn)时间完成。
但是有一个更好的解决方案, 我在面试中无法想到。只需构造一个k元素的最小堆, 就可以通过任何遍历遍历树将元素插入堆中。
如果堆根元素小于树中的当前节点, 请从堆中删除根元素, 然后将新元素插入堆中。最后, 在完全遍历树之后, 第k个最大元素将在堆的根处, 这使用O(nlogk)时间和O(k)空间。
但是他们对我的方法感到满意, 因为他们说我可以通过空间或时间来优化它。我采用了恒定的空间方法, 因此他们感到满意。
2.给定一个有向图, 找到是否存在一个循环, 如果存在则打印出来。
我给出了使用BFS的解决方案。我将一个节点放入队列, 然后添加了从当前节点可以访问的所有可能的节点。在遍历节点时, 我们只是将节点标记为在哈希图中已访问, 以避免节点之间发生不确定的循环。他们对我的方法感到满意。
最后, 他们询问了HashMap的实现方式及其工作方式(尤其是哈希码和索引的计算方式)。我设计了自己的哈希函数, 并解释了在哈希图中获取和放置函数的工作方式。他们对我的解释感到满意, 然后他们询问你在发生冲突时如何修改哈希函数, 并简要讨论了冲突处理技术。
他们问我是否对他们有任何疑问。我只是问了上一轮问的相同问题。
附注：对于每个问题, 我们都必须清楚地编写代码。不要只是直接进入编码部分, 请清楚说明你的方法。要有信心, 而且他们不希望为问题找到最佳解决方案, 他们会看到候选人如何解决问题。
