(G) Design / OOD 类算法题

Logger Rate Limiter

非常的 trivial ... 用一个 hashmap 做一个类似 inverted index 功能就可以了，需要注意的地方是如果这轮输出了 true，要同时更新 hashmap 里面的 timestamp，输出 false 的时候不更新，因为还没 print.

public class Logger {
    HashMap<String, Integer> map;
    /** Initialize your data structure here. */
    public Logger() {
        map = new HashMap<String, Integer>();
    }

    /** Returns true if the message should be printed in the given timestamp, otherwise returns false.
        If this method returns false, the message will not be printed.
        The timestamp is in seconds granularity. */
    public boolean shouldPrintMessage(int timestamp, String message) {
        boolean rst = false;

        if(!map.containsKey(message) || timestamp - map.get(message) >= 10) rst = true;
        if(rst) map.put(message, timestamp);

        return rst;
    }
}

Design Hit Counter

承接了 sliding window maximum 的灵感，维护一个所谓“固定大小”的 sorted deque，两端操作，从 peekLast() 开始看，小于当前起始 time interval 的就直接扔掉，也完全可以处理同一时间多个 hit 的情况。

不过貌似这写法速度不够快，126ms，只超过了 17.46%，一看论坛上快的解法都是用 int[] + circular buffer 的写法。

Follow up:

What if the number of hits per second could be very large? Does your design scale?

建 int[] array 显然就不现实了，不如 deque !

public class HitCounter {
    Deque<Integer> deque;
    /** Initialize your data structure here. */
    public HitCounter() {
        deque = new LinkedList<Integer>();
    }

    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    public void hit(int timestamp) {
        deque.offerFirst(timestamp);
    }

    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    public int getHits(int timestamp) {
        if(timestamp <= 300) return deque.size();

        int startTime = timestamp - 300;
        while(!deque.isEmpty() && deque.peekLast() <= startTime) deque.pollLast();

        return deque.size();
    }
}

Design Tic-Tac-Toe

这题的 index 用法其实和 N-queens 的备忘录法一样，存行，列，各个对角线就行了。

public class TicTacToe {
    // array[][index]
    // index 0 : # of player 1's pieces
    // index 1 : # of player 2's pieces
    private int[] leftDiag;
    private int[] rightDiag;

    private int[][] rows;
    private int[][] cols;

    private int n;

    /** Initialize your data structure here. */
    public TicTacToe(int n) {
        this.n = n;
        leftDiag = new int[2];
        rightDiag = new int[2];
        rows = new int[n][2];
        cols = new int[n][2];
    }

    /** Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins. */
    public int move(int row, int col, int player) {
        rows[row][player - 1] ++;
        cols[col][player - 1] ++;
        if(row == col) leftDiag[player - 1] ++;
        if(row + col == n - 1) rightDiag[player - 1]++;

        if(rows[row][player - 1] == n || cols[col][player - 1] == n ||
           leftDiag[player - 1] == n || rightDiag[player - 1] == n){
            return player;
        } else {
            return 0;
        }
    }
}

看了下论坛，这题还可以进一步做空间优化，利用只有两个玩家的特点省掉一半空间。

public class TicTacToe {
    // array[][index]
    // index 0 : # of player 1's pieces
    // index 1 : # of player 2's pieces
    private int leftDiag;
    private int rightDiag;

    private int[] rows;
    private int[] cols;

    private int n;

    /** Initialize your data structure here. */
    public TicTacToe(int n) {
        this.n = n;
        leftDiag = 0;
        rightDiag = 0;
        rows = new int[n];
        cols = new int[n];
    }

    /** Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins. */
    public int move(int row, int col, int player) {
        int delta = (player == 1) ? 1: -1;

        rows[row] += delta;
        cols[col] += delta;
        if(row == col) leftDiag += delta;
        if(row + col == n - 1) rightDiag += delta;

        if(Math.abs(rows[row]) == n || Math.abs(cols[col]) == n ||
           Math.abs(leftDiag) == n || Math.abs(rightDiag) == n){
            return player;
        } else {
            return 0;
        }
    }
}

Design Snake Game

先用 Deque 写了第一版，速度只超过了 2.35% .. 可能我每步都调用 String 复杂度太高了。

需要注意的细节：

