一亩三分地论坛

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

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

google电面

[复制链接] |试试Instant~ |关注本帖
wcongying 发表于 2015-12-3 05:32:14 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Fail在职跳槽

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

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

x
电面2次,现在题目能做出来也不一定能On site了。被拒绝的电话是HR打给我的。
. 鍥磋鎴戜滑@1point 3 acres
1,第一次的电面是先聊我的背景和项目,时间比较长。只有一个题目是:UTF-8。Q: Write a method isValidUTF8 that takes a byte array, and returns true iff that array is a valid UTF8 string.
<UTF8 String> ::= <UTF8 Codepoint Sequence>*
<UTF8 Codepoint Sequence> ::= <Header Byte> <Continuation Bytes>{n - 1}, where n == number of bytes in codepoint encoding.
0 == 0 bit, 1 == 1 bit, X == don’t care.
0XXXXXXX - Header Byte for 1 Byte Codepoint Encoding
10XXXXXX - Continuation Byte
110XXXXX - Header Byte for 2 Byte Codepoint Encoding
1110XXXX - Header Byte for 3 Byte Codepoint Encoding
11111110 - Header Byte for 7 Byte Codepoint Encoding
11111111 - Header Byte for 8 Byte Codepoint Encoding
[ 0b01110011, 0b00011110 ] = two-character string
[ 0b11000110, 0b10000110 ] = one-character string
这个题目是面经出现频率比较高的题目,我看了大家的总结很受益。但是这题我还没有开始写,面试官还没解释完时间就到了。其实这题google的要求简单。


2,第二次电面上来问我的对什么工作感兴趣,很简短。
只有一道题,就是LC 56 Merge intervals。  我面试的时候和面试官交流要不要写comparator类。 我应该是面试开始20分钟前就写完了主体。但是我犯了一个错误,也是编程不好的习惯:我自己写的方法有返回,可是我在开始写的时候,新建我的result的时候,没有直接在代码上加上return result的语句。在面试官提示下修改后还return 了一个不对的变量名。
我写这题有个步骤是排序,我开始问面试官我能用comparator吧,回答说可以用Library。可是我写完后问要反馈的时候,TA没让我写任何的排序方法。  我其实应该可以写排序方法,可是最后连comparator那4行都没写。面试官问了我时间空间复杂度还有各种问题。我对排序算法的时间复杂度回答太谨慎,其实不好。最快也就n*log n。还有我这次对java的程序的各种名称的英语说法说的不流利或者不对。我明明建立的是interval 的class,在class里面建立constructor,结果我在建class的时候说我建立的是constructor。  还有result是一个variable,电面的时候这个单词居然说不出来。什么都不能短板。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
还有面试官问我:在什么情况下这个程序会运行的慢。


3,最后HR说今年的bar很高。希望大家都能找到合适自己的工作。有什么问题欢迎提出

评分

2

查看全部评分

七夜雪 发表于 2015-12-3 13:59:26 | 显示全部楼层
自己写了第一题才发现好多关于byte的东西都不知道...貌似java里面如果一个byte是0b1xxxxxxx的话要bit shift会自动sign extension成int, 于是那个数就变成了 0b(24个1)+1xxxxxxx, 所以每次bit shifting都要mask

试着写了一下,不知道有没有更好的方法。。。觉得我的code质量好低。。。. from: 1point3acres.com/bbs
.鏈枃鍘熷垱鑷1point3acres璁哄潧
  1.         public boolean isValidUTF8(byte[] input){-google 1point3acres
  2.                 for(int i=0; i<input.length;){. from: 1point3acres.com/bbs
  3.                         byte header=input[i];
  4.                         int size=0;-google 1point3acres
  5.                         if(input[i]==(byte)0b11111111)
  6.                                 size=8;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  7.                         else if(input[i]==(byte)0b11111110)
  8.                                 size=7;
  9.                         else if((input[i]>>>1&0x7f)==0b1111110)
  10.                                 size=6;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  11.                         else if((input[i]>>>2&0x3f)==0b111110)
  12.                                 size=5;
  13.                         else if((input[i]>>>3&0x1f)==0b11110).1point3acres缃
  14.                                 size=4;
  15.                         else if((input[i]>>>4&0xf)==0b1110)
  16.                                 size=3;
  17.                         else if((input[i]>>>5&0x7)==0b110)
  18.                                 size=2;
  19.                         else if((input[i]>>>6&0x3)==0b10)
  20.                                 return false;
  21.                         else
  22.                                 size=1;
  23.                         if(size>1&&(i+size-1>=input.length||!isValidContinuation(input, i+1, i+size-1))).鐣欏璁哄潧-涓浜-涓夊垎鍦
  24.                                         return false;
  25.                         i=i+size;       
  26.                 }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  27.                 return true;
  28.         }
  29.        
  30.        
  31.         private boolean isValidContinuation(byte[] input, int lo, int hi){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  32.                 for(int i=lo; i<=hi; i++)
  33.                         if((input[i]>>>6&0x3)!=0b10)-google 1point3acres
  34.                                 return false;
  35.                 return true; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  36.         }
复制代码
回复 支持 反对

使用道具 举报

lcl3356897 发表于 2015-12-3 15:06:46 | 显示全部楼层
第一题是不是可以写个 leadingOnes(byte num) 的函数,返回byte的开头有多少个1


  1. int leadingOnes(byte num){
  2.                 for(int i = 7; i >= 0; i--){
  3.                         if( ((num >> i) & 1) == 0) return 7 - i;
  4.                 }
  5.                 return 8;
  6.         }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 00:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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