Re: [algogeeks] question
step 1: Sort array in place. Lets call it A. (N log N)
step 2: Create two additional copies of array, lets call them B and C. (this
is just for explanation, we can operate on same array A).
step 3: Take first element from array A. lets say its value is X. Find pair
from B and C whose sum is nearest to -X.
This step of finding pair is similar to Binary Search as array is sorted.
step 4: Repeat step 3 for entire array A.
On Mon, May 17, 2010 at 9:58 PM, Anurag Sharma anuragvic...@gmail.comwrote:
oops!
Anurag Sharma
On Mon, May 17, 2010 at 5:00 PM, Navin Naidu navinmna...@gmail.comwrote:
@anurag:
-99 -2 -1 3 +99
The min sum (=0) for value pair (-99, 99)
Now skip, +99 and -99, so -1 will be selected: (99, -99, -1) = -1
Actual result: -2, -1, 3 : 0
On Mon, May 17, 2010 at 8:48 AM, Anurag Sharma anuragvic...@gmail.comwrote:
@Navin : Let me work out the case you gave me array={-99,0,2,-1,99}
1. Sort the array in nlogn time: array={-99,-1,0,2,99}
2. consider all possible pairs of numbers and keep track of the sum
closest 2 zero:
-99+-1=-100, |-100|=100
-99+0=-99,|-99|=99
-99+2=-97,|-97|=97
-99+99=0,|0|=0 --- this is the minimum sum(=0) for value pair
(-99, 99)
-1+0=-1,|-1|=1
-1+2=1,|1|=1
-1+99=98,|98|=98
0+2=2,|2|=2
0+99=99,|99|=99
2+99=101,|101|=101
3. Now traversing the array skipping the values -99, 99 and trying to get
minimum sum after including it in the existing sum :
array={-99,-1,0,2,99}
take -99: skip
take -1: 0+-1= -1 and |-1|=1
take 0: 0+0=0 and |0|=0 this is the minimum so the third number
is 0
take 2: 0+2=2 and |2|=2
take 99: skip
this way we got the three numbers as -99,99 and 0. Were you expecting
some other combo?
In step 3 we can skip checking the rest of the elements when we find the
sum increasing as the array is already sorted.
Let me know if there is still some issue in it.
Regards,
Anurag Sharma
On Sun, May 16, 2010 at 9:26 PM, Navin Naidu navinmna...@gmail.comwrote:
@anurag: wont work, consider the following case: -99 0 2 -1 99
On Sun, May 16, 2010 at 9:12 PM, Rohit Saraf
rohit.kumar.sa...@gmail.com wrote:
@anurag : won't work
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14
--
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.
--
Thanks Regards,
- NMN
--
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.
--
Thanks Regards,
- NMN
--
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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] data structure and algorithm implementation
http://geeksforgeeks.org/ can be helpful. You can also find links to tutorials/articles http://geeksforgeeks.org/?page_id=6028 On Fri, May 21, 2010 at 3:57 AM, sharad kumar aryansmit3...@gmail.comwrote: @venky pls c www.topcoder.com/tc its gt tutorials,srm matches etc. On Fri, May 21, 2010 at 2:55 PM, venkat kumar svenkatkuma...@gmail.comwrote: i'm new to coding.it is difficult to implement algorithms and even standard data structures is there a sort of lab manual available and are there solutions to problems in uva,sphere etc etc websites kindly reply. thanks -- 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. -- yezhu malai vaasa venkataramana Govinda Govinda -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: another google telephone interview question
Find the median of the values and move the lower values to left and higher
values to the right. This can be done in o(n). now do the same on both the
parts recursively. And the total complexity will be o(nlogk).
On Fri, May 21, 2010 at 1:12 PM, Shachin Sharma shac...@gmail.com wrote:
No heapify will not barf. Here is how it goes:
Whenever you get a node value root value (you have already determined the
root value in first scan) you are sure that this isnt the actual value can't
be in a heap. So determine actual value.
if (pres_node_value root_value say R) //Value keeps frequency and isnt
actual
Call get_actual_value (pres_node_value)
get_actual_value (pres_node_value)
{
frequency_of_occurence = pres_node_value /R = Quotient
actual_value = pres_node_value % R = remainder
So e.g. when 2 is repeated twice and root value is 3 you will store (2
+ 3 +3 = 8). When you see 8 you know it is ROOT = 3 so get_actual_value
(8) will give 8/3 = 2 = frequency and 8% 3 = 2 = actual value.
}
Rest of heapify insertion works as usual. This way nothing in heap changes,
no property. And by the way how can you save bits in an integer ?? It is
always 4 bytes (on most of platforms) whether its = 1 or 1 + 1000 ? If you
said that there could be overflow I would still have agreed but I dont think
you are saving bits. In fact in your solution a whole new 4 byte chunk is
used when you keep something like 2:1 which is O(K) space and violates the
in-place property which says that extra space should have upper bound logn.
Thanks,
Sachin
On Thu, May 20, 2010 at 7:59 PM, Piyush Verma 114piy...@gmail.com wrote:
@shachin,when u add value of root in the child of root then for insertion
of new element when heap is called(so heapify is called) so now this child
becomes root which is not desired..
plzz correct me if i m wrong
--
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.
--
Bharath
--
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.
