Bloomberg吐血整理高频面经

Bloomberg

BB家的面试和一般的大公司还有点不太一样,喜欢考察他们感兴趣的点,以及考验你的解决问题的能力。所以系统设计和一些easy medium难度的算法会经常考察。当然少部分的时候会出一些奇怪的open minded的题目。他们家特别重视communication。说出你的想法,不断的沟通,并给出他们想要的解法是最最最重要的。用他们hr的话就是we look for fluency in data structures, algorithms and problem solving skills.

算法题

下面是很多网上的面经,我总结了一下,大部分都研究过了,需要我贴下代码和思路的可以给我留言。

1,所有和anagram有关的,他们家都喜欢考。建议全部刷一遍。 Group AnagramsFind All Anagrams in a StringValid Anagram

2,所有和topk有关的,BB家甚至system design都有一半是topk的问题。比如经典的topk股票问题。 Top K Frequent ElementsTop K Frequent WordsKth Largest Element in a Stream

3,所有和meeting room,interval有关的,特别是 Meeting Rooms IIMerge IntervalsNon-overlapping IntervalsIntersection of Two Arrays,例如,会考 find min number of room for N meeting appointments换个说法考。

4,和买卖股票相关的,毕竟他们的主营业务,所以 Best Time to Buy and Sell Stock交易次数没有限制,输出最大获利的各个买卖点这类的也是常考。

5, Number of Islands超级高频,请掌握,有时候要求会有点小改变,比不仅仅考虑4个方向的,要考虑对角线8个方向。还有另一个版本的题,和小岛数量实质是一模一样的,好像是算什么云。单纯的换个说法而已。记住好好研究下时间复杂度哦。

6,LRU cache相关的以及各种变种都会考,为数不多的hard题需要完全掌握。其实各大公司也都在考。LFU之类的。 LRU Cache有很多lru相关的变种,

Given a stream of 'query name' and 'execution time', 
design a data structure that can return the k fastest query name. 
If a new entry's query name is already seen, replace the old execution time with the new one.
ex stream:
query1, 10s
query2, 30s
query3, 20s
query1, 20s
class TopK:
def update(query, time):
def get(k):

一个马拉松比赛,假设路上有10个marker,然后你需要设计几个函数 Top(k)
返回跑在前面的k个人的id, Update(runnerId,markerId)每次跑到某个marker的时候 call这个函数。Hashmap + linkedlist (虽然这里我觉得好像和LRU没太大的关系。别人的面经)
k can is given at runtime.

7,Candy crush的一维版本,给一个string比如acbbbccddd, 消除连续3个以上的,返回最后的结果,先删3个b和3个d变成accc,再删c,最后返回a。

8, 给一个字典,里面包含很多词组什么的(我也不知道该叫什么好),比如{AppleTree,Pineapple,AppleTea}。让你实现一个功能,可以给一个input,返回字典里所有包含input的词组。比如pT是AppleTree,AppleTea的子串,所以你要返回AppleTree,AppleTea。

9,给2个array,比如arr1 {1, 2, 4, 5, 9}的sum是21,arr2 {2, 3, 5, 7, 10}的sum是27, 那么让你swap他们2个中的各一个元素,使得他们的sum相等,比如arr1中的2和arr2中的5换一下,就是sum1和sum2都是24了。

当时第一反应就是2个for loop把情况都扫出来,解释了一下time complexity是O(m*n),我就说感觉不是很好,应该可以优化。然后就讨论怎么优化。想了一会觉得可以用配合HashMap来做。就是for loop 2次把sum1和sum2先求出来,然后第二次for loop的时候,把arr2的元素都put进HashMap里作为Key。然后写一下公式:
int diff = sum1 - sum2;
sum1 - arr1[i] + arr2[j] = sum2 - arr[j] + arr[i] -> diff / 2 = arr[i] - arr[j], 通过map.containsKey判断出arr[j], 到最后好像也没优化多少,大家有什么好办法可以给我留言。

10, 有一些,原题海,我出现过的我直接贴在这里了,大家可以参考利口或者lintcode

🔎详情点击展开

