本文概述
- 在线回合
- 技术面试1
- 技术面试2
- 技术面试3
- 技术暨酒吧筹款回合
在线回合存在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个来自
浦那陆军技术学院
【亚马逊浦那泳池校园面试介绍】。我很幸运地成为其中一员。
推荐阅读
- PHP ftp_mkdir()函数用法详细介绍
- C++中的void函数返回详细介绍
- C++中的内联函数详细指南
- PHP atan()函数用法详细介绍
- Java比较器接口介绍和示例
- 在std::map中插入元素(插入,插入和运算符[])
- Scala选项Option用法介绍和解释
- 诺基亚网络面试体验
- C++中的reinterpret_cast用法介绍 |类型转换运算符