Re: [algogeeks] Inversion Count
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 nodes are there in the left subtree
from its left child node, and that is the number of inversions for the root
node. Keep doing this for all emenents and kep adding them to a counter.
When you have gone through all the n nodes, you have the total numbr of
inversions, that traversal would also take O(n) time.
When you are at any node, and you know its index in the array, all the
elements to the left sub-tree are inversions because all the elements to the
left of the node are to the left of in the actual array, and that this node
now holds all of the left side of the array rooted at its left child, so all
of them are inversions. And they are the only inversions possible for the
node in questions.
Let me know your views.
Regards
Topo.
On Thu, May 12, 2011 at 5:16 PM, Akshata Sharma
akshatasharm...@gmail.comwrote:
@Anshu:
My logic:
during merge step, lets say you have two array left and right (both are
sorted) and you are going to merge it.
l[i] represent the element of left arrray
r[j] represent the element of right array
if (r[j] l[i]) {
increase the inversion count by the number of elements lefts in left
array
put element r[j] into merged array
j++
} else {
no increase in count, just put the element r[i] into merged array
i++;
This will be O(nlogn) solution. Can we do better using BIT or segment
trees? Can you please provide me some hint of how to solve it using segment
trees, I just know the basics of it..
On Thu, May 12, 2011 at 5:00 PM, anshu mishra
anshumishra6...@gmail.comwrote:
explain your logic instead of posting code, use binary index tree or
segment tree or bst to solve this problem.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Topo.
There are days when solitude is a heady wine that intoxicates you with
freedom, others when it is a bitter tonic, and still others when it is a
poison that makes you beat your head against the wall. ~Colette
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] If anyone have this book please mail me Thanks in advance
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 Laakmannhttp://pothi.com/pothi/search/google?cx=014194668748364006794:ovhp_xhwczgcof=FORID:11query=Gayle%20Laakmannop=Searchform_id=google_cse_searchbox_form * -- **With Regards Deoki Nandan Vishwakarma IITR MCA Mathematics Department* * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Topo. There are days when solitude is a heady wine that intoxicates you with freedom, others when it is a bitter tonic, and still others when it is a poison that makes you beat your head against the wall. ~Colette -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] a google question
any element to the right of X in the same array is less than X. Any element to the top of X in the same column is less than X. so any element to the nrth east of X is less than X. All the elements to the south west, (including X) are not less than X. To the north west is a mix and to the south east there is a mix. So if we take a big north east, which leaves out only 2n-1 elements in the L they ought to be the largest. this is the same argument when u analyze the order statistics worst case O(n) bound. And this is the same argument u give when given 2 arrays of size N ( not sorted) u want to find whether there could be a sum =some constant C in O(NlogN) time becuas esorting takes NLogN. arrange one array as ascending(Y axis) and one descending(X axis). and form the grid. Property being any element X has its north east contaisn all the elements which are strickely less. and its south west, including it contaisn all elements which are greater than or equal to X. So we start from the top left hand corner and making our entire search start such that the N^2 sums form the south east ( where there is a mix) an then we go downwards if we need a bigger sum, and rightwards if we need a smaller sum. Since the north east and south west is clearly partitioned across any sum u r pointing to right now, and u have already ensured through ur operations that ur north west doesnt contain the sum of ur interest, u proceed south east and never travel back, making a total of 2N moves in the worst case. Its a similar argument. On Mon, Jul 26, 2010 at 2:25 PM, manish bhatia mb_mani...@yahoo.com wrote: How are we making sure that top n-elements would lie in this 'L' shaped array? Also, why don't we take an extreme case, such that the origin is bottom-left element 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...@gmail.com *To:* algogeeks@googlegroups.com *Sent:* Thu, 22 July, 2010 10:10:58 AM *Subject:* Re: [algogeeks] a google question im sry the L should look like this: 109 8 5 321 7 17 16 8 18 17 9 19 18 10 20 19 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 I missed a row in the last mail. On Thu, Jul 22, 2010 at 10:03 AM, topojoy biswas topojoy.bis...@gmail.com wrote: 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 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 basically have an array descending and have one array ascending. If you add them in a grid, check that for any sum, all sums to its right are less than it( in the same row), al sums above it( in the same column) are less than it, all sums below it( in the same row) are greater than it. 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 2019* 1614 13 12 12 *22 2120* 1715 14 13 13 *23 2221* 1816 15 14 So all sums which form the first quadrant origining at 19 are less than 19. And the 3rd quadrant formed by origining 19 including 19 are strickedly grater than or equal to 19. This means in the added array will look like this: __ ||___|__| ---xmy- x = no of elements in the underlined first quadrant y= no of elements in the 3rd quadrant excluding 19. m= the number of elements in the 2nd and the 4th quadrant including 19. So 19 would lie some whr in the 2n slot of this divided aray picture. So if we make x big enough so that m+y is small enough=O(n), we will reduce our load. so choose x=(n-2)(n-3) which means something like this: --(n-2)--- 109 8 5 321 7 17 1615 1210 98 --- 8 18 1716 1311 10 9 9 19 1817 1412 12 10 (n-3) 10 20 1918 1513 12 11 - 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 Then we will be left with an array of size m+y=5n-6 which is n for all n 2 like this: 109 8 5
Re: [algogeeks] a google question
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 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 basically have an array descending and have one array ascending. If you add them in a grid, check that for any sum, all sums to its right are less than it( in the same row), al sums above it( in the same column) are less than it, all sums below it( in the same row) are greater than it. 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 2019* 1614 13 12 12 *22 2120* 1715 14 13 13 *23 2221* 1816 15 14 So all sums which form the first quadrant origining at 19 are less than 19. And the 3rd quadrant formed by origining 19 including 19 are strickedly grater than or equal to 19. This means in the added array will look like this: __ ||___|__| ---xmy- x = no of elements in the underlined first quadrant y= no of elements in the 3rd quadrant excluding 19. m= the number of elements in the 2nd and the 4th quadrant including 19. So 19 would lie some whr in the 2n slot of this divided aray picture. So if we make x big enough so that m+y is small enough=O(n), we will reduce our load. so choose x=(n-2)(n-3) which means something like this: --(n-2)--- 109 8 5 321 7 17 1615 1210 98 --- 8 18 1716 1311 10 9 9 19 1817 1412 12 10 (n-3) 10 20 1918 1513 12 11 - 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 Then we will be left with an array of size m+y=5n-6 which is n for all n 2 like this: 109 8 5 321 7 17 16 8 18 17 9 19 18 10 20 19 11 21 20 12 22 2120 1715 14 13 13 23 2221 1816 15 14 Till this point it takes constant time. Now the first column of the L formed is sorted. So is the 2nd column. So is the horizonal part of L which is comprized of two sorted arays (20-13) and (21-14). All of the elements add to 5n-6. We can merge sort them in O(n) time. Take the biggest n elements. On Mon, Jul 19, 2010 at 12:18 PM, ankur aggarwal ankur.mast@gmail.comwrote: this ques was asked by google.. i* could find any gud soln than order n*n -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Topo. There are days when solitude is a heady wine that intoxicates you with freedom, others when it is a bitter tonic, and still others when it is a poison that makes you beat your head against the wall. ~Colette -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] a google question
im sry the L should look like this: 109 8 5 321 7 17 16 8 18 17 9 19 18 10 20 19 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 I missed a row in the last mail. On Thu, Jul 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 1817 1412 12 10 10 20 1918 1513 12 11 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 basically have an array descending and have one array ascending. If you add them in a grid, check that for any sum, all sums to its right are less than it( in the same row), al sums above it( in the same column) are less than it, all sums below it( in the same row) are greater than it. 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 2019* 1614 13 12 12 *22 2120* 1715 14 13 13 *23 2221* 1816 15 14 So all sums which form the first quadrant origining at 19 are less than 19. And the 3rd quadrant formed by origining 19 including 19 are strickedly grater than or equal to 19. This means in the added array will look like this: __ ||___|__| ---xmy- x = no of elements in the underlined first quadrant y= no of elements in the 3rd quadrant excluding 19. m= the number of elements in the 2nd and the 4th quadrant including 19. So 19 would lie some whr in the 2n slot of this divided aray picture. So if we make x big enough so that m+y is small enough=O(n), we will reduce our load. so choose x=(n-2)(n-3) which means something like this: --(n-2)--- 109 8 5 321 7 17 1615 1210 98 --- 8 18 1716 1311 10 9 9 19 1817 1412 12 10 (n-3) 10 20 1918 1513 12 11 - 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 Then we will be left with an array of size m+y=5n-6 which is n for all n 2 like this: 109 8 5 321 7 17 16 8 18 17 9 19 18 10 20 19 11 21 20 12 22 2120 1715 14 13 13 23 2221 1816 15 14 Till this point it takes constant time. Now the first column of the L formed is sorted. So is the 2nd column. So is the horizonal part of L which is comprized of two sorted arays (20-13) and (21-14). All of the elements add to 5n-6. We can merge sort them in O(n) time. Take the biggest n elements. On Mon, Jul 19, 2010 at 12:18 PM, ankur aggarwal ankur.mast@gmail.com wrote: this ques was asked by google.. i* could find any gud soln than order n*n -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Topo. There are days when solitude is a heady wine that intoxicates you with freedom, others when it is a bitter tonic, and still others when it is a poison that makes you beat your head against the wall. ~Colette -- Topo. There are days when solitude is a heady wine that intoxicates you with freedom, others when it is a bitter tonic, and still others when it is a poison that makes you beat your head against the wall. ~Colette -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] os problem
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 elf file for each process. B'cos while compiling the program you don;t know the actual physical address your program is going to reside during execution. On Tue, Jul 20, 2010 at 11:46 AM, divya sweetdivya@gmail.com wrote: You have 4GB ram, and at any time you have only 2 processes of 10mb each. so do you need any virtual memory for it? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Topo. There are days when solitude is a heady wine that intoxicates you with freedom, others when it is a bitter tonic, and still others when it is a poison that makes you beat your head against the wall. ~Colette -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] google
@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. But this hashtable also has a property like a FIFO queue which says 1st element will go out when the n+1th one comes in. Can we utilize that to give an amortized O(1) worst case bound? On Tue, Jul 6, 2010 at 10:36 AM, Anand anandut2...@gmail.com wrote: @topojoy. Why do we need linked list. We are use an array of struct which stores the response and request information. request identifier can be hashed to generate a key which can be used as an index to the array of structures. We don't need linked list as we do not need to parse the request and response. For indexing we are any way using hashing. On Sun, Jul 4, 2010 at 11:49 PM, Satya satya...@gmail.com wrote: See below links. Most of web applications(facebook,classmates) use memcached to speed up their sites. memcached uses hashing. http://memcached.org/ http://www.facebook.com/note.php?note_id=39391378919 http://memcached.org/http://en.wikipedia.org/wiki/Memcached . Satya On Fri, Jul 2, 2010 at 11:46 PM, sharad sharad20073...@gmail.com wrote: [1] Design a layer in front of a system which cache the last n requests and the responses to them from the system. what data structure would you use to implement the cache in the later to support following operations. [a] When a request comes look it up in the cache and if it hits then return the response from here and do not pass the request to the system [b] If the request is not found in the cache then pass it on to the system [c] Since cache can only store the last n requests, Insert the n+1th request in the cache and delete one of the older requests from the cache The objective is to achieve all the three operations in O(1). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Topo. There are days when solitude is a heady wine that intoxicates you with freedom, others when it is a bitter tonic, and still others when it is a poison that makes you beat your head against the wall. ~Colette -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] amazon question
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 array of elements.
and then visit each node write out its children to an array where element
numbered i is wriiten to array[i].
serialize thw array.
while deserializing it follow the steps to create a heap out of an array.
serialization takes O(n) time and O(n) space and so does deserialization.
On Mon, Jul 5, 2010 at 9:01 AM, harit agarwal agarwalha...@gmail.comwrote:
in my approach
a( b,c)- this implies that nodes within parenthesis are child of a where b
is left child and c is right child
if there is no left child then we can use a(,c) and
if there is no right child then use a(b) and
if there is no child use only a
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Topo.
There are days when solitude is a heady wine that intoxicates you with
freedom, others when it is a bitter tonic, and still others when it is a
poison that makes you beat your head against the wall. ~Colette
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] google
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 linked list as key. assumption: from the reqest/response, the data which identifis a request to be same is extractable in O(1). so when u add an element u just add it to the tail, calculate its hash insert it to the table and remove the element at the head from the linked list and its entry from the hashtable. the ad has to be done with a lock on both the data structures. collition in the hashtable cud be taken care by some perfect hashing scheme. guys pour in ur comments. On Sat, Jul 3, 2010 at 11:20 PM, sharad kumar sharad20073...@gmail.comwrote: @harit can u pl elaborate how we can do c part of ques by hashing in o(1) time -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Topo. There are days when solitude is a heady wine that intoxicates you with freedom, others when it is a bitter tonic, and still others when it is a poison that makes you beat your head against the wall. ~Colette -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