Tree相关的:

  • linkedlist找merge point,
  • copy linkedlist with random pointer,
  • flatten BST to linkedlist(把BST替换为2Dlinkedlist,本质不变),
  • depth, interseciton of linked list(一个一步一个多步是否可以(复杂度高))
  • word search I,
  • min stack,
  • stock transaction I(buy date is needed) II,
  • two sum,
  • subset,
  • unique paths II,
  • merge two/k sorted array/linked list,
  • Find kth largest number(quickselect, array partition),
  • sort colors,
  • remove duplicate from a sorted array,
  • search in sorted rotated array(binary search),
  • search for a range and delete it in array, next permutation,
  • find peak element(一个先降后升的数组,怎么在这个数组中找到target值 [先找到最小值,然后分别二分查找]),
  • rotate array,
  • single number(简单版-两个整数数组 所有元素完全相同 但第二个array少了一个数 求少的那个数。array中数字是乱序),
  • valid Parentheses(follow up如果加入" " 和 ’ ’ 怎么处理?" "中间的视为全部合理,里面的内容可以忽略),
  • Trapping Rain Water,
  • Container With Most Water,
  • course schedule II(topological sorting),
  • surrounded region(起点给定,而非四周,通过最后判断是否全X来判断给定的X是否封闭) palindrome number(先让count一下6位数的palindrome有多少种可能,比如100001,234432这种. 然后让print出所有的),
  • reverse integer(reverse a float, follow up 用 a == reverse(reverse(a)) 来判断overflow行不行), atoi, excel sheet column title/number, power(recursive; iterative), sqrt (指定精度 or返回double - 牛顿迭代),
  • RomanToInteger, IntegerToRoman,
  • 矩阵螺旋(给一个矩阵,从中间开始旋转着一圈一圈把值打印出来。代码写完之后还追问了一下如果要允许用户自定义螺旋的方向要怎么改)
  • reverse words in a string(1.一开始我想用两次while循环那种解法,边写边念叨思路。然后三哥说不要用这种,换一个一次循环的,函数容器随便用。感觉他确实在干别的事,我就直接把char *的input转成string然后空格分割存进vector再逆序合并
  • 去掉一句话中多余的空格。输入“ The sky is beautiful ! " 输出 ”The sky is beautiful!" 他开始给的例子里没有标点符号,我就没考虑到=。= 后来也没让修改了。。),
  • anagram [hashmap,面试官prefer质数],
  • add and search word(给一个string的字典和一个target string,要求找出字典中所有跟target近似的string,带*的匹配),
  • longest palindrome substring, shortest palindrome(从后面添加), strstr()

11, entry[1, 5, 9 15, 20], exit[2, 6, 18, 35,60] 里面存的是time stamp,记录是进入会议室的时间,给你一个时间,问你此时会议室里面有多少人,我说了一下方法就是binary search什么的,后来非要我优化,我就说了一种类似于radix sort的方法,已知一些数据可以进行预处理(?利用bucket sort预处理, e.g.每个bucket存10k ~10k+9, 在对应bucket内binary search)

12, find unique missing(1-100有99个数只出现一次,找到missing one, 用求和可能溢出 ----我说用平均数代替,他说用tree可以达到O(lgn))

int findUniqueMissing(const std::vector;int; a)     
    int ans = 100;     
    for (int i = 0; i < 90; i++){
         ans ^= i+1;         
         ans ^= a[i];     
    }     
    return ans; 
} 

若array为sort,可以binary search,类似: Given an array of unique integers in increasing order, return the integer with its value equal to its index in the array

13,

  • 求array 平均数, 非常基础,要求念出具体的code。又问数多溢出怎么办.
  • 有很多个node,每个node 存了一个int数组。 ——如何求一个global_Average,全部node里所有数组的平均值。简单。 ——如何求一个global_Median。他提示,你可以写一个function 去check If_global_median。 这个可以写,就是让每个node 返回有多少个数比他大,多少个数比他小,总个数,是否存在这个数。用第一步得到的平均数去check(or 最大最小的平均值),然后二分查找。
  • 找streaming median。 我用了两个heap,三哥说你确定要用这个吗,我说是,他说那你写吧,写完再说。 时间复杂度,nlgn。 他说还可以更快吗。我想了一下,可以建数组,存frequency,他问这样做问什么可以找median。

