Google MTV onsite

原帖地址:一亩三分地

大概是十一月份去的。已跪。年末发帖以纪念。。。
四轮。
1. 白女人。老题。在一个矩阵上选一个基地,such that这个基地到若干目的地的距离和最短。有障碍物。做bfs就行。
2. 小白。 大概也是dfs之类的。模型就是source-destination with weighted links的网络,找出所有path. 在算一些概率啊啥的。
3. 烙印。估计跪在这里了。写一个生日提示系统,每次查询时显示下一个谁过生日。这个有点偏system design, 比如他想看到你注意时区啊啥的很多细节(并不知道他是不是在黑我)。我直接说算法了,二分搜索。但是他似乎不理解我的版本的二分搜索。我用的二分搜索的版本是只改变一遍的那种。 e.g.public class Solution {
public int searchInsert(int[] num, int target) {
int lo = 0;
int hi = num.length – 1;
while(lo < hi) { int mid = (lo + hi)/2; if (num[mid] < target) lo = mid + 1; else hi = mid; } return num[lo] < target? lo+1: lo; } }复制代码4. japan man. 判断一个数字是不是质数。要用到两个trie。同时遍历两个trie是最优解。真的记得不太清楚了。 当时我觉得这题还挺有意思的。 只能来年再战了。。。