一亩三分地论坛

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

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

Square第二轮电面 2015/10/1

[复制链接] |试试Instant~ |关注本帖
Yunying 发表于 2015-10-2 10:15:04 | 显示全部楼层 |阅读模式

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

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

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

x
Square第二轮电面~

是写一个function, drop(double position, double size), 即从高处掉一个方块,左边的x坐标是position,方块的边长是size。然后它会一个个叠起来。
比如drop(1,4), drop(3,3)的话就会变成这样: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
   bbb. Waral 鍗氬鏈夋洿澶氭枃绔,
   bbb. more info on 1point3acres.com
   bbb
aaaa
aaaa
aaaa
aaaa

然后它掉一大堆方块下来之后任何时候想要call一个叫getHeight()的function的话,你就得返回这堆方块里地最高点(但getHeight在面试中没有写,面试官只叫我写了drop)

我就用map做了,做完后面试官说可以用tree,这样可以更加efficient。我感觉他那个方法还是没太懂。。。有没有大神来解释一下。。。
-google 1point3acres
就酱~不知道说清楚了没有。. from: 1point3acres.com/bbs

面试结束后1个小时就发来onsite邀请啦^_^

.鐣欏璁哄潧-涓浜-涓夊垎鍦明天Google Onsite加油加油加油~~~!!!
f1371342385 发表于 2015-10-2 10:53:51 | 显示全部楼层
LZ是用Map<Integer, Set<Integer>>这样的map来做的?
回复 支持 反对

使用道具 举报

 楼主| Yunying 发表于 2015-10-2 11:02:09 | 显示全部楼层
f1371342385 发表于 2015-10-2 10:53
LZ是用Map这样的map来做的?
. from: 1point3acres.com/bbs
木有~就map<double, double>。跟Skyline有点像,就是记录高度变化的节点们~
回复 支持 反对

使用道具 举报

f1371342385 发表于 2015-10-2 11:09:16 | 显示全部楼层
Yunying 发表于 2015-10-2 11:02
木有~就map。跟Skyline有点像,就是记录高度变化的节点们~

好的,感谢LZ哈
回复 支持 反对

使用道具 举报

hanchen999 发表于 2015-10-2 13:16:53 | 显示全部楼层
正整数还好,double感觉好难啊,我怎么觉得应该用interval来做。。
回复 支持 反对

使用道具 举报

brian1118 发表于 2015-10-3 02:56:25 | 显示全部楼层
map<double, double> 用來記錄每個x的高度嗎?
ex: drop(1,4) -> map[1] = 4, map[2] = 4, map[3] = 4, map[4] = 4
這樣嗎?
回复 支持 反对

使用道具 举报

obama555 发表于 2015-10-3 03:11:00 | 显示全部楼层
请问楼主,Square的电面每个人都是两轮吗?有没有第二轮和第一轮的表现有关吗?小弟上周刚面了第一轮,面完不到一小时就HR就发邮件问第二次电面的availability,下周要面第二轮。问一下,有第二轮说明第一轮过关了吗?还是说所有人都有第二轮?
回复 支持 反对

使用道具 举报

 楼主| Yunying 发表于 2015-10-3 12:13:24 | 显示全部楼层
obama555 发表于 2015-10-3 03:11. From 1point 3acres bbs
请问楼主,Square的电面每个人都是两轮吗?有没有第二轮和第一轮的表现有关吗?小弟上周刚面了第一轮,面完 ...

有第二轮当然是第一轮过关了啊。。。不过也没什么差吧。。。
回复 支持 反对

使用道具 举报

obama555 发表于 2015-10-3 12:23:30 | 显示全部楼层
Yunying 发表于 2015-10-3 12:13
有第二轮当然是第一轮过关了啊。。。不过也没什么差吧。。。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
大大地不一样有,如果所有人都有第二轮,那就不能因为有第二轮就认为第一轮过关,万一第一轮没过关就给第二轮,那无论第二轮面的多好都是fail,太伤感情了,花了时间不得好果子吃
回复 支持 反对

