一亩三分地论坛

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

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

google电面+onsite+加面

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

2016(7-9月) 码农类 硕士 全职@Google - 猎头 - Onsite |Other在职跳槽

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

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

x
发面经,攒人品!
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
phone第一题:
input是两个string,例如:"google", "algorithm"-google 1point3acres
output是一个string,按above例子就是:"lggooe"
写出一个function实现这个过程. 鍥磋鎴戜滑@1point 3 acres

phone第二题:
十个人赛跑,有好几个裁判。每个裁判提供一部分人的到达终点的前后顺序。
问怎么得出完整结果。. From 1point 3acres bbs
.1point3acres缃
onsite:
  • 反转链表
  • 看一个2d数组是不是对角线对称
  • 一个1m的side walk,有一个random的雨滴generator。每次下一滴雨,每滴1cm,能下到这个sidewalk的任何位置,问怎么知道sidewalk什么时候全部被覆盖
  • ood问题,有四种message,设计一些类,让他可以read和write。用inputstream和outputstream。这个说不太明白。。
  • 类似LRU
  • 有一个iterator的iterator。<<123>,<456>>。设计一个iterator类,next()的时候输出142536。多线程的时候,不能加锁的话,怎么解决race。

加面:
                       
  • 给两个数。假设为2和7。我们来玩一个游戏。
规则:将每一个数组中每一位两两相减,得到的绝对值如果不在这个array里,就append在这个array后面。求所有可能的解。



2. 炸弹人 只不过是用光和墙来表示。问站在哪里能照到更多的光。
follow up。如果这个matrix很大很大,而且很sparse,怎么存?怎么解?

3. 一个图,里面的节点有值和颜色。黑色绿色和红色。求所有 开始节点和经过的节点全是绿色,终点是黑色的 路径. From 1point 3acres bbs
               

. from: 1point3acres.com/bbs

评分

5

查看全部评分

本帖被以下淘专辑推荐:

rabbithui 发表于 2016-10-7 04:16:08 | 显示全部楼层
第一题:
. Waral 鍗氬鏈夋洿澶氭枃绔,
import java.lang.Math; // headers MUST be above the first class
import java.util.*;
. 鍥磋鎴戜滑@1point 3 acres
// one class needs to have a main() method
public class HelloWorld
{
  // arguments are passed using the text field below this editor
  public static void main(String[] args)
  {
    OtherClass myObject = new OtherClass();
           System.out.println(myObject.get("google","algorithm"));
  }
}

// you can add other public classes to this editor in any order
public class OtherClass
{
  public String get(String original,String order){
          HashMap<Character,String> map=new HashMap<>();. 1point3acres.com/bbs
   
    for(int i=0;i<order.length();i++){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
      char c=order.charAt(i);
      map.put(c,"");
    }
   
    String tail="";.鐣欏璁哄潧-涓浜-涓夊垎鍦
    for(int i=0;i<original.length();i++){
      char c=original.charAt(i);
      if(map.containsKey(c)){
              map.put(c,map.get(c)+c);
      }
      else
        tail+=c;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    }
    . Waral 鍗氬鏈夋洿澶氭枃绔,
    String result="";
    for(int i=0;i<order.length();i++){. visit 1point3acres.com for more.
      char c=order.charAt(i);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
      result+=map.get(c);
    }
   
    result+=tail;
   
    return result;
  }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
}
回复 支持 1 反对 0

使用道具 举报

wtcupup 发表于 2016-9-16 01:36:59 | 显示全部楼层
电面第一题什么意思啊?
回复 支持 反对

使用道具 举报

 楼主| hcheng81 发表于 2016-9-16 01:47:38 | 显示全部楼层
wtcupup 发表于 2016-9-16 01:36
电面第一题什么意思啊?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
他就是给你input 和 output的信息 让你推断出做了什么,再写出来 这个意思。
回复 支持 反对

使用道具 举报

Ridingstar01 发表于 2016-9-16 01:48:39 | 显示全部楼层
楼主加面是怎么个情况。。当天加的还是之后加的。。
回复 支持 反对

使用道具 举报

 楼主| hcheng81 发表于 2016-9-16 01:53:26 | 显示全部楼层
Ridingstar01 发表于 2016-9-16 01:48. From 1point 3acres bbs
楼主加面是怎么个情况。。当天加的还是之后加的。。