14, 把多个string存成一个string来传输,然后对方可以还原为多个string (cipher and decipher),过程要求无空格, 原串中可以包含任意字符。 - 可以用length的数值作分割,放在每一个string的前面,可以在数字后面加个# - 把一个非空格字符x变成1x, 空格变成00 - 转义:约定空格编码成\,原本的\用\来表示。那么在decode的时候如果看到了\,就看后面连着的是什么。如果是\就替换成, 如果就孤零零的\,那就是空格了。

15, 给个数组,例如{3,1,1,6,6,9,9,9}, 然后按照数字频率由高到低输出,如果频率一样,则大的先输出。结果就是“9,9,9,6,6,1,1,3”, 这道题用的hashtable先算每个数频率,然后对所有的arraylist排序。

16, fib数列, 基本递归(T(n)=T(n-1)+T(n-2)=> T(n) = ((1+sqrt(5) )/ 2)^n)和循环的让说了下复杂度,DP的代码让说了下

17, 给两个matrix S和P,判断P是否是S的submatrix,面试官说用brutal force即可。

To be continued!

7 Likes
  1. ABCDE 变成 DEFGH 就是平移了一下…然后给一个字典确定某个单词是都有效,要求是恢复全文,只考虑lower case.第一个单词找出所有possible shift distance然后第二个用第一个的结果narrow down这些可能的distance…一直到最后剩下一个就是我们要的…问是不是要读完所有单词,找到剩一个distance程序里的for就break了.

  2. 给一个array,让你找到最大和第二大的数 two array A and B, find the max positive difference between element a from A, element b from B, but a and b cannot have the same index. 其实简单到不行啊,就是一个找前两个最大的,一个找前两个最小的。

  3. Hamming Distance。就是给两个数,求他们有多少个bit不同。

  4. Search a 2D Matrix 10,20, 40, 50 12,22, 45, 52. 15,36, 47, 60 18,38, 48, 70

  5. 概率 1) shuffle card 2)现在有一个random generator可以generate 范围是1-5的integer, 问怎麽generate出1-7的integer, 要求要equal possibility. 3)16KB int的数随机数是rand(),然后64KB integer的用rand()怎么表示。(rand() << 32) + rand()

  6. string compression(1.问这有什么用,答可以压缩空间。问什么时候不能用,答abcd时候不行。还有什么时候不行(string 里含数字?)。三哥说如果重复很多会有什么问题。答应该会integer overflow 2.decompress string,a#3b#4cddf#4 -> aaabbbbcddffff)

  7. 给一个二维递增数组,最后一个空里面是space,最后的space可以和左边,右边,上边的数交换,可以交换好多步。要求的函数是给交换后的结果,从结果推出交换的步骤。这个数组里面的每个数都是确定的,永远是1-n,直接在空格周围找到该在这儿的数再不断交换直到space到最后一个空为止。 交换前的矩阵例子: 1 2 3 4. 4 5 7 8 9 10 11 12 13 14 15

  8. [event-driven] 1)每个人有死亡时间和出生时间,在1900-1999之间,找出哪年活人最多。 2)有一些schedule,不同人的,然后找到大家都有空的第一个slot;他不告诉你输入类型,所有的都是自己定义。

  9. [1,2,-2 ,1,-2]这样的叫singlecycle把,意思是,从index0开始,index0+array[index0]跳到1,然后index1+array[index1]继续跳,要求是,每个index都跳到,而且最终跳回index0.空间O(1),就想到用count来计数,count=array.length的时候检查当前index是否在0,结果烙印又给了个edge case[3, x, y, -3]。[while(index != index0 && count != array.length) 跳出循环后如果两个条件同时爆表则true 否则false]

  10. bst,给一个double数字n,要求找到bst里面跟这个数字最接近的节点.

  11. 给一个图,given你自己的node,返回有最多邻居的你的邻居。

  12. 问了integral image存像素的方法,让你实现两个function,update pixel 和 给定两个点,找出这两点组成的矩形内所有pixel之后,然后分析这两个function complexity. 找pixel sum的时候也要check 边界条件,和考虑

    integer overflow update {
       vector&lt;vector&lt;int&gt; &gt; 
       M, int x,int y,int value){ 
       // your code;   
      // 此处 check 边界条件
      M[x][y] = value
      } 
  1. 一个很长的linkedlist, 不知道head在哪里,给出一个node要你删掉。

  2. 1)put all white spaces in the end of the array input: char array. output: void note: in place 2)给一个int数组,把数组中所有的非零元素挪到数组的右边,所有零挪到数组的左边,要3)求不能改变非零元素原来的相对顺序。(其实0的相对位置改变了- -)

  3. 给两个数组,第一个记录数,第二个记录待删除的数的index。从第一个删掉第二个数组中出现的index对应位置的数。(先将后者排序)

  4. 数组/链表 找交集差集并集 给你N个数组代表N种股票的每天的交易员ID(比如1 2 2 2 8 2 1就代表7天里3个交易员在负责这些股票),返回所有参与过所有股票交易的交易员ID。 这个用hashmap存交易员id和他对应的count,同时记录当前扫到第k个股票的数组。如果看到一个id,并且count等于k-1,就加1。结束了把所有count等于k的id输出。 ——1)hashSet(当集合类别有限时可以考虑直接作为数组下标或用bit操作在一个int上记录(a-z)) ——2)先分别排序,然后类似merge得到结果(对于数组可以仅排序第一个,第二个通过binary search处理) ——3)多个可以依次拿之前的结果和之后的比or hashmap数个数or分治分布式,先分别两两处理,再同样方式处理结果

  5. 1)given a string, find the first duplicate/unique character in this string. remove duplicate in array考虑所有的edge case, 我用try catch exception 2) 如何找第一个字符串中出现的第一个第二个字符串的字母。给我举例子,S1 = “Hello”, S2 = “Apple”,那么返回2,因为s1(2) = ‘l’ == s2(3) 3)一个数组print出第一个出现次数为奇数的数。卤煮说用hashtable,value为count。印度小哥要求减少hashtable的空间,卤煮当时想半天也没想出来(后来觉得可以把count的类型定义为boolean或者byte,就比integer小了嘛——直接用hashSet插入/删除),卤煮给了另一个异或解法,pass。 Q4). 数组里有一堆数字,除了一个出现奇数次,其他都是偶数次。找到那个奇数次的。 就是single number,会问你如何检查输入数组是对的,比如全部是偶数,比如有两个奇数。这个拿第一次出来的结果回去再扫一次数组统计这个结果的出现次数验证之就可以了。[0, 错误输入检查?] ——1)hashmap记录出现次数(hash情况同23),queue记录出现顺序(如果需要) ——2)先排序 - remove duplicate from sorted

  6. 给个char数组然后打印排好序的,我最开始说mergesort,他不满意,我说用数组存下count,他说好

  7. 一个无序的数组,打印里面所有差值为3的pairs,pair中大的在前,小的在后。例如 [1, 3, 9, 2, 6, 8, 4, 7]那么就应该打印 (7,4) (9, 6) (6, 3) (4, 1) …我说全放到hashset里面遍历,看相差为3的元素在不在set里,然后分析时间空间复杂度。follow up问如果O(1) space怎么做,我说排序,然后双指针或者binary search,先分析时间复杂度,然后写代码

  8. 给一个只有0和1的矩阵,0是能走通的地方,1是过不去的墙,从0,0开始走,只能走上下左右,打印出所有能走得到的点。

  9. 找leading number。就是给个数组找出那些比其后出现数要大的数。比如2 4 12 5 3 4,leading number就是12 5。(O(n)从右往左扫一遍出来。)

  10. find mode value in an unsorted array. 我的思路是先radix sort,然后从左到右扫了一遍,update之前出现最多次数的count和对应的数。(mode value就是数组里出现的次数最多的element,不一定超过数组数量的一半,所以majority vote 不行)。

  11. 判断一个double的长度是否为k(连续*10至刚好为整数,并判断当前/10^(k-1)是否>=1 & <= 9),判断一个数的小数是不是K位(*10^k取整后不变&&末尾不为0)

  12. 1)链表里如果每个节点四个方向都有指针,给你这样的链表和一个值,让你找出值是否存在。遍历即可。
    2)就是一个字母的matrix和一个字典.要我找到所有这个字母matrix能组成的存在于字典的单词…和某道leetcode挺像.然后又问了不是2D的是3D多D怎么办,什么数据结构好使. 我恍了一下然后说了句adjacent list,只见他眼前一亮,于是我就想到了图, 我说可以构建图然后做BFS,他说那是exactly what I want,

  13. 排序 1)然后国人小哥问了sort的各种算法,让我从一个乱序的数组里面,找出所有(i,j)pair,其中i的index比j小,值却比j大。(merge sort) 2)external-sort 给一个file有上千个numbers,给一个size为50的array,sort这个file

  14. 给两个list,A = {1, 2, 3, 4, 5}, B = {1, 2, 8, 7, 3, 9}, 一种输出结果应该是 {1, 2, 8, 7, 3, 4, 9, 5},按照数字在A,B中出现的先后顺序合并。 (这道题用两个Map标记一个数在A和B中出现的位置,i, j为A、B当前的下标,A[i] == B[j],则添加一个,然后i++,j++,如果map_B[A[i]] > j,则添加B[j]到结果,j++; map_A[B[j]] > i,则添加A到结果,i++。若同时成立则有环,其他情况随便添加 or 拓扑排序) T

  15. 股票系统 Apple 300, Goole 150, Apple 150,。。。 烙印说你弄个maxvalue, minvalue,

  16. malloc a 2d array in c

  17. string to integer& integer to string带逗号,比如32,729 要变成32729.问edge case像空格啊字母啊要怎么处理(直接print)

  18. 找一个string的distinct substring数量,follow up如果这个string有100,000个char咋办(suffix trie)

  19. given一个linked list of numbers, check if it is a palindrome

  20. 给一个matrix of numbers,问怎样找出相同row。(类似bucket sort)
    40.(a+b)*c+(a+b)+c,去除没用的括号。

  21. 从一个字典中找出能被其他单词拼成的所有单词, 就是CC最后一章的题目

  22. 给一个list, list中有两个数. 过程中可以一直往list中加数进去(append在最后), 但必须一直遵守三个条件: 1. list中所有数均需大于0 2. list中所有数都必须为unique 3. 新加入的数必须为已存在list中的某两数的差 要做的事情是把所有可能的过程(一直加到没办法加入新的数字为止)都给打印或是回传 ex. [30, 5], 则最新加入的数只能为25, list变为[30, 5, 25] 继续, 只能再加入20, list成为[30, 5, 25, 20], 接着就有两种选择, 可以加10(30-20) 或是15(20-5). 于是会分出两个branch [30, 5, 25, 20, 10] 跟[30, 5, 25, 20, 15], 然后再把最后一个可能补上之后变成 [30, 5, 25, 20, 10, 15]跟[30, 5, 25, 20, 15, 10], 所以就回传这两个list. 可以预见的是如果一开始的两个数大小相差很多ex[99, 1] 那最后就会回传很多种path 加入的时候即刻存对所有数的差,预先通过最大公约数得到list的size

  23. 数字合并。就是1,2,3,4,6,7,9,11的话要变成1-4,6-7,9,11

  24. 给了一个自定义的类: Class Stream { vector<int> numbers; int getNextMin(); } numbers里面的数字是无序的。getNextMin方法返回下一个最小值。问题:用上面给出的类实现下面的新类: Class NewClass { vector<Stream> streams; int getNextMinNumber(); } 要求实现这个 getNextMinNumber 方法。

  25. remove 所有有且只有一个child的节点(将child连致parent)。Level order travel + hashmap解决。

  26. 类似two sum,两个array,unsorted,may have duplicate,里面的数值都是bytes,要求不用hash table,不用额外数组,找到一个pair sum to target value,然后想法是用一个long long的var当成bit vector,对于第一个array里的每个数,那个long long var的对应bit置1。。。[radix排序?]

