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


一亩三分地论坛

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

[找工就业] Refdash 面经

[复制链接] |试试Instant~ |关注本帖
kafkagre 发表于 2017-8-4 08:13:45 | 显示全部楼层 |阅读模式

2017(10-12月)-[15]CS硕士+fresh grad 无实习/全职 - 网上海投|BayArea 码农类全职@Refdashfresh grad应届毕业生

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

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

x
45min,感觉两个都是easy的题 。.1point3acres缃
1. 给一个数组,返回最大元素的index。 特别说明,如果最大值有多个,随机地返回其中一个index。要求: Space O(1) Time: O(N). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
做出来了 two passes, O(N)算法应该有one pass的算法。
2.选手跟AI做一个游戏。 给一个正整数(currentstate)。每次只可以减去perfect square数(1,4,9,....),而且结果不能是负数。如果最后ai 不能继续减了,就算你赢了,反之AI赢。函数API如下,int optimalmove(int currentstate),返回当前状态下应该减去多少才是最优的。假设AI总会作出最优的选择。
DP做的。


补充内容 (2017-8-9 04:42):
1. LC398的简化。
brn 发表于 2017-8-4 10:01:59 | 显示全部楼层
one pass 的算法应该就是在遍历数组时同时维护max并且进行reservoir sampling
回复 支持 1 反对 0

使用道具 举报

FightForTomo 发表于 2017-8-4 08:24:59 | 显示全部楼层
这个小哥态度挺好的。就是后面给联系面试的事落实不了。
回复 支持 反对

使用道具 举报

熟狗脸 发表于 2017-8-4 09:37:06 | 显示全部楼层
我也考过他们这个,第一轮是一个candy那个题,是hard level的。评分 3.2给我,然后第二轮面OOD/system design, 3.0 给我评分。之后就是让我选哪些公司想去onsite,目前还没回复他们,看到都是一些小公司。好像有nyc的2sigma,不过我不想去纽约
回复 支持 反对

使用道具 举报

 楼主| kafkagre 发表于 2017-8-4 12:33:51 | 显示全部楼层
熟狗脸 发表于 2017-8-4 09:37
我也考过他们这个,第一轮是一个candy那个题,是hard level的。评分 3.2给我,然后第二轮面OOD/system desi ...

我今天面了第一轮,评分3.0. 方便透露一下第二轮面试什么题目吗?
回复 支持 反对

使用道具 举报

 楼主| kafkagre 发表于 2017-8-4 12:35:14 | 显示全部楼层
brn 发表于 2017-8-4 10:01
one pass 的算法应该就是在遍历数组时同时维护max并且进行reservoir sampling

那我去看一下reservoir 算法. 好像跟LC398有点像。
回复 支持 反对

使用道具 举报

 楼主| kafkagre 发表于 2017-8-4 12:36:29 | 显示全部楼层
熟狗脸 发表于 2017-8-4 09:37. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我也考过他们这个,第一轮是一个candy那个题,是hard level的。评分 3.2给我,然后第二轮面OOD/system desi ...

Candy是指LC135 还是LC575?
回复 支持 反对

使用道具 举报

FightForTomo 发表于 2017-8-4 17:37:25 | 显示全部楼层
我第二轮是这两道题,得了3.1

Longest Palindromic Substrig
Find the longest palindromic substring.

Dead end leaf
Given a Binary Search Tree that contains positive integers, return the length of the longest path from root to a leaf such that the leaf is a dead end. A leaf is considered a dead end if and only if we are not able to insert any element after that node.
. 鍥磋鎴戜滑@1point 3 acres
第一题好像是原题,第二题我都不咋会。写了个宽搜。然后就也算有点代码放在那了。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
回复 支持 反对

使用道具 举报

 楼主| kafkagre 发表于 2017-8-5 08:06:54 | 显示全部楼层
FightForTomo 发表于 2017-8-4 17:37
我第二轮是这两道题,得了3.1

Longest Palindromic Substrig

dead end leaf 的意思是这个BST不能有duplicate的node是吧?
回复 支持 反对

使用道具 举报

eiei39 发表于 2017-8-6 19:19:46 来自手机 | 显示全部楼层
第一题返回最大值的index,第一遍找最大值,第二遍如果从保存了所有最大值的index中随机返回一个,那space也是o(n)。请教2 pass的思路。
回复 支持 反对

使用道具 举报

eiei39 发表于 2017-8-6 21:05:03 | 显示全部楼层
eiei39 发表于 2017-8-6 19:19
第一题返回最大值的index,第一遍找最大值,第二遍如果从保存了所有最大值的index中随机返回一个,那space ...

查到了这个问题。
one pass 和 two passes 都给了方法:
https://stackoverflow.com/questi ... ability-of-1-number
回复 支持 反对

使用道具 举报

FightForTomo 发表于 2017-8-7 14:07:37 | 显示全部楼层
kafkagre 发表于 2017-8-5 08:06
dead end leaf 的意思是这个BST不能有duplicate的node是吧?

就是返回不能继续添加子节点的叶子节点。
比如说
           4.鏈枃鍘熷垱鑷1point3acres璁哄潧
       2        5
          3
这个3就是一个dead leaf..
回复 支持 反对

使用道具 举报

 楼主| kafkagre 发表于 2017-8-9 04:46:02 | 显示全部楼层
eiei39 发表于 2017-8-6 19:19
第一题返回最大值的index,第一遍找最大值,第二遍如果从保存了所有最大值的index中随机返回一个,那space ...

one pass: 用 Reservoir sampling LC398的简化。
Two pass:
第一遍统计最大值的个数。记做Counts 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
int ithMax = rand(1,Counts)//生成1~Counts的随机数
第二遍:找到ithMax个最大值,返回index.鐣欏璁哄潧-涓浜-涓夊垎鍦
回复 支持 反对

使用道具 举报

gegeyongfu 发表于 2017-9-7 04:35:00 | 显示全部楼层
能问下面试官名字嘛
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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