【求大米】小马智行(pony.ai) 机器学习平台开发 四轮面经

PONY.AI

本人在海外，工作职位地点在北京。面试全部电话进行，主要就是motivation和算法数据结构的考核。对于基础知识和复杂度的掌握要求比较高，对于底层操作在最后的面试也有要求。总的来说是技术要求非常高的感觉。

• 第一轮，String Matching. 给定大String A = "abctieowkcbale", 小的String B = "abc", 问有String A 会有多少个sub string 匹配 String B。这里的匹配指的是两个String排完顺序后匹配。这个例子里，B 会匹配 A里的 "abc", "cab", 答案就是2。
• 第二轮，Top Kth element from an array. 给时间复杂度最低和期望时间复杂度最低的减法，并且证明期望时间复杂度的正确性。并且问，如果K在量级上原小于size of array, Heap的做法还是nlog(k)吗？实现这些算法，实现堆。
• 第三轮，机器学习e2e流程的讨论，模型的速度优化。用多种方式实现HashMap讨论优缺点和tradeoff.
• 第四轮，给一个unsigned int[] A, 求任意的i, j, 满足 i != j, 问A[i] & A[j] 的最大值。解释内存操作
  

祝大家好运！希望赏我大米多多：）

第四道有思路吗？

hunterinstant 发表于 2019-11-14 13:43
第四道有思路吗？

可以每一位来做filter，unsigned int: 32 bit

谢谢大米！

楼主，第二题有点疑惑，如果k远远小于数组长度，time complexity应该是多少？

secret 发表于 2020-3-3 15:05
楼主，第二题有点疑惑，如果k远远小于数组长度，time complexity应该是多少？

同问，zszs

楼主能分享下package大概有多少么