要回国了,写个简单的总结吧。

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 7933|回复: 28
收起左侧

8/21谷歌电面

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

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

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

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

x
刚刚面完谷歌二轮电面 (一面估计太搓)
直接上题:
struct LogEntry{
  string candidate;  投票姓名
  int time; 投票时间
};.1point3acres网
string findWinner(int time, vector<LogEntry> &logs); 让找出在这个时间时候的winner
c1(1), c2(2), c1(2), c2(3),c2(4) 括号里是投票时间。 所以. 1point3acres
findWinner(2, logs) = c1;. 留学申请论坛-一亩三分地
findWinner(4, logs) = c2;
用的hash表。找出最多的那个(投票在此时间后的不算) 来源一亩.三分地论坛.

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

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

说一千道一万,求bless进onsite

评分

2

查看全部评分


上一篇:Epic OA
下一篇:Cerner Onsite

本帖被以下淘专辑推荐:

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

使用道具 举报

我的人缘0
bobzhang2004 发表于 2015-12-6 06:03:20 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
写了下第二面的代码,quick selection的最大不好是输出是没有顺序的,如果要有序还得再排,minHeap就没有这个问题。.本文原创自1point3acres论坛
  1. public class Winner {
  2.         . from: 1point3acres
  3.         static class LogEntry {
  4.                 String candidate;. 牛人云集,一亩三分地
  5.                 int time;
  6.                 public LogEntry(String candidate, int time) {
  7.                         this.candidate = candidate;
  8.                         this.time = time;. 围观我们@1point 3 acres
  9.                 }. from: 1point3acres
  10.         }

  11.         static class People {
  12.                 String candidate;
  13.                 int votes;
  14.                 public People(String candidate, int votes) {.本文原创自1point3acres论坛
  15.                         this.candidate = candidate;
  16.                         this.votes = votes;. Waral 博客有更多文章,
  17.                 }.本文原创自1point3acres论坛
  18.         }
  19.         .本文原创自1point3acres论坛
  20.         public static String findWinner(int time, List<LogEntry> logs) {
  21.                 HashMap<String, Integer> map = new HashMap<String, Integer>();
  22.                 for (LogEntry entry : logs) {
  23.                         if (entry.time <= time) {
  24.                                 if (map.containsKey(entry.candidate)) {
    . Waral 博客有更多文章,
  25.                                         map.put(entry.candidate, map.get(entry.candidate) + 1);. From 1point 3acres bbs
  26.                                 } else {
  27.                                         map.put(entry.candidate, 1);
  28.                                 }
  29.                         }
  30.                 }. 牛人云集,一亩三分地
  31.                 String res = "";
  32.                 int max = 0;. more info on 1point3acres
  33.                 for (String candidate : map.keySet()) {
  34.                         if (map.get(candidate) > max) {
  35.                                 res = candidate;
  36.                                 max = map.get(candidate);
  37.                         }
  38.                 }
  39.                
  40.                 return res;. more info on 1point3acres
  41.         }
  42.         . more info on 1point3acres
  43.         public static List<String> findTopKWinner(int time, List<LogEntry> logs, int k) {. 牛人云集,一亩三分地
  44.                 HashMap<String, Integer> map = new HashMap<String, Integer>();. Waral 博客有更多文章,
  45.                 for (LogEntry entry : logs) {
  46.                         if (entry.time <= time) {
  47.                                 if (map.containsKey(entry.candidate)) {
  48.                                         map.put(entry.candidate, map.get(entry.candidate) + 1);
  49.                                 } else {
  50.                                         map.put(entry.candidate, 1); 来源一亩.三分地论坛.
  51.                                 }
  52.                         }
  53.                 }
  54.                 People[] candidates = new People[map.size()];
  55.                 int index = 0;
  56.                 for (String candidate : map.keySet()) {
  57.                         candidates[index++] = new People(candidate, map.get(candidate));
  58.                 }. 牛人云集,一亩三分地
  59.                 return topKCandidateQuickSelect(candidates, k);
  60.         }
    . Waral 博客有更多文章,
  61.        
  62.         private static List<String> topKCandidateQuickSelect(People[] candidates, int k) {
  63.                 List<String> res = new ArrayList<String>();. From 1point 3acres bbs
  64.                 if (k == candidates.length) {. 围观我们@1point 3 acres
  65.                         for (int i = 0; i < candidates.length; i++) {
  66.                                 res.add(candidates[i].candidate);
  67.                         }
  68.                         return res;
  69.                 }
  70.                 int start = helper(candidates, 0, candidates.length - 1, k);
  71.                 . 一亩-三分-地,独家发布
  72.                 for (int i = start; i < candidates.length; i++) {. visit 1point3acres for more.
  73.                         res.add(candidates[i].candidate);
  74.                 }
  75.                 return res;
  76.         }

  77.         private static int helper(People[] candidates, int start, int end, int k) {
  78.                 if (start > end) {
  79.                         return start;
  80.                 }. 牛人云集,一亩三分地
  81.                 int pos = quickSelect(candidates, start, end);
  82.                 if (pos == candidates.length - k) {
  83.                         return pos;
  84.                 } else if (pos < candidates.length - k) {
  85.                         return helper(candidates, pos + 1, end, k);
  86.                 } else {
  87.                         return helper(candidates, start, pos - 1, k);. from: 1point3acres
  88.                 }. Waral 博客有更多文章,
  89.         }

  90.         private static int quickSelect(People[] candidates, int start, int end) {. more info on 1point3acres
  91.                 int i = start;
  92.                 int j = start + 1;
  93.                 while (j <= end) {
  94.                         if (candidates[j].votes < candidates[start].votes) {.本文原创自1point3acres论坛
  95.                                 i++;
  96.                                 swap(candidates, i, j);. from: 1point3acres
  97.                                 j++;
  98.                         } else {. 1point3acres
  99.                                 j++;
  100.                         }
  101.                 }
    . From 1point 3acres bbs
  102.                 swap(candidates ,i, start);. 牛人云集,一亩三分地
  103.                 return i;
  104.         }

  105.         private static void swap(People[] candidates, int i, int j) {
  106.                 People tmp = candidates[i];
  107.                 candidates[i] = candidates[j];
  108.                 candidates[j] = tmp;
  109.         }

  110.         public static void main(String[] args) {
  111.                 LogEntry le1 = new LogEntry("c1", 1);.本文原创自1point3acres论坛
  112.                 LogEntry le2 = new LogEntry("c2", 2);
  113.                 LogEntry le3 = new LogEntry("c1", 2);
  114.                 LogEntry le4 = new LogEntry("c2", 3);
  115.                 LogEntry le5 = new LogEntry("c2", 4);
  116.                 List<LogEntry> logs = new ArrayList<LogEntry>();. 1point 3acres 论坛
  117.                 logs.add(le1);
  118.                 logs.add(le2);
  119.                 logs.add(le3);
  120.                 logs.add(le4);
  121.                 logs.add(le5);. 1point 3acres 论坛
  122.                 logs.add(new LogEntry("c3", 2));
  123.                 logs.add(new LogEntry("c3", 2));. From 1point 3acres bbs
  124.                 logs.add(new LogEntry("c3", 2));
  125. //                System.out.println(findWinner(2, logs));
  126. //                System.out.println(findWinner(4, logs));
  127.                 List<String> res = findTopKWinner(4, logs, 2);
    . 牛人云集,一亩三分地
  128.                 for (String str : res) {
  129.                         System.out.println(str);
  130.                 }
  131.         }
    . more info on 1point3acres

  132. }
