【生活质量系列】评测几款用过的咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 2378|回复: 20
收起左侧

[算法题] 面试的时候求最小值我用了初始最大整数,居然...

[复制链接] |试试Instant~
我的人缘0
finerve 发表于 2016-10-23 12:54:25 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (45)
 
 
10% (5)  踩

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

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

x
阿三面试官居然问,如果输入的值是最大整数怎么办...
(我觉得是凉拌吧,反正变量不会改变)

当时蒙了,现场写出了不用最大整数的解法,还是被黑了..当时应该据理力争?

上一篇:关于UML的使用
下一篇:求一道题思路
我的人缘0
stellari 发表于 2016-10-23 13:24:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (366)
 
 
1% (4)  踩
求什么的最小值?数组么?你的意思是面试官问你如果数组本身中含有INT_MAX该怎么办?
回复

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
 楼主| finerve 发表于 2016-10-23 13:30:31 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (45)
 
 
10% (5)  踩
stellari 发表于 2016-10-23 13:24
求什么的最小值?数组么?你的意思是面试官问你如果数组本身中含有INT_MAX该怎么办?

是的.其实是tree,不过没差了..
回复

使用道具 举报

我的人缘0
huai10 发表于 2016-10-23 13:59:05 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (26)
 
 
7% (2)  踩
finerve 发表于 2016-10-23 13:30
是的.其实是tree,不过没差了..

为何不用root的值做初始值
回复

使用道具 举报

我的人缘0
stellari 发表于 2016-10-23 14:07:46 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (366)
 
 
1% (4)  踩
finerve 发表于 2016-10-23 13:30
是的.其实是tree,不过没差了..

不管是什么容器,用能访问到的第一个数字做初始值就好了吧,比如数组是A[0],树是root->val. 还是说面试官有什么其他的限制条件?

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
 楼主| finerve 发表于 2016-10-23 16:31:29 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (45)
 
 
10% (5)  踩
stellari 发表于 2016-10-23 14:07
不管是什么容器,用能访问到的第一个数字做初始值就好了吧,比如数组是A[0],树是root->val. 还是说面试 ...

所以不能用吗? 就是看leetcode很多人随便就用了..
回复

使用道具 举报

我的人缘0
freeaccount 发表于 2016-10-23 20:23:30 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (79)
 
 
9% (8)  踩
本人刷题经验是。。如果你这么做了,但遇到一个corner case导致这个初始的最大值直接被当结果返回,就错了。。。
回复

使用道具 举报

我的人缘0
stellari 发表于 2016-10-24 02:36:19 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (366)
 
 
1% (4)  踩
finerve 发表于 2016-10-23 16:31
所以不能用吗? 就是看leetcode很多人随便就用了..

把minVal初始化成INT_MAX不是不可以,但是关键是你要清楚这可能会造成什么影响。如果仅是单纯地求容器内的“最小值”的话,这样没有问题:minVal初始化成容器的第一个数都可以, 那么初始化成肯定>=容器第一个数的INT_MAX更不会有问题了(当然要做好容器如果是空情况下的检查)。就你的描述而言,面试官或许就是期待一个“输入值即使有最大整数也不影响结果”的答案。

不过说起来单纯求tree的最小值有太过简单的嫌疑,所以面试官或许还安排了什么不为人所注意的限制也说不定。仅供参考。

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

回复

使用道具 举报

我的人缘0
stellari 发表于 2016-10-24 02:45:37 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (366)
 
 
1% (4)  踩
本帖最后由 stellari 于 2016-10-24 02:55 编辑
freeaccount 发表于 2016-10-23 20:23
本人刷题经验是。。如果你这么做了,但遇到一个corner case导致这个初始的最大值直接被当结果返回,就错了 ...

只要minVal初始化成一个合理的值,总是可以写出返回结果正确的代码的。如果是minVal初始化成INT_MAX代码就不能正常工作,那么这就是代码本身的整体逻辑有问题。这在面试时会被扣掉很多分的。
回复

