CareerCup

//Worst case Time Complexity: O(nlogn) where n is the number of log entries in the stream.
public class Event{
	long time;
	int tag;
}

public class Node{
	int time;
	int tag;
	Node prev;
	Node next;
	
	public Node(int tagVal,int timeVal){
		time = timeVal;
		tag = tagVal;
	}
}

public class StreamSvc{
	private TreeMap<Integer,Node> bst;
	private Set<Integer> tags;
	private int interval;
	
	
	public StreamSvc(int intervalSize){
		bst = new TreeMap<Integer,Node>();
		tagToTime = new HashSet<Integer>();
		interval = intervalSize;
	}
	
	public void readStream(Iterator<Event> it){
		while(it.hasNext()){
			Event e = it.next();
			Integer val = bst.lowerKey(e.time - interval);
			while(val != null){
				Node n = bst.get(val);
				while(n != null){
					if(n.next != null){
						n.next.prev = null;
						n.next = null;
					}
					tags.remove(n.tag);
					n = n.prev;
				}
				Integer next = bst.lowerKey(val);
				bst.remove(val);
				val = next;
			}
			if(!tags.contains(e.tag)){
				Node x = new Node(e.time,e.tag);
				if(bst.containsKey(x.time)){
					Node v= bst.get(x.time);
					v.next = x;
					x.prev = v;
				}
				bst.put(x.time,x);
				tags.add(x.tag);
			}
		}
		
		
	}

}

Can you explain your thought process a little bit? @divm01986

what's example input/output?

@divm01986 Is it necessary to have the tags set? You already have the tags in the tree.

Also, e.time - interval will not give you the timestamp of the last X seconds if the event is from yesterday. But probably in this kind of problem it is a normal assumption to make that the time of last event processed is the current time.Is it necessary to have the tags set? You already have the tags in the tree.

Also, e.time - interval will not give you the timestamp of the last X seconds if the event is from yesterday. But probably in this kind of problem it is a normal assumption to make that the time of last event processed is the current time.