复制代码
回复 支持 1 反对 0

使用道具 举报

我的人缘0
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
回复 支持 1 反对 0

使用道具 举报

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

使用道具 举报

我的人缘0
cqx83 发表于 2015-8-22 05:23:18 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
一面的题是我当时onsite的题。。
回复 支持 反对

使用道具 举报

我的人缘0
Williamslg 发表于 2015-8-22 05:39:24 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
cqx83 发表于 2015-8-22 05:23
一面的题是我当时onsite的题。。

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

使用道具 举报

我的人缘0
iorisli 发表于 2015-8-22 07:38:50 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
在无序数组里quick select只能找到第k大的数吧..? 能找top k吗?
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
iorisli 发表于 2015-8-22 12:36:06 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
danchou 发表于 2015-8-22 09:19
quick select的过程可以改变原数组,一次select之后k右边的数全部大于(或等于,看怎么实现了)arr[k]。可 ...

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

使用道具 举报

我的人缘0
say543 发表于 2015-8-22 12:40:34 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
感谢分享用quicksort 在如果candidates n 小于k(要求的number) 因该会有比较好的效果
回复 支持 反对

使用道具 举报

我的人缘0
muancy 发表于 2015-8-23 06:19:07 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
楼主能不能说说一面decode & encode的想法啊,找不到前面的面经了~
回复 支持 反对