• food 吃完之后还可以继续玩，蛇每次依然在动，所以要在合适的地方 access food matrix 免得越界。

• 吃自己身体会 game over，但是吃尾巴尖没事。。

用了另外一个 deque 存 body index 速度就快多了超过 54%， 但是没什么大改动就不贴代码了。另外一个小改动是，其实用不着存 score 变量，因为 score = 蛇长度 - 1

public class SnakeGame {
    int[][] food;
    int foodIndex;
    // deque of String "x y" representing positions of snake
    Deque<String> snake;

    int score;
    int rows;
    int cols;

    /** Initialize your data structure here.
        @param width - screen width
        @param height - screen height 
        @param food - A list of food positions
        E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */
    public SnakeGame(int width, int height, int[][] food) {
        this.rows = height;
        this.cols = width;
        this.food = food;
        this.foodIndex = 0;
        this.score = 0;
        this.snake = new LinkedList<String>();

        snake.offerFirst("0,0");
    }

    /** Moves the snake.
        @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down 
        @return The game's score after the move. Return -1 if game over. 
        Game over when snake crosses the screen boundary or bites its body. */
    public int move(String direction) {
        String[] coordinates = snake.peekFirst().split(",");
        int headX = Integer.parseInt(coordinates[0]);
        int headY = Integer.parseInt(coordinates[1]);

        if(direction.equals("U")) headX--;
        if(direction.equals("L")) headY--;
        if(direction.equals("R")) headY++;
        if(direction.equals("D")) headX++;

        // Hit wall
        if(headX < 0 || headX >= rows) return -1;
        if(headY < 0 || headY >= cols) return -1;

        // Hit itself
        String newPos = headX + "," + headY;
        // It's ok if you bite the tail
        if(snake.contains(newPos) && !snake.peekLast().equals(newPos)) return -1;

        // No food, just move
        if(foodIndex >= food.length){
            snake.offerFirst(newPos);
            snake.pollLast();
            return score;
        }

        int foodX = food[foodIndex][0];
        int foodY = food[foodIndex][1];

        // Got food !
        if(headX == foodX && headY == foodY){
            snake.offerFirst(newPos);
            score ++;
            foodIndex ++;
            return score;
        } else {
            snake.offerFirst(newPos);
            snake.pollLast();
            return score;
        }
    }
}

Design Twitter

一个典型的 Observer pattern；为了降低耦合度，每个 user 维护自己的 tweet list 和 follow list，而 post tweet 只是负责自行生产，而不主动执行 push; 每次刷新的时候自己从 follow 列表抓 tweets 就好了。

这题一个需要注意的细节是，排序顺序是按照 timestamp，接口里给的 tweetId ，和时间顺序没有必然的联系，所以要自行维护全局时间戳。

除此之外就是比较直观的 merge k sorted list 问题了，为了方便处理，我们维护了一个 Tweet object 的 LinkedList，但同时 Tweet 存了一个自己的 prev 指针，方便进行多路归并的时候正确找到下一个元素。

其他需要注意的就是各种 corner case : 关注自己，取关不存在的人，取关自己本来就没关注的人，自己或者自己的关注用户没有任何 post，等等。

public class Twitter {
    // Key : user
    // Value : list of tweets
    HashMap<Integer, LinkedList<Tweet>> tweetsMap;

    // Key : user
    // Value : list of userId's the user has been following
    HashMap<Integer, Set<Integer>> follows;

    int timestamp;

    private class Tweet implements Comparable<Tweet>{
        int timestamp;
        int tweetId;
        Tweet prev;

        public Tweet(int timestamp, int tweetId, Tweet prev){
            this.timestamp = timestamp;
            this.tweetId = tweetId;
            this.prev = prev;
        }
        public int compareTo(Tweet a){
            return a.timestamp - this.timestamp;
        }
    }

    /** Initialize your data structure here. */
    public Twitter() {
        tweetsMap = new HashMap<Integer, LinkedList<Tweet>>();
        follows = new HashMap<Integer, Set<Integer>>();
        timestamp = 0;
    }

