传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 3594|回复: 20
收起左侧

FB电面 9/15

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

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

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

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

x
很简单的两题1. LC91 Decode Ways
2. Find subsequence in an array which sums up to given target
. visit 1point3acres.com for more. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
秒过 求onsite 求大米

评分

5

查看全部评分

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

使用道具 举报

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

使用道具 举报

 楼主| ilovexiao77 发表于 2016-9-16 10:46:17 | 显示全部楼层
uranus23 发表于 2016-9-16 08:04. From 1point 3acres bbs
第二题要求连续吗?subsequence按定义是可以不连续的吧

是需要连续的
回复 支持 反对

使用道具 举报

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还是多种方法?

直接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
对,如果只有非负数,可以用LC 209 Minimum Size Subarray Sum的双指针方法做,空间是O(1).

恩~ 多谢指教~
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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
如果没有非负数限制呢

看了下没有非负数的做法,基本想法是如果有这么一个区间 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]
  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
对,如果只有非负数,可以用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做,无所谓有没有负数
回复 支持 反对

使用道具 举报

sugar 发表于 2017-9-8 11:02:41 | 显示全部楼层
ilovexiao77 发表于 2016-9-28 09:07
对的,如果用hashmap做,无所谓有没有负数

楼主你好,第二题返回什么呢?boolean还是一个解还是所有解
回复 支持 反对

使用道具 举报

shawnzhao 发表于 7 天前 | 显示全部楼层
第二题如果是连续的subsequence的话应该是类似lc325吧
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-22 02:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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