t*****l
发帖数: 38 | 1 找板上的兄弟refer了airbnb
recruiter很快联系了我，而且不得不说airbnb的recruiter态度特别好，堪比google
recruiter
电面二话不说上来就做题
一个餐馆，菜单上各种食物价格如下
A， $ X.XX
B， $ Y.YY
C， $ Z.ZZ
D, $ ...
问现在一个人有 一定数额的钱，比如 $MM.MM，如何点菜才能把钱全部花完？
面试官要求列出所有可能的组合
我用了recursive的方法，写出来了
但是在 比较 float number的时候，细节没有处理好
直接比较 X.XX == Y.YY 会出现错误，所以必须要做差来比较
经面试官提醒改了过来
然后周一被通知挂了
这题除了用recursive方法，有更好的解法吗？DP?
**************湾区码农求refer***********
两年左右经验，会python和一些web开发， java啥的之前也做过，但是不熟
刷题应该没问题，正在系统的学习系统设计
求各种refer！请站内联系 |
b**********5
发帖数: 7881 | 2 why u can't use == on float? is it a python thing? |
u********s
发帖数: 1047 | 3 almost all programming languages since fractional numbers are not precise
value in programming language, comparison is not guaranteed.
【在 b**********5 的大作中提到】
: why u can't use == on float? is it a python thing?
|
s*y
发帖数: 472 | 4 直接把菜价和钱乘以100用int来比较就好了
【在 t*****l 的大作中提到】
: 找板上的兄弟refer了airbnb
: recruiter很快联系了我，而且不得不说airbnb的recruiter态度特别好，堪比google
: recruiter
: 电面二话不说上来就做题
: 一个餐馆，菜单上各种食物价格如下
: A， $ X.XX
: B， $ Y.YY
: C， $ Z.ZZ
: D, $ ...
: 问现在一个人有 一定数额的钱，比如 $MM.MM，如何点菜才能把钱全部花完？
|
x***4
发帖数: 1815 | 5 是不是先排序，再做dfs，会快一点？
【在 t*****l 的大作中提到】
: 找板上的兄弟refer了airbnb
: recruiter很快联系了我，而且不得不说airbnb的recruiter态度特别好，堪比google
: recruiter
: 电面二话不说上来就做题
: 一个餐馆，菜单上各种食物价格如下
: A， $ X.XX
: B， $ Y.YY
: C， $ Z.ZZ
: D, $ ...
: 问现在一个人有 一定数额的钱，比如 $MM.MM，如何点菜才能把钱全部花完？
|
b****t
发帖数: 78 | |
b****t
发帖数: 78 | |
j***y
发帖数: 1640 | 8 应该是 DP coin change 问题。
估计是要 min # of dishes
【在 b****t 的大作中提到】
: x 100 后 不就是背包问题了？
|
t*****l
发帖数: 38 | 9 面试官要求列出所有可能的组合
【在 j***y 的大作中提到】
: 应该是 DP coin change 问题。
: 估计是要 min # of dishes
|
c*****m
发帖数: 271 | 10 谢谢分享！如果小数位数不定的话，就只能dfs了，先sort再dfs的话可以加些filter条
件（从最贵的菜往前总共值多少钱，在dfs的时候进行剪枝）；如果小数倍数确定，*
100 / 1000 ...确实是是好方法，然后就背包了，dp的过程中记录路径，最后全部输出
就可以吧？
【在 t*****l 的大作中提到】
: 面试官要求列出所有可能的组合
|
|
|
g*********n
发帖数: 282 | 11 把价格先乘以100，然后sort所有菜价格，再用leetcode的Combination Sum来解答？ |
h****3
发帖数: 421 | 12 一个菜可以点多次吧。好像是leetcode一题的变种。
【在 t*****l 的大作中提到】
: 找板上的兄弟refer了airbnb
: recruiter很快联系了我，而且不得不说airbnb的recruiter态度特别好，堪比google
: recruiter
: 电面二话不说上来就做题
: 一个餐馆，菜单上各种食物价格如下
: A， $ X.XX
: B， $ Y.YY
: C， $ Z.ZZ
: D, $ ...
: 问现在一个人有 一定数额的钱，比如 $MM.MM，如何点菜才能把钱全部花完？
|
t*****l
发帖数: 38 | 13 这是个好解法，但是感觉不sort也行？
【在 g*********n 的大作中提到】
: 把价格先乘以100，然后sort所有菜价格，再用leetcode的Combination Sum来解答？
|
e********2
发帖数: 495 | 14 不sort的话，不好剪枝。
【在 t*****l 的大作中提到】
: 这是个好解法，但是感觉不sort也行？
|
s*******u
发帖数: 220 | 15 + 1.
【在 s*y 的大作中提到】
: 直接把菜价和钱乘以100用int来比较就好了
|
r*******y
发帖数: 270 | 16 这尼玛又是背包又是dp coin的，你们是刷题刷的乱了套了吧。题目要求正好花光，这
就是一道combination sum的题目。 |
w********0
发帖数: 377 | 17 可是如何记录路径呢？ 感觉不是很容易可以做到记录路径呀。整个路径是动态变化的
，不到最后都不能确定。
【在 c*****m 的大作中提到】
: 谢谢分享！如果小数位数不定的话，就只能dfs了，先sort再dfs的话可以加些filter条
: 件（从最贵的菜往前总共值多少钱，在dfs的时候进行剪枝）；如果小数倍数确定，*
: 100 / 1000 ...确实是是好方法，然后就背包了，dp的过程中记录路径，最后全部输出
: 就可以吧？
|
b********1
发帖数: 137 | 18 私信我吧，我们有硅谷和西雅图各大公司内推群（只是内推，禁止猎头）和面试讨论。 |
