工业界资深数据科学家教你破解各大公司面试
FLAG等各大公司数科面试真题讲解

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
有你有策略
微策略(MicroStrategy)
2019校园招聘火热进行中
E轮2.5亿美元融资
K12教育独角兽一起作业诚聘
机器学习/数据统计/教育等职位
码农求职神器Triplebyte:
不用海投
内推多家公司面试
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 4963|回复: 61
收起左侧

[算法题] new grad 刷刷刷题怎么刷(真正的菜鸡变正常人)

    [复制链接] |试试Instant~
我的人缘0
sarahzjn 发表于 2018-9-6 07:29:25 | 显示全部楼层 |阅读模式
该内容以做模糊处理,您需要登录后才可查看. 登录 | Sign Up 注册获取更多干货

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

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

x
楼主刷了差不多也有700了。刷了可能也有9个月。自己还是有很多心得,也一直想给大家讲讲作为一个菜鸡该如何切入去理解“problem sovling ”这个事。

楼主说自己菜鸡那就真的是菜,不吹不黑的菜。。。不像有些人说啊binary index tree我都不懂怎么办啊我好菜啊。最菜的时候去年12月的时候写个tree的bfs都是有背的成分在里面,有声读物让我写一个heap直接崩崩崩崩。。。。。。。但是现在contest一般能3题。做的快也有个100多,偶尔4题进一下前100。感慨还是比较多,也上了好几个培训。也一直想和大家分享一下心得。下面就来讲讲我认为的problem solving面试的考察点。后面再讲讲如何提高和每个topic下的要注意的地方。

0.面试的过程,遇到不会做的题,没见过的题怎么办?
    0.1.拿到一个问题,怎么去分析呢? 首先这个就卡住了很多朋友,我认为最好的办法是你多画图,多举例子,在此期间不断地和面试官沟通,看看能不能cover尽可能多的case。这个实际上就是考察你作为一个人的角度去如何理解问题。有些时候就会有个大概的思路。所以第一步是找规律。
例如我fb电面被考到的题目,int to english(做题网站273)。粗略的看内心简直无比xxxx。但是你如果多举几个例子, 例如 123->"One Hundred Twenty Three" , 12345 -> "Twelve Thousand ////// Three Hundred Forty Five" 我相信大家如果平心静气的分析的话,而不是被那个hard的tag吓到,思路是有的,规律也是能看出来的。(三个三个的处理)

   0.2 这个阶段大家还不要急着去写。很多朋友有时候会遇到一个情况,我擦这是原题啊,例如说完思路就动笔就写(做题网站的最高票解)。然后pilipala然后的就挂了。这个时候大家该做的是去分析,尝试提出不同的解法,as mush as possilbe,并且尽可能的通过举例子想清楚细节问题
         这个部分我想举例子做题网站的359。这个是uber家的超级电面高频题,tag 是个easy。(题目大意自己去看吧)很多人的做法应该就是那个hashmap的高票解,但是这样做同时带来一个问题,如果有些数据很久没用呢?例如用了一次就再也没理,我们有没有办法节省空间呢?这个时候第二高票的解提出了一个用优先队列解决的办法。有人用了这个答案又挂了(看面经看到的)。大家有没有想过在这个问题里时间是线性增长的,是不是本来这些time stamp就是有序的呢?这个时候优先队列真的有必要嘛?队列是不是就够了呢?
         还有做题网站的第一题 2sum。很多人上来就写一个hashmap的,这个时候为何不问问面试官如果他在意时间就hashmap,如果在意空间为啥不试试排序的那个做法?如果你的input不能改变的话排序是不是又不行了?
         大家看到原题千万别急着下手,有时候就跪在你最熟悉的地方。如果你能在这一步分析清楚最优的时间复杂度是多少,大大加分。实际上就是想明白worst case在哪里。

   0.3 这个时候就进入第三个阶段,看出来了规律,做好了细致的分析,并且做假设。。这个我来说说大家要注意的地方。实际上这个时候大家更应该做的是耐心的提出所有的假设。例如还是那个int to english吧。大家该提出的就应该包括:(有没有非法输入, 例如数的范围是多少,有没有小数,有正数嘛,有负数嘛, 0怎么办)。做足了假设,才能保证你的代码在你的假设下是bug free的没有真正bug free的代码,你只能保证代码在你的假设下是对的。