使用道具 举报

我的人缘0
 楼主| finerve 发表于 2016-10-24 04:19:34 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (45)
 
 
10% (5)  踩
freeaccount 发表于 2016-10-23 20:23
本人刷题经验是。。如果你这么做了,但遇到一个corner case导致这个初始的最大值直接被当结果返回,就错了 ...

预先判断input为空能不能排除掉你说的corner case? 求指正
回复

使用道具 举报

我的人缘0
 楼主| finerve 发表于 2016-10-24 04:25:37 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (45)
 
 
10% (5)  踩
stellari 发表于 2016-10-24 02:36
把minVal初始化成INT_MAX不是不可以,但是关键是你要清楚这可能会造成什么影响。如果仅是单纯地求容器内 ...

多谢解答,也不是单纯求了,就是比如validate bst的初始值之类的.

好像第一个node的INT_MAX和本身的INT_MAX会造成False,但是如果只有一个Node应该是True.

所以就应该完全避免使用INT_MAX了..?

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
yxyxyx 发表于 2016-10-24 05:13:55 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (678)
 
 
2% (15)  踩
finerve 发表于 2016-10-23 16:25
多谢解答,也不是单纯求了,就是比如validate bst的初始值之类的.

好像第一个node的INT_MAX和本身的INT_ ...

这类问题的处理方式大概有两种:
1.1. 把input为极值的情况单独处理。比如在代码里专门写如果输入时极大/小值该如何如何。
1.2. 如你所说,先判断下input为空在某些时候也可以。

2. 另外一个比较cheese的做法就是把input从int转成long,然后用LONG_MAX作为极大值去比。这样的好处是如果面试官认为可以的话实现起来最简单,坏处是面试官也可以顺着问:
“那如果input本身就是long怎么办?”
“那就用long long"
“那如果input本身就是long long怎么办”
“...DOUBLE_MAX?????”

所以看情况。其实根据以前的经验不少情况下方法2就可以了
回复

使用道具 举报

我的人缘0
yxyxyx 发表于 2016-10-24 05:31:58 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (678)
 
 
2% (15)  踩
本帖最后由 yxyxyx 于 2016-10-23 17:33 编辑
finerve 发表于 2016-10-23 16:25
多谢解答,也不是单纯求了,就是比如validate bst的初始值之类的.

好像第一个node的INT_MAX和本身的INT_ ...

恩就validate bst这道题来说的话:

比如我想用inorder traversal, 比上一个遍历过的值和现在node的值,那么有多个做法:

