g*****i
发帖数: 91 | 1 Given a log file which consists of timestamp, customer ID, page id visited
by that particular customer. Write a function to return all customers who
have visited 5 unique pages in last 30 mins
这个题目最近看面经见得很多，还有类似的是这个：
http://www.mitbbs.com/article_t/JobHunting/32644779.html | h****n
发帖数: 1093 | 2 sort the log by timestamp
read the log and insert the entry to map(5)>
This is enough for this problem, whenever the vector reach size 5, push the
result into the result vector
For another problem, when read new entry, you need to pop_front and push_
back the new pageID in the tail of the mapped vector.
at the same time, maintain a map(5), int counter> and the
maximum counter value and page list.
【在 g*****i 的大作中提到】
: Given a log file which consists of timestamp, customer ID, page id visited
: by that particular customer. Write a function to return all customers who
: have visited 5 unique pages in last 30 mins
: 这个题目最近看面经见得很多，还有类似的是这个：
: http://www.mitbbs.com/article_t/JobHunting/32644779.html
| g*****i
发帖数: 91 | 3 谢谢！
第一问可以避免排序吗？ 感觉复杂度很高啊
the
【在 h****n 的大作中提到】
: sort the log by timestamp
: read the log and insert the entry to map(5)>
: This is enough for this problem, whenever the vector reach size 5, push the
: result into the result vector
: For another problem, when read new entry, you need to pop_front and push_
: back the new pageID in the tail of the mapped vector.
: at the same time, maintain a map(5), int counter> and the
: maximum counter value and page list.
| p*****2
发帖数: 21240 | 4
排序nlogn，不排序n
不过一般这样的文件可能已经排好续了
如果用Clojure的话，一行代码应该可以搞定。
【在 g*****i 的大作中提到】
: 谢谢！
: 第一问可以避免排序吗？ 感觉复杂度很高啊
:
: the
| g*****i
发帖数: 91 | 5 in last 30 mins
我的理解是和当前时间比，所以维护一个hashmap>就可以吧，
每读一行看时间是不是和当前时间差超过30分钟，如果不是，就把page_id放到hashset
里。
二爷请指教一下...
【在 p*****2 的大作中提到】
:
: 排序nlogn，不排序n
: 不过一般这样的文件可能已经排好续了
: 如果用Clojure的话，一行代码应该可以搞定。
| p*****2
发帖数: 21240 | 6
hashset
没看过原题，不过感觉这样就可以了。
【在 g*****i 的大作中提到】
: in last 30 mins
: 我的理解是和当前时间比，所以维护一个hashmap>就可以吧，
: 每读一行看时间是不是和当前时间差超过30分钟，如果不是，就把page_id放到hashset
: 里。
: 二爷请指教一下...
|
|