####设计题
【1】马拉松
一个track上有很多runners(runner已经给的属性有id和name),还有很多check points(已给属性为distance:距离终点的距离,和id),check points可以检测到哪个runner跑过它.
[需要往这两个对象里加什么样的properties]

  1. 实时更新top k的选手
  2. 用这个系统生成一个dashboard显示runner现在的名次/实时更新排名表。
    Sol:
    问题就是如果有40个人,都在两个cp之间,而且在冲刺的话,他们的顺序会发生变化。在进入下一个cp之前我没办法知道到底谁在前谁在后
    basic: 每个cp记录跑过运动员个数,若该个数 <= 10则返回当前运动员runnerIdx & 该cp的distance & 个数
    sol1. 对于topk, 可以用hashMap & maxheap构成indexMaxHeap,存储(runnerId, dist)接受到条目后,或decrease_key,或删除最大(top)&插入(仅在严格<时操作) {类似股票} 0(nlogk) n : k*num of check points
    sol2. 每个CP维护一个list,将当前pass的人从之前删除,添加至当前list,cp记录当前pass了多少人,用以对runner设置名次,若名次在前10,通知leadboard更新离终点最近cp,对每个cp取list, 直到第一个当前设定超过10的cp
    sol3. 相当于LRU, 维护一个list, 每个cp存当前刚pass过的runner所对应位置,每个cp检测到runner后,将该runner删除,并加入改cp指向的位置下一个 ,更新cp指向位置(可以将list改为size为k, 仅记录号小于k的cp参与,添加删除同前)

