一亩三分地

 找回密码 注册账号

扫描二维码登录本站


Salarytics=Salary Analytics
查询工资数据
系统自动计算每年收入

码农求职神器Triplebyte
不用海投
内推多家公司面试

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250

深入浅出AB Test
从入门到精通
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 575|回复: 1
收起左侧

[其他] 前谷歌员工深度解剖面试题:骑士拨号和搜索词同义

[复制链接] |试试Instant~
我的人缘0

分享帖子到朋友圈
liux0656 | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (464)
 
 
0% (4)    👎

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

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

x
hackermoon上经常有一些算法面试题总结和解析,这次介绍一位小哥哥,2012年毕业哥伦比亚大学的计算机科学工程系双学位课程。进入Google纽约,Adwords算法优化到核心业务逻辑。除了工作之外也做了面试的志愿工作,下面就是他深度剖析2道面试题



面试题1:骑士拨号


                               
登录/注册后可看大图


你将骑士放在电话拨号盘上。骑士按照大写“L”的形状移动:水平两步,然后是垂直一步,或者水平一步,然后垂直两步

这是我在面试过程中遇到的第一个问题,也是第一个泄密并被禁止的问题。我喜欢它,因为它有很多优点

  • 很容易陈述和理解。
  • 有许多解决方案,每个解决方案都需要不同程度的算法和数据结构知识
  • 每个解决方案都可以在相对较少的行中实现,时空转化的理想选择。


作者提到用Python编写代码。因为它易于学习,紧凑,并且具有绝对庞大的标准库。即使没有语言限制,我面试的人中有90%使用Python。具体分析如下

系列1:https://hackernoon.com/google-in ... dialer-f780d516f029
系列2:https://hackernoon.com/google-in ... dition-c288da1685b8

涵盖的技能和你应该开发的习惯:

  • 始终首先手动解决问题的一个小实例。在这个问题中递归关系和函数重复调用很明显。
  • 注意解决方案中你不需要的计算,比如计数解决方案如何生成序列但实际上并没有使用它们。减少不必要的计算通常可以提供更简单的解决方案,如果不打开更高效的解决方案的大门。
  • 知道递归。它在大多数生产代码中几乎没用,因为它在堆栈中溢出,但它是一种非常强大的算法设计策略。递归解决方案通常可以进行调整和改进:知道指数解和线性时间最优解的差异。
  • 了解你的Big O分析!在面试过程中,几乎肯定会问这个问题。
  • 努力寻找memoization的机会。如果函数是确定性的,并且将使用相同的输入多次调用它,那么解决方案可能会受益于memoization。
  • 查找并写出递归关系。N跳的计数仅取决于N-1跳的计数。


问题2:https://medium.com/@alexgolec/go ... ueries-36425145387c

想象一个受欢迎的搜索引擎,在你的日志中你会看到两个问题,比如说“奥巴马支持率”和“奥巴马普及率”这两个查询是不同的字符串,虽然这两个搜索字符串不一样,但基本上是在搜同一个东西,在计算查询,显示结果等时应该被认为是等价的。我们如何检测到两个查询是同义词?

假设你有两个输入。1 表示同义词的字符串对的列表,其中对中的两个字符串彼此同义,2 表示查询的字符串对列表。
为了使这个具体,这里有一个示例输入来说明:


[Bash shell] 纯文本查看 复制代码
SYNONYMS = [
 ('rate', 'ratings'),
 ('approval', 'popularity'),
]
 
QUERIES = [
 ('obama approval rate', 'obama popularity ratings'),
 ('obama approval rates', 'obama popularity ratings'),
 ('obama approval rate', 'popularity ratings obama')
]


任务是输出布尔值列表,每个条目指示相应的查询对是否是同义的。

想清问题

从表面上看,这是一个很简单的问题。但是,越是细想,它就越复杂。首先,这个问题的定义不是很明确。单词可以有多个同义词吗?单词的顺序重要吗?同义词之间是否具有传递性,例如,如果 A 与 B 同义,B 与 C 同义,那么 A 是否也与 C 同义?同义词可以跨多个单词吗,例如“USA”与“United States of America”同义,还是与“United States”同义?

这种模棱两可给了优秀候选人一个脱颖而出的机会。好的候选人会先找出这些含糊不清的地方,并试图解决它们。他们的做法因人而异:有些人会走到白板前,试图手动解决一些特定的情况,而另一些人一看到问题,就会立即发现其中的“陷阱”。无论如何,关键的是要尽早发现这些问题。


                               
登录/注册后可看大图



我非常看重这个“理解问题”阶段。我喜欢将软件工程称为分形学科,这意味着它与分形具有相同的特性,通过放大问题来显示额外的复杂性。当你认为你理解了一个问题,仔细一看,就会发现其实忽略了一些细微之处,或者一些可以改进的实现细节,或者有其他新的方法可以用来分析这个问题并揭示出额外的见解。

工程师的能力在很大程度上取决于他们对问题理解的深度。将一个模糊的问题陈述转化为一组详细的需求是这个过程的第零步,像这样故意向候选人提出不明确问题的做法可以帮助面试官评估候选人应对意外情况的能力。

具体代码见链接

https://medium.com/@alexgolec/go ... ueries-36425145387c


评分

参与人数 5大米 +9 收起 理由
石头OAPG + 1 很有用的信息!
gu4p + 1 给你点个赞!
starzero + 2 给你点个赞!
从前有座山 + 2 很有用的信息!
14417335 + 3

查看全部评分


上一篇:FB DFS+UF 打卡,第五遍
下一篇:关于语言和new grad求职的问题:Java和Python
我的人缘0
gu4p 2019-8-22 04:34:23 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (11)
 
 
0% (0)    👎
很好的论题. 多谢楼主分享.
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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

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

手机版||一亩三分地

GMT+8, 2019-9-19 06:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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