补发一下狗家详细实习桂晶 诚心求大米～

一面：给一个二维数组，求有没有四个值都是V的elements在一个矩形的四个角例如：
// A = [[7, 9, 6, 1, 7],
//      [8, 1, 0, 2, 1],
//      [7, 0, 1, 0, 7],
//      [1, 1, 6, 1, 1],
//      [5, 2, 9, 7, 1]]
// When V = 1, return true,
// When V = 7, return true,
// When V = 6, return false



我的思路是:

您好！
本帖隐藏的内容需要积分高于 130 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 130 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

二面：给你N个candies, 你要把他们放在几个boxes里，每个box最多能放M个candies。盒子不能有正好13个candies，也不能用正好13个boxes。问需要多少个盒子

我的思路是：

您好！
本帖隐藏的内容需要积分高于 130 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 130 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

欢迎大家讨论

跪求大米啊啊啊啊～ 积分太低了很多帖子看不了 🙏 祝大家面试好运！!

1. int box(int N_candidate, int M_box) {
   
2.     int num = 0;
   
3.     if(M_box == 13) M_box = 12;
   
4.     int d = N_candidate / M_box;
   
5.     int r = N_candidate % M_box;
   
6.     // N_candidate = d * M_box + r;
   
7.     // orginal box num should be d + (r != 0);
   
8.     num = d + (r != 0);
   
9.     // deal with the case that r is 13
   
10.     if(M_box > 13) { // only when M_box is bigger than 13, can r be 13
    
11.         if(r == 13 && M_box == 14) {
    
12.             // only in this case, we need to use 2 box to store 13 candidates, because
    
13.             // we cannot pick 1 candidate from one of the d box, and store it to the box
    
14.             // that hold r candidate.
    
15.             // when M_box >= 15: M_box, M_box, ..., M_box - 1, 13 + 1. So none of the number would be 13. And we don't need extra box
    
16.             num++;
    
17.         }
    
18.     }
    
19.     // deal with the case num is 13
    
20.     if(num == 13)
    
21.         num++;
    
22.     return num;
    
23. }

复制代码

楼主好 感觉楼主第二题是不是有个case过不了啊 如果最大容量是15 之后余数是13 那把其中一个装15个糖果的box那一个给最后一个装13个糖果的box就可以了， 不需要盒子数加一啊

第二题请问盒子是越少越好吗？

wzy602867832 发表于 2018-11-1 10:45
第二题请问盒子是越少越好吗？

是的 最少需要多少盒子

是“这三个有一个是不符合要求，就盒子数量 + 1”吧？

hjysos 发表于 2018-11-1 11:42
是“这三个有一个是不符合要求，就盒子数量 + 1”吧？

是的 盒子数量 + 1！

对于第一题，如果是一个m*n的矩阵，如果我没理解错的话题主的方法需要O(m^2n^2)吧。
我这里有一个思路，就是用一个dict，key是矩阵数值，value是对应的矩阵坐标。这样这样这个问题就演化成了"find valid rectangle in a set of points"。
然后最坏情况是矩阵都是一个值，那么我们可能有O(mn)个点，但是这些点最多只有n个横坐标(x)。我们可以进一步用横坐标 x group这些点（相当于用另外一个dict，key是横坐标，value是一个set保存这个横坐标对应的纵坐标y），然后任意两个group做一个intersection。只要数量大于2说明就可以形成一个rectangle。
这样的话，intersection的复杂度是O(m)，总的复杂度就是O(mn^2)，相对来说优异些吧

copperface 发表于 2018-11-2 11:49
[mw_shl_code=cpp,true]int box(int N_candidate, int M_box) {
    int num = 0;
    if(M_box == 13) M ...

逻辑清晰 赞一个

rxxt 发表于 2018-11-2 04:48
对于第一题，如果是一个m*n的矩阵，如果我没理解错的话题主的方法需要O(m^2n^2)吧。
我这里有一个思路，就 ...

哇 思路清晰 赞一个