HRT

bar很高，但是面试题难度绝对不算高，可能有很多culture fit和隐藏要素 会议室里已经有了待会用的断网的Mac，各种IDE都装好了（Atom都有呢）

  • How does Java garbage collector work? (GC for other languages, C++ and Python)
  • 2Sum -- 比较几种实现方式的优缺点 －－ follow up 如果double怎么办 （String expression -- customized Epsilon）
  • Asked how to find the kth largest element of a sequence of n elements.
  • If I have a jar with 1000 coins and one is double headed and I pick one coin randomly and flip 10 heads what is the probability it is the double headed coin?
  • How do you support multi-threading without kernel?
  • How would you triage and go about fixing infrastructure problems? Giving an input file, get the number of lines matching a specific piece of text using bash scripting. Give the percentage of lines in the file that match that string.
  • 有 1000 个瓶子，其中999瓶是水，有1瓶是毒药 一天发作 有10只老鼠 在一天里检测哪一个是毒药 -- follow up 如果两瓶毒药
  • 问了array和linked list的区别。 什么是hash table，如何handle collision。想在hash table里加一个功能，keep track of order of addition，要怎么办。最后问了two sum。我说了hash map的解法后他又问怎么reduce space complexity。
  • Super hard core http://www.1point3acres.com/bbs/thread-182999-1-1.html
  • MaxFlow
  • cpp -- copy constructor 和 assignment constructor 写一个 vector v -- loop push_back class instance 问这个过程多少个 default constructor copy constructor assignment constructor destructor -- 然后 vector push_back class 发生了 什么 操作 超过capacity reallocation的时候 class怎么办 －－ vector push_back 时间 复杂度 然后 如果每次只增加 size 5 时间复杂度 那按1.1 倍增加的时候 时间复杂度 那 每次double前 sort一次的在打印出来 时间复杂度是多少
  • c++ java 不同
  • java gc怎么工作 不用java的gc 自己设计一个gc java是mark sweep －－ reference count 和 copying collection －－讨论各个方法的 优缺点 －－ 先问我java的gc机制。我来劲了，刚要和他解释eden/survivor/young/old这些东西，他反而先将我一军问我哪些东西可以当root reference（因为java是根索引机制）
  • 内存管理和分配 vector v 是在 stack heap上 什么是 heap
  • dynamically allocated array和linkedlist的区别，我说了不同operation的复杂度 java中的arraylist在append的时候如何操作
  • process thread 之间 interact
  • tcp和udp的区别，tcp的window的意义是什么flow control，不是congestion control，一般如何判断合理的window size －－ 他真正想要我提到的就是优化tcp的那个windoW大小（用比较大的window）。不过还是表示其他基本的排错（MTU设定，物理连接，检查packet的丢失状况的一些方式等等）也是有意义的
  • array product except itself －－ 考虑0
  • 两个机器人碰面问题 －－ 就是如何设定好程序，让两个在一维坐标轴上相隔一段距离的机器人能碰面，彼此无法沟通，但是可以侦测地面上是否有足迹（无法判断谁的）。我说的办法就是让两个机器人匀速朝一个方向走，第一个碰到足迹的加速追赶。网上有个办法是让机器人走三角函数那样的折回路线，两个迟早都会撞一起
  • process和thread的区别，然后fork（）出来的是process还是thread之类的。我连fork（）的源代码里的clone（）都看过，很轻松过了
  • 直接丢给我一堆打印好的文档，上面从头到尾解释了最大流，相关的基于DFS的解法（BFS的优化解没提，要求写DFS的），然后描述了输入（用stdin持续读进去N行基础数据）和要求输出。让我在2个小时内实现它。offer大神也是这题。这里对比offer大神的经验，我犯了好几个错，想起来依然很悔恨。第一我没提前问input是否合法，结果花了快半个小时为了完整验证输入，写了一大堆try catch还感觉很好，后来2小时结束的时候才知道input完全合法（直接用scanner＋nextInt一路读输入就好）。第二，也可能是最大的问题，就是我以为2小时是随便用，在那真的做满了2个小时（结果依然有小bug，丢人），而大神直接15分钟不到写完全部算法交卷，似乎把人家都吓到了直接提前进入后面几轮（我是下午才面了后面几轮）。总之在这一轮尽快做完，有点小bug都不要紧，效率第一，别被2小时的时限迷惑了 算法的具体细节，大家自己简单看下最大流的dfs解法和你熟悉的语言的实现就好，然后能用array就别用arraylist，能用arraylist就别用linkedlist，这种优化技巧很受这种追求微优化的高频交易公司的欢迎。写完代码被带去公司餐厅（公司有个专属大厨每天做各种饭菜，不过口味看起来比较随机）吃饭＋和其他组员聊天（总共就10几个人的组，全都在餐桌上，难道这也是隐藏面试环节？），同时面试官在会议室review我的代码，回来了继续聊。吃饭的时候另外一个来面试的中国小哥在我旁边，我挂了的现在他的成功率应该更高了，祝他好运
  • 解释下我实现的算法里每一步的复杂度，要考虑到具体的实现。这里我答得不好，没有分析出来dfs解法可能要做O(|最大流数|)次dfs。然后我用了matrix来存图，遍历matrix的复杂度也提高了本来dfs的V＋E的复杂度。完了追加问了下arraylist和linkedlist哪个遍历快，答arraylist因为他们在内存里是一起的
  • 我有写做OS相关的项目，他就从virtual memory问到了paging。看到我有database的经验，就问了B＋tree和index的用途以及实现原理。然后继续问了基于UDP的服务器单对多通信要如何保证所有客户端都能拿到正确的信息（服务器存一份cache，然后客户端负责检查错误＋找服务器要缺失的，短期内的pull请求整合到一起然后做一次multicast）
  • 用C实现big endian和little endian的检测，这个网上随便看下吧
  • 为啥hrt，为啥纽约，人生的5年计划，还在面哪些公司，什么时候其他offer截止 让我提问。问了他们用啥open source，问了他们的工作里有多少financial的知识需求（core组基本不需要），然后问了下公司文化的东西
  • 囚犯帽子问题 及相关 http://www.matrix67.com/blog/?s=%E5%9B%9A%E7%8A%AF