Uber onsite 面经

1. Merge Two Sorted Lists
2. Sparse Matrix Multiplication
3. 挂在这道:


给一个n列类似俄罗期方块的盘, 往下掉方块. 方块定义如下:
class Block {
        i

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

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

atsapp

后面花了好几天用segment tree给解了第3题.

1. public class FallingBlock {
   
2. 
   
3.     static class Block {
   
4.         int left;
   
5.         int right;
   
6.         int height;
   
7. 
   
8.         public Block(int left, int right, int height) {
   
9.             this.left = left;
   
10.             this.right = right;
    
11.             this.height = height;
    
12.         }
    
13.     }
    
14. 
    
15.     private int boardWidth;
    
16.     int[] heights;
    
17. 
    
18.     // width is the board width
    
19.     public FallingBlock(int width) {
    
20.         // Height of segment tree
    
21.         int x = (int) (Math.ceil(Math.log(width) / Math.log(2)));
    
22.         // Maximum size of segment tree
    
23.         int maxSize = 2 * (int) Math.pow(2, x) - 1;
    
24.         heights = new int[maxSize]; // Memory allocation
    
25.         boardWidth = width;
    
26.     }
    
27. 
    
28.     public void fallBlock(Block block) throws IllegalArgumentException {
    
29.         fallBlockInternal(block, 0, boardWidth - 1, 0);
    
30.     }
    
31. 
    
32. 
    
33.     public int fallBlockInternal(Block block, int start, int end, int index) {
    
34.         // haven't init this segment yet
    
35.         if (heights[index] == 0) heights[index] = heights[(index - 1) / 2];
    
36. 
    
37.         if (start >= block.left && start <= block.right) {
    
38.             // If segment of this node is a part of given range, then
    
39.             heights[index] += block.height;
    
40.             // System.out.println("start:" + start + " end:" + end + " index:" + index + " height:" + heights[index]);
    
41.             return heights[index];
    
42.         } else if (start > block.right || end < block.left) {
    
43.             // If segment of this node is outside the given range
    
44.             // System.out.println("start:" + start + " end:" + end + " index:" + index + " height:" + heights[index]);
    
45.             return heights[index];
    
46.         } else {
    
47.             // If a part of this segment overlaps with the given range
    
48.             int mid = (start + end) >>> 1;
    
49.             heights[index] = Math.max(
    
50.                     fallBlockInternal(block, start, mid, index * 2 + 1),
    
51.                     fallBlockInternal(block, mid + 1, end, index * 2 + 2));
    
52.             // System.out.println("start:" + start + " end:" + end + " index:" + index + " height:" + heights[index]);
    
53.             return heights[index];
    
54.         }
    
55.     }
    
56. 
    
57.     public int getMaxHeight() {
    
58.         return heights[0];
    
59.     }
    
60. 
    
61.     public static void main(String[] args) throws Exception {
    
62.         FallingBlock fallingBlock = new FallingBlock(100);
    
63.         fallingBlock.fallBlock(new Block(20, 50, 1));
    
64.         fallingBlock.fallBlock(new Block(30, 70, 2));
    
65.         fallingBlock.fallBlock(new Block(10, 40, 3));
    
66. //        fallingBlock.fallBlock(new Block(80, 90, 10));
    
67. 
    
68.         System.out.println("max height is " + fallingBlock.getMaxHeight());
    
69.     }
    
70. 
    
71. }

复制代码

第三题是不是想多了？可以直接用height[width]和最高maxHeight。每放一个block，找到left到right的最大高度h，然后更新left到right的高度h+block的height，如果新的高度比当前的maxHeight高就更新它。

卧槽在职跳槽也考线段树？

这真的是四年前的面经么。。

楼主的第二题需要自己给sparse的matrix设计数据结构然后再求multiplication吗？

Fallingblock那题可以用扫描线的方法做吗