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

8/21谷歌电面

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

使用道具 举报

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

使用道具 举报

🔗
 楼主| siyuan808 2015-8-29 00:02:41 | 只看该作者
全局:
siyuan808 发表于 2015-8-28 23:51
谢大家祝福啊。 昨天打电话说进onsite了。

21楼是我的解法
回复

使用道具 举报

🔗
JaySong 2015-11-18 12:18:35 | 只看该作者
全局:
我觉得follow up最简单的解法是用PriorityQueue, 时间复杂度是一样的,几行代码就写完了,楼主觉得如何
回复

使用道具 举报

🔗
bobzhang2004 2015-12-6 06:03:20 | 只看该作者
全局:
写了下第二面的代码,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. }
复制代码
回复

使用道具 举报

🔗
tbmichael 2016-3-9 12:38:30 | 只看该作者
全局:
必须祝福,能进onsite
回复

使用道具 举报

🔗
ariesxiao 2016-9-14 03:03:01 | 只看该作者
全局:
请问求TOP1用的HEAP?如果有多个相同的票数的,是不是要把HEAP顶的一个个挪出来,再塞回去?HEAP没有GET TOP K吧
回复

使用道具 举报

无效楼层,该帖已经被删除
🔗
xiaofengshan 2018-1-26 05:11:46 | 只看该作者
全局:
bobzhang2004 发表于 2015-12-6 06:03
写了下第二面的代码,quick selection的最大不好是输出是没有顺序的,如果要有序还得再排,minHeap就没有这 ...

quick sort方法好啊!之前一直想的是用一个min heap。。
回复

使用道具 举报

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

本版积分规则

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