Google 实习面(gui)经

两轮背靠背
第一轮：
    给一个vote类

1. Vote{<div>    String name;</div><div>    int timestamp;</div><div>}</div>

复制代码

输入是一个vote的collection和一个给定target timestamp，求到target的时间时，得票最多的人。
    比如输入：

1. "a"  10001
   
2. "b"  10003
   
3. "b"  10007
   
4. "c"  10020
   
5. "a"  10030
   
6. "a"  10050

复制代码

如果target是10010，返回b; 如果target是10036，返回a,b; 如果target是10051，返回a。collection未排序。

第二轮：
    一个什么游戏，大概意思是，有一个source string，一个target string。二者都只包含"L","R","_" 三种字符，L可以往左移，R可以往右移，不能jump over。
    让设计一个函数，判断能否从source走到target，返回boolean;
   比如

1. "_L_R" ,"L__R"---> true
   
2. "_L_R_" ,"L___R"---> true
   
3. "_R_L_" ,"_R__L"---> false

复制代码

第一轮面的时候信号不行，断线好几次。浪费了一些时间。当时先写了个O(N^2)的，然后说稍微改一下能优化到O(Nlog(N)), 结果面试官说没时间了，象征性地说了个great，问题都没让问。
第二轮在小哥提示下才磕磕绊绊写出来，感觉小哥不是很满意。

move on了

求问楼主第二轮的思路到底是啥。。楼上提出的算法貌似都不对。不是没有考虑到 'R' ‘L’ 只能向固定位置移动就是没考虑到可能连续的'RR'或者没考虑到‘R’， 'L' 不能 jump over 的情况

请教另外一个同学，他的思路是首先固定L的位置，然后看看可否把R移动到相应的位置，（可以通过两根指针来做，O（N）复杂度），然后再固定R的位置，看看能否把L移到相应的位置。当然这样做起来也是比较复杂，不过至少可以证明是正确的

第一题，不知道是不是我理解不到位。如果直接遍历整个collection，然后找到其中timestamp小于target的进行处理不就好了么，建个map数一数就行。

看楼上的讨论有点懵逼，
第一题难道不是O(n)就能搞定嘛？直接loop一遍collection，统计timestamp<target的各个name的个数。

第二题我的想法，定义两个变量num_L. num_R记录L和R出现的个数，同时loop source和target，由于source里的L只能向左，R只能向右，所以同时loop时一定是target里先遇到L（或者同时遇到），且一定是source里先遇到R（或者同时遇到），所以loop时遇到target[i]为L, 则num_L加一， 如果source[i]为L， 则num_L减一，如果source[i]是R，则num_R加一，如果target[i]是R，则num_R减一。若任意时刻出现num_L<0 或num_R<0，说明source走不到target，return False。这样O(n)就搞定了。

请问LZ第二题是怎么做的啊？

请问楼主 第一题最后是怎么做的啊

感谢楼主分享～～～

第一题可以这样做吗？写一个vote 类的comparator, sort 一下 O(nlgn)，然后遍历这个collection，中timestamp小于等于target的votes, 用一个hashmap来记录每个人的得票数, key->name, value-> countOfVotes， space complexity O(N)。

请问面试的时候除了做题问了别的了吗？比如简历上的项目什么的？

楼主第二题是怎么写的？

第二题感觉可以greedy，首先比较string length，如果相同，开始逐位比较，source上是'R'且target上是'_'，且source后一位也是'_'，source上与后一位swap，i++，否则return false；source上是'_'且target上是'L'，且target后一位也是'_'，target上与后一位swap，j++，否则return false；两位相同时i++，j++，其余情况均return false，两个string到头时return true

第二题 通过观察 可以看到 在target里 所有R 的左边的L 的个数 不能大于 source里 对应R 左边L的个数

所以 可以建一个数组 记录target里 每一个R左边的L的个数 然后再source里检验就好了 这样 计算复杂度是 On  空间也是On