谈谈使用过的几款咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

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

Zenefits电面

[复制链接] |试试Instant~ |关注本帖
头像被屏蔽
我的人缘0
qiaoyu314 发表于 2015-6-1 10:31:29 | 显示全部楼层 |阅读模式
提示: 作者被禁止或删除 内容自动屏蔽

上一篇:几家小公司面经
下一篇:Bloomberg onsite
我的人缘0
liyanjia92 发表于 2015-10-27 11:51:31 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
这题怎么做?就是O(N^2)比较吗?
回复 支持 反对

使用道具 举报

我的人缘0
Chasego 发表于 2015-10-27 22:46:20 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
liyanjia92 发表于 2015-10-27 11:51
这题怎么做?就是O(N^2)比较吗?

至少需要排序,根据开始时间和结束时间分别排序
回复 支持 反对

使用道具 举报

我的人缘0
Chasego 发表于 2015-10-27 23:05:33 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
liyanjia92 发表于 2015-10-27 11:51
这题怎么做?就是O(N^2)比较吗?

刚想了一个思路,先按开始时间排好, 如下(每一行是个time interval

1                          8
    2              6
         3    5
                                 9    10

然后对于每一个interval,看它之后的interva(按顺序)l有没有和它冲突, 直到找到一个没有和题冲突或者所有后面的intervals都遍历过。
譬如对于(1, 8),(2,6)和(3,5)都有冲突,因为它们的结束时间都小于或者等于8.
然后接着 (2, 6)用同样的方式找到(3,5)
(3,5) 没有和后面冲突
最后一行(9, 10) 不用管
回复 支持 反对

使用道具 举报

我的人缘0
aiuou 发表于 2015-10-31 12:48:07 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
这道题的做法叫扫描线法,大概由以下几步构成
1. 先声明一个class
class point{
     int time;
     int intervalIndex;
     String attribute;. From 1point 3acres bbs

2. 把每一个interval拆成两个point, start 和 end. 存在一个一维的数组里 point[] points
3. 按照point.time sort 数组
4. 用一条扫描线从左向右扫,同时maintain一个set。 如果扫到的point是start 就把这个start point对应的interval index加入set, 如果扫到的是一个end point就把这个end point对应的interval index 从set中删除。这就使得当你每扫到一个新的start point时,set里的interval都还没有结束,也就是说这个新加入的start point所对应的interval 与目前set中的所有interval overlap。把这些overlap 都加到result里面去。
5.扫描所有点后,返回result. visit 1point3acres for more.

复杂度就是sort的o(nlgn). Waral 博客有更多文章,
回复 支持 反对

使用道具 举报

我的人缘0
jyang_2015 发表于 2015-11-4 14:07:06 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
aiuou 发表于 2015-10-31 12:48
这道题的做法叫扫描线法,大概由以下几步构成
1. 先声明一个class . Waral 博客有更多文章,
class point{
. 一亩-三分-地,独家发布
感觉整体算法还是比较直观的,但求问一下这里的time和 attribute具体指什么呢?
回复 支持 反对

使用道具 举报

我的人缘0
jyang_2015 发表于 2015-11-4 14:41:47 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
jyang_2015 发表于 2015-11-4 14:07. 1point 3acres 论坛
感觉整体算法还是比较直观的,但求问一下这里的time和 attribute具体指什么呢?

哦 我懂了,这里time其实就可以用position,然后attribute 我们可以其实存一个指针用来link start point 和 end point。这样你从set中删除end point对应的interval index时(i.e. start point) 就可以O(1) time了。. 1point 3acres 论坛

但这种方法有个要注意的问题就是边界点怎么办? 比如[1,2]和[2,4] 算conflict么?如果算的话,sort的时候除了要根据当前点的position,还要看对应的同一个interval的另一个端点的postiion哈
回复 支持 反对

使用道具 举报

我的人缘0
Chasego 发表于 2015-11-9 01:55:19 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
aiuou 发表于 2015-10-31 12:48
这道题的做法叫扫描线法,大概由以下几步构成
1. 先声明一个class
class point{
. 1point 3acres 论坛
你的方法和我描述应该一样?虽然我不用额外的数据结构

补充内容 (2015-11-9 02:17):
主要考虑到你每次把冲突部分加进去的时候,所用的时间还是和加入的冲突的个数成正比(即使你用了set)。换句话说,除了排序的方法,你的方法和我一样,找conflict pair 的时间和conflict 的pair的个数成正比?
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
misshary 发表于 2016-2-12 20:22:20 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
求题目细节,貌似lz被屏蔽了~~~~
回复 支持 反对

使用道具 举报

我的人缘0
freetrek 发表于 2016-2-29 13:56:39 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
“Skype电面,美国人。 题目:给定很多time interval,找到所有有conflict的pair。 数据结构,输入输出都是自己设计。” @misshary
回复 支持 反对

使用道具 举报

我的人缘0
misshary 发表于 2016-3-23 20:54:35 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
freetrek 发表于 2016-2-29 13:56. from: 1point3acres
“Skype电面,美国人。 题目:给定很多time interval,找到所有有conflict的pair。 数据结构,输入输出都是 ...

谢谢哈~字数字数
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

custom counter

GMT+8, 2018-6-23 16:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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