biswajit.86
BAN USERMap<Long,ConcurrentHashMap<Long,Long>> memorize =
Collections.synchronizedMap(new HashMap<Long, ConcurrentHashMap<Long,Long>>());
public static void main(String[] args) {
Example1 example=new Example1();
long start=System.nanoTime();
System.out.println(example.powerSimple(3,46));
long end=System.nanoTime();
System.out.println("simple done in "+ (end-start) );
start=System.nanoTime();
System.out.println(example.power(3,46));
end=System.nanoTime();
System.out.println("memorize done in "+ (end-start) );
}
public long power(long a, long b){
if(a==0 )
return 0;
if(b==0)
return 1;
if(b==1)
return a;
ConcurrentHashMap<Long, Long> values=memorize.get(a);
if(values==null){
memorize.put(a, new ConcurrentHashMap<Long, Long>() );
}
Long value=memorize.get(a).get(b);
if(value!=null)
return value;
if(b%2==0){
value=power(a,b/2) * power(a,b/2);
}else{
value=power(a,(b-1)/2) * power(a,(b-1)/2)*a;
}
memorize.get(a).put(b, value);
return value;
}
public long powerSimple(long a, long b){
if(a==0 )
return 0;
if(b==0)
return 1;
if(b==1)
return a;
if(b%2==0){
return power(a,b/2) * power(a,b/2);
}else{
return power(a,(b-1)/2) * power(a,(b-1)/2)*a;
}
}
Return:
8500964271916320249
simple power calc done in 679916 nanos
8500964271916320249
memorize power calc done in 46696 nanos
removing the post as I misunderstood the problem. thanks srini
- biswajit.86 April 23, 2014I understand this question to be finding the billionth user to hit google servers.This can be achieved by using the technique to find the median of n numbers in a distributed architecture.
If the server logs are arranged by timestamp(which they usually are), one needs to find the median of values on each server and send back the count to a master server.The master server counts the total of these values . If it is less than a billion , it discards the values to left of the median and subtracts the total number from the billion(call this x where x=billion-total). It then tries to find the x highest number on the undiscarded set
Create 2 data structure, a max-heap b ased on a array an a hashmap
The array is ordered according to the number of the hits. So an extra hit is a heapifyUp and a new hit is addition at the last index of the heap
The hashmap contains the item as key and its index in the previous heap structure as the value.When an item is popped out completely, it is removed from this hashmap.
Peek/Top: O(1)
Push: (O(logN) if it is a existing element
O(1) if it is a new element
Pop: This is ambiguous if pop decreases a hit or completely pops the element out. Whatever the answer, its a heap pop and hence it is O(logN)
Yes, you need to override the compareTo method and use the id field in the comparision
- biswajit.86 May 21, 2016