DesignLogStorageSystem [source code]
public class DesignLogStorageSystem {
static
/******************************************************************************/
public class LogSystem {
private PriorityQueue<long[]> pq;
int[] yearDays = new int[60]; //number of days till the end of year[1970 + index]
int[][] monthDays = new int[60][12]; //number of days till the end of month[1 + index]
public LogSystem() {
pq = new PriorityQueue<long[]>((a,b) -> (int) (a[1] - b[1]));
Arrays.fill(yearDays, 365);
for (int i = 0; i < 60; i++) {
if (isLeap(1970 + i))
yearDays[i]++;
if (i > 0)
yearDays[i] += yearDays[i - 1];
}
for (int i = 0; i < 60; i++)
for (int j = 0; j < 12; j++) {
monthDays[i][j] = getMonthDayNum(i, j);
if (j > 0)
monthDays[i][j] += monthDays[i][j - 1];
}
}
public void put(int id, String timestamp) {
long time = translateTime(timestamp, "", false);
pq.offer(new long[]{id, time});
}
public List<Integer> retrieve(String s, String e, String gra) {
List<Integer> res = new ArrayList<>();
Object[] ls = pq.toArray();
long[][] lss = new long[ls.length][];
for (int i = 0; i < ls.length; i++)
lss[i] = (long[]) ls[i];
Arrays.sort(lss, (a,b) -> (int) (a[1] - b[1]));
long start = translateTime(s, gra, true), end = translateTime(e, gra, false);
for (long[] log : lss)
if (log[1] < end && log[1] >= start)
res.add((int) log[0]);
return res;
}
public long translateTime(String timestamp, String gra, boolean isStart) {
long res = 0;
String[] tokens = timestamp.split("\\:");
int[] nums = new int[6];
for (int i = 0; i < 6; i++)
nums[i] = Integer.parseInt(tokens[i]);
int[] weights = calculateWeights(nums);
if (gra.equals("")) {
for (int i = 0; i < 6; i++) {
if (i < 3)
res += weights[i];
else
res += weights[i] * (long) nums[i];
}
return res;
} else {
int index = getGraLevel(gra);
if (isStart) {
for (int i = 0; i < 6; i++)
if (i <= index) {
if (i < 3)
res += weights[i];
else
res += nums[i] * (long) weights[i];
}
} else {
int[] next = incrementTime(nums, index);
int[] newWeights = calculateWeights(next);
for (int i = 0; i < 6; i++)
if (i <= index) {
if (i < 3)
res += newWeights[i];
else
res += next[i] * (long) newWeights[i];
}
}
return res;
}
}
public int[] calculateWeights(int[] nums) {
int[] weights = new int[6];
//0-based tokens
weights[5] = 1; //second
weights[4] = weights[5] * 60; //minute
weights[3] = weights[4] * 60; //hour
//1-based tokens
weights[2] = nums[2] == 1 ? 0 : (nums[2] - 1) * 24 * weights[3]; //day
weights[0] = 24 * weights[3] * (nums[0] - 1970 - 1 >= 0 ? yearDays[nums[0] - 1970 - 1] : 0); //year
weights[1] = 24 * weights[3] * (nums[1] - 1 - 1 >= 0 ? monthDays[nums[0] - 1970][nums[1] - 1 - 1] : 0); //month
return weights;
}
public int[] incrementTime(int[] nums, int index) {
int[] limits = {
Integer.MAX_VALUE, //year
13, //month
getMonthDayNum(nums[0], nums[1]) + 1, //day
25, //hour
60, //minute
60, //second
};
int[] res = Arrays.copyOf(nums, 6); //avoid side effects / mutation
while (index >= 0) {
if (++res[index] > limits[index]) {
res[index] = 0;
index--;
} else break;
}
return res;
}
public int getGraLevel(String gra) {
// translate Year:Month:Day:Hour:Minute:Second to index
if (gra.equals("Year"))
return 0;
else if (gra.equals("Month"))
return 1;
else if (gra.equals("Day"))
return 2;
else if (gra.equals("Hour"))
return 3;
else if (gra.equals("Minute"))
return 4;
else
return 5;
}
public boolean isLeap(long year) {
if (year % 100 == 0) {
if (year % 400 == 0)
return true;
}
else if (year % 4 == 0)
return true;
return false;
}
public int getMonthDayNum(int year, int month) {
switch (month) {
case 2: return isLeap(year) ? 29 : 28;
case 4: return 30;
case 6: return 30;
case 9: return 30;
case 11: return 30;
default: return 31;
}
}
}
/******************************************************************************/
public static void main(String[] args) {
DesignLogStorageSystem.LogSystem tester;
tester = new DesignLogStorageSystem.LogSystem();
tester.put(1,"2017:01:01:23:59:59");
tester.put(2,"2017:01:01:22:59:59");
tester.put(3,"2016:01:01:00:00:00");
System.out.println(tester.retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Year")); //1,2,3
System.out.println(tester.retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Hour")); //1,2
tester = new DesignLogStorageSystem.LogSystem();
tester.put(1,"2017:01:01:23:59:59");
tester.put(2,"2017:01:02:23:59:59");
System.out.println(tester.retrieve("2017:01:01:23:59:59","2017:01:02:23:59:59","Month")); //1,2
}
}
design问题的一个关键, 之前也讨论过, 就是internal structure的选择;
这里一个小疑问: 冒号是否有必要存储? 这个的答案是很明显的; 更进一步的, separator本身的存储问题, 可能在大部分类似的问题中, 都可以用这个思路;
大概看了一下题目, 好像关键是设计一个高效的树状查询结构?
感觉好像就是一个trie比较好用? 而且note还给出了branching factor的上限, 感觉也是鼓励了这个想法;
不过这个问题好像没有必要给这么一个复杂? 虽然看起来好像有好几个stage的key, 但是整个所有的这些key组成的是一个时间, 而时间本身是有一个线性的大小的关系的, 所以直接就所有的key全都转换成为数字, 这样一个timestamp直接就转换成一个int, 好像也可以? 这样做最起码存储会方便很多, 至于read的时候怎么做呢? 是不是只要代入gra这个概念, 来找到一个需要的query的int的范围就行了呢?
好像可以; 不对, 这个问题有一个致命的缺陷, 这样做最后的int的范围是会overflow的: 如果是2017年, 最高精确度到秒的话, 最后能够达到的int的最大值是一个6开头的11位数. 这个是非常大的;
那么用long就是了? 好像可以?
瞄了一眼editorial, 总共有两个做法, 第一个做法就是这种convert的做法. 但是还有一个第二种做法, 所以这个题目确实是有一个比这种convert更好的做法的;
我就做一下这个笨办法的就行了, editorial的提示是, 这种做法是可以AC的;
Arrays.copyOf的用法;
copyOf(int[] original, int newLength)
original – original array
newLength – copy of original array
为了让put更方便, 一个直接的想法就是用PriorityQueue, 但是用PriorityQueue的话, retrieve的时候又有点麻烦, 因为这种结构的get可以说是一种destructive的;
This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).
好像有办法;
写了挺久, 好不容易写出来这个算法, 但是这个算法是有问题的, 最后的问题还是在溢出上面:
java> System.out.println(Long.MAX_VALUE)
9223372036854775807
java> long d = 31536000 * 2017
long d = -816397440
java> long d = Long.MAX_VALUE
long d = 9223372036854775807
查了一下, 好像可以解决:
In Java, all math is done in the largest data type required to handle all of the current values. So, if you have int int, it will always do the math as an integer, but int long is done as a long.
In this case, the 102410241024*80 is done as an Int, which overflows int.
The "L" of course forces one of the operands to be an Int-64 (long), therefore all the math is done storing the values as a Long, thus no overflow occurs.
所以在operand上面直接一个强制的cast就行了;
这个题目写到这个时候的时候基本已经可以确定是写歪了, 就是实现一个parse time这么简单的功能, 却花了大量的时间, 这个明显不可能是题目希望考察的点. 后面想了一下, 好像JAVA本身是有这么一个把时间做成秒的API的, 只不过我自己忘记了;
算了, 干脆自己想办法解决一下这个问题好了; 这种转换为epoch时间的任务也可以看成是一个对自己的锻炼; 这个问题的一个难点在于, 从month开始的这些token, 你都是可以直接就乘以对应的权重(比如一个month有多少秒)就行了; 但是year是不行的, 就是因为有这个闰年问题的存在; 比如2017年, 你应该把从1970年开始, 到2016年的所有的day的数量加起来, 而不是直接2017乘以2017年有多少day;
意识到计算上有一个严重的问题: hour, minute, second这几个全都是0-based的, 所以可以直接用token乘以权重; 但是year month day这几个, 全都是1-based, 所以直接乘以权重是不行的, 比如是计算当前这个, 比如month前面的所有month贡献的day/second的总和;
注意我这里两个array的设置方式, 都是 起点+index 这样的设置方式; 所以index这种0-based的值, 很多时候更适合被看成是增量; 很多时候涉及到这种频繁的0-based和1-based之间的转换的时候, 会觉得容易混淆, 其实只要你自己记好你的index代表什么(增量between year and start point year, 或者用例子来记: [0]对应1970 year之类的), 以及每一个entry代表什么(比如如果是一个统计值, 统计的终点是到哪里);
吭哧吭哧总算是写完了! 最后的速度是194ms (43%), 居然还可以接受; 总体来说虽然这个题目花了很多时间, 不过还是学到了很多的东西; 其实这个题目本身算法上面的东西并不难, 难就难在整个solution本身的设计上面, 估计这个也是为什么这个题目的tag上面有一个design; 能够:
- 在脑子里envision, 将会接收到什么样的数据input;
- 怎样个性化的存储这些数据;
- 怎样有效的输出这些数据;
我觉得都是挺有意思的锻炼内容;
这个算法本身设计的难点在于translate这个函数; 因为同样的一个timestamp, 在不同的环境下, 有不同的convert方式, 但是我又希望这几种convert能够被一个函数涵盖, 所以就要做几个用来分情况讨论的flag参数; 函数本身其实也不算难写;
刚开始我有一个坏习惯我没有意识到, 就是喜欢用hardcode的方式(多重if或者switch)来完成一个lookup的操作. 但是后面想想, 这种操作最好的方法还是用一个dictionary或者assoc list类型的数据结构来做比较好;
这个解法本身只能说其实时间复杂度并不好, 在put的时候其实已经是需要NlgN来维护PriorityQueue了, 而最后get的时候, 其实也并没有很轻松; 因为PriorityQueue不支持ordered iterator, 所以最后只能先让PriorityQueue吐出来, 然后重新再来一个sort; 最后并没有做到O(N)的复杂度;
这题看到最后editorial的时候想到一个问题, 既然无法保证ordered iteration, 那这个PriorityQueue还有卵用? 直接用list或者array来做算了! 算了不改了, 知道这个问题就行了; furthermore, 还是要搞清楚PriorityQueue的局限性: 只能完成获取最值或者destructive ordered iteration这样的操作; 单纯的observative ordered iteration并无法完成;
另外, 搜了一下标准的API做法:
You can simply parse it to java.util.Date using java.text.SimpleDateFormat and call it's getTime() function. It will return the number of milliseconds since Jan 01 1970.
public static final String strDate = "04/28/2016";
try {
Long millis = new SimpleDateFormat("MM/dd/yyyy").parse(strDate).getTime();
} catch (ParseException e) {
e.printStackTrace();
}
估计方便很多;
Date d = SimpleDateFormat(String pattern).parse(String strDate); It parses a string (formatted date) by a pattern specified and returns a java.util.Date object.
editorial1的做法就是这种convert, 不过他最后的代码比我好像短很多:
This solution is based on converting the given timestap into a number. This can help because retrieval of Logs lying within a current range can be very easily done if the range to be used can be represented in the form of a single number. Let's look at the individual implementations directly.
这个说的很有道理, 而且是一个诱因式的分析;
为了避免year的权重带来的overflow, 他也是使用了选择起点的做法, 不过他的起点选择的是2000而不是1970;
But, since, we need to take care of granularity, before doing the conversion, we need to consider the effect of granularity. Granularity, in a way, depicts the precision of the results. Thus, for a granularity corresponding to a Day, we need to consider the portion of the timestamp considering the precision upto Day only. The rest of the fields can be assumed to be all 0's. After doing this for both the start and end timestamp, we do the conversion of the timestamp with the required precision into seconds.
对于granularity的解释;
public class LogSystem {
ArrayList < long[] > list;
public LogSystem() {
list = new ArrayList < long[] > ();
}
public void put(int id, String timestamp) {
int[] st = Arrays.stream(timestamp.split(":")).mapToInt(Integer::parseInt).toArray();
list.add(new long[] {convert(st), id});
}
public long convert(int[] st) {
st[1] = st[1] - (st[1] == 0 ? 0 : 1);
st[2] = st[2] - (st[2] == 0 ? 0 : 1);
return (st[0] - 1999L) * (31 * 12) * 24 * 60 * 60 + st[1] * 31 * 24 * 60 * 60 + st[2] * 24 * 60 * 60 + st[3] * 60 * 60 + st[4] * 60 + st[5];
}
public List < Integer > retrieve(String s, String e, String gra) {
ArrayList < Integer > res = new ArrayList();
long start = granularity(s, gra, false);
long end = granularity(e, gra, true);
for (int i = 0; i < list.size(); i++) {
if (list.get(i)[0] >= start && list.get(i)[0] < end)
res.add((int) list.get(i)[1]);
}
return res;
}
public long granularity(String s, String gra, boolean end) {
HashMap < String, Integer > h = new HashMap();
h.put("Year", 0);
h.put("Month", 1);
h.put("Day", 2);
h.put("Hour", 3);
h.put("Minute", 4);
h.put("Second", 5);
String[] res = new String[] {"1999", "00", "00", "00", "00", "00"};
String[] st = s.split(":");
for (int i = 0; i <= h.get(gra); i++) {
res[i] = st[i];
}
int[] t = Arrays.stream(res).mapToInt(Integer::parseInt).toArray();
if (end)
t[h.get(gra)]++;
return convert(t);
}
}
整个代码简短很多;
我前面只意识到PriorityQueue是多余的, 没有意识到其实这里连最后get的时候的sort也是多余的. 完全不知道当时脑子里在想的是什么? 这个问题为什么要先sort? 没有道理的;
他这个解法, granularity函数里面的这个Map如果做成instance var的话, 可能能省掉不少时间, 不然每一个get call都要来两次, 太浪费时间了;
注意他convert函数里面对头三个token的处理, 同样是一个基于1-based value属性造成的处理; 在不考虑闰年问题的情况下, 其实主要就是一个conditional -1的处理;
他这里看到两个问题, 就是针对这个题目本身, 有两个地方是不需要做的, 但是我没有看出来, 还是做了;
一个就是, leap year造成的年和二月的天数问题是不需要判断的; 他这里的做法, 没一个月都当成31天, 每一年都当成12 * 31天; 为什么可以这样做? 其实date这种形式的数据, 虽然很常见, 但是其背后的复杂性以后都没有考虑过; 这种hierarchical的结构, 其实很想是比如string of int这样的parse结构; 更深层次的:
Digit Weights vs. Soft Constraints
如果你单纯的是想要设计一套weight系统来反映这个hierarchy, 那么需要的逻辑其实非常类似425上课的时候soft constraint的设计准则; 比如你希望year的权重比month重, 这个代表的是什么意思呢? 实际上的意思就是按照这套weight系统convert出来的这个int, 要让year更大的date的int始终比year较小的date的int要大; 也就是权重小的digit只用来break ties of higher digits; 这个跟当时我们425做soft constraints的时候的诉求是一样的; 当时解决的办法就是, 你只要保证比如digit month能达到的最大contribution都小于digit year哪怕1的contribution就行了;
这里也是一样的问题. 其实完成一个soft constraint就是这个题目唯一的要求. 当然像我这样把epoch完整的实现出来, 是可以达到这个目的的, 但是这个就属于overkill了; 事实上, 直接用类似int string那样的做法也可以, 当然不能直接照搬2^R这样的做法: 比如year digit的weight, 应该是等于month digit的domain_upper_limit * month_weight就行了;
另外一个他这里做到的优化, 就是granularity在end的时候的处理: 我的做法就是很规矩的, 不仅要加, 而且还要进位; 但是事实上你想一想, 这个进位是有必要的吗? 这个end要完成的其实就是一个not inclusive的上限; 你比如一个digit你+1, 然后超限了, 进位和不进位, 对于convert to int这样一个事情, 有差别吗? 没有的! 你设计的时候就是保证高一位的weight等于低一位的位置一个进位所需的数值; 进位这个东西只有在你int to string的时候, 才有作用, 而单纯做int的时候, 进位是没有必要的;
完成了这两个优化之后, 这个人的代码确实比我的代码简练的多; 我的接近150行, 人家的这个四五十行就搞定了;
editorial2在以上解法的基础上进行优化:
This method remains almost the same as the last approach, except that, in order to store the timestamp data, we make use of a TreeMap instead of a list, with the key values being the timestamps converted in seconds form and the values being the ids of the corresponding logs.
Thus, the put method remains the same as the last approach. However, we can save some time in retrieve approach by making use of tailMap function of TreeMap, which stores the entries in the form of a sorted navigable binary tree. By making use of this function, instead of iterating over all the timestamps in the storage to find the timestamps lying within the required range(after considering the granularity as in the last approach), we can reduce the search space to only those elements whose timestamp is larger than(or equal to) the starting timestamp value.
所以其实还是有一种可以维护的时候是ordered, 然后iterate的时候也可以nondestructively ordered的结构的, 这样的一个结构在查询的时候就高效很多;
public class LogSystem {
TreeMap < Long, Integer > map;
public LogSystem() {
map = new TreeMap < Long, Integer > ();
}
public void put(int id, String timestamp) {
int[] st = Arrays.stream(timestamp.split(":")).mapToInt(Integer::parseInt).toArray();
map.put(convert(st), id);
}
public long convert(int[] st) {
st[1] = st[1] - (st[1] == 0 ? 0 : 1);
st[2] = st[2] - (st[2] == 0 ? 0 : 1);
return (st[0] - 1999L) * (31 * 12) * 24 * 60 * 60 + st[1] * 31 * 24 * 60 * 60 + st[2] * 24 * 60 * 60 + st[3] * 60 * 60 + st[4] * 60 + st[5];
}
public List < Integer > retrieve(String s, String e, String gra) {
ArrayList < Integer > res = new ArrayList();
long start = granularity(s, gra, false);
long end = granularity(e, gra, true);
for (long key: map.tailMap(start).keySet()) {
if (key >= start && key < end)
res.add(map.get(key));
}
return res;
}
public long granularity(String s, String gra, boolean end) {
HashMap < String, Integer > h = new HashMap();
h.put("Year", 0);
h.put("Month", 1);
h.put("Day", 2);
h.put("Hour", 3);
h.put("Minute", 4);
h.put("Second", 5);
String[] res = new String[] {"1999", "00", "00", "00", "00", "00"};
String[] st = s.split(":");
for (int i = 0; i <= h.get(gra); i++) {
res[i] = st[i];
}
int[] t = Arrays.stream(res).mapToInt(Integer::parseInt).toArray();
if (end)
t[h.get(gra)]++;
return convert(t);
}
}
代码本身的差别不大; 注意这个tailMap函数完成的是一个减少搜索空间的优化, 但是减少的只有start这一边的, 并不能两边都做到优化;
结果这个破算法并不如我的算法快? 这个真的不理解了; 或许是大问题的波动;
分析认为TreeMap是用红黑tree实现的, 所以put就是O(lgN)的操作; get的复杂度取决于start的取值;
这个是submission上面的一个解法, 虽然不是最优解, 但是很简练:
public class LogSystem {
Map<Integer, String> map;
public LogSystem() {
map = new HashMap<>();
}
public void put(int id, String timestamp) {
map.put(id, timestamp);
}
public List<Integer> retrieve(String s, String e, String gra) {
int x = 0;
switch(gra) {
case "Year":
x = 4;
break;
case "Month":
x = 7;
break;
case "Day":
x= 10;
break;
case "Hour":
x = 13;
break;
case "Minute":
x = 16;
break;
case "Second":
x = 19;
break;
}
s = s.substring(0, x);
e = e.substring(0, x);
List<Integer> ans=new ArrayList<>();
for (Integer i: map.keySet()) {
String ss = map.get(i).substring(0, x);
if (ss.compareTo(s) >= 0 && ss.compareTo(e) <= 0) {
ans.add(i);
}
}
return ans;
}
}
所以直接利用string本身的compare就行了, 不用专门convert;
这个是discussion上面一个类似的:
public class LogSystem {
List<String[]> timestamps = new LinkedList<>();
List<String> units = Arrays.asList("Year", "Month", "Day", "Hour", "Minute", "Second");
int[] indices = new int[]{4,7,10,13,16,19};
public void put(int id, String timestamp) { timestamps.add(new String[]{Integer.toString(id), timestamp}); }
public List<Integer> retrieve(String s, String e, String gra) {
List<Integer> res = new LinkedList<>();
int idx = indices[units.indexOf(gra)];
for (String[] timestamp : timestamps) {
if (timestamp[1].substring(0, idx).compareTo(s.substring(0, idx)) >= 0 &&
timestamp[1].substring(0, idx).compareTo(e.substring(0, idx)) <= 0) res.add(Integer.parseInt(timestamp[0]));
}
return res;
}
}
首先用indexOf来完成一个gra to index的转换, 很聪明; 跟以前的string.contains/indexOf的做法不完全一样, 但是异曲同工;
其他的基本好像就差不多了;
discussion的高票解好像基本都是鼓吹concise而不是速度. 事实上, 这样一个题目, 太鼓吹速度确实是没有太大的意思的; 比如这种indexOf的做法肯定没有一个switch快, 但是代码看起来就精神多了;
关于这个string的compare:
For compareTo method, there is a link: http://docs.oracle.com/javase/7/docs/api/java/lang/String.html#compareTo%28java.lang.String%29
The comparison is based on the Unicode value of each character in the strings.
感觉这个做法应该是这个题目更加鼓励的一个做法, 因为题目本身提到了有padding. 而这个string compare的原理其实就是依赖于, 冒号separator之间是严格对位, 也就是必然形成tie的; 所以lexicographic的order正好就可以保证是我们需要的这个hierarchical的order;
注意这个做法, 对于end, 没有做这个+1的操作, 而是在判断的时候, 对end进行inclusive来替代达到同样的效果; 确实简单很多; 当然这个是需要一些insight的: 自己画几个例子只要取值止步于gra对应的位置的时候, 就一定可以保证正确;
比如你想要分析这个结论的时候, 有一个uncertainty就是不知道我们的这个pool里面实际上到底有多少个timestamp, 以及它们之间并不是连续的; 那么我们处理掉这个uncertainty就行了. 我们就假设每一秒的timestamp我们都有; 然后我们再来几个example query来看看gra这个东西到底怎么理解好一些;
事实上, 这个不+1, 而是转换为inclusive end的做法, 只是用于string compare的做法? 举几个例子的出来的结论; 如果使用convert to int的做法, 还真的无法保证可以这么简单的处理; 这里也更进一步证实string compare确实是出题者本意希望我们采取的做法;
一个思路类似的JAVA8解法:
class LogSystem {
Map<Integer,String> map = new HashMap<>();
public enum Index {
Year(4), Month(7), Day(10), Hour(13), Minute(16), Second(19);
int idx; Index(int i) {this.idx = i;}
}
public void put(int id, String timestamp) { map.put(id,timestamp); }
public List<Integer> retrieve(final String s, final String e, String gra) {
Function<String, String> fn = str -> str.substring(0, Index.valueOf(gra).idx);
return map.entrySet().stream().filter(
x -> fn.apply(x.getValue()).compareTo(fn.apply(s)) >= 0 && fn.apply(x.getValue()).compareTo(fn.apply(e)) <= 0)
.collect(mapping(v -> v.getKey(), toList()));
}
}
学习一下这里stream和enum的解法;
这个是一个妹子给出的解法:
public class LogSystem {
private String min, max;
private HashMap<String, Integer> map;
private TreeMap<String, LinkedList<Integer>> logs;
public LogSystem() {
min = "2000:01:01:00:00:00";
max = "2017:12:31:23:59:59";
map = new HashMap<>();
map.put("Year", 4);
map.put("Month", 7);
map.put("Day", 10);
map.put("Hour", 13);
map.put("Minute", 16);
map.put("Second", 19);
logs = new TreeMap<>();
}
public void put(int id, String timestamp) {
if(!logs.containsKey(timestamp)) logs.put(timestamp, new LinkedList<>());
logs.get(timestamp).add(id);
}
public List<Integer> retrieve(String s, String e, String gra) {
int index = map.get(gra);
String start = s.substring(0, index)+min.substring(index), end = e.substring(0, index)+max.substring(index);
NavigableMap<String, LinkedList<Integer>> sub = logs.subMap(start, true, end, true);
LinkedList<Integer> ans = new LinkedList<>();
for (Map.Entry<String, LinkedList<Integer>> entry : sub.entrySet()) {
ans.addAll(entry.getValue());
}
return ans;
}
}
虽然miss掉了一些insight, 所以并不如之前的那些最优解, 但是透露出的很多信息还是值得学习的;
比如她这里就完成了我之前提到的, 把Map改成instance var的优化;
以及她对于gra的处理:
Given the granularity we can set a lower bound and upper bound of timestamp so we could do a range query using TreeMap. To get the lower bound we append a suffix of "2000:01:01:00:00:00" to the prefix of s and to get the upper bound we append a suffix of "2017:12:31:23:59:59" to the prefix of e.
其实还是挺有想法的; 跟正常的+1的做法非常类似, 只不过是在string的基础上直接完成(以feed给string的compare)而不是先convert成int;
另外注意她最后这里subMap的使用; 所以实际上TreeMap是可以完成两头的优化的;
discussion到目前看到的这几个解法其实都是一个普通的穷搜的解, 虽然有各种各样的优化, 但是本质其实都是差不多的;
我觉得这个题目好像还是可以用trie来做; 只不过目前discussion上面还是没有对应的解法; 后面再次回头来看这个题目的时候如果还是没有, 我就自己写一个算了;
trie解法的有点我认为是, 可以直接用subtree的概念来处理granularity;
Problem Description
You are given several logs that each log contains a unique id and timestamp. Timestamp is a string that has the following format: Year:Month:Day:Hour:Minute:Second, for example, 2017:01:01:23:59:59. All domains are zero-padded decimal numbers.
Design a log storage system to implement the following functions:
void Put(int id, string timestamp): Given a log's unique id and timestamp, store the log in your storage system.
int[] Retrieve(String start, String end, String granularity): Return the id of logs whose timestamps are within the range from start to end. Start and end all have the same format as timestamp. However, granularity means the time level for consideration. For example, start = "2017:01:01:23:59:59", end = "2017:01:02:23:59:59", granularity = "Day", it means that we need to find the logs within the range from Jan. 1st 2017 to Jan. 2nd 2017.
Example 1:
put(1, "2017:01:01:23:59:59");
put(2, "2017:01:01:22:59:59");
put(3, "2016:01:01:00:00:00");
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Year"); // return [1,2,3], because you need to return all logs within 2016 and 2017.
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Hour"); // return [1,2], because you need to return all logs start from 2016:01:01:01 to 2017:01:01:23, where log 3 is left outside the range.
Note:
- There will be at most 300 operations of Put or Retrieve.
- Year ranges from [2000,2017]. Hour ranges from [00,23].
- Output for Retrieve has no order required.
Difficulty:Medium
Total Accepted:2.6K
Total Submissions:5.6K
Contributor: fallcreek
Companies
snapchat
Related Topics
design string
Similar Questions
Design In-Memory File System
/**
- Your LogSystem object will be instantiated and called as such:
- LogSystem obj = new LogSystem();
- obj.put(id,timestamp);
- List
param_2 = obj.retrieve(s,e,gra);
*/