【2】电话薄phone book (一个人名对应多个电话号码)

  1. output the phone book by alphabetic order
    2.输入人名:0)auto-complete, 1)查找对应电话号码,2)返回和这个人是neighbor的另外4个人的phone number(alphabetic order)
    3.输入电话号码找名字
    4.如果不考虑memory,在disk上做,怎么设计这个数据结构[电话本在disk上应该就是简单的database吧,一列是人名,另一列是电话,因为一个人可以有多个电话,所以同一个人名可以有多行。然后primary key 应该是人名和电话的组合]
    Sol:
    数据结构:Tire or treeMap (or hashMap ——不涉及alphabetic order的情况下)
    ——对于Trie返回neighbor:
    查找下一个:直接在当前节点的children里找下一个,如果没有则返回parent节点,从下一个child开始遍历。
    查找上一个:返回parent节点,从上一个child开始逆序遍历。
    *每个节点可以存它所有可能到达的节点array,可以直接输出下一个(array的内容or parent array的内容来加速: 但array只在顺序添加人名的情况下为sort的)
    ——对于treemap完成auto-compelete, 找到第一个大于等于输入的节点,输出从当前节点开始,保证最后一个字母不变情况下的正序遍历的结果。

【3】公司-股票-价格
1.1)一个系统假设不停接收交易数据(公司名字,交易数量),让写一个程序返回当前交易量最大的十个公司. (接着问如果要随时调取最大交易量的N只股票怎么做,我说可以先数据分析,根据normal distribution 搞一个high confidence 的group, 再用同样的原理只考虑统计结果给出的股票,烙印貌似挺满意没有纠结。)
2)系统会不断推送<股票名,当前价格>给你,要求你实现三个接口:currentPrice(String name)返回该股票的当前价格,currentProfit(String name)返回该股票目前的利润(其实就是当前价格减去起始价格),top20返回当前利润最大的20个股票/股票价格变动次数最多的10个公司/当前历史最高股价排名前k高的公司和他的最高股价。