0.4 到这一步终于可以到实现了,这一块每个人的习惯各不相同,我认为比较好的做法的是列出所有的method submethod的  输入输出函数名(signature)。并且粗略的讲一下你的代码的结构。例如还是那个int to english吧。处理3位3位的明显就可以单独抽出一个逻辑对不对,那主函数的逻辑就是处理3个3个的输入了。这个时候大家心里就有谱,也不会慌。

   0.5 写完代码后自己一定要做proofreading啊。看看代码有没有啥错误,手误啥的。。。。。然后才是大家都知道的提出test case的阶段。并且run test case。
   切记一定要抱着解决问题的态度去交流(就是接受很多dirty work,我看大家有时候很痛恨做题网站的valid number,简直无数个反对,我恰恰认为这是很好的problem solving的题。。。),而不是做题。

1.讲完了面试过程,讲讲如何准备和提高
我认为大家有个误区就是基础不大好的时候就直接去刚leetcode。。。。还有说法做了300题好几遍就好很多云云。我亲测这样只能让我熟练的背300多题的答案。。我同学背了400多题,依然算法很苦逼。有段时间我写bfs都魔怔了,一定要在pop queue加个size变量,让bfs有个分层打印的效果(可能有人看不懂,反正就是不对233).
     所以我认为最好的办法是先好好去上个课,公开课这么多,并且练习练习很多经典的模型和他们的变形,根深才能站的稳。leetcode我刷了700多个题,实际上出去sql差不多刷完了,我自己深切的感觉就是LeetCode只是一个面经集合。用来辅助面试的可以的,切不可用来当做学习的材料。
那什么是学习的材料和正确的方法呢?
     我觉得首先大家先自己动手实现实现各种数据结构,例如heap, hashmap, binary search tree等等。 自己去写写经典的算法,最朴素的版本,就例如binary search,leetcode大部分binary search题都是他的变型,并没有多少经典的binary search。
      然后刷题的话我推荐初学者试试Lintcode,上面有很多很朴素的版本的题,例如背包问题,例如经典二分法,例如排序等等等等。
      然后做做我们的面经网站。重视一题多解(例如那个359 rate limiter),重点分类归纳提高。

