## biswajit.86

BAN USER```
Map<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)

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

Yes, you need to override the compareTo method and use the id field in the comparision

- biswajit.86 May 21, 2016