Compress Number List II – AlgoBox by dietpepsi
Given a stream of positive integers, design a data structure supporting two operations:
1.
2.
The compressed format is like this, for example:
Given
Return
time. The difference is for this problem we need to maintain intervals rather than numbers.
The trick is to use the start point as key and endpoint as value.
-- or we can just use binary index tree.
第一题和大家都一样 Populating Next Right Pointers in Each Node II，follow up 空间优化到constant，面试官是个说话很快的老美，一直很nice的引导我
第二题 给一个stream的integer，然后要提供query返回当前所有的range，举例: 读了8, 6, 4, 7 这个时候query的结果是 4, 6-8，时间不多了就说了一下做法，时间空间的tradeoff什么的。
Read full article from Compress Number List II – AlgoBox by dietpepsi
Given a stream of positive integers, design a data structure supporting two operations:
1.
void insert(int x) insert an element.2.
String toString() print out the integers in a compressed format.The compressed format is like this, for example:
Given
[8, 6, 4, 7]Return
"4, 6-8"Method 1: BST
Using a balanced BST we could perform insertion, deletion and search in time. The difference is for this problem we need to maintain intervals rather than numbers.The trick is to use the start point as key and endpoint as value.
-- or we can just use binary index tree.
class DisjointIntervalTree {
private TreeMap<Integer, Integer> intervals = new TreeMap<>();
public void insert(int x) {
if (intervals.containsKey(x)) return;
Map.Entry<Integer, Integer> lower = intervals.lowerEntry(x);
if (lower != null && lower.getValue() >= x) return;
//try to merge intervals
int start = x, end = x;
Map.Entry<Integer, Integer> higher = intervals.higherEntry(x);
if (higher != null && higher.getKey() == x + 1) {
end = higher.getValue();
intervals.remove(x + 1);
}
if (lower != null && lower.getValue() == x - 1) {
start = lower.getKey();
intervals.remove(start);
}
intervals.put(start, end);
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
for (Map.Entry<Integer, Integer> interval : intervals.entrySet()) {
int start = interval.getKey();
int end = interval.getValue();
builder.append(start);
if (end > start)
builder.append("-").append(end);
builder.append(",");
}
builder.deleteCharAt(builder.length() - 1);
return builder.toString();
}
}
http://www.1point3acres.com/bbs/thread-146729-1-1.html第一题和大家都一样 Populating Next Right Pointers in Each Node II，follow up 空间优化到constant，面试官是个说话很快的老美，一直很nice的引导我
第二题 给一个stream的integer，然后要提供query返回当前所有的range，举例: 读了8, 6, 4, 7 这个时候query的结果是 4, 6-8，时间不多了就说了一下做法，时间空间的tradeoff什么的。
Read full article from Compress Number List II – AlgoBox by dietpepsi