2. 最后分类讲下我认为的每个topic下的细节吧
我一直认为搞清楚算法的过程就是一个扣清楚细节和不断熟悉的过程,有人曾经和我说binary serach写个大概就行了,白板看不清等等等等,实际上你不是大于等于 >= 只是一个大于>都可能造成死循环。所以我就想单独说说每个topic的细节问题。
      2.1 指针问题,这种题一般代表有move zero,让你手写个归并排序等等,指针一般有including和excluding两种,例如有时候指针自己指的不是答案,指针的左侧才是我们需要的答案。
      2.2 binary search。这个一定要记住他的核心思想只是减少我的搜索范围。。。。而不是只有在排序数组的情况下我们才能用binary search。有时候你知道答案的上下界也可以用binary search。写的时候要注意避免死循环(大于等于, left = mid 还是 mid + 1)。建议熟悉经典后再去做。
      2.3. queue和stack的问题。queue一般规律性比较明显,重点是stack, stack很多时候能维护很多已经遍历过的数据,并且栈顶都有一些性质。例如字符串的压缩问题等等。并且大家把递归转成迭代的时候多想想函数进系统栈的顺序。
      2.4. linkedlist:这个一般的考察就是递归。。。一定要画清楚图。分析清楚,别写出NPE就不好看了。
      2.5 这个是linkedlist的高级版本,考察点仍然是递归。搞清楚post order尤其重要,很多题的最优解都是他得来的。(这也是递归的定义,先解决小问题再看大问题)。
      2.6 DFS问题,这个部分写代码一般不难,但是难的是画清楚你的递归树和分析清楚时间复杂度(递归树的深度和branch factor)。这个也是很多题的暴力解法,给不出好解法的时候先写个dfs也无妨,再转成DP。
      2.7 BFS问题。分为用队列还是优先队列,一般可以解决分层问题和最短路径。
      2.8 堆,hashMap,set等等数据结构的运用,根据我的经验这种题一般都会加个follow up,问他们的底层实现,所以这个时候基础就格外重要了,
      2.9 字符串问题,这个分类实在有点杂糅。。。这里就不展开讨论了。
      2.10 递归和动态规划。 这个很多时候一眼是很难看出来的,所以我个人的建议是很多时候先写个递归的版本的。大问题转成小问题。再画递归树,看看哪些部分重复计算了,加个cache。这样的画叫做memorized,一般也就OK了,和dp本质一样。如果遇到严格的面试官,再根据之前的代码写dp吧,就会好很多。
     2.11 高级数据结构 Trie,这个实际上现在考的很多...不只是谷歌,而且很多普通题也会这样做,例如做题网站的word break2,很多公司会要求写trie版本的。。。。(TA, google,fb啥的)。
     2.12 图搜索问题: 如果你要面谷歌这个是大头,图分类比较杂,联通不联通,有向无向,有环无环,有权重无权重。遍历可能都不一样。。。这里也很难展开讨论。然后有时候公司也会考察写图的排序问题(拓扑排序)。
     2.13 数学问题: 这个一般我发现也就微软爱考。。考到咋办我也不知道233
     2.14 位运算: 这个一般不会直接考,但是是优化的重要思路之一,希望大家掌握好最基本的。
     2.15 随机抽样问题: 除了蓄水池抽样其他的也要看看啊,发现有些朋友用蓄水池用的都魔怔了,一说抽样就是蓄水池。 例如pemutation和shuffle实际上都是个抽样问题。。。。(全排序就是每次选一个字符,shuffle同理)。
     2.16 啥线段树, binary index tree我觉得前15个topic没明白的话,就不要去看了。
     先写到这里吧,还有啥可以补充的我再想想,祝大家刷题愉快,也可以私信我交流~

评分

参与人数 65大米 +437 收起 理由
donnice + 10 很有用的信息!
biomedicineman + 10 给你点个赞!
hlckl123456 + 5 给你点个赞!
bdfxwyf + 5 很有用的信息!
ywcctc + 3 很有用的信息!
MarsZns + 3 很有用的信息!
cong1995 + 1 给你点个赞!
azureclouds + 5 很有用的信息!
cat110 + 5 很有用的信息!
Hannah_sy + 5 很有用的信息!
xuca9220 + 5 给你点个赞!
elsawake + 3 很有用的信息!
robinleizeling + 5 给你点个赞!
YAAOOO + 3 给你点个赞!
markpen + 5 很有用的信息!

查看全部评分


上一篇:Leetcode Premium Subscription 转让
下一篇:拉群互相监督刷题 最好是JAVA

本帖被以下淘专辑推荐:

  • · CS|主题: 227, 订阅: 14
  • · 2018招聘|主题: 146, 订阅: 14
