查看: 6337|回复: 3
收起左侧

Affirm 跪经

|只看干货
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   91% (299)
 
 
8% (29)    👎

2017(1-3月) 码农类General 硕士 实习@Affirm - 内推 - 技术电面  | Fail | 应届毕业生

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
地理好心人帮忙内推的。亚裔小哥, 一上来聊了一会,然后开始做题,codepair上面。一打开就有个结构写着。
class PStack {

int size() {};
PStack push(int x) {}
PStack pop() {}

}
小哥说你来design 一个persistent stack, push,pop 的时候都得返回一个这个数据PStack. 比如: 现在有s1 = 1,2,3,4, 这个时候call push(5), 应该返回一个新的PStack s2 = 1,2,3,4,5, 而
现有的Stack里面的元素不变。同理如果这个时候call pop(), 应该返回一个新的s3 = 1,2,3,4, 之前的不变。 我就迅速写了个Stack的实现方式,弄个temp Stack 来倒腾元素,然后返回新的
Stack,秒了之后。小哥问这个复杂度是多少,我说O(n),因为你得每次返回一个新的Stack,然后还得装那么多元素啊。然后他说能不能优化到O(1), 想了会,没搞清楚怎么弄。然后他提示说
用shared data structure, 比如用个arrayList, 然后我就写了写,挪一挪指针啥的,返回新的PStack的时候传入指针。然后发现一个bug, 如果你反复push, pop, 还要保留
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
ent stack是个什么玩意了,真心搞不懂为什么出题要这么绕弯子,根本没想到最终是用一个树来实现所谓的Stack. 写完了口头run了一下。然后他说对的,时间就到了。
然后昨天收到消息说跪了。果然这种公司不好进。能进这种牛逼公司的都是真正的牛人。
发面经攒人品,这周三个面试,希望能有个好结果。

评分

参与人数 1大米 +1 收起 理由
hanxiaobow + 1 给你点个赞!

查看全部评分


上一篇:Amazon phone interview
下一篇:pocket gem实习一面面经
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (3)
 
 
0% (0)    👎
这题为什么不能对原stack做操作后,直接返回this。。。

补充内容 (2017-2-28 14:17):
懂了,看漏条件了
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   75% (77)
 
 
24% (25)    👎
还是没明白他说的“persistent stack ”啥意思 如果用tempStack 相当于每次返回一个新的存储stack所以空间是O(n), 如果要是O(1)的话那就是用tree做,返回最底层leave node的指针,从leave node一路往上找parent,所以是O(1)?  那和"persistent"这个词有啥关系。。?  求解
回复

使用道具 举报

 楼主| adrianliu729 2017-3-19 04:13:17 | 显示全部楼层 | 🔍试试Job多多
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   91% (299)
 
 
8% (29)    👎
haveto 发表于 2017-3-19 04:10
还是没明白他说的“persistent stack ”啥意思 如果用tempStack 相当于每次返回一个新的存储stack所以空间 ...

这是funcional programming 里面的概念吧。http://www.geeksforgeeks.org/persistent-data-structures/ 你看了这篇文章应该就知道persistent的意义了。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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