programmer
BAN USER- 0of 0 votes
AnswersQuestion from my friend's interview.
- programmer in United States
Problem statement : How would you design a logging system for something like Google , you should be able to query for the number of times a URL was opened within two time frames.
i/p : start_time , end_time , URL1
o/p : number of times URL1 was opened between start and end time.
Some specs : Database is not an optimal solution A URL might have been opened multiple times for given time stamp. A URL might have been opened a large number of times within two time stamps. start_time and end_time can be a month apart. time could be granular to a second.| Report Duplicate | Flag | PURGE
Groupon Software Engineer / Developer
Yes, doublylinked list would be feasible than singlyLinkedlist.
- programmer August 30, 2012Linkedlist+HashTable
Linkedlist: Stores the elements
HashTable: Key=value, Value=some structure (containing one pointer to store the address of the value, one "count" variable - to store the number of duplicate values in the list and one linkedlist to store the address of the duplicate values).
1. Enqueue : into hash table and list.
If the value to be inserted is a duplicate value then increment the count(in the structure of the HashValue O(1)). Insert the value in the linkedlist and store tohis address into the pointer(in the structure of the HashValue). O(1) - Thus u can keep track of even the duplicate values easily.
2. Dequeue: Remove the value from the linked list. - O(1)
- Find the value in the Hash and check the value of the count -O(1). If it is >0 then decrement it and delete the respective address from the linkedList(in the structue of the HAshValue) - O(1).
3. Delete: First find the element in the HashTable - O(1). And the follow the same procedure as above(Dequeue). O(1)
4.IsNumberPresent: can be found from the HashTable. O(1)
Comments are Appreciated.
@atul gupta: can u elaborate ur explanation?
- programmer August 23, 2012
In java using hashMap
- programmer March 06, 2015