Solution:
——对于key的大小只增不减or只减不增的top k, 可以用hashMap & minheap构成indexMinHeap of size k,存储(name, price/volume)接受到条目后,或increase_key,或删除最小(top)&插入 0(nlogk)
——若key有增有减or k不定,对所有股票建立indexHeap, 每次弹出前k
2. 老印设计一个class for stock name/price
function:. 1. insert 2. update 3. delete 4. sortedByPrice 5. sortedByName
我:dictionary , sort 的时候上array, 写了比较完整的code; 老印: space太大 我: tree?. 老印: 继续 compare time complexity 我:(写下来完整time complexity 老印: 如果我加date 怎么写 我要排序打印 要考虑你之前写过的function 的 time complexity 比如 stock price date. 我:在name tree里边再加个array 再sort, 最后一问想了很久 主要是要考虑当前 要用tree的状态(price作为node的field如何sort?)
3. 所有东西你都自己定义,一个让用户可以更新每个公司最新股价,一个可以把所有最新股价打印出来。hashtable就能解。
写followup,如果有很多很多entry进来,可是系统内存有限,你觉得你的代码哪里可能出错。 (内存不足?)
再followup问如果我想知道每个公司最近30个股价的均值和方差,你考虑加点什么,queue
再followup如果我想公司顺序按alphabetical order现实你咋办,我说那用trie?未置可否。
4. 统计
1)stock price coming, 有一个window的size是n, O(1)更新window里数据的average,就是旧的average*totalnumber再减去dequeue的加上新进来的再除以totalnumber,这题要写class,我就写了个window的class,constructor,dequeue,enqueue啥的
2) input是(公司名,股票数量), 让算平均数, 再记录如果有些股票update了,怎么update平均数(差值/公司数+之前均值)