使用道具 举报

我的人缘0
samuel1989 发表于 2015-8-23 12:16:25 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
能解释下encode list and decode string to list吗?
回复 支持 反对

使用道具 举报

我的人缘0
cqx83 发表于 2015-8-23 15:51:28 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
贴一下我encode和decode string list的那道题我自己的解法,当时onsite的时候就是这么做的。供大家参考

import java.util.*;
public class combineStrings{.本文原创自1point3acres论坛
    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);. from: 1point3acres
                System.out.println(result);
                String[] newArr = deserialize(result);
                for(String s : newArr) {
                        System.out.println(s);. 1point3acres
                }
        }
        public static String serialize(String[] arr) {
                StringBuilder sb = new StringBuilder();
                sb.append(arr.length + "#");
                for (String s : arr) {
                        sb.append(s.length() + "%");
                }
                for (String s : arr) {. from: 1point3acres
                        sb.append(s);
                }
                return sb.toString();
        }
        public static String[] deserialize(String s) {
                String[] sizeAndContent = s.split("#");
                int len = Integer.parseInt(sizeAndContent[0]);
                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++) {
                        size[i] = Integer.parseInt(eachSize[i]);
                        total += size[i];
                }
                String content = s.substring(s.length() - total, s.length());. from: 1point3acres
                String[] result = new String[len];
                for (int i = 0; i < len; i++) {
                        result[i] = content.substring(0, size[i]);
                        content = content.substring(size[i]);
                }
                return result;
        }
}
回复 支持 反对

使用道具 举报

我的人缘0
wenqiang88 发表于 2015-8-23 21:39:37 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
宝贝忆彼岸 发表于 2015-8-22 04:20
请问楼主第一题hash的意思就是遍历这个vector,然后candidate作为key,然后这个candidate的票数作为value是 ...

用quick sort的话不一定复杂度更低吧。
回复 支持 反对

使用道具 举报

我的人缘0
wenqiang88 发表于 2015-8-23 21:45:19 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
cqx83 发表于 2015-8-23 15:51
贴一下我encode和decode string list的那道题我自己的解法,当时onsite的时候就是这么做的。供大家参考

...

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

使用道具 举报

我的人缘0
say543 发表于 2015-8-24 00:23:56 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
第一面哪边有完整的题目阿? 找不到...谢谢
回复 支持 反对

使用道具 举报

我的人缘0
宝贝忆彼岸 发表于 2015-8-24 00:57:49 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
wenqiang88 发表于 2015-8-23 21:39
用quick sort的话不一定复杂度更低吧。

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

使用道具 举报

我的人缘0
alucardzhou 发表于 2015-8-24 02:41:40 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
祝福进onsite
回复 支持 反对

使用道具 举报

我的人缘0
cqx83 发表于 2015-8-24 03:48:16 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
wenqiang88 发表于 2015-8-23 05:45
请问题目里说了String不包含数字吗?

-google 1point3acres没说啊,可以包含任何字符。我的解法可以适用于所有情况
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

我的人缘0
donghao 发表于 2015-8-26 04:20:24 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
祝福进入onsite 加油
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-27 20:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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