一亩三分地论坛

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

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

FB电面 9/15

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

2016(7-9月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Pass在职跳槽

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

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

x
很简单的两题1. LC91 Decode Ways. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
2. Find subsequence in an array which sums up to given target. 1point 3acres 璁哄潧

秒过 求onsite 求大米

评分

4

查看全部评分

uranus23 发表于 2016-9-16 08:04:43 | 显示全部楼层
第二题要求连续吗?subsequence按定义是可以不连续的吧
回复 支持 反对

使用道具 举报

 楼主| ilovexiao77 发表于 2016-9-16 10:46:17 | 显示全部楼层
uranus23 发表于 2016-9-16 08:04
第二题要求连续吗?subsequence按定义是可以不连续的吧
.鏈枃鍘熷垱鑷1point3acres璁哄潧
是需要连续的
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-9-16 11:38:51 | 显示全部楼层
第一题直接dp还是多种方法?
回复 支持 反对

使用道具 举报

1451427216 发表于 2016-9-16 11:44:20 | 显示全部楼层
楼主内推多久拿到了面试啊?
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-9-16 11:55:14 | 显示全部楼层
第二题有说非负数吗?这两题感觉一会儿就做完了?那剩下时间全部闲聊吗?
回复 支持 反对

使用道具 举报

 楼主| ilovexiao77 发表于 2016-9-16 14:35:58 | 显示全部楼层
houqingniao 发表于 2016-9-16 11:38
第一题直接dp还是多种方法?
-google 1point3acres
直接DP,没要求多种解法。。。顺便问下其他的解法是递归吗?
回复 支持 反对

使用道具 举报

 楼主| ilovexiao77 发表于 2016-9-16 14:36:53 | 显示全部楼层
1451427216 发表于 2016-9-16 11:44
楼主内推多久拿到了面试啊?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
很快,内推之后大概一周就和recruiter电话了,但是安排电面比较慢
回复 支持 反对

使用道具 举报

 楼主| ilovexiao77 发表于 2016-9-16 14:40:47 | 显示全部楼层
iPhD 发表于 2016-9-16 11:55
第二题有说非负数吗?这两题感觉一会儿就做完了?那剩下时间全部闲聊吗?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第二题我用hashmap做的。没说非负数。后来想了下,这题是不是还有那种双指针滑动窗口的那种做法?有负数的情况下是不是双指针的那种方法就失效了?
其实做题过程中和面试官一直交流,最后没剩下什么时间,简单问了俩问题就结束了。
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-9-16 21:22:10 | 显示全部楼层
ilovexiao77 发表于 2016-9-16 14:40
第二题我用hashmap做的。没说非负数。后来想了下,这题是不是还有那种双指针滑动窗口的那种做法?有负数 ...

对,如果只有非负数,可以用LC 209 Minimum Size Subarray Sum的双指针方法做,空间是O(1).
回复 支持 反对

使用道具 举报

 楼主| ilovexiao77 发表于 2016-9-17 03:48:10 | 显示全部楼层
iPhD 发表于 2016-9-16 21:22. visit 1point3acres.com for more.
对,如果只有非负数,可以用LC 209 Minimum Size Subarray Sum的双指针方法做,空间是O(1).
. visit 1point3acres.com for more.
恩~ 多谢指教~
回复 支持 反对

使用道具 举报

meanderer 发表于 2016-9-23 10:27:36 | 显示全部楼层
ilovexiao77 发表于 2016-9-16 14:40
第二题我用hashmap做的。没说非负数。后来想了下,这题是不是还有那种双指针滑动窗口的那种做法?有负数 ...

能不能讲下 hashmap 做的思路?thanks!
回复 支持 反对

使用道具 举报

DreamBoy 发表于 2016-9-23 12:26:55 | 显示全部楼层
如果第一题没有非负数条件怎么做呢。。brute force不算
回复 支持 反对

使用道具 举报

DreamBoy 发表于 2016-9-23 12:27:14 | 显示全部楼层
iPhD 发表于 2016-9-16 21:22
对,如果只有非负数,可以用LC 209 Minimum Size Subarray Sum的双指针方法做,空间是O(1).

如果没有非负数限制呢
回复 支持 反对

使用道具 举报

meanderer 发表于 2016-9-24 03:51:51 | 显示全部楼层
DreamBoy 发表于 2016-9-23 12:27. 1point 3acres 璁哄潧
如果没有非负数限制呢

看了下没有非负数的做法,基本想法是如果有这么一个区间 a[i..j] 的和是 target,那么 s[j] - s[i-1] == target,其中 s[k] = a[0] + a[1] + ... + a[k]. 于是可以顺序计算 s[j]: s[0], s[1], ..., s[n-1], 并用一个 hashmap 记录之前遇到的 s 的值,这样就可以随时查找 s[i-1] = s[j] - target 是否已经在这个 hashmap 中了:

  1. s[0] = a[0]. visit 1point3acres.com for more.
  2. map[s[0]] = 0 // s[i] => i
  3. for j = 1 to n-1:
  4.     s[j] = s[j-1] + a[j]
  5.     map[s[j]] = j
  6.     if map has key (s[j] - target)
  7.         i = map[s[j]-target]+1
  8.         find_solution(a[i..j])
复制代码
回复 支持 反对

使用道具 举报

hanabeast 发表于 2016-9-25 07:39:41 | 显示全部楼层
meanderer 发表于 2016-9-24 03:51
看了下没有非负数的做法,基本想法是如果有这么一个区间 a 的和是 target,那么 s[j] - s == target,其 ...

这种方法是可以返回所有的满足解
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-9-28 04:38:24 | 显示全部楼层
iPhD 发表于 2016-9-16 21:22. from: 1point3acres.com/bbs
对,如果只有非负数,可以用LC 209 Minimum Size Subarray Sum的双指针方法做,空间是O(1).

是不是负数都无所谓吧,如果求SUM再用HASHMAP
回复 支持 反对

使用道具 举报

 楼主| ilovexiao77 发表于 2016-9-28 09:07:41 | 显示全部楼层
liurudahai 发表于 2016-9-28 04:38. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
是不是负数都无所谓吧,如果求SUM再用HASHMAP

对的,如果用hashmap做,无所谓有没有负数
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 06:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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