OOD
1.如果跟一个不懂computer science和programming的人讲明白object oriented中的object是什么? 2.design讲几个software architectural pattern,具体解释一下,举个实际例子说明一个pattern,楼主比较弱,就讲了一个MVC和server client,其他的没讲。
3.设计class,card和deck,shuffle card,设计方法.
4.设计一个百货公司,里面有不同dept的employee,还有customer,还有商品.
5.parking lot
6. 音乐播放器的随机播放。(问的很细,包括函数是怎么生成随机数的,怎么用这个随机数实现具体随机播放功能,然后怎么避免重复播放,还有一堆关于设计的东西。)
设计手机上的音乐播放器,面试官一步步的说需要的功能,例如shuffle,搜索等等,主要讨论了用什么数据结构,最后讨论Database的table怎么设计。
7. 设计一个画板。我个人不太认可这类题的是,就算现实中的项目,我问你requirement你也该告诉我,问清楚需求才能做嘛,结果问什么美国大哥都说随你,我就懵了,你妹啊,我要知道你期待什么啊。感觉答的一般,给出了解法,但感觉并不出彩,空间复杂度有些高。要求就是没要求。问什么都是随你,我就想看你怎么设计。大概就是画板,有画刷,不同的brush画不同的东西,比如圆,三角,方框。然后还有要支持undo功能。而且支持点一下和拖着画。
如何实现windows paint的画方框功能
8.( strategy pattern)一个test car的系统,比如carA要test turn left, turn right, start, stop等等, carB要test speedUp, slowDown, turn angle等等,还会有carC,carD等等,要test可能不同,也可能有相同的部分。写一个class不管是哪个car都可以通过run这一个class来test. 不会啊!!。【设计题把测试方法抽象出接口,然后测试方法都继承它。车类持有多个测试方法类型的成员变量。这样应该可以.。 interface carTest{ void test(); } class turnLeft implements carTest{ public void test(){System.out.println(“Turn Left”);} } class Break implements carTest{ public void test(){System.out.println(“Break”);}
}
class CarA { private carTest turnL = new turnLeft(); private carTest Break = new Break(); public void tests(){ turnL.test();
Break.test(); } } 这样可扩展性更强, 当然抽象出Car类更好, 测试项目多了可以用ArrayList存。
是比较基本的多态。可以想象一下base class animal; derived class tiger, money; virtual function eat()的设计
9.有很多股票信息更新到系统里,同时需要把这些信息发给subscriber,问这个系统怎么设计(observer pattern)

