(G) Design / OOD 类算法题
Logger Rate Limiter
用hashmap来存timestamp, 需要注意的一点是Java没有办法在iterate过程中删除key, 必须要通过iterator.
public class Logger {
/** Initialize your data structure here. */
HashMap<Integer, HashSet<String>> map;
public Logger(){
map = new HashMap<Integer, HashSet<String>>();
}
/** 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) {
Iterator<Map.Entry<Integer, HashSet<String>>> iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry<Integer, HashSet<String>> entry = iter.next();
if(entry.getKey()<=timestamp-10){
iter.remove();
}
}
for(Integer key : map.keySet()){
if(map.get(key).contains(message)) return false;
}
if(!map.containsKey(timestamp))
map.put(timestamp, new HashSet<String>());
map.get(timestamp).add(message);
return true;
}
}
另一种方式是存inverted <string, integer> mapping
非常的 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
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
public HitCounter() {
}
/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
public void hit(int timestamp) {
Iterator<Map.Entry<Integer, Integer>> iter = map.entrySet().iterator();
while(iter.hasNext()){
Map.Entry<Integer, Integer> entry = iter.next();
if(entry.getKey()<=timestamp-300){
iter.remove();
}
}
map.put(timestamp, map.getOrDefault(timestamp, 0)+1);
}
/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
public int getHits(int timestamp) {
int count = 0;
for(Integer key : map.keySet()){
if(key>timestamp-300) count += map.get(key);
}
return count;
}
承接了 sliding window maximum 的灵感，维护一个所谓“固定大小”的 sorted deque，两端操作，从 peekLast() 开始看，小于当前起始 time interval 的就直接扔掉，也完全可以处理同一时间多个 hit 的情况。
不过貌似这写法速度不够快，126ms，只超过了 17.46%，一看论坛上快的解法都是用 int[] + circular buffer 的写法。
建立两个array. timestamp和hit.
public class HitCounter {
int[] timestamps;
int[] hit;
/** Initialize your data structure here. */
public HitCounter() {
timestamps = new int[300];
hit = new int[300];
}
/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
public void hit(int timestamp) {
int idx = timestamp%300;
if(timestamps[idx]!=timestamp){
timestamps[idx]=timestamp;
hit[idx]=1;
}
else
hit[idx]++;
}
/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
public int getHits(int timestamp) {
int count = 0;
for(int i=0;i<300;i++){
if(timestamp-timestamps[i]<300)
count+=hit[i];
}
return count;
}
}
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
第一次写, beats了85.90%, 几乎一次AC, 厉害了,word哥.
需要注意的细节：
food 吃完之后还可以继续玩，蛇每次依然在动，所以要在合适的地方 access food matrix 免得越界。
吃自己身体会 game over，但是吃尾巴尖没事。。
思路:
- 建立food和snake的list.
- 每一步check结果
- 碰到边界, 返回-1
- 碰到食物, 加分, 身体头部变为当前食物位置.
- 碰到自己身体, 返回-1. 注意有自循环模式. 判断时不判断尾巴尖.
- 碰到空, 加入next位置, 删除尾巴尖.
public class SnakeGame {
/** 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]. */
int width;
int height;
LinkedList<int[]> food = new LinkedList<int[]>();
LinkedList<int[]> snake = new LinkedList<int[]>();
int score;
public SnakeGame(int width, int height, int[][] food1) {
this.width = width;
this.height = height;
for(int[] f:food1){
food.offer(f);
}
int[] pos = new int[2]; pos[0] = 0; pos[1] = 0;
snake.offer(pos);
score = 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) {
int[] head = snake.getFirst();
int[] next = new int[2];
if(direction.equals("U")){
next[0] = head[0]-1; next[1] = head[1];
}
else if(direction.equals("D")){
next[0] = head[0]+1; next[1] = head[1];
}
else if(direction.equals("L")){
next[0] = head[0]; next[1] = head[1]-1;
}
else if(direction.equals("R")){
next[0] = head[0]; next[1] = head[1]+1;
}
//reach to board
if(next[0]<0 || next[0]>=height || next[1]<0 || next[1]>=width)
return -1;
//reach to food
if(!food.isEmpty()){
int[] curFood = food.getFirst();
if(next[0]==curFood[0] && next[1] ==curFood[1]){
curFood = food.poll();
score++;
snake.offerFirst(next);
return score;
}
}
//check if reach to body
//special case: self circle
for(int i=0;i<snake.size()-1;i++){
if(next[0]==snake.get(i)[0] && next[1]==snake.get(i)[1]) return -1;
}
//normal/empty move
snake.removeLast();
snake.offerFirst(next);
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，未来可能会有
这道题一个关键是merge K sorted list来getPost. 这里我自己纠结了半天, 是用iterator还是新建一个object(listidx, curidx). 最舒服的方式还是对tweet创造prev field. 这也是merge K sorted list的标准做法.
class Tweet implements Comparable<Tweet>{
int timestamp;
int tweetId;
Tweet prev;
public Tweet(int tweetId, int timestamp){
this.tweetId = tweetId;
this.timestamp = timestamp;
}
public int compareTo(Tweet a){
return a.timestamp - this.timestamp;
}
}
/** Initialize your data structure here. */
HashMap<Integer, LinkedList<Tweet>> userTweet;
HashMap<Integer, HashSet<Integer>> userFollow;
int timestamp;
public Twitter() {
userTweet = new HashMap<Integer, LinkedList<Tweet>>();
userFollow = new HashMap<Integer, HashSet<Integer>>();
timestamp=0;
}
/** Compose a new tweet. */
public void postTweet(int userId, int tweetId){
if(!userTweet.containsKey(userId)) userTweet.put(userId, new LinkedList<Tweet>());
Tweet tweet = new Tweet(tweetId, timestamp);
if(userTweet.get(userId).size()>0) tweet.prev = userTweet.get(userId).peek();
userTweet.get(userId).addFirst(tweet);
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> ans = new ArrayList<Integer>();
PriorityQueue<Tweet> pq = new PriorityQueue<Tweet>();
if(userTweet.containsKey(userId) && userTweet.get(userId).size()>0) pq.offer(userTweet.get(userId).getFirst());
if(userFollow.containsKey(userId)){
for(Integer followee : userFollow.get(userId)){
System.out.println(userId + " " + followee);
if(userTweet.containsKey(followee)) System.out.println(userTweet.get(followee).size());
if(userTweet.containsKey(followee) && userTweet.get(followee).size()>0){
pq.offer(userTweet.get(followee).getFirst());
}
}
}
while(ans.size()<10 && !pq.isEmpty()){
Tweet t = pq.poll();
//if(t==null) continue;
ans.add(t.tweetId);
if(t.prev!=null)
pq.offer(t.prev);
}
return ans;
}
/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
public void follow(int followerId, int followeeId) {
if(followerId == followeeId) return;
if(!userFollow.containsKey(followerId)) userFollow.put(followerId, new HashSet<Integer>());
userFollow.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(userFollow.containsKey(followerId)){
userFollow.get(followerId).remove(followeeId);
}
}
}
Design Phone Directory
稍微快一点的做法是，用一个 Queue 维护目前所有空位，用 Set 维护目前所有已经使用的电话号码。主要 overhead 在于初始化的时候要花 O(n) 时间建队列，还有在 HashSet 里面做删除操作。别忘了number>=maxnumber是无效的.
这种做法是靠均摊复杂度平摊 cost 的典型例子。
public class PhoneDirectory {
HashSet<Integer> set;
Queue<Integer> queue;
int max = 0;
/** Initialize your data structure here
@param maxNumbers - The maximum numbers that can be stored in the phone directory. */
public PhoneDirectory(int maxNumbers) {
queue = new LinkedList<Integer>();
set = new HashSet<Integer>();
for(int i=0;i<maxNumbers;i++)
queue.add(i);
max = maxNumbers-1;
}
/** Provide a number which is not assigned to anyone.
@return - Return an available number. Return -1 if none is available. */
public int get() {
if(queue.isEmpty()) return -1;
int ans = queue.poll();
set.add(ans);
return ans;
}
/** Check if a number is available or not. */
public boolean check(int number) {
return !set.contains(number) && number<=max;
}
/** Recycle or release a number. */
public void release(int number) {
if(set.contains(number)){
set.remove(number);
queue.add(number);
}
}
}
/**
* Your PhoneDirectory object will be instantiated and called as such:
* PhoneDirectory obj = new PhoneDirectory(maxNumbers);
* int param_1 = obj.get();
* boolean param_2 = obj.check(number);
* obj.release(number);
*/
这题的另一种比较省空间的做法是用 BitSet，就看对 API 的熟悉程度了。
bitset.nextClearBit(smallestFreeIndex);
bitset.clear(number);
bitset.get(number) == false;
bitset.set(smallestFreeIndex);
All O`one Data Structure
这道题基本思路就是用一个map存key:value, 另外一个map存value:key. 同时维护最大的key和最小的key,使得操作都是O(1)的复杂度.
开始写的解法,用了TreeMap存, 其实都用hashmap就可以.
几个细节
- arraylist.remove(2) 是基于index的, arraylist.remove(Integer.valueOf(2))是值为2的Integer
- Long.valueOf 返回的是Long Object, Long.parseInt是long type
public class AllOne {
HashMap<String, String> k2v;
TreeMap<String, ArrayList<String>> v2k;
/** Initialize your data structure here. */
public AllOne() {
k2v = new HashMap<String, String>();
v2k = new TreeMap<String, ArrayList<String>>(new Comparator<String>(){
public int compare(String s1, String s2){
return Integer.parseInt(s1)-Integer.parseInt(s2);
}
});
}
/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
String addOne(String key){
char[] arr = key.toCharArray();
int i=arr.length-1;
while(i>=0&&arr[i]=='9') {arr[i]='0'; i--;}
if(i>=0){
arr[i] = (char)(((arr[i]-'0')+1)+'0');
return new String(arr);
}
else{
StringBuilder sb = new StringBuilder("1");
sb.append(new String(arr));
return sb.toString();
}
}
String decOne(String key){
char[] arr = key.toCharArray();
int i=arr.length-1;
while(i>=0&&arr[i]=='0') {arr[i]='9'; i--;}
if(i>=0){
arr[i] = (char)(((arr[i]-'0')-1)+'0');
return new String(arr);
}
return "";
}
public void inc(String key) {
if(!k2v.containsKey(key)){
k2v.put(key, "1");
if(!v2k.containsKey("1")) v2k.put("1", new ArrayList<String>());
v2k.get("1").add(key);
}
else{
String value = k2v.get(key);
String newValue = addOne(value);
k2v.put(key, newValue);
v2k.get(value).remove(key);
if(v2k.get(value).size()==0) v2k.remove(value);
if(!v2k.containsKey(newValue)) v2k.put(newValue, new ArrayList<String>());
v2k.get(newValue).add(key);
}
}
/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
public void dec(String key) {
if(!k2v.containsKey(key)){
return;
}
else if(k2v.get(key).equals("1")){
k2v.remove(key);
v2k.get("1").remove(key);
if(v2k.get("1").size()==0) v2k.remove("1");
}
else{
String value = k2v.get(key);
String newValue = decOne(value);
k2v.put(key, newValue);
v2k.get(value).remove(key);
if(v2k.get(value).size()==0) v2k.remove(value);
if(!v2k.containsKey(newValue)) v2k.put(newValue, new ArrayList<String>());
v2k.get(newValue).add(key);
}
}
/** Returns one of the keys with maximal value. */
public String getMaxKey() {
if(v2k.isEmpty() || v2k.get(v2k.lastKey()).size()==0)
return "";
return v2k.get(v2k.lastKey()).get(0);
}
/** Returns one of the keys with Minimal value. */
public String getMinKey() {
if(v2k.isEmpty()) return "";
if(v2k.isEmpty() || v2k.get(v2k.firstKey()).size()==0)
return "";
return v2k.get(v2k.firstKey()).get(0);
}
}