📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
回复: 28
跳转到指定楼层
上一主题 下一主题
收起左侧

8/21谷歌电面

全局:

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

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
刚刚面完谷歌二轮电面 (一面估计太搓)
直接上题:
struct LogEntry{
  string candidate;  投票姓名
  int time; 投票时间
};
string findWinner(int time, vector<Log
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
ector<string> decode(string s);
这一题出现过, 可以搜。 估计做的太慢, 加面一轮。

说一千道一万,求bless进onsite

评分

参与人数 2大米 +6 收起 理由
lchen77 + 3 感谢分享!
baobozo + 3 感谢分享!

查看全部评分


上一篇:被epic拒了……连电面都没给……
下一篇:Cerner Onsite

本帖被以下淘专辑推荐:

 楼主| siyuan808 2015-8-28 23:51:29 | 只看该作者
全局:
谢大家祝福啊。 昨天打电话说进onsite了。
回复

使用道具 举报

全局:
写了下第二面的代码,quick selection的最大不好是输出是没有顺序的,如果要有序还得再排,minHeap就没有这个问题。
  1. public class Winner {
  2.        
  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;
  9.                 }
  10.         }

  11.         static class People {
  12.                 String candidate;
  13.                 int votes;
  14.                 public People(String candidate, int votes) {
  15.                         this.candidate = candidate;
  16.                         this.votes = votes;
  17.                 }
  18.         }
  19.        
  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)) {
  25.                                         map.put(entry.candidate, map.get(entry.candidate) + 1);
  26.                                 } else {
  27.                                         map.put(entry.candidate, 1);
  28.                                 }
  29.                         }
  30.                 }
  31.                 String res = "";
  32.                 int max = 0;
  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;
  41.         }
  42.        
  43.         public static List<String> findTopKWinner(int time, List<LogEntry> logs, int k) {
  44.                 HashMap<String, Integer> map = new HashMap<String, Integer>();
  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.         }
  61.        
  62.         private static List<String> topKCandidateQuickSelect(People[] candidates, int k) {
  63.                 List<String> res = new ArrayList<String>();
  64.                 if (k == candidates.length) {
  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++) {
  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);
  88.                 }
  89.         }

  90.         private static int quickSelect(People[] candidates, int start, int end) {
  91.                 int i = start;
  92.                 int j = start + 1;
  93.                 while (j <= end) {
  94.                         if (candidates[j].votes < candidates[start].votes) {
  95.                                 i++;
  96.                                 swap(candidates, i, j);
  97.                                 j++;
  98.                         } else {
  99.                                 j++;
  100.                         }
  101.                 }
  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);
  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>();
  117.                 logs.add(le1);
  118.                 logs.add(le2);
  119.                 logs.add(le3);
  120.                 logs.add(le4);
  121.                 logs.add(le5);
  122.                 logs.add(new LogEntry("c3", 2));
  123.                 logs.add(new LogEntry("c3", 2));
  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.         }

  132. }
复制代码
回复

使用道具 举报

推荐
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
回复

使用道具 举报

全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
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吗?
回复

使用道具 举报

🔗
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吗?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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