不知道。。。可能是意见有分歧或者是第一次面的太简单了。我在nyc面的。. from: 1point3acres.com/bbs

补充内容 (2016-9-16 01:59):
阿,是之后一周通知我再去一次的。
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-9-16 01:57:15 | 显示全部楼层
hcheng81 发表于 2016-9-16 01:47
他就是给你input 和 output的信息 让你推断出做了什么,再写出来 这个意思。

所以能说说两个string 发生了什么?没看出规律
回复 支持 反对

使用道具 举报

superbinhugo 发表于 2016-9-16 02:03:41 | 显示全部楼层
我的天,现在都8轮onsite了啊= =
回复 支持 反对

使用道具 举报

lxxxxxxx 发表于 2016-9-16 02:04:00 | 显示全部楼层
第一题是把string1中的char按string2中的出现顺序排序? 想知道剩下的该咋办,例如不是google而是googlep 那么e和p都没出现是保留原始顺序么?
回复 支持 反对

使用道具 举报

hello2pig 发表于 2016-9-16 02:04:29 | 显示全部楼层
wtcupup 发表于 2016-9-16 01:57
所以能说说两个string 发生了什么?没看出规律

应该是对一个string重新排序吧,char的数据依照第二个string出现的次序 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

补充内容 (2016-9-16 02:04):
char的顺序
回复 支持 反对

使用道具 举报

 楼主| hcheng81 发表于 2016-9-16 02:11:49 | 显示全部楼层
lxxxxxxx 发表于 2016-9-16 02:04
第一题是把string1中的char按string2中的出现顺序排序? 想知道剩下的该咋办,例如不是google而是googlep  ...

对,保留顺序append在后面。
回复 支持 反对

使用道具 举报

阿满 发表于 2016-9-16 02:19:02 | 显示全部楼层
楼主能说一下onsite 6 在多线程的时候该怎么做吗? 多谢!
回复 支持 反对

使用道具 举报

 楼主| hcheng81 发表于 2016-9-16 03:06:44 | 显示全部楼层
阿满 发表于 2016-9-16 02:19
楼主能说一下onsite 6 在多线程的时候该怎么做吗? 多谢!

我现在还不会做。。

他提示说应该用一个像buffer一样的东西。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
求大神解惑。
回复 支持 反对

使用道具 举报

lingeast 发表于 2016-9-16 09:18:59 | 显示全部楼层
Onsite-3 是赠券收集者问题? https://en.wikipedia.org/wiki/Coupon_collector%27s_problem
回复 支持 反对

使用道具 举报

pinkdatura 发表于 2016-9-16 13:58:36 | 显示全部楼层
请问phone第二题,就是类似merge k sorted list的样子吗
加面第一题,请问是给的2个数还是数组啊?有点没看明白题目。
谢谢啦~各种bless!!!
回复 支持 反对

使用道具 举报

 楼主| hcheng81 发表于 2016-9-16 22:01:19 | 显示全部楼层
pinkdatura 发表于 2016-9-16 13:58. from: 1point3acres.com/bbs
请问phone第二题,就是类似merge k sorted list的样子吗
加面第一题,请问是给的2个数还是数组啊?有点没 ...

phone 第二题:

第一个裁判给的结果是:参赛者到终点顺序为:2 9 4 3. visit 1point3acres.com for more.
第二个裁判给的结果是:参赛者到终点顺序为:9 6 5 4. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第三个裁判给的结果是:参赛者到终点顺序为:2 8 1
.鐣欏璁哄潧-涓浜-涓夊垎鍦
。。。

求最终顺序。


------------------------------------------------

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
加面第一题,我写的不是很清楚不好意思。。。

输入是一个数组[2, 7],输出应该是一个list的数组。

规则是这个数组里的每一个数两两相减,所得的新数append在后面

比如[2, 7] 会变成 [2, 7, 5]

[2, 7, 5] 会变成 [2, 7, 5,3]

[2,7,5,3] either变成 [2,7,5,3,1] 或者 [2,7,5,3,4]

[2,7,5,3,1] -〉[2,7,5,3,1, 6] 或者 [2,7,5,3,1, 4] -〉[2,7,5,3,1, 6, 4]  或者 [2,7,5,3,1,4,6]

[2,7,5,3,4] -〉 [2,7,5,3,4,1] -〉[2,7,5,3,4,1,6] . 鍥磋鎴戜滑@1point 3 acres

