去年年末面试Bloomberg遇到一个奇怪的题目，至今也不知道怎么做，想和大家探讨一下，大家有好的思路可以在下面讨论奥！感谢！
如下，有一个api叫做priceToSupply(price)，return的值就是supply. Api内部如何实现是未知的，给你的权限就是只能调用这个api.
在不断的讨论过程中，唯一确定的就是supply和price的关系，非线性上升，一直都是上升的单调的，告诉我supply和price都是integer（这是我强行要的不知道是不是原来想让我用double/float做）让我实现这个api的反转，即supplyToPrice。
楼主用的二分做的，但是做到最后有一个问题，说如果你这个持续二分下去，这个点不是accurate的点怎么办，你有什么办法得到真正的点么。不知道怎么做。ML？弄个模型出来拟合？我实在说不上，就说getAverage取个平均close to的数值吧。然后就挂了。
还告诉这是一个open minded的题目，ok，fine。。。大家有什么好办法吗？？！
1 Like
Dad
(市委书记李达康)
2
牛顿法 不过二分怎么可能不精确啊 顶多就是慢一点嘛
对了 你这是sde面试？哪个组啊，只是一轮么？
sde。2轮游，第一轮我没贴。一个自己创的算法题和一个system design。
不过这个题目他就是要精确的。否则我都不觉得奇怪了。
Dad
(市委书记李达康)
4
sorry 我搞错了 这个没法搞斜率…而且还有左右限制 牛顿法也不行
Dad
(市委书记李达康)
7
感觉既然都说了是开放性问题可能就只是想看看你懂多少domain knowledge吧 比如knn linear reg之类的 对了 那前一轮呢 求面经 我下周onsite去
给2个array，比如arr1 {1, 2, 4, 5, 9}的sum是21，arr2 {2, 3, 5, 7, 10}的sum是27, 那么让你swap他们2个中的各一个元素，使得他们的sum相等，比如arr1中的2和arr2中的5换一下，就是sum1和sum2都是24了。
设计一个租车系统
1 Like
我觉得这道题目可能是想要让你设计一个数据结构去Cache，比如10块-供给6个，11块供给7个。然后当你调用supplyToPrice的时候，比如输入是10.5，通过这个Cache得到一个初始的范围[6,7]，然后你通过binary search再搜索得到10.5对应的答案。
他问你，这个点不是accurate的点这个问题本身就不合理，因为只要这个函数本身是单调的，就肯定能通过二分搜索到答案。