1. 把“上一个遍历过的值”设成LONG_MIN. 这样的做法代码如下:
  1. bool helper(TreeNode *root, long &prev_val) {
  2.     if (root == NULL) return true;
  3.     bool left_valid = helper(root->left, prev_val);
  4.     if (!left_valid) return false;
  5.     if (prev_val >= root->val) return false;
  6.     prev_val = root->val;
  7.     return helper(root->right, prev_val);
  8. }
  9.    
  10. bool isValidBST(TreeNode* root) {
  11.     long prev_val = LONG_MIN;
  12.     return helper(root, prev_val);
复制代码
2. 当然“上一个遍历过的值”是可以初始化成INT_MIN的,但是你需要代码里专门处理下如果这个数里面存在INT_MIN怎么办(比如最左节点是INT_MIN)。一个可行的处理方法就是看你是不是已经遍历过了最左节点,因为一个正确的BST里,INT_MIN只可能存在于最左节点。这样的代码如下:
  1. bool helper(TreeNode *root, int &prev_num, bool &visited_leftmost) {
  2.     if (root == NULL) return true;
  3.     bool left_valid = helper(root->left, prev_num, visited_leftmost);
  4.     if (!left_valid) return false;
  5.         
  6.     if (root->val == INT_MIN) {
  7.         if (visited_leftmost) return false;
  8.         else visited_leftmost = true;
  9.     } else if (root->val <= prev_num) return false;
  10.     visited_leftmost = true;
  11.     prev_num = root->val;
  12.     return helper(root->right, prev_num, visited_leftmost);
  13. }
  14.    
  15. bool isValidBST(TreeNode* root) {
  16.     int prev_num = INT_MIN;
  17.     bool visited_leftmost = false;
  18.     return helper(root, prev_num, visited_leftmost);
  19. }
复制代码
当然你也可以采取另外一种方式validate bst,那就是看当前节点的值是不是比左子树的最大值大且比右子树的最小值小。这类做法也有写法可以把你的最大值最小值用INT_MIN和INT_MAX初始化而不用担心树里有INT_MIN和INT_MAX的node。提示一下:用postorder traversal做。


评分

参与人数 1大米 +20 收起 理由
finerve + 20 细致,经典

查看全部评分

回复

使用道具 举报

我的人缘0
xietao0221 发表于 2016-10-24 05:57:49 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (41)
 
 
0% (0)  踩
用Integer类型,设置为null就好了,判断的时候多加一个if
回复

使用道具 举报

我的人缘0
 楼主| finerve 发表于 2016-10-24 07:19:45 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (45)
 
 
10% (5)  踩
yxyxyx 发表于 2016-10-24 05:31
恩就validate bst这道题来说的话:

比如我想用inorder traversal, 比上一个遍历过的值和现在node的值 ...

大神,如果想用迭代+in-order的方法判断valid bst,"上一个node"变量不能设初始值为root,如果也不能设初始值为最小int,只能初始为null 再加判断了是吗?
回复

使用道具 举报

我的人缘0
 楼主| finerve 发表于 2016-10-24 07:21:10 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (45)
 
 
10% (5)  踩
xietao0221 发表于 2016-10-24 05:57
用Integer类型,设置为null就好了,判断的时候多加一个if

这方法好,虽然很朴素,不过感觉各种情况通吃啊~
回复

使用道具 举报

我的人缘0
ykwwind 发表于 2016-10-24 07:59:10 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (817)
 
 
9% (85)  踩
finerve 发表于 2016-10-24 07:21
这方法好,虽然很朴素,不过感觉各种情况通吃啊~

你这个不是技术问题...

阿三一旦发问,不要怂,直接干. 不服就举例,摁不死他就是被摁死. 千万不要被阿三带着走.....人家未必就是想黑你,但是阿三就这风格,就是喜欢突然岔开去...搞着搞着最后面的人崩了.
回复

使用道具 举报

我的人缘0
yxyxyx 发表于 2016-10-24 09:24:24 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (678)
 
 
2% (15)  踩
finerve 发表于 2016-10-23 19:19
大神,如果想用迭代+in-order的方法判断valid bst,"上一个node"变量不能设初始值为root,如果也不能设初始 ...

恩听起来你用的是Java?如果java里有NULL定义的话那自然最好了,c++里的int不幸不能设定成NULL,所以没有这个选项
回复

使用道具 举报

我的人缘0
xietao0221 发表于 2016-10-24 09:32:21 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (41)
 
 
0% (0)  踩
yxyxyx 发表于 2016-10-24 09:24
恩听起来你用的是Java?如果java里有NULL定义的话那自然最好了,c++里的int不幸不能设定成NULL,所以没有 ...

其实如果没有null也没关系,可以另外设置一个bool变量作为是否第一个值已经赋值,其实是一个道理,只是代码会多一些东西。
回复

使用道具 举报

我的人缘0
freeaccount 发表于 2016-10-24 10:46:56 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (79)
 
 
9% (8)  踩
finerve 发表于 2016-10-23 15:19
预先判断input为空能不能排除掉你说的corner case? 求指正

我忘了我的case了。应该是可以,总之就是要对corner case做特殊处理,input为空当然是corner case的一种。
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-9-23 21:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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