一道某搜索公司的onsite题

其他都是lc原题/地里今年的面经题
只有一道题之前从来没见过，发出来分享一下

用一个二维矩阵表示一个城市， 每个cell代表的是一栋楼的高度
例如
2 1 1
1 1 1
1 1 1

然后给两个数列 一个代表这个城市的主视图 一个代表这个城市的左视图
比如这个题的例子就是[2,1,1]和[2,1,1]
Q：现在只知道这个城市的主视图和

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

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

阴沟翻船眼泪掉下来哭晕在厕所
---------------------------
发个面经求大米oooorz 还要面别的家TAT
人生不易 至今没offer 好想脱坑

我的想法是，
1.把主视图由低到高排序，得到一个数组heights，然后再存一个sums数组，每一位是相对应heights的rolling sum，即高度小于等于某个值的高度总和 （这一步是o(nlogn), n是边长），同时做个处理，每个sum加上还没算进去的heights个数乘当前height （类似于补全后面比他高的建筑物）
2.扫一遍左视图，每一次找当前左视图里高度在主视图的rank，然后找相对应的sum，加起来，即最后结果

举个栗子：
左视图[5，5，3]， 主视图[5, 3, 1]。 先排序主视图得[1, 3, 5], sums是[3, 7, 9] (例如7是1+3+3), 所以最后最大总体积/高度是 9+9+7=25

欢迎指正 这道题还挺有意思的

楼主是妹子吗，妹子的题还是会平和一些。我上周去的onsite，难度简直爆炸。

这道题是这样的吧：
给俩数组 A[a1, a2, a3, a4], B[b1, b2, b3, b4, b5]; A, B中任取一个元素，取其中的最小值加入到结果中去 sum += (a, b). a belongs to A, b belongs to B
从头到尾遍历这俩数组，如果A[i] <= B[j], 那么A[i] 和 B[j] 及其以后元素都不用比较了，直接A[i] 胜出。改了一下楼上的代码：
public static int cal(int[] leftView, int[] mainView) {
        Arrays.sort(leftView);
        Arrays.sort(mainView);
        int res = 0, left = 0, main = 0;
        int m = leftview.length, n = mainView.length;
        while(left<m && right<n) {
                if(leftView[left]<=mainView[right]) {
                        res += leftView[left]*(n - right);
                        ++left;
                } else {
                        ret += mainView[main]*(m - left);
                        ++main;
                }
        }
        return res;
}

请问如何做到O(nlgn)的 只想到计算每个位置可以取的楼层高度的最大值然后相加

chenxiaocong 发表于 2017-11-23 23:59
我的想法是，
1.把主视图由低到高排序，得到一个数组heights，然后再存一个sums数组，每一位是相对应heigh ...

这样很好，支持层主，感恩楼主。

请问一下啥叫主视图？

chenxiaocong 发表于 2017-11-23 23:59
我的想法是，
1.把主视图由低到高排序，得到一个数组heights，然后再存一个sums数组，每一位是相对应heigh ...

你这个做法是对的 也是当时我最先想出来的做法
然后面试官说还可以继续优化到不需要sum数组。。我当时就崩溃了

然后发现你还可以给左视图也排个序
你对每个左视图扫对应的主视图的时候 因为左视图是递增的 所以主视图只用一直向右扫就可以了
也不需要sum数组了 维护一个左边的和的常数就行了

这道题确实挺有意思的（还好是bonus  要不然原地爆炸了）

15daysleft 发表于 2017-11-24 06:36
你这个做法是对的 也是当时我最先想出来的做法
然后面试官说还可以继续优化到不需要sum数组。。我当时就 ...

楼主还是好厉害啊

yrfzh 发表于 2017-11-24 06:47
楼主还是好厉害啊

向脸书大佬低头！

15daysleft 发表于 2017-11-24 06:51
向脸书大佬低头！

我太水了。。。。