我的人缘0
hzyfree 发表于 2018-9-6 14:37:27 | 显示全部楼层
本楼: 【顶】   100% (7)
 
 
0% (0)   【踩】
全局: 顶  94% (67)
 
 
5% (4)  踩
我觉得LeetCode是挺好的学习材料啊,看discuss和solution能学到很多东西
回复

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
pkk5488 发表于 2018-9-11 08:55:02 | 显示全部楼层
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  89% (279)
 
 
10% (32)  踩
楼主讲得很好,我最近也大概领悟了一点点心得。抛砖引玉说一下,我觉得题目分为problem solving和solid coding两个部分。solid coding就是考察你的基本功和数据结构,比较straightforward相当于给出你interface,如何写一个二分法,写一个dfs,bfs,写一个recursion。用什么数据结构优化,比如栈,队列,优先队列,哈希表。如何写代码最优,想要稳过面试而不是背题,solid coding是一定要过关的,要深入理解为什么这样写,为什么有的dfs不需要return有的return,二分法边界到底如何处理。大部分medium的题目都是考察solid coding。而hard题更考察problem solving和交流,考察你拿到题目如何抽象,分解成一个个小问题,再用solid coding去解决。最近刷Google的题目,感觉没有一道题是直来直往的,都挺绕。。绕完了要找出问题再解决。problem solving的能力需要慢慢培养,但是solid coding大部分人还是可以做得更好的。向楼主学习。
回复

使用道具 举报

我的人缘2
rexue70 发表于 2018-9-7 02:09:11 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  65% (763)
 
 
34% (404)  踩
加分拉满。我看到写的最好的算法总结。
回复

使用道具 举报

我的人缘0
talentednew 发表于 2018-9-6 08:42:39 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
100% (1)   【踩】
全局: 顶  96% (52)
 
 
3% (2)  踩
顶兄弟一波

评分

参与人数 2大米 +13 收起 理由
Vvvvickyyyy + 3 给你点个赞!
sarahzjn + 10 给你点个赞!

查看全部评分

回复

使用道具 举报

我的人缘0
ddwysg1 发表于 2018-9-6 07:40:10 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (16)
 
 
15% (3)  踩
感谢楼主分享刷题经验~正在边刷题边找intern的人深有感触啊,如果没有把基本的算法了解清楚,光是背题,理解不够的话,确实就很不牢固,面试时候就容易慌,代码速度较平时也会慢很多。希望自己能够克服问题取得进步~
回复

使用道具 举报

我的人缘0
wystefan 发表于 2018-9-6 07:40:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (15)
 
 
6% (1)  踩
写的真的很好!赞一个!正在苦逼刷题中,楼主很多意见真的是刷了很久得出的经验啊,很多地方我也深有体会。加油加油!
回复

使用道具 举报

我的人缘0
熊猫杀很大缺积分 发表于 2018-9-6 07:46:03 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (109)
 
 
6% (7)  踩
萌妹子你好
回复

使用道具 举报

我的人缘0
wangdi561 发表于 2018-9-6 07:47:48 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (343)
 
 
4% (17)  踩
帮顶一下,师弟线下分享会给我们带来很多不错的经验。

评分

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

查看全部评分

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.


回复

使用道具 举报

我的人缘0
wangdi561 发表于 2018-9-6 07:48:15 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (343)
 
 
4% (17)  踩

熊猫你好~~~~~~
回复

使用道具 举报

我的人缘2
励志成为学霸的小学渣 发表于 2018-9-6 07:52:38 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (69)
 
 
1% (1)  踩
前辈写的超级棒!希望自己早日从菜鸡变成战斗机hhh
回复

使用道具 举报

我的人缘0
熊猫杀很大缺积分 发表于 2018-9-6 07:54:09 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (109)
 
 
6% (7)  踩

我已经,, 刷不动了
回复

使用道具 举报

我的人缘0
wangdi561 发表于 2018-9-6 07:59:58 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (343)
 
 
4% (17)  踩

我们H1选手还要奋战到明年2月呢......
回复

使用道具 举报

我的人缘0
熊猫杀很大缺积分 发表于 2018-9-6 08:01:35 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (109)
 
 
6% (7)  踩
wangdi561 发表于 2018-9-6 07:59
我们H1选手还要奋战到明年2月呢......

= = 这么一说还是我比较轻松
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-11-13 01:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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