peeyush.fun
BAN USERWell, my approach: We will be traversing from a[n] to a[0] and b[n] to b[0].
COMPARING
(A)Max[a[n],b[n]) + Max[unvisited nodes:a[i],b[j]](captured by variable i and j) (this can also be found in o(1)).
WITH
(B)Maximum two visited node (they are still unvisited wrt each other and is referred to as visited only wrt to Max(a[n],b[n])). (captured by variable k and l)
===> ACTION:
if(A) > (B), put (A) in the result and compute next highest unvisited element by comparing highest unvisited (this will be used in next iteration to comparison)
(if(a[i] > b[j]) i++ else j++)
else
update k and l.
(i admit the tricky part is to get these visited maximum right as if not optimized this can ruin the performance to o(n2) and if optimized properly it can lead to o(n) solution (at cost of memory. i think it can be done by maintaining in memory the state (visited/unvisited) in some matrix which will capture the visit of 1 value wrt to another-basically DP approach)).
Any comments are welcome!
the question appears to be simple. we can use a stack for this. push and pop are o(1) as done at the same end of list and min (i assume it to be the least recently used) is also o(1). Am i missing something here?
- peeyush.fun July 29, 2010
There is a flaw with this design. If we divide the logs over say 1000 machines and ask each of them for top 100 ips with max hit. In this case if some ip say occurred at say 100+ rank in all 1000 machines such that even if does not qualify to be in top 100 results of a machine but combined that ip falls in top 100.
- peeyush.fun July 30, 2010The mapping(better the logging) has to be sophisticated enough to process the logs from same ip to single (or lesser) number of machines.