亚麻OA求砸,面经神衣护体!


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 10204|回复: 40
收起左侧

google电面+onsite+加面

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

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

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

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

x
发面经,攒人品!
. 鍥磋鎴戜滑@1point 3 acres
phone第一题:
input是两个string,例如:"google", "algorithm"
output是一个string,按above例子就是:"lggooe". From 1point 3acres bbs
写出一个function实现这个过程
.鏈枃鍘熷垱鑷1point3acres璁哄潧
phone第二题:
游客,本帖隐藏的内容需要积分高于 166 才可浏览,您当前积分为 0。
查看如何攒积分 Click here to access restricted content

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



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

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


评分

6

查看全部评分

本帖被以下淘专辑推荐:

rabbithui 发表于 2016-10-7 04:16:08 | 显示全部楼层
第一题:. visit 1point3acres.com for more.

import java.lang.Math; // headers MUST be above the first class
import java.util.*;

// one class needs to have a main() method
. visit 1point3acres.com for more.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.鏈枃鍘熷垱鑷1point3acres璁哄潧
{
  public String get(String original,String order){
          HashMap<Character,String> map=new HashMap<>();
    . visit 1point3acres.com for more.
    for(int i=0;i<order.length();i++){.鏈枃鍘熷垱鑷1point3acres璁哄潧
      char c=order.charAt(i);
      map.put(c,"");
    }
    . 1point3acres.com/bbs
    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;. From 1point 3acres bbs
    }
   
    String result="";
. From 1point 3acres bbs    for(int i=0;i<order.length();i++){
      char c=order.charAt(i);
      result+=map.get(c);
    }
   
    result+=tail;
    . visit 1point3acres.com for more.
    return result;. visit 1point3acres.com for more.
  }
}
回复 支持 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
楼主加面是怎么个情况。。当天加的还是之后加的。。

不知道。。。可能是意见有分歧或者是第一次面的太简单了。我在nyc面的。

补充内容 (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 在多线程的时候该怎么做吗? 多谢!

我现在还不会做。。
. From 1point 3acres bbs
他提示说应该用一个像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
请问phone第二题,就是类似merge k sorted list的样子吗
加面第一题,请问是给的2个数还是数组啊?有点没 ...
.1point3acres缃
phone 第二题:
-google 1point3acres
第一个裁判给的结果是:参赛者到终点顺序为:2 9 4 3
第二个裁判给的结果是:参赛者到终点顺序为:9 6 5 4
第三个裁判给的结果是:参赛者到终点顺序为:2 8 1

。。。

求最终顺序。


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


加面第一题,我写的不是很清楚不好意思。。。
. Waral 鍗氬鏈夋洿澶氭枃绔,
输入是一个数组[2, 7],输出应该是一个list的数组。

规则是这个数组里的每一个数两两相减,所得的新数append在后面
. Waral 鍗氬鏈夋洿澶氭枃绔,
比如[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]

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

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

补充内容 (2016-9-16 22:13):
. 1point 3acres 璁哄潧
第一个裁判给的结果是:参赛者到终点顺序为:2 9 4 3


这个意思是,选手2在选手9 之前到达终点,选手9在选手4之前,选手4在选手3之前。
回复 支持 反对

使用道具 举报

leonardcohen 发表于 2016-9-16 23:42:04 | 显示全部楼层
LZ 's information:
phone第二题:
十个人赛跑,有好几个裁判。每个裁判提供一部分人的到达终点的前后顺序。
问怎么得出完整结果。
第一个裁判给的结果是:参赛者到终点顺序为:2 9 4 3
这个意思是,选手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]

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.


补充内容 (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
. visit 1point3acres.com for more.LZ 's information: . more info on 1point3acres.com
phone第二题:
十个人赛跑,有好几个裁判。每个裁判提供一部分人的到达终点的前后顺 ...

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

使用道具 举报

domofeng 发表于 2016-9-17 11:31:01 | 显示全部楼层
hcheng81 发表于 2016-9-16 22:01
phone 第二题:
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第一个裁判给的结果是:参赛者到终点顺序为:2 9 4 3
. 1point 3acres 璁哄潧
谢谢楼主这么详细的说明, 有个小问题

[2,7,5,3,1, 4] -> [2,7,5,3,1,4,6]-google 1point3acres
-google 1point3acres
这个应该出不来吧, 因为,  [2,7,5,3,1, 4], 4和前面任意数的差都达不到6.
. more info on 1point3acres.com
此外, 此题还应该注意hash去重, 否则在构造
[2,7,5,3,4]时候会有2个[2,7,5,3,4,1], 一个是从abs(4-5)来的, 一个是从abs(4-3)来的

回复 支持 反对

使用道具 举报

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

[2,7,5,3,1, 4] -> [2,7,5,3,1,4,6]
. Waral 鍗氬鏈夋洿澶氭枃绔,
是两两相减 . from: 1point3acres.com/bbs

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

使用道具 举报

domofeng 发表于 2016-9-17 16:12:29 | 显示全部楼层
hcheng81 发表于 2016-9-17 13:32
是两两相减

2,7,5,3,1,4 里 1和7可以变成6

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-10-22 07:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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