There are n (id, value) pairs, where id is an integer between 1 and n and value is a string. No two pairs have the same id.
Design a stream that takes the n pairs in an arbitrary order, and returns the values over several calls in increasing order of their ids.
Implement the OrderedStream class:
OrderedStream(int n) Constructs the stream to take n values and sets a current ptr to 1.
String[] insert(int id, String value) Stores the new (id, value) pair in the stream. After storing the pair:
If the stream has stored a pair with id = ptr, then find the longest contiguous incrementing sequence of ids starting with id = ptr and return a list of the values associated with those ids in order. Then, update ptr to the last id + 1.
class OrderedStream {
Map<Integer, String> map;
int ptr;
int n;
public OrderedStream(int n) {
map = new HashMap();
ptr = 1;
this.n = n;
}
public List<String> insert(int id, String value) {
map.put(id, value);
List<String> res = new ArrayList();
if (map.containsKey(ptr)) {
int i = ptr;
for (; i <= this.n; i ++) {
if (map.containsKey(i)) {
res.add(map.get(i));
} else {
break;
}
}
ptr = i;
}
return res;
}
}
/**
* Your OrderedStream object will be instantiated and called as such:
* OrderedStream obj = new OrderedStream(n);
* List<String> param_1 = obj.insert(id,value);
*/