一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 4572|回复: 27
收起左侧

8/21谷歌电面

[复制链接] |试试Instant~ |关注本帖
siyuan808 发表于 2015-8-22 03:34:37 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Other在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
刚刚面完谷歌二轮电面 (一面估计太搓). more info on 1point3acres.com
直接上题:
struct LogEntry{. from: 1point3acres.com/bbs
  string candidate;  投票姓名
  int time; 投票时间
};
string findWinner(int time, vector<LogEntry> &logs); 让找出在这个时间时候的winner. more info on 1point3acres.com
c1(1), c2(2), c1(2), c2(3),c2(4) 括号里是投票时间。 所以
findWinner(2, logs) = c1;.1point3acres缃
findWinner(4, logs) = c2;
用的hash表。找出最多的那个(投票在此时间后的不算)

第二题(follow up)
给一个时间,找出前k个winner。
我的做法是用hash表 先统计每个candidate的票数, 形成一个array,然后就是找前k大个数。 用的quick select。刚刚写完,partition的时候估计有bug。. visit 1point3acres.com for more.

回馈地里, 求bless。
还是把一面的情况也说说吧。
string encode(vector<string>& list);
vector<string> decode(string s);
这一题出现过, 可以搜。 估计做的太慢, 加面一轮。

说一千道一万,求bless进onsite

评分

2

查看全部评分

 楼主| siyuan808 发表于 2015-8-28 23:51:29 | 显示全部楼层
谢大家祝福啊。 昨天打电话说进onsite了。
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-8-22 04:20:43 | 显示全部楼层
请问楼主第一题hash的意思就是遍历这个vector,然后candidate作为key,然后这个candidate的票数作为value是么?然后followup找到前k大的数是不是需要再遍历一边hashtable,然后把票数所对应的candidate找出来?
感觉lz答的挺好的,followup我一开始想的是用heap,最后才想到用quick select复杂度更低
祝楼主拿到onsite
回复 支持 反对

使用道具 举报

cqx83 发表于 2015-8-22 05:23:18 | 显示全部楼层
一面的题是我当时onsite的题。。
回复 支持 反对

使用道具 举报

Williamslg 发表于 2015-8-22 05:39:24 | 显示全部楼层
cqx83 发表于 2015-8-22 05:23
一面的题是我当时onsite的题。。

请问能否详细说一下?是run length coding嘛?
回复 支持 反对

使用道具 举报

iorisli 发表于 2015-8-22 07:38:50 | 显示全部楼层
在无序数组里quick select只能找到第k大的数吧..? 能找top k吗?
回复 支持 反对

使用道具 举报

danchou 发表于 2015-8-22 09:19:26 | 显示全部楼层
iorisli 发表于 2015-8-22 07:38. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
在无序数组里quick select只能找到第k大的数吧..? 能找top k吗?

quick select的过程可以改变原数组,一次select之后k右边的数全部大于(或等于,看怎么实现了)arr[k]。可以参看一下CLRS 9.2
回复 支持 反对

使用道具 举报

iorisli 发表于 2015-8-22 12:36:06 | 显示全部楼层
danchou 发表于 2015-8-22 09:19. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
quick select的过程可以改变原数组,一次select之后k右边的数全部大于(或等于,看怎么实现了)arr[k]。可 ...

感谢指点......
回复 支持 反对

使用道具 举报

say543 发表于 2015-8-22 12:40:34 | 显示全部楼层
感谢分享用quicksort 在如果candidates n 小于k(要求的number) 因该会有比较好的效果
回复 支持 反对

使用道具 举报

muancy 发表于 2015-8-23 06:19:07 | 显示全部楼层
楼主能不能说说一面decode & encode的想法啊,找不到前面的面经了~
回复 支持 反对

使用道具 举报

samuel1989 发表于 2015-8-23 12:16:25 | 显示全部楼层
能解释下encode list and decode string to list吗?
回复 支持 反对

