Uber Onsite
1 Behavior + 2 System Design Or 1 System Design and 1 Bar raiser behavior questions + 2 Coding
Behavior
HM: Talk about your projects
Bar Raiser: All behavior questions like how to handle conflict/Disagreement with manager, your experience about coordination with other teams. There’s an interesting one: if you left your job, what about you that you think your manager won’t miss you most?


System Design
1. (High frequent) Design an uber feature which notifies drivers for the riders.
Interviewer will have a paper with 2 requirements:
Display the density of cars in the current area real time ( heatmap )
Able to read history hourly or daily/ read history in the last 20 mins and last 24 hours
Optional: draw heatmap UI
Similar ones: How to match drivers and riders? (map geo index)
Note 1: The poster discussed what servers the system needs, how to use them to pass data, how to display data in front end, how to store data in database.
Note 2: heatmap + LB strategies + nosql vs sql + diff between memcached and redis + implement a cache with LRU (pseudo code) + cache use strategy
Note 3: Look up Uber engineer’s blog online.
Resource:
https://myslide.cn/slides/2891#

2. (High frequent) Design Messager/whatsapp/Uber in-app chat/ slack

3. (High frequent) Draw architect of your projects and explain it./ The interviewer gives you an architect graph, you talk about how to design log / metrics system based on the given architect so that the system can record data for future analytics purposes.

4.(Medium frequent) Design stock trade system. Resource: Look up data-intensive applications system design online

5.Design a uber feature to warn drive about long time drive + design a generic scheduling service.

6.Design a system that users can update and share real time location to friends and multiple friends can subscribe to that user.
7.Design time series db.
Resource: Read about uber’s own time series db https://m3db.github.io/m3/m3db/

8.Design an online photo upload system, for example, upload 5 small photos via phone, how does backend combine 5 small ones to a big one ( No need to design the photo combination implementation itself, assume you have a library to do so). How to scale this system?

9. Design twitter

10. Design Short URL for twitter
Interviewer’s possible questions:
What database are you gonna use to store data? How to add index, why can index fasten read speed of database?
If there’s huge traffic to system, how will you scale? DB sharding, cache server, local cache on web server，load balancer for web server
Is there consistency problem for local cache?
If the owner who generated that short url can delete it, how to modify the design system? How to design the delete API?

11.Design battle ship game. Two players, each one has a few ships on the board, ships’ positions are fixed. Each player can only see his own board, can’t see the other person’s and don’t know ships positions from the other player. Each player takes turns to fire to a coordination. If hit, that mark the hit ship position and the fire position for future reference. Ship can only be placed vertically or horizontally.
Follow ups:
If the game is not local, it is for 2 ppl online.
How to look up quickly about which ship is hit from the fire coordination. The poster said binary search rows and columns, time complexity is O(logn), then interviewer asked if we don’t worry about memory usage, can it be faster? The poster said record the coordination of all ships, then it’s O(1), the interviewed said bingo...

12. (Identity and secret storage team) Design authentication system to add user, authenticate user, get user’s profile and log out user.

Questionable ones:
13. Design 秒杀系统 (I don’t know wtf is this, I’ll come back later)
14. Merge SQL rows. Solution: use union find.
Coding
LC Questions:
139/140: Word break I and II (High frequent)
465 (High frequent)
21: Merge Two Sorted Lists
449: serialize/deserialize binary tree https://leetcode.com/problems/serialize-and-deserialize-bst
Follow up: serialize/deserialize n tree

621: https://leetcode.com/problems/task-scheduler

267: https://leetcode.com/problems/palindrome-permutation-ii

218: https://leetcode.com/problems/the-skyline-problem

 longest substring with at most k distinct characters

Coding: Given a treeNode in a binary tree, find all nodes that are K distance away from this tree node.

Coding: Twist of classic number of island question. All positions are water (0), no island (1) at first, implement a function that input is a coordination, purpose is to put an island in the given coordination, output is the number of island now. Every time after the function is called, the number of islands can be more/less/equal because islands could be connected.
Similar one: Minesweep

