CareerCup

1) Since the size of the Window is not relevant nor is the TimeStamp, this would break down to checking for the occurrence of an ip address that is more than an arbitrary k value.
2) For a stream or a static file:
a. HashMap<Ip, Frequency>
b. Increment each ip as they occur
c. Keep a counter with (value = k) and check (while inserting a value) that if it crosses K.
d. Return that IP and break.

Please let me know if my thinking is correct.

I assume both timestamps and ip address are represented in string.
All you need to do is create a Hash Table.

Map<String,List<String>> map=new HashMap<();
for data in stream
	if(!map.containsKey(ip))
		map.put(ip, new ArrayList<String>(Arrays.asList(timestamp)));
	else map.get(ip).add(timestamp);

List<String> result=new ArrayList();
for key in map.keySet()
	if(map.get(key).size()>=k) 
		result.add(key);

return result;

I assume the time window will be specified. My approach: use a double edge queue to keep timestamp/IP pairs within T and a hash map of IP/counter to count the IP address occurrences. For every new entry coming from file or stream, decrement the count of deque's front's IP in the hash map and pop it from deque's front. Then keep adding new entries while incrementing their counters in a loop until we exceed current_time+T. Check against K and print the offender when updating hash map. Then repeat.

I assume the window size T is expected. This is about the frequency of a string within a variable size sliding window. A combination of double edge queue (to store timestamp/IP) and a hash map (key=IP, value=count) will do. And a couple of loops.

why should use deque? why not just normal (priority by time)queue?

Why should use deque??? why not normal priority queue by timestamp?

IS YOUR CAPS LOCK LOCKED?