Citadel 2020年OA & 电面面经汇总

本帖最后由 匿名 于 2020-5-14 10:55 编辑

OA
1、Jungle book

2、number of distinct palindromic substring

3、longest string chain

4、数组 找一个点 左右加和相等

5、判断三个正数 能否组成三角形的三个边

6、给一个数组 按照数值分类把每个类的index打印出来

7、给你一个dict,返回另一个dict,key变成value,value变成key,如果新的dict中某个key有多个value,做成list。

8、从文件中读取一个2d array的string,将它rotate,就是行变成列,列变成行

9、Linux上写个bash script,找到default route的ip地址


电面

1、给一个多项式比如 8a^3b^3z^5 - 6c^2z^4d^5 + 9x^3u^9 + ......
用什么样的数据结构存储这个多项式可以快速并方便的读取这个多项式的信息, 比如说我要知道哪几个 item有a的平方 那几个item有d的三次方 诸如此类的。

2、写一个排序的算法,无论用什么排序方法 但是完全不能使用任何loop,代码里面只能用递归

3、sliding window minimum

4、给定一个函数bool predicate(int), 一个vector, 一个int k. 把满足predicate的element聚集到index k的前后。满足predicate的element需要保持原有次序,不满足的element也需要。不可以使用extra space。
e.g {1, -1, 2, -2, 3, -3, 4, -4}   k = 4, predicate is the integer > 0.
需要把 k之前的elements 从{1, -1, 2, -2}变成 {-1, -2, 1, 2}      // 大于0的往后移,但是1, 2仍保有原有顺序,-1, -2也是
k之后的elements从{3, -3, 4, -4}变成{3, 4, -3, -4}      // 大于0的往前移,但是3, 4仍保有原有顺序,-3, -4也是
vector变成了{-1, -2, 1, 2, 3, 4, -3, -4}
相当于把满足predicate的element聚集在index k的前后。

5、一个round table数组, arr表示坐着的那个人标号, 此数组首尾相连。每个人都有喜欢和不喜欢的人(可以认为输入中有 Map<Integer, Set<Integer>> likeMap, dislikeMap)
然后写一个函数, 判断一个round table 的seating arrangement是否满足如下条件:
条件是:
(1)任何一个人不能和不喜欢的人临座
(2)任何一个人必须和所有喜欢的人临座
Followup:
如何利用上面写的函数, 再写一个函数, 构建一个valid的seating arrangement array

6、给一堆process,每个process有start和end time,求最多多少并发。就是meeting rooms。Follow up:那我们变一下吧,假设有个scheduler,给定最多允许的并发数,写一个schedule函数,每次输入一个process,判断能不能schedule。就是说把输入换成了stream data。

7、数据结构的应用,说有个交易系统,给一个品牌(一家公司)服务, 现在一堆买家和卖家,当买家出得价格比卖家高的时候,才能算一个match,对于买家,卖家出价最高为最优match,反之,对于卖家,买家最低为最优, 问怎样快速的找的match.而且卖家和买家谁都有可能先到。
接着followup 1, 问此时有很多品牌,该如何存储。
followup 2,每个品牌有个limit,只有交易额大于limit才能交易,问如何实现。
followup 3,问如果multithreading的环境下,map可以更新,之前的map用什么作lock

8、Leetcode 16

9、linked list vs list:增删查找的时间复杂度,遍历n个element虽然同为O(n)但哪个更快,遍历时CPU里具体发生了什么

10. 如何实现hashmap, 有collision怎么办

11、在浏览器里输入一个网址后发生了什么

12、binary search in sorted array

13、斐波那契数列  实现fib(n)  分析复杂度

14、A list of unsorted numbers, compute the maximum product of any three numbers. 分析复杂度 followup问数字是复数怎么办

15、给一个linkedlist 每个node包含child和next指针和val要求返回flattened list. child设为null就好了
example:
1 -> 3 -> 4 -> 5
        |               |
        6-> 7       9
        |
        8
输出为1->3 -> 4 -> 5->6->7->9->8

16、有一个大hashtable 每秒钟有数百万次的读, insert 和 update 操作,shared by multithread保证效率和正确性 要你来design这个 并写出代码

17、设计实现一个multi-consumer的消息队列,大概应用场景就是上层的应用会不断的往这个队列里加events,然后需要有一些worker来不断地处理这个队列里的events。

18、lc题目:numbe of islands

19、语言是Python,给一个Dict,写一个函数来反转,用原来的value当key。follow up是如果有conflict,保留最小的那个,然后问保留最大的那个,然后说如果要把这个作为一个utility tool给别人用,有啥想法

20、让你实现一个moving average,可以自定义区间,加数据或者读取avg。

21、C++ 和 Python 怎么看,比较一下,运行效率,开发效率等等。
    * C++ 和 Python 类的继承的比较和问题等等;
    * 用什么工具在machine 上 测试或者监控 C++ 程序的性能;
    * 我C++ 不是特别强,问了一些之后 就转向python了;

22、给我一段很简单的python multi process 的concurrent 的代码,让我解释什么意思。问为什么 不用 threading,用processing,用threading 的限制是什么

23、Python decorator 和 generator 都是什么。usecases有哪些。有没有用过Data Science的包,比如panda。

24、SQL database query的时候,有哪些需要注意的,可以提高query性能。
    * 还有 create一个新的 index,有什么额外的开销。

25、走楼梯dp

26、OOD,给的就是一个残破不堪的文件,主要考察的就是singleton,聪明指针,object工厂之类的,singleton要注意得不允许copy constructor之类的。

标签: 暂无标签

写了 4 篇文章,拥有财富 0,被 0 人关注

回复

使用道具

您需要登录后才可以回帖 登录 | 立即注册
B Color Link Quote Code Smilies

成为第一个吐槽的人

返回顶部