    /** Compose a new tweet. */
    public void postTweet(int userId, int tweetId) {
        if(!tweetsMap.containsKey(userId)) tweetsMap.put(userId, new LinkedList<Tweet>());

        Tweet prev = (tweetsMap.get(userId).size() == 0) ? null: tweetsMap.get(userId).peekFirst();
        tweetsMap.get(userId).offerFirst(new Tweet(timestamp, tweetId, prev));
        timestamp++;
    }

    /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
    public List<Integer> getNewsFeed(int userId) {
        List<Integer> list = new ArrayList<>();
        PriorityQueue<Tweet> maxHeap = new PriorityQueue<Tweet>();

        if(tweetsMap.containsKey(userId) && tweetsMap.get(userId).size() > 0)
            maxHeap.offer(tweetsMap.get(userId).peekFirst());

        if(follows.containsKey(userId)){
            for(int followee : follows.get(userId)){
                if(tweetsMap.containsKey(followee) && tweetsMap.get(followee).size() > 0) 
                    maxHeap.offer(tweetsMap.get(followee).peekFirst());
            }
        }

        for(int i = 0; i < 10 && !maxHeap.isEmpty(); i++){
            Tweet tweet = maxHeap.poll();
            list.add(tweet.tweetId);
            if(tweet.prev != null) maxHeap.offer(tweet.prev);
        }

        return list;
    }

    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    public void follow(int followerId, int followeeId) {
        // Can't follow yourself
        if(followerId == followeeId) return;
        if(!follows.containsKey(followerId)) follows.put(followerId, new HashSet<Integer>());

        follows.get(followerId).add(followeeId);
    }

    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    public void unfollow(int followerId, int followeeId) {
        if(!follows.containsKey(followerId) || !follows.get(followerId).contains(followeeId)) return;

        follows.get(followerId).remove(followeeId);
    }
}

Design Phone Directory

我还以为要写个 trie 什么的。。这题是什么鬼。。写个 boolean[] 都能 AC.... 697 ms 好么。。

下面这个代码的 get 时间复杂度为 O(maxNumber)，显然太高了。

public class PhoneDirectory {
    boolean[] phoneBook;
    /** Initialize your data structure here
        @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
    public PhoneDirectory(int maxNumbers) {
        phoneBook = new boolean[maxNumbers];
    }

    /** Provide a number which is not assigned to anyone.
        @return - Return an available number. Return -1 if none is available. */
    public int get() {
        for(int i = 0; i < phoneBook.length; i++){
            if(!phoneBook[i]){
                phoneBook[i] = true;
                return i;
            }
        }
        return -1;
    }

    /** Check if a number is available or not. */
    public boolean check(int number) {
        return !phoneBook[number];
    }

    /** Recycle or release a number. */
    public void release(int number) {
        phoneBook[number] = false;
    }
}

稍微快一点的做法是，用一个 Queue 维护目前所有空位，用 Set 维护目前所有已经使用的电话号码。主要 overhead 在于初始化的时候要花 O(n) 时间建队列，还有在 HashSet 里面做删除操作。

这种做法是靠均摊复杂度平摊 cost 的典型例子。

这题的另一种比较省空间的做法是用 BitSet，就看对 API 的熟悉程度了。

• bitset.nextClearBit(smallestFreeIndex);

• bitset.clear(number);

• bitset.get(number) == false;

• bitset.set(smallestFreeIndex);

public class PhoneDirectory {
    Set<Integer> set;
    Queue<Integer> available;
    /** Initialize your data structure here
        @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
    public PhoneDirectory(int maxNumbers) {
        set = new HashSet<>();
        available = new LinkedList<>();
        for(int i = 0; i < maxNumbers; i++){
            available.offer(i);
        }
    }

    /** Provide a number which is not assigned to anyone.
        @return - Return an available number. Return -1 if none is available. */
    public int get() {
        if(available.size() == 0) return -1;
        int num  = available.poll();
        set.add(num);
        return num;
    }

    /** Check if a number is available or not. */
    public boolean check(int number) {
        return !set.contains(number);
    }

    /** Recycle or release a number. */
    public void release(int number) {
        if(!set.contains(number)) return;

        available.offer(number);
        // Amortized O(1) to remove in hashmap / hashset
        set.remove(number);
    }
}

(G) Design Battleship Game

(G) Design Elevator

(A) Design Parking lot

(LinkedIn) Data Stream as Disjoint Intervals