使用道具 举报

cjqhenry 发表于 2015-10-3 12:41:53 | 显示全部楼层
obama555 发表于 2015-10-3 12:23
大大地不一样有,如果所有人都有第二轮,那就不能因为有第二轮就认为第一轮过关,万一第一轮没过关就给第 ...

应该是过了第一轮才有第二轮,反正不管怎么样,都得好好面啊。 加油!
回复 支持 反对

使用道具 举报

cjqhenry 发表于 2015-10-7 08:05:52 | 显示全部楼层
楼主能说下具体咋做的么? 感觉略难啊,多谢!
回复 支持 反对

使用道具 举报

开水蛙 发表于 2015-10-8 17:43:11 | 显示全部楼层
你们面square的后来都怎么样了啊
回复 支持 反对

使用道具 举报

ammmmy11 发表于 2015-10-10 08:27:27 | 显示全部楼层
square onsite面经好少啊,强烈建议楼主onsite回来share下下,提前预祝楼主拿offer哈哈
回复 支持 反对

使用道具 举报

 楼主| Yunying 发表于 2015-10-10 09:23:34 | 显示全部楼层
cjqhenry 发表于 2015-10-7 08:05
楼主能说下具体咋做的么? 感觉略难啊,多谢!

就是类似于Skyline的思路。弄一个map,然后把所有高度变化的节点都存在Map里,然后每掉下来一个方块就update map就好了
回复 支持 反对

使用道具 举报

 楼主| Yunying 发表于 2015-10-10 09:23:42 | 显示全部楼层
开水蛙 发表于 2015-10-8 17:43
你们面square的后来都怎么样了啊

还没onsite啊
回复 支持 反对

使用道具 举报

zxl9171 发表于 2015-10-27 16:20:13 | 显示全部楼层
这题用segment tree吧
回复 支持 反对

使用道具 举报

ammmmy11 发表于 2015-10-29 15:15:21 | 显示全部楼层
zxl9171 发表于 2015-10-27 16:20
这题用segment tree吧

我也觉得用segment tree, 但是建树要有个上限,这道题不知道有没有给上限
回复 支持 反对

使用道具 举报

zxl9171 发表于 2015-11-3 12:15:56 | 显示全部楼层
所以这道题到底应该怎么做啊
回复 支持 反对

使用道具 举报

kelong 发表于 2016-2-22 11:32:43 | 显示全部楼层
这个题是比较典型的线段树(segment tree)。一种解法是:
1. define Node { double x1, x2, h },即代表X轴上坐标x1到x2之间能够遇到的最大高度为h
2. 每次来一个方块,设x坐标范围为(a, b),高度ht, 那么查找segment tree,得到(a, b)之间最大高度,设为H,则(a,b)区间的新高度需要变成(H+ht)
3. 更新segment tree,使(a, b)区间新高度为(H+ht):从根节点开始遍历,
    1)如果cur_node的(x1,x2)完全包括了(a,b)
          1) cur_node.h = (H+ht)
          2) 如果cur_node有子节点, 递归更新子节点
    2) 如果(x1, x2)跟(a,b)部分重合,假设 a < x1 < b < x2:
           1)生成一个新节点,范围:(a,x2)
           2)新节点left_child生成新节点, 范围(a,x1),right_child = cur_node (范围为x1-x2)
           3) 递归更新cur_node, 但范围从开始的(a,b)变成了(x1,b)

如此即可。
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-3-9 14:13:44 | 显示全部楼层
brian1118 发表于 2015-10-3 02:56
map 用來記錄每個x的高度嗎?
ex: drop(1,4) -> map[1] = 4, map[2] = 4, map[3] = 4, map[4] = 4
這樣嗎 ...

应该是 纪录 (1,4)(5, 0)。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 16:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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