中午刚刚面完的FB intern电面,题目是从一堆有x, y轴坐标的points里面找到k个离原点(0,0)最近的points。e.g.: points [[1,1], [1,2], [-1, -1], [3,3]](求离原点[0,0]的距离)
k = 2
results: [[1,1], [-1, -1]]
楼主没写出最优解,没选好合适的ds就着急做题了。
用了一个叫longest的int variable来track当前最长的points,然后更新size为k的array里放的points, 复杂度是nlogk,
最后还是在面试官一堆提示下才写完的…
最后他提示可以用更好的ds去做,想了一下可以用priority queue做maxHeap直接找到最小的k个points,
这样时间复杂度应该是klogk。
takeaway: 写题前先交流好要用的ds并判断是否合适,能节省你自己和面试官的很多时间…
挺简单的一道题,大概率是跪了…
希望能对大家有所帮助