由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 问一个EPI(elements of programming interviews)里的题
相关主题
刷完一遍leetcode之后要干嘛Element of programming interview 300题
EPI是本好书leetcode vs EPI
EPI (Elements of Programming Interviews) 要看多少?google面试问题
leetcode刷三遍,CC150 , EPI各读一遍问两道微软题
The time complexity on finding the kth largest element in a老题目一问
Palantir新鲜面经find elements in an array that sum up to a given number
问一道google面试题google 一题
[求解]codility online test的cannon打炮问题Find the intersection of two sorted arrays【扩展】
相关话题的讨论汇总
话题: epi话题: interviews话题: elements话题: complexity
进入JobHunting版参与讨论
1 (共1页)
b********a
发帖数: 70
1
you are given a server log file containing billions of lines. Each line
contains a number of fields. For this problem the relevant field is a string
denoting the page that was accessed.
Write a function to read a log file line with O(1) time complexity, and a
function to find the k most visited pages with O(k) time complexity.
想不出来怎么可以用这么少的时间做到
呼唤大牛
c*******e
发帖数: 373
2
我觉得问题的关键在于文件不可能是乱序的
否则 O(k) 时间内,连扫描一遍所有的行都不够。乱序文件,如果有些行没有扫描到,
那就不可能给出"k most visited"
所以整个题目可以解释为:
1. 该怎么把那个大log文件预处理一下,变成一个有利于寻找"most visited"的数据结
构,然后另存到文件,或者全部、部分缓存到内存
2. 在1的基础上,再写题目要求的两个函数
1 (共1页)
进入JobHunting版参与讨论
相关主题
Find the intersection of two sorted arrays【扩展】The time complexity on finding the kth largest element in a
明天10点要去面bloomberg了,求Bless!Palantir新鲜面经
array a1,a2,... ,an, b1,b2,..., bn问一道google面试题
Time complexity[求解]codility online test的cannon打炮问题
刷完一遍leetcode之后要干嘛Element of programming interview 300题
EPI是本好书leetcode vs EPI
EPI (Elements of Programming Interviews) 要看多少?google面试问题
leetcode刷三遍,CC150 , EPI各读一遍问两道微软题
相关话题的讨论汇总
话题: epi话题: interviews话题: elements话题: complexity