攒人品，脸家电面以及visa的流程问题

三哥，有口音但还行，1. 最长公共prefix, 原题
2. interval变种题, 找出最大利润情况下，最合适的价格。比如接受价格范围A[8, 10] B[6,

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

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

里。
请问这个是new grad的标准流程吗。。是的话我就自己投了，万一过了也没有组的限制

xiebw 发表于 2018-10-10 11:39
俺写了一个大概的代码。。有啥不对的还请多多指教！
public int maxProfix(Interval[] customers) {
  ...

最后计算的时候应该是

1. if (curt.acceptable) {
   
2.     maxPro = Math.max(maxPro,++count * price);
   
3. } else {
   
4.     maxPro = Math.max(maxPro,count-- * price);
   
5. }
   
6.            

复制代码

zqyzdsjdy 发表于 2018-10-11 02:43
我没太明白你的意思，你确定的价格只有一个不是分区间，比如[3,6] [6,9] [10, 11]你可以先试6后试 11；  ...

俺写了一个大概的代码。。有啥不对的还请多多指教！
public int maxProfix(Interval[] customers) {
        if (customers == null || customers.length == 0) {
            return 0;
        }
        PriorityQueue<Price> timeline = new PriorityQueue<Price>(new Comparator<Price>() {
            public int compare(Price p1, Price p2) {
                if (p1.value == p2.value) {
                     if (p1.acceptable) {
                         return -1;
                     }
                     return 1;
                }
                return p1.value - p2.value;
            }
        });
        for (int i = 0; i < customers.length; i++) {
            timeline.offer(new Price(customers[i].start,true));
            timeline.offer(new Price(customers[i].end,false));
        }
        int maxPro = -1;
        int count = 0;
        while (!timeline.isEmpty()) {
            Price curt = timeline.poll();
            int price = curt.value;
            if (curt.acceptable) {
                count ++;
            }
            else {
                count --;
            }
            maxPro = Math.max(maxPro,count * price);
        }
        return maxPro;
    }
}

zqyzdsjdy 发表于 2018-10-11 02:43
我没太明白你的意思，你确定的价格只有一个不是分区间，比如[3,6] [6,9] [10, 11]你可以先试6后试 11；  ...

是这样的。。你这个不是扫描线算法。。扫描线算法的意思是，我把区间拆成两份。比如[3,6]， start 是3， end 是6， 再java里面我们就可以建一个node(int index, boolean isStart)这样子。 然后把所有的node都存入 pq里面。这个题用min heap。这样可以在弹出price的时候动态更新count。 遇到1个start就证明有一个人能接受价格，count ++， 遇到一个end就证明有一个人不能接受， count --。  想你给的这个例子里面 heap出来的node和能接受的人数count分别如下：  price为3的时候，count 1,   price 6 count 2（因为区间边界重合先加后减），因为price 6的node有两个，所以计算完count 2之后， price 6 count 1,   然后就是price 9count 1， price 10 count 1, price 11 count 1. 每次在区间边界都是更新之后算完profit才结束。 这样算下来，最好的就是6 * 2= 12的profit

请问第一题题号是什么呀？

第二题还是不太懂怎么做。。能再讲解一下吗？

请问第一题是蠡口食肆吗？

lzsapril666 发表于 2018-9-21 10:46
请问第一题是蠡口食肆吗？

是的，字数字数。。

diet_coke 发表于 2018-9-21 09:49
请问第一题题号是什么呀？

楼下有人说了，一道ez题，不过要注意优化啊，leetcode讨论里有

diet_coke 发表于 2018-9-21 10:05
第二题还是不太懂怎么做。。能再讲解一下吗？

我做完后大概和同学讨论的，具体思路记不清楚了。。你把interval的题做一遍，里面有一道是sort后用priorityqueue的，思路估计和那个差不多吧

好的好的，谢谢面筋

diet_coke 发表于 2018-9-21 23:34
好的好的，谢谢面筋

请问你有找到第二题是哪题吗？找到的话麻烦说下，非常感谢~

第二题感觉可以用sweep line来做吧，维护一个count表示能接受当前价格的人的数量，profit就是当前点的price*count