https://docs.google.com/document/d/1qxA2wps0IhVRWULulQ55W4SGPMu2AE5MkBB37h8Dr58
11。log start log finish 没太看懂题
有一个Class叫Logger,它有两个函数,一个是LogStart(int logId, int timestamp),一个是LogFinish(int logId, int timestamp)。Log开始时LogStart会被调用,log结束时LogFinish会被调用。要求是实现这两个函数,并打印已经结束的log,打印log时要按log的开始时间排序。
interface Logger {
void started(long timestamp, String requestId);
void finished(long timestamp, String requestId);
void print();
}
started(100, "1")
started(101, "2")
finished(102, "2")
started(103, "3")
finished(104, "1")
finished(105, "3")
print()
Expected Output:
$1 start at 100 end at 104
$2 start at 101 end at 102
$3 start at 103 end at 105
思路:
和lru差不多, hash map + double linked list维护顺序(hanxiao yan:弱弱问一下,这个log的题为啥要用double linkedlist呀,用single linkedlist不可以么)(editor:这里可以用single list,作者因为觉得和lru题目相似,直接用的dll,这里不需要操作中间节点,感觉可以用single list)
Node {
String id;
long start;
long end;
}
Map<String , Node> map
start 的时候加入map,设置好开始时间,end时间还没有设置
finish的时候设置好node的end值,然后从map中移除
打印的话直接遍历一遍dll即可
code
Provider: null
public class MyLogger implements Logger {
private class Node {
String id;
long start;
long end;
Node prev;
Node next;
public Node(String id, long start) {
this.id = id;
this.start = start;
end = -1;
}
}
Node head, tail;
Map<String, Node> map;
public MyLogger() {
head = new Node(“”, -1);
tail = new Node(“”, -1);
head.next = tail;
tail.prev = head;
map = new HashMap<>();
}
@Override
public void started(String id, long time) {
Node curr = new Node(id, time);
map.put(id, curr);
add(curr);
}
@Override
public void finished(String id, long time) {
Node curr = map.get(id);
if(curr != null && curr.end == -1) {
curr.end = time;
map.remove(id);
}
}
public void print() {
Node curr = head.next;
while(curr != tail) {
if(curr.end != -1) {
System.out.println(curr.id + “start at” +u curr.start + “ end at ” + curr.end);
}
curr = curr.next;
}
}
private void add(Node curr) {
if(curr == null) return ;
curr.next = tail;
curr.prev = tail.prev;
tail.prev.next = curr;
tail.prev = curr;
}
}
log start log finish (频率 8)
第四轮:
中国小哥
log timestamp那道,实现start(id, ts), end(id, ts), 按start time顺序打印log
有一个Class叫Logger,它有两个函数,一个是LogStart(int logId, int timestamp),一个是LogFinish(int logId, int timestamp)。Log开始时LogStart会被调用,log结束时LogFinish会被调用。要求是实现这两个函数,并打印已经结束的log,打印log时要按log的开始时间排序。
interface Logger {
void started(long timestamp, String requestId);
void finished(long timestamp, String requestId);
}
started(100, "1")
started(101, "2")
finished(102, "2")
started(103, "3")
finished(104, "1")
finished(105, "3")
Expected Output:
$1 start at 100 end at 104
$2 start at 101 end at 102
$3 start at 103 end at 105
思路:
和lru差不多, hash map + double linked list维护顺序
Node {
String id;
long start;
long end;
}
Map<String , Node> map
start 的时候加入map,设置好开始时间,end时间还没有设置
finish的时候设置好node的end值,然后从map中移除
打印的话直接遍历一遍dll即可
code
Provider: Xing
public class MyLogger implements Logger {
private class Node {
String id;
long start;
long end;
Node prev;
Node next;
public Node(String id, long start) {
this.id = id;
this.start = start;
end = -1;
}
}
Node head, tail;
Map<String, Node> map;
public MyLogger() {
head = new Node(“”, -1);
tail = new Node(“”, -1);
head.next = tail;
tail.prev = head;
map = new HashMap<>();
}
@Override
public void started(String id, long time) {
Node curr = new Node(id, time);
map.put(id, curr);
add(curr);
}
@Override
public void finished(String id, long time) {
Node curr = map.get(id);
if(curr != null && curr.end == -1) {
curr.end = time;
map.remove(id);
}
}
public void print() {
Node curr = head.next;
while(curr != tail) {
if(curr.end != -1) {
System.out.println(curr.id + “start at” + curr.start + “ end at ” + curr.end);
}
curr = curr.next;
}
}
private void add(Node curr) {
if(curr == null) return ;
curr.next = tail;
curr.prev = tail.prev;
tail.prev.next = curr;
tail.prev = curr;
}
}