从旧金山人口变化,谈湾区买房地段选择

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 2224|回复: 8
收起左侧

Google 两轮电面 8/26 9/7

[复制链接] |试试Instant~ |关注本帖
我的人缘0
Clytze 发表于 2016-9-29 08:53:40 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

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

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

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

上一篇:Amazon OA1
下一篇:问一个FB DESIGN题涉及到的CACHE一致性的问题

本帖被以下淘专辑推荐:

我的人缘0
yiyizheliu 发表于 2016-9-29 09:57:13 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第一题我倒是想到一个很类似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

使用道具 举报

我的人缘0
ymsf 发表于 2016-9-29 08:59:40 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
是 “出现次数 >= array_size/4"吧
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| Clytze 发表于 2016-9-29 09:01:29 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
ymsf 发表于 2016-9-29 08:59. 围观我们@1point 3 acres
是 “出现次数 >= array_size/4"吧

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

使用道具 举报

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

使用道具 举报

我的人缘0
yiyizheliu 发表于 2016-9-29 10:32:34 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
写了一下第二题的代码,请大家critique一下:
  1. public class Reorder {
  2.         public List<String> solution(String s){. visit 1point3acres for more.
  3.                 //same method to get the permutation
  4.                 //but every time check the previous char in the result string
  5.                 //choose a different character . Waral 博客有更多文章,
  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. . Waral 博客有更多文章,
  11.                 getPermutation(counts, result, new StringBuffer(), s.length());
    . 一亩-三分-地,独家发布
  12.                 return result;
  13.         }
  14.        
  15.         private void getPermutation(Map<Character, Integer> counts, List<String> result, StringBuffer sb, int size){
  16.                 if(sb.length() == size){. 留学申请论坛-一亩三分地
  17.                         result.add(sb.toString());
  18.                         return;
  19.                 }

  20.                 //when we add a char in the string, we decrement the corresponding count
  21.                 //as we need to backtrack, when the count == 0, we don't remove it
  22.                 //but we have to check the count each time
  23.                 for(char c : counts.keySet()){
  24.                         if(counts.get(c) == 0) continue;-google 1point3acres
  25.                         if(sb.length() != 0 && sb.charAt(sb.length() - 1) == c) continue;
  26.                         sb.append(c);.本文原创自1point3acres论坛
  27.                         counts.put(c, counts.get(c) - 1);. from: 1point3acres
  28.                         getPermutation(counts, result, sb, size);. 1point 3acres 论坛
  29.                         sb.deleteCharAt(sb.length() - 1);
  30.                         counts.put(c, counts.get(c) + 1);
  31.                 }
  32.         }
  33. .本文原创自1point3acres论坛
  34.         private void getCounts(Map<Character, Integer> map, String s){
  35.                 for(int i = 0; i < s.length(); i++){. Waral 博客有更多文章,
  36.                         map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
  37.                 }
  38.         }
  39.        
  40.         public void printResult(List<String> list){
  41.                 System.out.println("===== test =====");
  42.                 for(String s : list){
  43.                         System.out.print(s + "  ");                       
  44.                 }
  45.                 System.out.println();
  46.         }. From 1point 3acres bbs
  47.         public static void main(String[] args) {
  48.                 // TODO Auto-generated method stub
  49.                 Reorder ro = new Reorder();-google 1point3acres
  50.                 String test1 = "ab";
  51.                 ro.printResult(ro.solution(test1));
  52.                
  53.                 String test2 = "aaab";
  54.                 ro.printResult(ro.solution(test2));. 1point 3acres 论坛
  55.                
  56.                 String test3 = "aab";
  57.                 ro.printResult(ro.solution(test3));. more info on 1point3acres
  58.                
  59.                 String test4 = "acbd";
  60.                 ro.printResult(ro.solution(test4));
  61.         }

  62. . 留学申请论坛-一亩三分地
  63. }
复制代码
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
 楼主| Clytze 发表于 2016-9-29 11:16:58 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
mren 发表于 2016-9-29 10:29
第一题有四个潜在答案,在n/4, 2n/4, 3n/4, n处,因为是有序的,所以依次做二分查找这四个位置的值的左右边 ...

第一题我后来跟同学讨论后得出最合理的解法应该就是你说的。.本文原创自1point3acres论坛
第二题统计次数后从个数最多的数开始,奇偶位置插空即可。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
dokolo 发表于 2016-9-29 11:23:58 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
4楼的解法是正解
不过可以加一些判断,比如连续两个分点都是一个元素直接返回该元素
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-6-18 05:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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