Coding:Given a 2D array, each element means car or empty spot, return the distance from each element in the array to the closest car. Might be a leetcode question.

Coding: input is a few intervals, find overlapped intervals.
Follow up: Some of them is not overlapped, some of them 2 times, 3 times, return intervals that are overlapped moe than K times

Coding: return all valid partitioned palindrome for a string + return the valid palindrome list with smallest partitions

Coding: Students has prefer list to apply colleges, colleges has prefer list for students, how to allocate students to colleges. Students’ preference takes higher priority. The core part is to check if there is conflict in different students’ preferences. If there is, see which student is in the higher priority list from college’s prefer list. If there is no conflict, even if the student is not on school’s prefer list, the student can still get in. Possible solution: use map.

Coding: Parse CSV. (Says high frequency, not sure the real question though)
Similar one: Use JS to parse input JSON.


Coding: Given 2 numbers num1 and num2, return result of num1/num2, e.g. if 1/2, return 0.5, if 1/3 whose result has repeat numbers 0.333333333333333, use braces () for repeat digits, I guess return 0.(3)

Coding: input is a string, print all palindromes that can be formed by using all characters in the string, if can’t form any palindrome, print []. ???

Coding: Given a 2d board like Tetris with width n, blocks fall into the bottom. The definition of blocks are:
class Block {
        int left;
        int right;
        int height;
}
0<= left < right < n, blocks will be built up one on top of the other like Tetris, return the maximum height.
class FallingBlock {
public FallingBlock(int width);
public void fallBlock(Block block);
public int getMaxHeight();
}


Possible solution 1 (I don’t understand what this person is talking):
Use height[width] and maxHeight. Every time when a block is placed, find the max height h from left to right and then update  the height to h+block’s height, if it’s higher than current maxHeight, update it.

Possible solution 2:
public class FallingBlock {

    static class Block {
        int left;
        int right;
        int height;

        public Block(int left, int right, int height) {
            this.left = left;
            this.right = right;
            this.height = height;
        }
    }

    private int boardWidth;
    int[] heights;

    // width is the board width
    public FallingBlock(int width) {
        // Height of segment tree
        int x = (int) (Math.ceil(Math.log(width) / Math.log(2)));
        // Maximum size of segment tree
        int maxSize = 2 * (int) Math.pow(2, x) - 1;
        heights = new int[maxSize]; // Memory allocation
        boardWidth = width;
    }

    public void fallBlock(Block block) throws IllegalArgumentException {
        fallBlockInternal(block, 0, boardWidth - 1, 0);
    }


    public int fallBlockInternal(Block block, int start, int end, int index) {
        // haven't init this segment yet
        if (heights[index] == 0) heights[index] = heights[(index - 1) / 2];

        if (start >= block.left && start <= block.right) {
            // If segment of this node is a part of given range, then
            heights[index] += block.height;
            // System.out.println("start:" + start + " end:" + end + " index:" + index + " height:" + heights[index]);
            return heights[index];
        } else if (start > block.right || end < block.left) {
            // If segment of this node is outside the given range
            // System.out.println("start:" + start + " end:" + end + " index:" + index + " height:" + heights[index]);
            return heights[index];
        } else {
            // If a part of this segment overlaps with the given range
            int mid = (start + end) >>> 1;
            heights[index] = Math.max(
                    fallBlockInternal(block, start, mid, index * 2 + 1),
                    fallBlockInternal(block, mid + 1, end, index * 2 + 2));
            // System.out.println("start:" + start + " end:" + end + " index:" + index + " height:" + heights[index]);
            return heights[index];
        }
    }

    public int getMaxHeight() {
        return heights[0];
    }

    public static void main(String[] args) throws Exception {
        FallingBlock fallingBlock = new FallingBlock(100);
        fallingBlock.fallBlock(new Block(20, 50, 1));
        fallingBlock.fallBlock(new Block(30, 70, 2));
        fallingBlock.fallBlock(new Block(10, 40, 3));
//        fallingBlock.fallBlock(new Block(80, 90, 10));

        System.out.println("max height is " + fallingBlock.getMaxHeight());
    }

}