一亩三分地论坛

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

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

Google 两轮电面 8/26 9/7

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

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

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

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

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:
求大家指正,或者有没有更好的方法
  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"吧
. Waral 鍗氬鏈夋洿澶氭枃绔,
对,手快打错了
回复 支持 反对

使用道具 举报

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

使用道具 举报

yiyizheliu 发表于 2016-9-29 10:32:34 | 显示全部楼层
写了一下第二题的代码,请大家critique一下:
  1. public class Reorder {
  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;. visit 1point3acres.com for more.
  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;. more info on 1point3acres.com
  18.                 }. From 1point 3acres bbs

  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;
  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);. 1point3acres.com/bbs
  28.                         sb.deleteCharAt(sb.length() - 1);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  29.                         counts.put(c, counts.get(c) + 1);
  30.                 }
  31.         }
  32. . 1point3acres.com/bbs
  33.         private void getCounts(Map<Character, Integer> map, String s){
  34.                 for(int i = 0; i < s.length(); i++){. from: 1point3acres.com/bbs
  35.                         map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
  36.                 }
  37.         }
  38.        
  39.         public void printResult(List<String> list){
  40.                 System.out.println("===== test =====");.鏈枃鍘熷垱鑷1point3acres璁哄潧
  41.                 for(String s : list){
  42.                         System.out.print(s + "  ");                       
  43.                 }
  44.                 System.out.println();. 1point 3acres 璁哄潧
  45.         }
  46.         public static void main(String[] args) {
  47.                 // TODO Auto-generated method stub
  48.                 Reorder ro = new Reorder();
  49.                 String test1 = "ab";-google 1point3acres
  50.                 ro.printResult(ro.solution(test1));. visit 1point3acres.com for more.
  51.                
  52.                 String test2 = "aaab";. From 1point 3acres bbs
  53.                 ro.printResult(ro.solution(test2));
  54.                 .1point3acres缃
  55.                 String test3 = "aab";
  56.                 ro.printResult(ro.solution(test3));
  57.                
  58.                 String test4 = "acbd";. 1point 3acres 璁哄潧
  59.                 ro.printResult(ro.solution(test4));. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  60.         }
  61. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  62. }
复制代码
回复 支持 反对

使用道具 举报

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楼的解法是正解
不过可以加一些判断,比如连续两个分点都是一个元素直接返回该元素
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 00:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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