注册一亩三分地论坛，查看更多干货！
您需要 登录 才可以下载或查看附件。没有帐号？注册账号 
x
简单介绍一下自己情况，目前在美CS博士第五年，国内本科以及本科结束期间参与过三个研究项目，发表的论文有署名但并非第一作者。来美后熬了三四年，会议论文于2017年发表两篇一作，三篇二作。传感器网络、物联网、普适计算方向，会议PerCom，UbiComp，IoTDI，SmartComp一类。硬伤是机器学习，人工智能，深度学习，计算机视觉，自然语言处理，分布式系统一类虽有涉猎但不是主要领域。
下面是正题。
（实习期间电话面经由于时间久远且年年跪，参考价值或许稍小，合适的话再发）
感谢地里帮我内推的大神。一月Google联系准备电话面试一轮，面经如下（java）：
问题描述：现有一仓库，结构为一横排N+1个位置，其中前N位被放置了编号1到N的箱子各一个。箱子顺序在一开始被打乱。比如N=5，仓库布置为 2 3 1 5 4 0，其中编号0代表空位。
目前仓库中有搬运机器人Robot，初始在第1个位置停留。Robot的类已被写好以下函数：
moveLeft()，如果可能，向左移动一位；
moveRight()，如果可能，向右移动一位；
pickUp()，如果Robot手中没有箱子，则拿起面对位置的那个箱子；
putDown()，如果Robot手中有箱子，则把箱子放置在面对的空位上。
现需实现函数sort(int[] m)，m为仓库里箱子的布置，机器人运行此函数后应调用自带的四个函数，用某种策略把仓库的箱子排序。若输入为 [2 3 1 5 4 0]，结束时仓库应为[1 2 3 4 5 0]。
思路如下：
先实现几个函数，例如··移动到第x个位置"，和··把箱子从位置a移动到位置b"。
首先想到的是可以利用空位实现两个箱子位置的交换，例如：
2 3 1 5 4 0，拿起箱子2移动到最右边空位上放下箱子，变成 0 3 1 5 4 2；回去拿起箱子3回到最左边放下，变成 3 0 1 5 4 2；最后把2号箱子移动到空位，最终得到 3 2 1 5 4 0。
但实际上这消耗了太多的”拿起放下操作“。
比较好的解法是：2 3 1 5 4 0 -> 0 3 1 5 4 2 -> 1 3 0 5 4 2 -> 1 0 3 5 4 2 -> 1 2 3 5 4 0 -> ....
这个想法的来源是：观察地图，可见错放的箱子形成一个个"环"。此例子中，"2 3 1"是一个环，"5 4"是一个环。对于每一个环，只需要把一个箱子移动到空位，再循环把该放至正确位置的箱子一次次填补到新产生的空位即可。
LZ编码大致为找到错放的箱子，把它放到空位上，然后进入类似于DFS或while循环的结构一直下去解决一个环，再找下一个错放的箱子。
但是！这个思路只能最优化··最少的拿起放下操作''，还没有优化到··最少的左右移动''！
由于这个问题实在太难，没有编码，就与面试官交流了一下思路，大致是利用函数step(Set<Integer> cycle, int emptySlot, int robotPosition)计算出对于环cycle而言，空位在emptySlot，Robot处在robotPosition时需要多少步就可以解决这个环。具体操作时，需要动态计算step函数值并且在合适的时候暂停对当前环的操作，转而解决就近的环！
如以上例子，如果空位在位置3，解决环"2 3 1"消耗的步数会比空位在位置5更少。最好的解法或许是：2 3 1 5 4 0 -> 2 3 1 0 4 5 -> 2 3 0 1 4 5 -> 2 0 3 1 4 5 -> 0 2 3 1 4 5 -> 1 2 3 0 4 5 -&。checkAvailability(String phoneNumber)返回十位手机号phoneNumber是否被占用了；selectPhoneNumber()返回一个新的未被占用的手机号并注册之。
解：利用HashSet<String>或HashSet<Integer>存储所有被占用的手机号。每次请求新手机号时，直接随机一个号，如果被占用了，重新随机，直到找到未被占用的号。
follow up：如果被占用的号码太多，很难再找到新的手机号怎么办？
解：同时利用HashSet<String>或HashSet<Integer>存储所有未被占用的手机号。每次请求新手机号时，随机一个小于等于此集合元素量的值r，利用Iterator遍历集合取值到第r次时输出此号，把这个号码从"未占用"移到"已占用"里面。
follow up：单个计算机无法处理如此大规模的数据量，现怎么设计分布式系统或数据库来解决这个问题？
解：我们知道手机号前三位甚至前六位是能代表区号等等信息的。让每个区的服务器只存储自己的那个部分，然后主服务器维护一个树形结构（类似于前缀树）来记录每个区的服务器保存哪些号码段。用户请求新号时，首先按照区号去请求。如果那个区发现号都被占了，则向主服务器返回失败信息。主服务器若发现分配失败，则利用某种遍历法从维护的树中逐个询问哪个节点可以分配一个新号。
第五轮：
问题描述：给定int[][] board，解数独？
等等不是这一轮要让我来介绍研究方向的吗？面试官检查邮件发现自己搞错了，于是在我刚提出DFS，与使用一组HashSet存储每个格子的目前可行解后，转而尬聊。
刚好一周后通知送hc，之后三个工作日后说我被拒了，大致理由是期望stronger background and skills。平生第一次Onsite并没有太多的体会，面试官和hr的反馈也很模糊。目前正考虑转战各个公司，感谢各位能帮我指点一二或帮助内推的朋友，祝大家找工作顺利！
| 
匿名用户-CQWBH
2018-2-22 03:25:18
收藏
淘帖
好苗
杂草
提升卡
置顶卡
关贴卡
开贴卡
变色卡
千斤顶
狗仔卡
