Stripe初面

new grad， Grace Hopper Conference上的job fair.

技术面，自带笔记本，给出一组int数组A，表示机器id(从1)开始，让你找出第一个available的server id给assign给新的一个server，其实就是找first missing number，扫两遍可以做到线性求解，也可以排序后找，但是时间复杂度是O(n log n), 但是面试官在这一步不care效率，只要求快速求解，然后我就用sorting的方式秒了，中间follow up是怎么test，要考虑什么， 答考虑duplicate ids，然后改了下算法处理这个问题。

问题2是上面的提升版，有一组String数组A，element的形式是若干个letter最后跟着几个数字，比如apibox1, apibox2，表示对apibox这个type的server的备份，需要实现String allocate(String type), void deallocate(String name)这两个函数，功能和第一题一样，只不过要针对不同的server type分别处理。第一个版本是HashMap<String, LinkedList<Integer>>实现，实现的过程中我说这不是最优方式，但是因为要快速实现first version所以先这么写。跑通后开始讨论最优方式，LinkedList<Integer>部分用一个priorityqueue取代，并且每个server type记录一个upperbound， priorityqueue存的是missing numbers，每次allocate时，取最小的missing number  x，如果x == upperbound，再把(x+1)丢到priorityqueue里， upperbound++. priorityqueue直接把当前的id扔到queue里。

求next step.


补充内容 (2017-10-10 07:06):
next step来了~~

next step来了~~

问下楼主deallocate的时候如果需要先查找number是否存在，需要在heap里面寻找的话，成了O(n)了吧？

请问楼主是内推还是还投呢？能分享个链接吗？谢谢

楼主，放在在解释一下第一题的follow up ？ 怎么 test 和 test 要考虑什么是什么意思？

woyouyihuoer 发表于 2017-10-29 07:20
问下楼主deallocate的时候如果需要先查找number是否存在，需要在heap里面寻找的话，成了O(n)了吧？

应该可以用一个HashSet存着哪些number还在, 这样就不用查heap了

求问楼主。。。第二问的input 是 Stiring[]  然后里面有work1, work2, work3 这样的吗？ 这个string array 里面只有一种work type 还是会有很多种？而且type 的名字和数字是分开的吗？还是合在一起的？我们需要先把数字分离出来吗？ 这个function 的 signature 是什么样子的？

楼主说 “第一个版本是HashMap<String, LinkedList<Integer>>实现” 这个是啥意思哈哈~~ linkedlist<integer>里面的是server 的数字吗？ 这个需要我们自己构建真的个Linkdlist 吗？还是题目给的？

楼主说 “第一个版本是HashMap<String, LinkedList<Integer>>实现” 这个是啥意思哈哈~~ linkedlist<integer>里面的是server 的数字吗？ 这个需要我们自己构建真的个Linkdlist 吗？还是题目给的？