Cartesian trees could also help.
Cartesian tree takes O(n) time to build, and if you have the count of how
many nodes are there in a tree rooted at any node, by just having the index
of the element also stored there. Once the cartesian tree is built, just
traverse from the root and find how many
http://megaupload.com/?d=NB80UORF
password:ebooksclub.org
Its a 7 zip file.
On Tue, Apr 19, 2011 at 11:05 PM, D.N.Vishwakarma@IITR deok...@gmail.comwrote:
Cracking the Coding Interview by *Gayle
of the grid, then we have only 2n-1 elements to chose n
biggest elements from.
So, can we prove that taking Ist quardrant as (n-2)x(n-3) would leave
n-biggest out? What is the criterion to chose the Ist quardrant?
manish...
--
*From:* topojoy biswas topojoy.bis
consider these arrays:
10 9 8 5 3 2 1
and
13 12 11 10 9 8 7
form a grid like this:
109 8 5 321
7 17 1615 1210 98
8 18 1716 1311 10 9
9 19 1817 1412 12 10
10 20 1918 1513 12 11
11 21 20
22, 2010 at 10:03 AM, topojoy biswas
topojoy.bis...@gmail.comwrote:
consider these arrays:
10 9 8 5 3 2 1
and
13 12 11 10 9 8 7
form a grid like this:
109 8 5 321
7 17 1615 1210 98
8 18 1716 1311 10 9
9 19
But you dont need a swap filesystem right?
On Thu, Jul 22, 2010 at 8:41 AM, Anand anandut2...@gmail.com wrote:
Yes you do need virtual memory even if you have 4GB of RAM. Because if you
do not have virtual memory, you could not have uniform addressing. and that
prevents you creating the final
@anand
very true... i also realized after writing it.
Only a hashtable would do.
but i have another qs in mind...perfect hash functions are built on an
expected probability of collition.
Even if we do rehashing, that also does not give an upper bound on the
number of times we need to rehash.
number the nodes in the tree like this:
root=1
left child of root=2
right child of root=3
left child of {left child of root}=4
right child of {left child of root}=5
left child of {right child of root}=6
right child of {right child of root}=7
something similar to how you create a heap out of an
a linked list with pointer to the head and tail stored containing each
request response tuple, and the pointers to the tuple stored in a hashtable
described below.
a hash table of size n containing the hash of the request identifier as the
hashfunction, and the pointer to the element in the
