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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 谢谢! : 第一问可以避免排序吗? 感觉复杂度很高啊 : : the
| g*****i 发帖数: 91 | 5 in last 30 mins
我的理解是和当前时间比,所以维护一个hashmap>就可以吧,
每读一行看时间是不是和当前时间差超过30分钟,如果不是,就把page_id放到hashset
里。
二爷请指教一下...
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 排序nlogn,不排序n : 不过一般这样的文件可能已经排好续了 : 如果用Clojure的话,一行代码应该可以搞定。
| p*****2 发帖数: 21240 | 6
hashset
没看过原题,不过感觉这样就可以了。
【在 g*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : in last 30 mins : 我的理解是和当前时间比,所以维护一个hashmap>就可以吧, : 每读一行看时间是不是和当前时间差超过30分钟,如果不是,就把page_id放到hashset : 里。 : 二爷请指教一下...
|
|