Google 面试技术题，求教考点在哪？

Google面试的一道技术题，愣是没弄明白这题的考点在哪，哪个算法？面试官最后提到要用到一个data structure，面完后想了几天也没想到他到底考的什么。题目如下：

Say you have a web server and a logging component. The component has two functions as below. When a request come in to the web server, started(string, int) get called first, then completed(string, int) get called.

+started(reqId:string, timestamp:int64)
+completed(reqId:string, timestamp:int64)

You are required to print out a logging statement for each request in the following format. Sorted by the started time.

Request {ReqId1} started at {Y1} finished at {Z1}
Request {ReqId2} started at {Y2} finished at {Z2}
Request {ReqId3} started at {Y3} finished at {Z3}
Request {ReqId4} started at {Y4} finished at {Z4}

我当时想到可能是考多线程，说了半天多线程，他最后说我miss了题目的point。。。新手请教大家这题到底要考啥？



补充内容 (2019-2-20 18:30):
请教了一位Google的面试官，他给出的答案见7楼 https://www.1point3acres.com/bbs ... 069&pid=5710718

需要加一个超时处理，否则会卡在里面。这是我的Revised版本：

void completed(timestamp, requestId) {
  byId[requestId].tFinished = timestamp;
  while(!queue.isEmpty()) {

    if (queue.peek().tFinished != null) {
         byId.remove(queue.peek().id);
        LOGGING FINISH STATEMENT
    } else {
        if (queue.peek().tStarted < now - timeout) {
               byId.remove(queue.peek().id);
               LOGGING TIMEOUT STATEMENT
        }
    }
  }
}

Solution from Google SWE interviewer. Thanks to @bowenzh

Pseudocode:    建一个普通的class即可，class Request {id, tStarted, tFinished}
Queue<Request> queue;
HashMap<String, Request> byId;
void started(timestamp, requestId) {
  Request req = new Request(id=requestId, tStarted=timestamp);
  queue.enqueue(req);
  byId[requestId] = req;
}
void completed(timestamp, requestId) {
  byId[requestId].tFinished = timestamp;
  while(queue.peek().tFinished != null) {
    byId.remove(queue.peek().id);
    LOGGING STATEMENT
  }
}

步惊云 发表于 2019-2-7 06:16
只能瞎猜了..

1)request进来先进先出, 那就是你理解的. 每一个的起始跟结束时间的差只看task, 但是起始 ...

一个request进来先call started(), 执行完task后call completed(), int parameter就是要打印在log里的时间, 打印的顺序要按started()里的这个int的值顺序.

不会真像楼上那位说的就是排序吧, call started()的时候把ReqId and Y存进hash map, call completed()的时候排序+打印hash map的内容?

是不是考排序啊……

Y1 Y2 Y3 Y4 跟 Z1 Z2 Z3 Z4 之间有什么前后关系么？

在started里面用个 ConcurrentHashMap 把 start timestamp 用 reqid 存起来，然后在completed里面再取出来？

alexws 发表于 2019-2-7 05:20
Y1 Y2 Y3 Y4 跟 Z1 Z2 Z3 Z4 之间有什么前后关系么？

在started里面用个 ConcurrentHashMap 把 start ti ...

Y, Z是request 的开始时间和结束时间, Y1->Z1, Y2->Z2, Y3->Z3, Y4->Z4. log的打印顺序要求按Y排序. 他最后提到我miss one data structure. 可能就是说的hashmap..他不是想问concurrency..

qingzi1993 发表于 2019-2-7 01:37
是不是考排序啊……

考Queue, 答案见我上面的回复

alexws 发表于 2019-2-7 05:20
Y1 Y2 Y3 Y4 跟 Z1 Z2 Z3 Z4 之间有什么前后关系么？

在started里面用个 ConcurrentHashMap 把 start ti ...

考Queue, 答案见我上面的回复

步惊云 发表于 2019-2-7 06:16
只能瞎猜了..

1)request进来先进先出, 那就是你理解的. 每一个的起始跟结束时间的差只看task, 但是起始 ...

终于弄清楚了. 应该是考Queue, 答案见我上面的回复