功能性design***】

  1. 如何实现一个内存管理。 例如: a = new(100); //分配100MB内存. b = new(200); delete a;
    c = new(500);
    2.信息发送的load balancing。假设给你一个send()函数,可以发送一个message。要求你写个函数balancedSend(int msg, int cd),可以在cd的秒数内最多发送msg条信息(比如balancedSend(10, 60)就是60秒内最多10秒),并且尽可能降低每一条message的延迟。 就是个基本的写函数问题,跑send()之前计时,发完msg个信息后检查消耗时间,如果超过cd就直接下一轮,如果没超过就sleep(cd - 消耗时间)。
  2. 第一个问题是 database 和 本地通信比较慢,如何优化。我提出用cache解决
  3. 用户会发送buy和sell的指令给后台的服务器组,sell之前必须要有buy。但是服务器组内部跑指令可能会把指令顺序搞乱,如何保证能够正确执行原始的指令顺序。 这个其实我和他们聊了一阵子也不太明白是什么概念,毕竟我的想法是如果用户恶意输入无效指令我们也要去试图恢复吗(比如sbsbsbsb)。然后就是如何知道用户的原始指令顺序是什么,然后就是如何把信息递给服务器组(本身是个大黑盒,你不知道会如何)。总之聊了一下换题了,感觉不是很get到考点。
    5.问了两个超大字符串的处理。最后连上follow up,还问了一些cpu运行速度计算(什么鬼),multithread处理。主要题目大概是两个超大字符串如何用最小空间+最短时间消除他们互相含有的字符。然后给出CPU计算时间。(分布式)
  4. 大概就是frond end会发大量query到back end,怎么设计back end的system,可以handle海量的query,一个server是肯定要挂的。。。感觉要弄成distributed.
  5. 设计一个traffic light system,要求是从南到北的十个红绿灯一开始都是红灯,如果有辆车从最南端开到北端,会触发第一个灯绿,并且接下来的灯能逐渐变绿让车能一直开到北边不需要停。 这题我回答的是写一个light class,用一个state表示红绿黄,然后写一个function,利用thread.sleep控制变化时间,同时在主函数里面不断唤醒下一个红绿灯。
    8.scaliability
    然后给了个图,说有个queue,queue里有股票的信息,怎么把股票信息存到database里去。。。我说那就存进去啊。。。完全不懂要问什么。。。问怎么存?我说按每只股票的信息存到对应的table里面。他说好使,但是一会你同事发来贺电,queue爆了存不下了,为什么?我说那存不下了,说明queue太小,把queue增大,他说好,两小时后你同事用发来贺电,又爆了。我说那说明enqueue的速度远远大于dequeue的速度啊,这样再大的queue也得爆,他说是啊,怎么办?支支吾吾了一会说,dequeue端多线程提高dequeue速度。他说好使,但是这个的股票必须persevrve order,怎么办?每支股对应一个特定的线程。他说好使,但是两天后同事贺电又爆了,到这时我直接崩溃了,恨不得掐死同事。。。不知道怎么办了,他说你知道问题在哪吗?老实回答不知道。他说bottleneck有很多可能,有可能是你dequeue不够快,但是也有可能是database写入不够快,你上来不应该理所当然的认为加快dequeue速度就能解决. 问题,应该先找出问题在哪!然后问写的太慢怎么办,我说有的database专门有写优化的,可以试试用这种database,他说是,但是你同事很不爽他不愿意换啊!丧心病狂的同事。。。怎么办?想不出,他说你之前用过同样的pattern了啊,这时候时间快到了,他也不等我了,直接说每支股票分配一个database进行partation,哦,我说这是要sharding啊,cluster 前面搞个key value查看哪个股票存哪个database。

综合design

  1. 很理论的搜索系统的设计
  2. 设计一个系统可以一直读 twetter feeds 然后显示在版面上 印度人一直抓着要 real-time 和有很多clients
  3. 关于disjoint set。设计一个系统可以匹配互相能成为朋友的人,然后把能成为朋友的人组成group。
1 Like

应届生也会考这么多design的问题么?

嗯,现在bar上去了。很多大公司比如谷歌都开始考了。

我还没写全,一般来说2轮BB必考一轮系统设计。需要了解一下的。BB不分new grad和senior,只是在录取之后根据工作时间来决定给不给title。所以肯定是会考的。

omg. 一月份面BB,还没有开始准备系统设计

吐血感谢

:grinning:加油哈!

太感谢了! 准备on-campus

@Ranger lz如果有code的话可以分享一下么 有一些不是leetcode的题目有点找不到

本来有一部分代码,中途换工作relocation然后电脑被快递公司寄丢了,有点晕。所以没办法给你源码了。

依然感谢lz分享 谢谢