巨硬巨难的送命OA题 :(

转自leetcode discussion:  

Assume, there is a Data store which stores documents, where each document has a field, documentDate, of string type in the format YYYYMMDDhhmmss.

Assume there is an Ap

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

that would be made to GetDocumentsCount when startDateTime is 19700225000000 and the endDateTime is 20190430000000

what will be optimal solution?

目测可以用datadog那种多级bucket的思路解决 本质上就是线段树

求solution啊

关键词已经给你了 如果不懂请自行股沟 但是我觉得OA的话一个map就够了并不需要最优解

lc19890306 发表于 2019-9-22 10:45
关键词已经给你了 如果不懂请自行股沟 但是我觉得OA的话一个map就够了并不需要最优解

我怀疑我们理解的题目不一样 不一样。。可能是我没理解，这题不需要实现GetDocumentsCount， 所以不需要线段树吧，只是给个区间，实现GetDocumentsInRangeCount让调用GetDocumentsCount次数最少

hankok 发表于 2019/09/22 11:08:51
我怀疑我们理解的题目不一样 不一样。。

我说的是内部的实现 如果只是要求call的次数 我觉得应该考虑是在前半年还是后半年 具体还是分级做加减法吧

没学过线段树之类的…我naive的想法就是，timestamp本质上就是个非十进制的int，所以简化问题为，假如起始时间为444，结束时间为666，求它们之间的doc count，并且可以用X来作为query parameter的尾缀(比如query 45X会return 450 451 452… 459这10个bucket里的doc数量count的total)，那么至少要query多少次？我觉得就是444 445 446 447 448 449 45X 46X 47X 48X 49X 5XX 60X 61X 62X 63X 64X 65X 660 661 662 663 664 665 666一共这么多次，也就是在不超越结束日期的情况下，进行incremental query，每次query时greedily使用最多个的X作为尾缀。
是不是我想得太简单了？还请大神们解读一下

想问一下楼主是哪天的HE?

Dirty小熊猫 发表于 2019-10-9 04:15
想问一下楼主是哪天的HE?

不是我的，一楼有link