亚马逊面试体验|S266(SDE1的校外)

2021年5月16日17:11:33 发表评论 91 次浏览

笔试(在Hackerrank上)

90分钟内可解决20个MCQ和2个编码问题

1)

下一个排列:具有相同数字集的下一个最大数字。

例如:I/P:123, O/P:132

2)DFS + DP标准问题。我不记得确切的问题陈述, 但这是非常标准的陈述, 需要DFS + DP解决方案。

第一回合(电话)

1)

给定一个零和一的数组。你可以将任意一个0翻转为零, 以使一个连续的数字最大化。

2)

仅给定二叉树的节点, 找到下一个有序后继

在O(1)空间中。树的根是未知的。

正如他告诉我们假设除root位置以外的任何其他内容一样, 为了解决该问题, 我假设Treenodes也包含指向其各自父级的父级指针。

第二轮(F2F)

1)

给定二叉树。垂直打印其元素。使用"水平距离"概念和哈希图解决了该问题。

2)上述问题的变体, 不允许使用Hashmap。讨论了许多方法。在经过大量讨论和变型后, 他提出了不使用任何哈希的约束, 该解决方案是"节点列表的双向链接列表"。由于不允许使用散列, 我要做的变化是维护指向双向链表的全局指针, 将其在双向链表中移至当前树节点的左子节点, 并向右移至当前树的右子节点-节点。

第三回合(F2F)

介绍和实习相关的讨论, 然后是这些技术问题

1)给定一个排序的整数流。输入向量的大小未知。查找给定的整数。预期的复杂性;日志(n)

提示:在二进制搜索方法中, 将Perfect Square用作开始索引和结束索引。

2)上述问题的变化, 因为我们不知道终点。假设我们有一个函数, 如果阈值索引(输入向量的大小)则返回NULL

越过了。现在改进上述解决方案以处理该案件。

例如:假设数组大小为

3)主题相关问题:TCP v/s UDP, 虚拟内存, 密码术等

4)设计一个音乐播放器, 以随机顺序播放歌曲而无需重复播放。提出O(n)时间和O(1)空间解决方案。

第四回合(F2F)

简介, 与项目相关的问题, 其次是:

1)

给定k个排序的链表。将它们合并为一个排序列表。

使用自定义的Min堆方法执行相同的操作。

2)针对上述问题实施自定义最小堆。

3)

在二叉树中, 以距给定节点" k"的距离打印节点。

第五回合(电话)

1)介绍和项目讨论。

2)将给定的整数转换为罗马数字格式, 但要使用最少数量的条件语句。想出了很多方法,

他对任何方法都不满意, 要求我删除尽可能多的条件语句。

3)

给定一个零和一的数组。查找具有相等数目的零和一的子数组的最大大小。

提出O(n)时间和O(n)空间解决方案。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: