There is a stream of n(idKey, value) pairs arriving in an arbitrary order, where idKey is an integer between 1 and n and value is a string. No two pairs have the same id.
Design a stream that returns the values in increasing order of their IDs by returning a chunk (list) of values after each insertion. The concatenation of all the chunks should result in a list of the sorted values.
Implement the OrderedStream class:
OrderedStream(int n) Constructs the stream to take n values.
String[] insert(int idKey, String value) Inserts the pair (idKey, value) into the stream, then returns the largest possible chunk of currently inserted values that appear next in the order.
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
// Note that the values ordered by ID is ["aaaaa", "bbbbb", "ccccc", "ddddd", "eeeee"].
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"].
// Concatentating all the chunks returned:
// [] + ["aaaaa"] + ["bbbbb", "ccccc"] + [] + ["ddddd", "eeeee"] = ["aaaaa", "bbbbb", "ccccc", "ddddd", "eeeee"]
// The resulting order is the same as the order above.
Constraints:
1 <= n <= 1000
1 <= id <= n
value.length == 5
value consists only of lowercase letters.
Each call to insert will have a unique id.
Exactly n calls will be made to insert.
Solutions
Solution 1
1 2 3 4 5 6 7 8 91011121314151617
classOrderedStream:def__init__(self,n:int):self.data=[None]*nself.ptr=0definsert(self,idKey:int,value:str)->List[str]:self.data[idKey-1]=valueans=[]whileself.ptr<len(self.data)andself.data[self.ptr]:ans.append(self.data[self.ptr])self.ptr+=1returnans# Your OrderedStream object will be instantiated and called as such:# obj = OrderedStream(n)# param_1 = obj.insert(idKey,value)
1 2 3 4 5 6 7 8 9101112131415161718192021222324
classOrderedStream{privateString[]data;privateintptr;publicOrderedStream(intn){data=newString[n];ptr=0;}publicList<String>insert(intidKey,Stringvalue){data[idKey-1]=value;List<String>ans=newArrayList<>();while(ptr<data.length&&data[ptr]!=null){ans.add(data[ptr++]);}returnans;}}/** * Your OrderedStream object will be instantiated and called as such: * OrderedStream obj = new OrderedStream(n); * List<String> param_1 = obj.insert(idKey,value); */
1 2 3 4 5 6 7 8 910111213141516171819202122
classOrderedStream{public:vector<string>data;intptr=0;OrderedStream(intn){data.resize(n,"");}vector<string>insert(intidKey,stringvalue){data[idKey-1]=value;vector<string>ans;while(ptr<data.size()&&data[ptr]!="")ans.push_back(data[ptr++]);returnans;}};/** * Your OrderedStream object will be instantiated and called as such: * OrderedStream* obj = new OrderedStream(n); * vector<string> param_1 = obj->insert(idKey,value); */
1 2 3 4 5 6 7 8 910111213141516171819202122232425
typeOrderedStreamstruct{data[]stringptrint}funcConstructor(nint)OrderedStream{data:=make([]string,n)returnOrderedStream{data,0}}func(this*OrderedStream)Insert(idKeyint,valuestring)[]string{this.data[idKey-1]=valuevarans[]stringforthis.ptr<len(this.data)&&this.data[this.ptr]!=""{ans=append(ans,this.data[this.ptr])this.ptr++}returnans}/** * Your OrderedStream object will be instantiated and called as such: * obj := Constructor(n); * param_1 := obj.Insert(idKey,value); */
1 2 3 4 5 6 7 8 910111213141516171819202122232425
classOrderedStream{privateptr:number;privatevals:string[];constructor(n:number){this.ptr=0;this.vals=newArray(n);}insert(idKey:number,value:string):string[]{this.vals[idKey-1]=value;constres=[];while(this.vals[this.ptr]!=null){res.push(this.vals[this.ptr]);this.ptr++;}returnres;}}/** * Your OrderedStream object will be instantiated and called as such: * var obj = new OrderedStream(n) * var param_1 = obj.insert(idKey,value) */
structOrderedStream{ptr:usize,vals:Vec<Option<String>>,}/** * `&self` means the method takes an immutable reference. * If you need a mutable reference, change it to `&mut self` instead. */implOrderedStream{fnnew(n:i32)->Self{Self{ptr:0,vals:vec![None;nasusize],}}fninsert(&mutself,id_key:i32,value:String)->Vec<String>{self.vals[(id_key-1)asusize]=Some(value);letmutres=Vec::new();whileself.ptr<self.vals.len(){ifletSome(s)=&self.vals[self.ptr]{res.push(s.clone());self.ptr+=1;}else{break;}}res}}