Design / OOD类算法题
Logger Rate Limiter
public class Logger {
Map<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 result = false;
if (!map.containsKey(message) || map.get(message) + 10 <= timestamp) {
result = true;
}
if (result) {
map.put(message, timestamp);
}
return result;
}
}
Design Hit Counter
解法一： 用queue来做，在hit()和getHits()这两个function里都加上remove方法。因为如果只在getHits()里加remove方法的话，如果hit()的调用频率远高于getHits()的调用频率，而call一次getHits()时，我们会话费很多的时间去remove，用户的体验就不是很好。
public class HitCounter {
Queue<Integer> queue;
/** Initialize your data structure here. */
public HitCounter() {
queue = new LinkedList<Integer>();
}
/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
public void hit(int timestamp) {
remove(timestamp);
queue.offer(timestamp);
}
/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
public int getHits(int timestamp) {
remove(timestamp);
return queue.size();
}
private void remove(int timestamp) {
while (!queue.isEmpty() && queue.peek() + 300 <= timestamp) {
queue.poll();
}
}
}
解法二：circular array
public class HitCounter {
int[] times;
int[] hits;
int N;
/** Initialize your data structure here. */
public HitCounter() {
N = 300;
times = new int[N];
hits = new int[N];
}
/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
public void hit(int timestamp) {
int index = timestamp % 300;
if (times[index] == timestamp) {
hits[index]++;
} else {
times[index] = timestamp;
hits[index] = 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 total = 0;
for (int i = 0; i < 300; i++) {
if (timestamp - 300 < times[i]) {
total += hits[i];
}
}
return total;
}
}
Design Phone Directory
用一个queue来循环available number，用一个set来存正在被使用的number。
public class PhoneDirectory {
Queue<Integer> availableQueue;
Set<Integer> usedSet;
int maxNumbers;
/** Initialize your data structure here
@param maxNumbers - The maximum numbers that can be stored in the phone directory. */
public PhoneDirectory(int maxNumbers) {
this.maxNumbers = maxNumbers;
availableQueue = new LinkedList<Integer>();
usedSet = new HashSet<Integer>();
for (int i = 0; i < maxNumbers; i++) {
availableQueue.add(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 (availableQueue.isEmpty()) {
return -1;
}
int num = availableQueue.poll();
usedSet.add(num);
return num;
}
/** Check if a number is available or not. */
public boolean check(int number) {
return number >= 0 && number < maxNumbers && !usedSet.contains(number);
}
/** Recycle or release a number. */
public void release(int number) {
if (!usedSet.contains(number)) {
return;
}
usedSet.remove(number);
availableQueue.offer(number);
}
}
Design Tic-Tac-Toe
可以只用两个一维数组来记录每一个row和每一个col当前的sum，用两个变量来记录两条对角线当前的sum。这样做的好处就是我们不用维护一个二维的数组了，也不用每次走完一步，就扫一遍这个人是不是已经赢了。时间和空间上都优化了。
public class TicTacToe {
int n;
int[] rows;
int[] cols;
int diagonal;
int anti_diagonal;
/** Initialize your data structure here. */
public TicTacToe(int n) {
this.n = n;
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) {
// define player moves + 1, player2 moves -1
int toAdd = player == 1 ? 1 : -1;
rows[row] += toAdd;
cols[col] += toAdd;
if (row == col) {
diagonal += toAdd;
}
if (row + col == n - 1) {
anti_diagonal += toAdd;
}
if (Math.abs(rows[row]) == n || Math.abs(cols[col]) == n || Math.abs(diagonal) == n || Math.abs(anti_diagonal) == n) {
return player;
}
return 0;
}
}
Design Snake Game
- 把二维坐标转化成一维坐标
- 用set记录当前身子的position
- deque内的顺序就是身体的顺序
- 每次新到一个点，就把新的position加到deque的头上，同时更新set
- 如果当前的食物没有被吃完且新的这个点就是食物的点，就不要remove tail了，否则remove tail且把tail index从set里也remove掉
- 有一个edge case是新的头恰好是之前身子的尾，所以我们在检查set是否contains新的头的时候，记得先把之前的尾给remove了，之后如果发现新的头就是食物的位置，就把尾的index加回到set里，否则就把尾从deque里给remove了。
public class SnakeGame {
Set<Integer> set;
Deque<Integer> deque;
int width, height;
int[][] food;
int i = 0;
/** 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.width = width;
this.height = height;
this.food = food;
set = new HashSet<Integer>();
deque = new ArrayDeque<Integer>();
set.add(0);
deque.offer(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 x = deque.peekFirst() / width;
int y = deque.peekFirst() % width;
if (direction.equals("U")) {
x -= 1;
} else if (direction.equals("L")) {
y -= 1;
} else if (direction.equals("R")) {
y += 1;
} else {
x += 1;
}
int index = x * width + y;
set.remove(deque.peekLast());
if (x < 0 || x >= height || y < 0 || y >= width || set.contains(index)) {
return -1;
}
set.add(index);
deque.addFirst(index);
if (i < food.length && food[i][0] == x && food[i][1] == y) {
set.add(deque.peekLast());
return ++i;
}
deque.pollLast();
return i;
}
}
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，等等。
- 用OOD的思想，有一个User类，user是可以follow别人，unfollow别人，发一条tweet。
- 有一个Tweet类，一条tweet有一个tweetId和一个timstamp，还有一个prev指针。
- 在Tweet类有prev指针，就可以不必维护一个tweetList了，通过一个tweetHead，便可以得到这个user的所有tweet。
public class Twitter {
private static int timestamp = 0;
Map<Integer, User> userMap;
/** Initialize your data structure here. */
public Twitter() {
userMap = new HashMap<Integer, User>();
}
/** Compose a new tweet. */
public void postTweet(int userId, int tweetId) {
timestamp++;
if (!userMap.containsKey(userId)) {
User u = new User(userId);
userMap.put(userId, u);
}
userMap.get(userId).post(tweetId, 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> result = new ArrayList<Integer>();
if (!userMap.containsKey(userId)) {
return result;
}
Set<Integer> users = userMap.get(userId).followed;
Queue<Tweet> queue = new PriorityQueue<Tweet>(new Comparator<Tweet>(){
public int compare(Tweet t1, Tweet t2) {
return t2.timestamp - t1.timestamp;
}
});
for (int user: users) {
Tweet t = userMap.get(user).tweetHead;
if (t != null) {
queue.offer(t);
}
}
int i = 0;
while (!queue.isEmpty() && i < 10) {
Tweet t = queue.poll();
result.add(t.id);
i++;
if (t.prev != null) {
queue.offer(t.prev);
}
}
return result;
}
/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
public void follow(int followerId, int followeeId) {
if (!userMap.containsKey(followerId)) {
User u = new User(followerId);
userMap.put(followerId, u);
}
if (!userMap.containsKey(followeeId)) {
User u = new User(followeeId);
userMap.put(followeeId, u);
}
userMap.get(followerId).follow(followeeId);
}
/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
public void unfollow(int followerId, int followeeId) {
if (followerId == followeeId || !userMap.containsKey(followerId)) {
return;
}
userMap.get(followerId).unfollow(followeeId);
}
}
class Tweet {
int id;
int timestamp;
Tweet prev;
public Tweet(int id, int timestamp) {
this.id = id;
this.timestamp = timestamp;
}
}
class User {
int id;
Set<Integer> followed;
Tweet tweetHead;
public User(int id) {
this.id = id;
followed = new HashSet<Integer>();
follow(id);
tweetHead = null;
}
public void follow(int followeeId) {
followed.add(followeeId);
}
public void unfollow(int followeeId) {
followed.remove(followeeId);
}
public void post(int tweetId, int timestamp) {
Tweet t = new Tweet(tweetId, timestamp);
t.prev = tweetHead;
tweetHead = t;
}
}
下面是没有建User类的写法，比较类似，不过还是更推荐第一种
public class Twitter {
private static int timestamp;
Map<Integer, Set<Integer>> followsMap;
Map<Integer, Tweet> tweetMap;
/** Initialize your data structure here. */
public Twitter() {
timestamp = 0;
followsMap = new HashMap<Integer, Set<Integer>>();
tweetMap = new HashMap<Integer, Tweet>();
}
/** Compose a new tweet. */
public void postTweet(int userId, int tweetId) {
timestamp++;
Tweet t = new Tweet(tweetId, timestamp);
if (tweetMap.containsKey(userId)) {
t.prev = tweetMap.get(userId);
}
tweetMap.put(userId, t);
}
/** 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> result = new ArrayList<Integer>();
if (!followsMap.containsKey(userId)) {
followsMap.put(userId, new HashSet<Integer>());
}
if (!followsMap.get(userId).contains(userId)) {
followsMap.get(userId).add(userId);
}
Set<Integer> users = followsMap.get(userId);
if (!users.contains(userId)) {
users.add(userId);
}
Queue<Tweet> queue = new PriorityQueue<Tweet>(new Comparator<Tweet>(){
public int compare(Tweet t1, Tweet t2) {
return t2.timestamp - t1.timestamp;
}
});
for (int user: users) {
if (!tweetMap.containsKey(user)) {
continue;
}
queue.offer(tweetMap.get(user));
}
int i = 0;
while (!queue.isEmpty() && i < 10) {
Tweet t = queue.poll();
result.add(t.id);
i++;
if (t.prev != null) {
queue.offer(t.prev);
}
}
return result;
}
/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
public void follow(int followerId, int followeeId) {
if (!followsMap.containsKey(followerId)) {
followsMap.put(followerId, new HashSet<Integer>());
}
if (!followsMap.containsKey(followeeId)) {
followsMap.put(followeeId, new HashSet<Integer>());
}
followsMap.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 (followerId == followeeId || !followsMap.containsKey(followerId)) {
return;
}
followsMap.get(followerId).remove(followeeId);
}
}
class Tweet {
int id;
int timestamp;
Tweet prev;
public Tweet(int id, int timestamp) {
this.id = id;
this.timestamp = timestamp;
}
}