以此类推,到最后没有数字可以往上加了的时候停止,求所有的组合。红字为结果。

补充内容 (2016-9-16 22:02):
[2,7,5,3,1,4,6]  这个也是结果,上面忘记加红色了。

补充内容 (2016-9-16 22:13):-google 1point3acres

第一个裁判给的结果是:参赛者到终点顺序为:2 9 4 3

. 鍥磋鎴戜滑@1point 3 acres
这个意思是,选手2在选手9 之前到达终点,选手9在选手4之前,选手4在选手3之前。
回复 支持 反对

使用道具 举报

leonardcohen 发表于 2016-9-16 23:42:04 | 显示全部楼层
LZ 's information:
phone第二题:
十个人赛跑,有好几个裁判。每个裁判提供一部分人的到达终点的前后顺序。
问怎么得出完整结果。
第一个裁判给的结果是:参赛者到终点顺序为:2 9 4 3. 鍥磋鎴戜滑@1point 3 acres
这个意思是,选手2在选手9 之前到达终点,选手9在选手4之前,选手4在选手3之前。

My guess and solution, could LZ verify below is right or not:
Question: give you partly relative sequence to get whole sort sequence
give you 7518, 6718, 9436, 2967  to get : 294367518
Solution pseudo  code :
initial array [1,2,3,4,5,6,7,8,9]
while the relative position in [7518, 6718, 9436, 2967] is not same as the relative position in array:
swap the element in array to make sure the relative position in array is same as in [7518, 6718, 9436, 2967]
. 1point 3acres 璁哄潧
123456789 + 7518 --> 723456189 + 6718 --> 623457189 + 9436 --> 923457186 + 2967 (first round finish)--> 293456187 + 7518 (second round begin) --> 293476518 + 6718 --> 293467518 + 9436 --> 294367518 (bingo!)

It really hard.. Waral 鍗氬鏈夋洿澶氭枃绔,


补充内容 (2016-9-17 01:12):
This solution come out from myself is Naive.
Here is the right solution:
http://stackoverflow.com/questio ... nown-order-sequence
Google ask this in phone, OMG
回复 支持 反对

使用道具 举报

amszhou 发表于 2016-9-17 00:36:26 | 显示全部楼层
leonardcohen 发表于 2016-9-16 23:42
LZ 's information:
phone第二题:
十个人赛跑,有好几个裁判。每个裁判提供一部分人的到达终点的前后顺 ...

粗暴一点,topology sort,应该没问题
回复 支持 反对

使用道具 举报

domofeng 发表于 2016-9-17 11:31:01 | 显示全部楼层
hcheng81 发表于 2016-9-16 22:01
phone 第二题:
. more info on 1point3acres.com
第一个裁判给的结果是:参赛者到终点顺序为:2 9 4 3
. From 1point 3acres bbs
谢谢楼主这么详细的说明, 有个小问题

[2,7,5,3,1, 4] -> [2,7,5,3,1,4,6]

这个应该出不来吧, 因为,  [2,7,5,3,1, 4], 4和前面任意数的差都达不到6.

此外, 此题还应该注意hash去重, 否则在构造. 1point 3acres 璁哄潧
[2,7,5,3,4]时候会有2个[2,7,5,3,4,1], 一个是从abs(4-5)来的, 一个是从abs(4-3)来的
. 1point 3acres 璁哄潧
回复 支持 反对

使用道具 举报

 楼主| hcheng81 发表于 2016-9-17 13:32:40 | 显示全部楼层
domofeng 发表于 2016-9-17 11:31
谢谢楼主这么详细的说明, 有个小问题

[2,7,5,3,1, 4] -> [2,7,5,3,1,4,6]
.鏈枃鍘熷垱鑷1point3acres璁哄潧
是两两相减

2,7,5,3,1,4 里 1和7可以变成6
回复 支持 反对

使用道具 举报

domofeng 发表于 2016-9-17 16:12:29 | 显示全部楼层
hcheng81 发表于 2016-9-17 13:32
是两两相减 . From 1point 3acres bbs
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
2,7,5,3,1,4 里 1和7可以变成6

没理解清楚题意, 不好意思, 以为只能求最后一个新加的diff, 和前面所有的diff. 谢谢楼主
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 15:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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