一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 2124|回复: 8
收起左侧

Google 两轮电面 8/26 9/7

[复制链接] |试试Instant~ |关注本帖
Clytze 发表于 2016-9-29 08:53:40 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 本科 全职@Google - 网上海投 - 技术电面 |Failfresh grad应届毕业生

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

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

x
第一次是一个中国面试官,给一个sorted array,  定义popular number是array里出现次数>= 4/array_size的数,要找最小的popular number,要求时间O(logn)..鐣欏璁哄潧-涓浜-涓夊垎鍦
第二次是印度哥哥,给一个string,要求重新排列它的characters使没有两个相同的character是相邻的。
可能因为我是妹子,两道题都不难,是我自己太紧张脑子不转了。

本帖被以下淘专辑推荐:

yiyizheliu 发表于 2016-9-29 09:57:13 | 显示全部楼层
第一题我倒是想到一个很类似binary search的方法:
从array a, index start to end中找最小的popular number:
求大家指正,或者有没有更好的方法. 鍥磋鎴戜滑@1point 3 acres
  1. index = (start + end)/4;
  2. if(a[index] == a[start]) return a[start];
  3. else{
  4.    find the first ele which is not equal to a[start];
  5.    set start there.
  6. }
复制代码
回复 支持 2 反对 0

使用道具 举报

ymsf 发表于 2016-9-29 08:59:40 | 显示全部楼层
是 “出现次数 >= array_size/4"吧
回复 支持 反对

使用道具 举报

 楼主| Clytze 发表于 2016-9-29 09:01:29 | 显示全部楼层
ymsf 发表于 2016-9-29 08:59
是 “出现次数 >= array_size/4"吧

对,手快打错了
回复 支持 反对

使用道具 举报

mren 发表于 2016-9-29 10:29:46 | 显示全部楼层
第一题有四个潜在答案,在n/4, 2n/4, 3n/4, n处,因为是有序的,所以依次做二分查找这四个位置的值的左右边界,如果长度够n/4就可以返回了.. from: 1point3acres.com/bbs
第二题和leetcode的一个rearrange charactor相似,可以直接按照那个思路来做距离设为2.也就是先对字符统计个数,利用优先队列优先安排个数多的字符,2个为一组,完了个数减一再扔回优先队列.
回复 支持 反对

使用道具 举报

yiyizheliu 发表于 2016-9-29 10:32:34 | 显示全部楼层
写了一下第二题的代码,请大家critique一下:
  1. public class Reorder {. Waral 鍗氬鏈夋洿澶氭枃绔,
  2.         public List<String> solution(String s){
  3.                 //same method to get the permutation
  4.                 //but every time check the previous char in the result string
  5.                 //choose a different character
  6.                 List<String> result = new ArrayList<String>();
  7.                 Map<Character, Integer> counts = new HashMap<Character, Integer>();

  8.                 //get the counts
  9.                 getCounts(counts, s);

  10.                 getPermutation(counts, result, new StringBuffer(), s.length());
  11.                 return result;
  12.         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  13.        
  14.         private void getPermutation(Map<Character, Integer> counts, List<String> result, StringBuffer sb, int size){. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  15.                 if(sb.length() == size){
  16.                         result.add(sb.toString());
  17.                         return;
  18.                 }. more info on 1point3acres.com

  19.                 //when we add a char in the string, we decrement the corresponding count
  20.                 //as we need to backtrack, when the count == 0, we don't remove it. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  21.                 //but we have to check the count each time
  22.                 for(char c : counts.keySet()){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  23.                         if(counts.get(c) == 0) continue;. 1point3acres.com/bbs
  24.                         if(sb.length() != 0 && sb.charAt(sb.length() - 1) == c) continue;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  25.                         sb.append(c); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  26.                         counts.put(c, counts.get(c) - 1);
  27.                         getPermutation(counts, result, sb, size);
  28.                         sb.deleteCharAt(sb.length() - 1);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  29.                         counts.put(c, counts.get(c) + 1);-google 1point3acres
  30.                 }
  31.         }

  32.         private void getCounts(Map<Character, Integer> map, String s){
  33.                 for(int i = 0; i < s.length(); i++){
  34.                         map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
  35.                 }
  36.         }
  37.        
  38.         public void printResult(List<String> list){
  39.                 System.out.println("===== test =====");
  40.                 for(String s : list){
  41.                         System.out.print(s + "  ");                       
  42.                 }. from: 1point3acres.com/bbs
  43.                 System.out.println();
  44.         }
  45.         public static void main(String[] args) {
  46.                 // TODO Auto-generated method stub
  47.                 Reorder ro = new Reorder();
  48.                 String test1 = "ab";. 1point3acres.com/bbs
  49.                 ro.printResult(ro.solution(test1));
  50.                 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  51.                 String test2 = "aaab";
  52.                 ro.printResult(ro.solution(test2));
  53.                
  54.                 String test3 = "aab";
  55.                 ro.printResult(ro.solution(test3));
  56.                
  57.                 String test4 = "acbd";
  58.                 ro.printResult(ro.solution(test4));
  59.         }.1point3acres缃

  60. }
复制代码
回复 支持 反对

使用道具 举报

WhatsFLAG 发表于 2016-9-29 10:45:20 | 显示全部楼层
第二题的确不难,第一题我有个思路感觉不够精炼,不知道楼主能否帮我矫正?用分治法来求左边出现次数最多的元素,判断是否大于四分之一
回复 支持 反对

使用道具 举报

 楼主| Clytze 发表于 2016-9-29 11:16:58 | 显示全部楼层
mren 发表于 2016-9-29 10:29
第一题有四个潜在答案,在n/4, 2n/4, 3n/4, n处,因为是有序的,所以依次做二分查找这四个位置的值的左右边 ...

第一题我后来跟同学讨论后得出最合理的解法应该就是你说的。
第二题统计次数后从个数最多的数开始,奇偶位置插空即可。.鐣欏璁哄潧-涓浜-涓夊垎鍦
回复 支持 反对

使用道具 举报

dokolo 发表于 2016-9-29 11:23:58 | 显示全部楼层
4楼的解法是正解
不过可以加一些判断,比如连续两个分点都是一个元素直接返回该元素
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-12-15 05:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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