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:
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
.
Example:
Input ["OrderedStream", "insert", "insert", "insert", "insert", "insert"] [[5], [3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]] Output [null, [], ["aaaaa"], ["bbbbb", "ccccc"], [], ["ddddd", "eeeee"]] Explanation OrderedStream os= new OrderedStream(5); os.insert(3, "ccccc"); // Inserts (3, "ccccc"), returns []. os.insert(1, "aaaaa"); // Inserts (1, "aaaaa"), returns ["aaaaa"]. os.insert(2, "bbbbb"); // Inserts (2, "bbbbb"), returns ["bbbbb", "ccccc"]. os.insert(5, "eeeee"); // Inserts (5, "eeeee"), returns []. os.insert(4, "ddddd"); // Inserts (4, "ddddd"), returns ["ddddd", "eeeee"].
Constraints:
1 <= n <= 1000
1 <= id <= n
value.length == 5
value
consists only of lowercase letters.insert
will have a unique id.
n
calls will be made to insert
.use std::collections::HashMap;
struct OrderedStream {
ptr: i32,
pairs: HashMap<i32, String>,
n: i32,
}
impl OrderedStream {
fn new(n: i32) -> Self {
let pairs = HashMap::new();
let ptr = 1;
OrderedStream { ptr, pairs, n }
}
fn insert(&mut self, id: i32, value: String) -> Vec<String> {
self.pairs.insert(id, value);
let mut res = vec![];
if self.ptr == id {
for i in id..=self.n {
if let Some(v) = self.pairs.get(&i) {
res.push(v.to_string());
self.ptr += 1;
} else {
break;
}
}
}
res
}
}
#[test]
fn test() {
let mut obj = OrderedStream::new(5);
assert_eq!(obj.insert(3, "ccccc".to_string()), vec_string![]);
assert_eq!(obj.insert(1, "aaaaa".to_string()), vec_string!["aaaaa"]);
assert_eq!(
obj.insert(2, "bbbbb".to_string()),
vec_string!["bbbbb", "ccccc"]
);
assert_eq!(obj.insert(5, "eeeee".to_string()), vec_string![]);
assert_eq!(
obj.insert(4, "ddddd".to_string()),
vec_string!["ddddd", "eeeee"]
);
}