使用道具 举报

cqx83 发表于 2015-8-23 15:51:28 | 显示全部楼层
贴一下我encode和decode string list的那道题我自己的解法,当时onsite的时候就是这么做的。供大家参考

import java.util.*;. from: 1point3acres.com/bbs
public class combineStrings{
    public static void main(String[] args) {
                String[] arr = {"abc%cde", "a#aa", "haha"};
                for(String s : arr) {
                        System.out.println(s);
                }
                String result = serialize(arr);
                System.out.println(result);
                String[] newArr = deserialize(result);
                for(String s : newArr) {
                        System.out.println(s);
                }
        }
        public static String serialize(String[] arr) {
                StringBuilder sb = new StringBuilder();
                sb.append(arr.length + "#");
                for (String s : arr) {
                        sb.append(s.length() + "%");.鏈枃鍘熷垱鑷1point3acres璁哄潧
                }
                for (String s : arr) {. 1point 3acres 璁哄潧
                        sb.append(s);
                }. 1point 3acres 璁哄潧
                return sb.toString();
        }
        public static String[] deserialize(String s) {
                String[] sizeAndContent = s.split("#");
                int len = Integer.parseInt(sizeAndContent[0]);
. 1point3acres.com/bbs                s = s.substring(sizeAndContent[0].length()+1);
                String[] eachSize = s.split("%");
                int[] size = new int[len];
                int total = 0;
                for (int i = 0; i < len; i++) {. visit 1point3acres.com for more.
                        size[i] = Integer.parseInt(eachSize[i]);.鐣欏璁哄潧-涓浜-涓夊垎鍦
                        total += size[i];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                }. from: 1point3acres.com/bbs
                String content = s.substring(s.length() - total, s.length());. 1point 3acres 璁哄潧
                String[] result = new String[len];.鏈枃鍘熷垱鑷1point3acres璁哄潧
                for (int i = 0; i < len; i++) {
                        result[i] = content.substring(0, size[i]);
                        content = content.substring(size[i]);
                }
                return result;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        }
}
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-8-23 21:39:37 | 显示全部楼层
宝贝忆彼岸 发表于 2015-8-22 04:20
请问楼主第一题hash的意思就是遍历这个vector,然后candidate作为key,然后这个candidate的票数作为value是 ...
. 1point 3acres 璁哄潧
用quick sort的话不一定复杂度更低吧。
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-8-23 21:45:19 | 显示全部楼层
cqx83 发表于 2015-8-23 15:51
贴一下我encode和decode string list的那道题我自己的解法,当时onsite的时候就是这么做的。供大家参考

...

请问题目里说了String不包含数字吗?
回复 支持 反对

使用道具 举报

say543 发表于 2015-8-24 00:23:56 | 显示全部楼层
第一面哪边有完整的题目阿? 找不到...谢谢
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-8-24 00:57:49 | 显示全部楼层
wenqiang88 发表于 2015-8-23 21:39
用quick sort的话不一定复杂度更低吧。

一般情况下,quick selection的时间复杂度是O(N)
回复 支持 反对

使用道具 举报

alucardzhou 发表于 2015-8-24 02:41:40 | 显示全部楼层
祝福进onsite
回复 支持 反对

使用道具 举报

cqx83 发表于 2015-8-24 03:48:16 | 显示全部楼层
wenqiang88 发表于 2015-8-23 05:45
请问题目里说了String不包含数字吗?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
没说啊,可以包含任何字符。我的解法可以适用于所有情况
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-24 03:48:59 | 显示全部楼层
wenqiang88 发表于 2015-8-23 21:45
请问题目里说了String不包含数字吗?

既然是涉及到encode  decode的题目,就不用问数字不数字的,肯定是什么都可以有,不然没意义了
回复 支持 反对

使用道具 举报

donghao 发表于 2015-8-26 04:20:24 | 显示全部楼层
祝福进入onsite 加油
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 02:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表