Re: [algogeeks] point lying inside or not
Hi I hace a similar problem. The above algorithm works well, but how can we determine which side it intersects ? On 1 July 2010 21:30, sharad kumar sharad20073...@gmail.com wrote: @jalaj ur method fail when it is lying on the corner plzz consider case for that also -- 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. -- Siddharth Srivastava When you have learned to snatch the error code from the trap frame, it will be time for you to leave. -- 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: A nice Prob
what is the website having collection of ms questions? On Thu, Jul 1, 2010 at 6:48 PM, vicky mehta...@gmail.com wrote: Actually i saw a forum of MS questions and same as i wrote was written there. I too was confused but finally came to conclusion as u. Anyways On Jul 1, 5:51 pm, Gene gene.ress...@gmail.com wrote: On Jul 1, 6:46 am, vicky mehta...@gmail.com wrote: It took me more time to understand this problem then solving after i understood. You guys too have a look @ it.:: Let f(k) = y where k is the y-th number in the increasing sequence of non-negative integers with the same number of ones in its binary representation as y, e.g. f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 1, f(4) = 3, f(5) = 2, f(6) = 3 and so on. Given k = 0, compute f(k). There must be a mistake in you problem statement or examples. It only makes sense if you change it as follows: Let f(k) = y where k is the y-th number in the increasing sequence of non-negative integers with the same number of ones in its binary representation as k, -- change this from y to k. -- 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] Project on finding an optimal route given a map.
@Anand: Let me know your input we can modify it accordingly. I have already mentioned it in previous posts.. for your sake I ll do it again.. Input is a a map of a small area..(some college campus)..it can be in the form of an image, osm format (www.openstreetmap.org) or in the kml format ( maps.google.com) for that particular region... So creating distance matrix is the problem.. I do not want to do it manually(ie finding the distance of each node/dept from other nodes manually and then updating the distance matrix).. so i was thinking of writing an algorithm which takes the input and creates the distance matrix... which is the main challenge in this project. I request you to join the group..(http://groups.google.co.in/group/* optiroute* http://groups.google.co.in/group/optiroute ) so that we discuss about this there..instead of spamming this group.. @Sidhartha: we will face following problems if we use open Route Service: 1) we ll have to zoom in to the place everytime we open/refresh the page. 2) and the main thing is it works only for Europe. thanks for the help by the way. why dont you also join the group.. http://groups.google.co.in/group/*optiroute*http://groups.google.co.in/group/optiroute -- 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] Finding Duplicates in Random Array
1. (1) Maintain a hash table and insert the elements in the table when passing through the array. And if there is a collision then that element is a duplicate element in the array.Time - O(n) and the space is O(n). (2) Duplicate is detected by the above process. Then it can be easily removed. I can't get what it means that remove duplicates without hampering the array! The hash table anyway would contain all the distinct elements. 2. Pass the array checking if the current element is lower than the previous one. If found such element The current element is the start of the original sorted array. If such element is not found then the first element of the present is the desired element. Note down the index. Takes O(n). Now do binary search. The mid point of the array is manipulated by considering the index that we have saved. One trivial method could be keep track of the array in each recursion and then get the half length and then calculate the index according to the placement of the starting index at that recursion. This takes O(logn). So overall Time O(n). Space O(1) [no extra space]. Correct me if I am wrong. -Abhirup On Fri, Jul 2, 2010 at 1:50 AM, Vikas Jayaprakash vikas.jayaprak...@gmail.com wrote: Hi AlgoGeeks, Can anyone provide me answers for the below. 1. given an array of random integers write a program to (1) detect duplicate (2) remove duplicate (array should not get hampered at any cost!). 2 - In a sorted array some of the elements say N are rotated. for example initially 1 2 3 6 7 8 9 after rotation of 3 elements 7 8 9 1 2 3 6.So how do you search an element in this array? Regards, Vikas J -- 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. -- 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] microsoft
I think those two sensors should not be exactly opposite to each other to make the decision meaningful. On Fri, Jul 2, 2010 at 11:58 AM, Jitendra Kushwaha jitendra.th...@gmail.com wrote: I think two sensors beside one another is enough to find the direction of rotation. At some time both will be sensing the same color but when there will be change of color below one of the senser, after some time same change will be below other one, and from this we can say that the direction of the disk rotation is from first senser to second senser direction. hope i am clear... -- Regards Jitendra Kushwaha MNNIT, Allahabad -- 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. -- 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] recurring number
Can you please elaborate on the solution you have with auxiliary array? On Fri, Jul 2, 2010 at 3:53 AM, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: we are given with Numerator and Denominator. After division we might get a recurring decimal points float as the answer. For example 23.34563456 ... return 3456 i.e the recurring part i did it by converting the decimal part into string(itoa).. then a scan to find the first repeated character ...then outputting the string upto that location of first character-1 i found first repeated character using an auxilarry array[0..9].. total 3 scans.. O(n) any better solutions please ?? -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- 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. -- 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] recurring number
@dave is 1/17 recurring...?? @abhirup now convert float to string ..only part after decimal now let the string be .346346346. take an auxilarry array a[0--9]..initialize it to zero as you encounter update inceremnt a[s[i]-48] wheneva you element in tha array becomes 2 store i-1 now from 0 to i-1 is the desired answer On Fri, Jul 2, 2010 at 3:45 PM, Abhirup Ghosh abhiru...@gmail.com wrote: Can you please elaborate on the solution you have with auxiliary array? On Fri, Jul 2, 2010 at 3:53 AM, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: we are given with Numerator and Denominator. After division we might get a recurring decimal points float as the answer. For example 23.34563456 ... return 3456 i.e the recurring part i did it by converting the decimal part into string(itoa).. then a scan to find the first repeated character ...then outputting the string upto that location of first character-1 i found first repeated character using an auxilarry array[0..9].. total 3 scans.. O(n) any better solutions please ?? -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- 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. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- 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] array
make a bst of all numbers (nlogn) include a count in the structure..as soon as the count become n return the data of that node On Thu, Jul 1, 2010 at 10:13 PM, sharad sharad20073...@gmail.com wrote: 1.an array of 2n+1 elements is given .one element is repeated n times and rest all are different.find the no repeated. 2.same question as above but this time other no's are not different ..i.e they can repeat. -- 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. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- 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] Finding Duplicates in Random Array
second question can be done in O(logn) do a modified binary search to find the starting index of the rotated array i.e the smallest element. after that you have two sorted arrays.. for eg 789 1236 (your modified binary search should return index of 1) now check if the elemnent you are searching in greater then a[min] then do binary search in 1st array else do in second array On Fri, Jul 2, 2010 at 3:29 PM, Abhirup Ghosh abhiru...@gmail.com wrote: 1. (1) Maintain a hash table and insert the elements in the table when passing through the array. And if there is a collision then that element is a duplicate element in the array.Time - O(n) and the space is O(n). (2) Duplicate is detected by the above process. Then it can be easily removed. I can't get what it means that remove duplicates without hampering the array! The hash table anyway would contain all the distinct elements. 2. Pass the array checking if the current element is lower than the previous one. If found such element The current element is the start of the original sorted array. If such element is not found then the first element of the present is the desired element. Note down the index. Takes O(n). Now do binary search. The mid point of the array is manipulated by considering the index that we have saved. One trivial method could be keep track of the array in each recursion and then get the half length and then calculate the index according to the placement of the starting index at that recursion. This takes O(logn). So overall Time O(n). Space O(1) [no extra space]. Correct me if I am wrong. -Abhirup On Fri, Jul 2, 2010 at 1:50 AM, Vikas Jayaprakash vikas.jayaprak...@gmail.com wrote: Hi AlgoGeeks, Can anyone provide me answers for the below. 1. given an array of random integers write a program to (1) detect duplicate (2) remove duplicate (array should not get hampered at any cost!). 2 - In a sorted array some of the elements say N are rotated. for example initially 1 2 3 6 7 8 9 after rotation of 3 elements 7 8 9 1 2 3 6.So how do you search an element in this array? Regards, Vikas J -- 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. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- 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: recurring number
Yes. What if the recurring number is more than 20 digits? On Fri, Jul 2, 2010 at 9:33 AM, Dave dave_and_da...@juno.com wrote: Does it work for 1/17, 2/17, 3/17, etc.? Dave On Jul 1, 5:23 pm, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: we are given with Numerator and Denominator. After division we might get a recurring decimal points float as the answer. For example 23.34563456 ... return 3456 i.e the recurring part i did it by converting the decimal part into string(itoa).. then a scan to find the first repeated character ...then outputting the string upto that location of first character-1 i found first repeated character using an auxilarry array[0..9].. total 3 scans.. O(n) any better solutions please ?? -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- 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 and regards Rizwan A Hudda http://sites.google.com/site/rizwanhudda -- 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] rotation
why not block reversal? On Fri, Jul 2, 2010 at 5:36 PM, Saurabh Ahuja nsit.saur...@gmail.comwrote: a[0] = a[2] a[1] = a[3] a[2] = a[4] a[0] and a[1] has been changed a[3] = a[0] a[4] = a[1] so this solution would not work. On Fri, Jul 2, 2010 at 5:14 PM, Akash Gangil akashg1...@gmail.com wrote: wouldn't this work: for i in range(0,len) a[i] = a[(i+2)%5]; where len is the length of array On Sat, Jun 26, 2010 at 3:37 PM, sharad kumar sharad20073...@gmail.comwrote: i have to right rotate an array by k positions 1 2 3 4 5 for k=2 o/p shud be 3 4 5 1 2 P.S---do not give block reversal method for array rotation and soln must be inplace.plzz write ur logic also along with d code -- 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. -- Best Regards Akash Gangil -- 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. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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: array
@ dave its not always that the number be adjacent as the array is not sorted suppose array is 2 1 3 4 2 On Fri, Jul 2, 2010 at 6:04 PM, Dave dave_and_da...@juno.com wrote: For problem 1, finding a number that is repeated just once is enough. Scan the array to see if there are two adjacent numbers that are equal. If so, that is your repeated number. Otherwise, look for the repeat in the first 5 numbers. O(n). Dave On Jul 1, 11:43 am, sharad sharad20073...@gmail.com wrote: 1.an array of 2n+1 elements is given .one element is repeated n times and rest all are different.find the no repeated. 2.same question as above but this time other no's are not different ..i.e they can repeat. -- 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. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- 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] BST with duplicates?
Disagree a BST can have duplicate entries the 'equal to' term in the definition allows that I am surprised to see in the Wiki: From the above properties it naturally follows that: - Each node (item in the tree) has a distinct key. The example in the question is definitely wrong in the sense that it allows duplicates in both directions once the definition is fixed one can have duplicates in 1 direction i.e. left or right I believe. On Thu, Jul 1, 2010 at 10:01 PM, mohit ranjan shoonya.mo...@gmail.comwrote: @Amit as per wiki, BST definition is - The left subtree of a node contains only nodes with keys *less than the node's key*. - The right subtree of a node contains only nodes with *keys greater than or equal to the node's key*. so, this following example is not a BST... Mohit On Thu, Jul 1, 2010 at 8:04 PM, amit amitjaspal...@gmail.com wrote: Can a BST have duplicate entries ?? .8 .../...\ .7..9 /..\/..\ ...6...8..8...10 i.e is this a BST . -- 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. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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: recurring number
hmm. :-o On Fri, Jul 2, 2010 at 5:57 PM, Dave dave_and_da...@juno.com wrote: Yes. With a period of 16: 1/17 = 0.0588235294117647 0588235294117647 0588235294117647 ... Dave On Jul 2, 5:22 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: @dave is 1/17 recurring...?? @abhirup now convert float to string ..only part after decimal now let the string be .346346346. take an auxilarry array a[0--9]..initialize it to zero as you encounter update inceremnt a[s[i]-48] wheneva you element in tha array becomes 2 store i-1 now from 0 to i-1 is the desired answer On Fri, Jul 2, 2010 at 3:45 PM, Abhirup Ghosh abhiru...@gmail.com wrote: Can you please elaborate on the solution you have with auxiliary array? On Fri, Jul 2, 2010 at 3:53 AM, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: we are given with Numerator and Denominator. After division we might get a recurring decimal points float as the answer. For example 23.34563456 ... return 3456 i.e the recurring part i did it by converting the decimal part into string(itoa).. then a scan to find the first repeated character ...then outputting the string upto that location of first character-1 i found first repeated character using an auxilarry array[0..9].. total 3 scans.. O(n) any better solutions please ?? -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- 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 algogeeks%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 algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD- Hide quoted text - - Show quoted text - -- 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. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- 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] array
On Fri, Jul 2, 2010 at 3:41 PM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote: make a bst of all numbers (nlogn) include a count in the structure..as soon as the count become n return the data of that node Can you please tell me why you chose a bst, simply traversing the array and incrementing the count would have also worked in this case and it would have been O(n). On Thu, Jul 1, 2010 at 10:13 PM, sharad sharad20073...@gmail.com wrote: 1.an array of 2n+1 elements is given .one element is repeated n times and rest all are different.find the no repeated. 2.same question as above but this time other no's are not different ..i.e they can repeat. -- 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. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- 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. -- Best Regards Akash Gangil -- 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.
[algogeeks] lru cache
how would u implement LRU cache -- 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] rotation
i think this should work. for(i=1;i=k;i++) { var=a[n-1] for(j=n-1;j=1;j--) a[i]=a[i-1] a[0]=var } On Fri, Jul 2, 2010 at 5:36 PM, Saurabh Ahuja nsit.saur...@gmail.comwrote: a[0] = a[2] a[1] = a[3] a[2] = a[4] a[0] and a[1] has been changed a[3] = a[0] a[4] = a[1] so this solution would not work. On Fri, Jul 2, 2010 at 5:14 PM, Akash Gangil akashg1...@gmail.com wrote: wouldn't this work: for i in range(0,len) a[i] = a[(i+2)%5]; where len is the length of array On Sat, Jun 26, 2010 at 3:37 PM, sharad kumar sharad20073...@gmail.comwrote: i have to right rotate an array by k positions 1 2 3 4 5 for k=2 o/p shud be 3 4 5 1 2 P.S---do not give block reversal method for array rotation and soln must be inplace.plzz write ur logic also along with d code -- 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. -- Best Regards Akash Gangil -- 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] microsoft
place the sensors on the same color portion well apart to distinguish which one indicated the change first the sensor number to indicate a change first indicates the direction. On Fri, Jul 2, 2010 at 3:37 PM, Abhirup Ghosh abhiru...@gmail.com wrote: I think those two sensors should not be exactly opposite to each other to make the decision meaningful. On Fri, Jul 2, 2010 at 11:58 AM, Jitendra Kushwaha jitendra.th...@gmail.com wrote: I think two sensors beside one another is enough to find the direction of rotation. At some time both will be sensing the same color but when there will be change of color below one of the senser, after some time same change will be below other one, and from this we can say that the direction of the disk rotation is from first senser to second senser direction. hope i am clear... -- Regards Jitendra Kushwaha MNNIT, Allahabad -- 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. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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.
[algogeeks] Re: recurring number
Okay. Here is some code to determine the number of digits in the period of repetition of the decimal expansion of 1/n, where n 0: int period(int n); { int i=1,j=0; while( n % 2 == 0 ) n /= 2; while( n % 5 == 0 ) n /= 5; do { i = (10 * i) % n; ++j; } while( i 1 ); return j; } Given the relatively prime pair of integers m and n, once you know the number of digits in a repeat of 1/n, you can easily find the repeating digits in the decimal expansion of the fraction m/n. Dave On Jul 2, 7:42 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: hmm. :-o On Fri, Jul 2, 2010 at 5:57 PM, Dave dave_and_da...@juno.com wrote: Yes. With a period of 16: 1/17 = 0.0588235294117647 0588235294117647 0588235294117647 ... Dave On Jul 2, 5:22 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: @dave is 1/17 recurring...?? @abhirup now convert float to string ..only part after decimal now let the string be .346346346. take an auxilarry array a[0--9]..initialize it to zero as you encounter update inceremnt a[s[i]-48] wheneva you element in tha array becomes 2 store i-1 now from 0 to i-1 is the desired answer On Fri, Jul 2, 2010 at 3:45 PM, Abhirup Ghosh abhiru...@gmail.com wrote: Can you please elaborate on the solution you have with auxiliary array? On Fri, Jul 2, 2010 at 3:53 AM, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: we are given with Numerator and Denominator. After division we might get a recurring decimal points float as the answer. For example 23.34563456 ... return 3456 i.e the recurring part i did it by converting the decimal part into string(itoa).. then a scan to find the first repeated character ...then outputting the string upto that location of first character-1 i found first repeated character using an auxilarry array[0..9].. total 3 scans.. O(n) any better solutions please ?? -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- 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 algogeeks%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 algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD- Hide quoted text - - Show quoted text - -- 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. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD- Hide quoted text - - Show quoted text - -- 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.
[algogeeks] Re: array
@Jalaj. You apparently missed the sentence Otherwise, look for the repeat in the first 5 numbers. Dave On Jul 2, 7:42 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: @ dave its not always that the number be adjacent as the array is not sorted suppose array is 2 1 3 4 2 On Fri, Jul 2, 2010 at 6:04 PM, Dave dave_and_da...@juno.com wrote: For problem 1, finding a number that is repeated just once is enough. Scan the array to see if there are two adjacent numbers that are equal. If so, that is your repeated number. Otherwise, look for the repeat in the first 5 numbers. O(n). Dave On Jul 1, 11:43 am, sharad sharad20073...@gmail.com wrote: 1.an array of 2n+1 elements is given .one element is repeated n times and rest all are different.find the no repeated. 2.same question as above but this time other no's are not different ..i.e they can repeat. -- 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. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD- Hide quoted text - - Show quoted text - -- 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.
[algogeeks] Re: array
@Saurabh. Checking three adjacent numbers won't work, as the example 1,2,3,4,1 shows. You apparently missed the sentence, Otherwise, look for the repeat in the first 5 numbers. If you don't find two equal adjacent numbers, then there will be a repeat within the first five numbers. How do you know this? If there are no equal adjacent numbers, then within the last 2*n-4 numbers, there can be no more than n-2 occurrences of the repeating number. Thus, the remaining two or three occurrences must be within the first five numbers. Dave On Jul 2, 8:35 am, saurabh gupta sgup...@gmail.com wrote: @Dave, for 2n+1 you can have a configuration where repeated nos may not be adjacent you need a block of 3 instead of 2. On Fri, Jul 2, 2010 at 6:04 PM, Dave dave_and_da...@juno.com wrote: For problem 1, finding a number that is repeated just once is enough. Scan the array to see if there are two adjacent numbers that are equal. If so, that is your repeated number. Otherwise, look for the repeat in the first 5 numbers. O(n). Dave On Jul 1, 11:43 am, sharad sharad20073...@gmail.com wrote: 1.an array of 2n+1 elements is given .one element is repeated n times and rest all are different.find the no repeated. 2.same question as above but this time other no's are not different ..i.e they can repeat. -- 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. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci.- Hide quoted text - - Show quoted text - -- 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] second shortest path
we can do this in a much better time than divya's algorithm since he does the shortest path algorithm E+1 times here's my approach: find the shortest path using dijkstra since in dijkstra we have the shortest path to each vertex now look at the edges that end at the destination if the shortest path to their other end + their weight is the shortest path to the destination then they made the shortest path so if we remove them from graph and find the shortest path again the result would be the second shortest path so we can do it in 2 * running time of dijkstra -- 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] lru cache
keep n bits (depending on the usage level you want) to track for each element (cell/page) etc in the cache. Now whenever an element is loaded into cache set all the bits and on further use increment by 1 if not max value. Decrement value by 1 for all the block periodically. Now whenever you need to remove an element, select one with least value. On Fri, Jul 2, 2010 at 6:59 PM, sharad kumar sharad20073...@gmail.comwrote: how would u implement LRU cache -- 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] yahoo!!!
the rank of median in the merged list of the two lists is (N1+N2)/2 so if it's rank in list A is i and it's rank in list B is j then i+j=(N1+N2)/2 (it's rank in the list that it does not belong is i when A[i]medianA[i+1] ) we do an changed binary search as follows: pick the middle element of A it's index in A is i and since i+j=(N1+N2)/2 we can obtain j (it's rank in B if it's the median) then if B[j]A[i]B[j+1] , A[i] is the median (the same thing for B[j]) else whether A[i] is less than them or it's bigger than both of them if it's bigger than both of them the median is somewhere in the first half of A and the second half of B we can do the rest of search in there the opposite thing happens if it's less then B[j] and B[j+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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] array
both problems can be done in O(n) pick the first two elements count the number of their appearances in the array ( O(n) ) if they are not the result we now that there is an element that is repeated n times in 2n-1 elements and we can do the moore's algorithm for finding it here's a link to this algorithm: userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html -- 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.
[algogeeks] 2_D matrix
how to search a number in a 2d matrix which is sorted both row wise and column wise in less then O(n) -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- 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: array
for count suppose if there are very big numbers ..then space will nt be efficient On Fri, Jul 2, 2010 at 7:05 PM, saurabh gupta sgup...@gmail.com wrote: @Dave, for 2n+1 you can have a configuration where repeated nos may not be adjacent you need a block of 3 instead of 2. On Fri, Jul 2, 2010 at 6:04 PM, Dave dave_and_da...@juno.com wrote: For problem 1, finding a number that is repeated just once is enough. Scan the array to see if there are two adjacent numbers that are equal. If so, that is your repeated number. Otherwise, look for the repeat in the first 5 numbers. O(n). Dave On Jul 1, 11:43 am, sharad sharad20073...@gmail.com wrote: 1.an array of 2n+1 elements is given .one element is repeated n times and rest all are different.find the no repeated. 2.same question as above but this time other no's are not different ..i.e they can repeat. -- 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. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- 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] rotation
reverse full array first then, reverse last k elemnts and initial n-k elements seperately this will do On Fri, Jul 2, 2010 at 8:34 PM, Ratnesh Thakur ratneshthaku...@gmail.comwrote: correction.. a[j]=a[j-1] instead of a[i]=a[i-1] On Fri, Jul 2, 2010 at 7:30 PM, Ratnesh Thakur ratneshthaku...@gmail.comwrote: i think this should work. for(i=1;i=k;i++) { var=a[n-1] for(j=n-1;j=1;j--) a[i]=a[i-1] a[0]=var } On Fri, Jul 2, 2010 at 5:36 PM, Saurabh Ahuja nsit.saur...@gmail.comwrote: a[0] = a[2] a[1] = a[3] a[2] = a[4] a[0] and a[1] has been changed a[3] = a[0] a[4] = a[1] so this solution would not work. On Fri, Jul 2, 2010 at 5:14 PM, Akash Gangil akashg1...@gmail.comwrote: wouldn't this work: for i in range(0,len) a[i] = a[(i+2)%5]; where len is the length of array On Sat, Jun 26, 2010 at 3:37 PM, sharad kumar sharad20073...@gmail.com wrote: i have to right rotate an array by k positions 1 2 3 4 5 for k=2 o/p shud be 3 4 5 1 2 P.S---do not give block reversal method for array rotation and soln must be inplace.plzz write ur logic also along with d code -- 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. -- Best Regards Akash Gangil -- 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. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- 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.
[algogeeks] microsoft interview(numbers)
given some positive numbers output the numbers in decreasing oeder of frequency..in case of atie print the number which occurd first for eg: 1,3,3,1,2,3,5,2,3 the output should be 11225 -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- 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] computational geometry
number the elements in clockwise order from 1..n suppose n is 12 then start from a point here we start from the point 1 then we find the farthest point from it in O(n) suppose that's point 5 now if we want to find the farthest point from point 2 since we moved clockwise the farthest point must turn clockwise i.e. points 3 and 4 cannot be the farthest point from 2 since the farthest point must turn clockwise when we want to find the farthest point from point 5 the farthest point would be point 1 this means that when we want to find the farthest point from the next point we don't search the hole polygon it just can be incremented from the last result a few times i hope it's clear now -- 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] 2_D matrix
i think this might work Binsearch on matrix for the column in which the element may lie... use last element of the coloumn for comparisons \ then binsearch in the coloumn to find if the element is there or not -- 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.
[algogeeks] Re: array
@Jalaj. I don't understand how your comment contributes to the discussion. Please explain. Dave On Jul 2, 10:56 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: for count suppose if there are very big numbers ..then space will nt be efficient On Fri, Jul 2, 2010 at 7:05 PM, saurabh gupta sgup...@gmail.com wrote: @Dave, for 2n+1 you can have a configuration where repeated nos may not be adjacent you need a block of 3 instead of 2. On Fri, Jul 2, 2010 at 6:04 PM, Dave dave_and_da...@juno.com wrote: For problem 1, finding a number that is repeated just once is enough. Scan the array to see if there are two adjacent numbers that are equal. If so, that is your repeated number. Otherwise, look for the repeat in the first 5 numbers. O(n). Dave On Jul 1, 11:43 am, sharad sharad20073...@gmail.com wrote: 1.an array of 2n+1 elements is given .one element is repeated n times and rest all are different.find the no repeated. 2.same question as above but this time other no's are not different ..i.e they can repeat. -- 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. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD- Hide quoted text - - Show quoted text - -- 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.
[algogeeks] Re: rotation
@Jalaj. The original poster said, P.S---do not give block reversal method for array rotation Dave On Jul 2, 10:54 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: reverse full array first then, reverse last k elemnts and initial n-k elements seperately this will do On Fri, Jul 2, 2010 at 8:34 PM, Ratnesh Thakur ratneshthaku...@gmail.comwrote: correction.. a[j]=a[j-1] instead of a[i]=a[i-1] On Fri, Jul 2, 2010 at 7:30 PM, Ratnesh Thakur ratneshthaku...@gmail.comwrote: i think this should work. for(i=1;i=k;i++) { var=a[n-1] for(j=n-1;j=1;j--) a[i]=a[i-1] a[0]=var } On Fri, Jul 2, 2010 at 5:36 PM, Saurabh Ahuja nsit.saur...@gmail.comwrote: a[0] = a[2] a[1] = a[3] a[2] = a[4] a[0] and a[1] has been changed a[3] = a[0] a[4] = a[1] so this solution would not work. On Fri, Jul 2, 2010 at 5:14 PM, Akash Gangil akashg1...@gmail.comwrote: wouldn't this work: for i in range(0,len) a[i] = a[(i+2)%5]; where len is the length of array On Sat, Jun 26, 2010 at 3:37 PM, sharad kumar sharad20073...@gmail.com wrote: i have to right rotate an array by k positions 1 2 3 4 5 for k=2 o/p shud be 3 4 5 1 2 P.S---do not give block reversal method for array rotation and soln must be inplace.plzz write ur logic also along with d code -- 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. -- Best Regards Akash Gangil -- 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. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD- Hide quoted text - - Show quoted text - -- 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.
[algogeeks] Amazon: sort array
Given an array of n elements and an integer k where kn. Elemnts {a[0].a[k] and a[k+1].a[n] are already sorted. Give an algorithm to sort in O(n) time and O(1) space. -- 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: sort array
This is an example of bitonic sequence if we reverse the bottom half of the array. Sequence is called Bitonics if the sequence of number first increases(ascending order) and then decrease(descending order). 1. We need to reverse the bottom half the array to make it bitonic. 2. Appy Bitonic Merge to get the final sorted array.: Complexity.O(n) In the below code, I have implemented sorting n/w to sort any kind of array but for bitonic sequence we only bitonic merge function call which take O(n). Refer section Sorting network from Corman for more details http://codepad.org/ZhYEBqMw On Fri, Jul 2, 2010 at 11:30 AM, ANKUR BHARDWAJ ankibha...@gmail.comwrote: Given an array of n elements and an integer k where kn. Elemnts {a[0].a[k] and a[k+1].a[n] are already sorted. Give an algorithm to sort in O(n) time and O(1) space. -- 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] 2_D matrix
Consider the bottom half elment of the given 2 - D array. if it is less than the number to be search, ignore the whole column and if less ignore the whole row. if it equal note the array index. repeat the above procedure till all rows and column are scanned. By doing with complexity less than O(n), we can search the required number from 2D array. On Fri, Jul 2, 2010 at 10:39 AM, Rahul Kushwaha rahul.kushw...@gmail.comwrote: i think this might work Binsearch on matrix for the column in which the element may lie... use last element of the coloumn for comparisons \ then binsearch in the coloumn to find if the element is there or not -- 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] Amazon: sort array
@Anand: good one On Sat, Jul 3, 2010 at 2:02 AM, Anand anandut2...@gmail.com wrote: This is an example of bitonic sequence if we reverse the bottom half of the array. Sequence is called Bitonics if the sequence of number first increases(ascending order) and then decrease(descending order). 1. We need to reverse the bottom half the array to make it bitonic. 2. Appy Bitonic Merge to get the final sorted array.: Complexity.O(n) In the below code, I have implemented sorting n/w to sort any kind of array but for bitonic sequence we only bitonic merge function call which take O(n). Refer section Sorting network from Corman for more details http://codepad.org/ZhYEBqMw On Fri, Jul 2, 2010 at 11:30 AM, ANKUR BHARDWAJ ankibha...@gmail.comwrote: Given an array of n elements and an integer k where kn. Elemnts {a[0].a[k] and a[k+1].a[n] are already sorted. Give an algorithm to sort in O(n) time and O(1) space. -- 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.
[algogeeks] Binary trees with 3 nodes
How to find all the possible trees with 3 nodes from a given tree -- 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] 2_D matrix
@Rahul: the worst case running time for your algo is O(nlogn) but here's another approach: suppose we're searching for x binary search on the diameter of the matrix (note that the diameter is sorted) if x is not on the diameter when you find i such that a[i][i]xa[i+1][i+1] split the matrix to four matrices - | R1 | R2 | |- | R3 | R4 | - x cannot be in R1 since it's biggest element is a[i][i] which is less than x and it can't be in R4 since it's least element is a[i+1][i+1] which is bigger than x so we search recursively in R3 and R2 in avg case since the avg size of R3 and R2 is n/2 * n/2 T(n) = 2T(n/2) + O(lgn) using the master method the running time is O(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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: array
@Dave: ah, yeah, you are right On Fri, Jul 2, 2010 at 11:13 PM, Dave dave_and_da...@juno.com wrote: @Jalaj. I don't understand how your comment contributes to the discussion. Please explain. Dave On Jul 2, 10:56 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: for count suppose if there are very big numbers ..then space will nt be efficient On Fri, Jul 2, 2010 at 7:05 PM, saurabh gupta sgup...@gmail.com wrote: @Dave, for 2n+1 you can have a configuration where repeated nos may not be adjacent you need a block of 3 instead of 2. On Fri, Jul 2, 2010 at 6:04 PM, Dave dave_and_da...@juno.com wrote: For problem 1, finding a number that is repeated just once is enough. Scan the array to see if there are two adjacent numbers that are equal. If so, that is your repeated number. Otherwise, look for the repeat in the first 5 numbers. O(n). Dave On Jul 1, 11:43 am, sharad sharad20073...@gmail.com wrote: 1.an array of 2n+1 elements is given .one element is repeated n times and rest all are different.find the no repeated. 2.same question as above but this time other no's are not different ..i.e they can repeat. -- 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 algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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 algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD- Hide quoted text - - Show quoted text - -- 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. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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] microsoft interview(numbers)
i think that the best method would be a balanced binary search tree which counts the number of appearances for each element O(nlogn) -- 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] 2_D matrix
not clear yaar suppose the matrix is 0 1 3 7 2 4 5 8 6 9 10 11 8 12 13 14 how wiill you search 9.. elaborate On Fri, Jul 2, 2010 at 11:09 PM, Rahul Kushwaha rahul.kushw...@gmail.comwrote: i think this might work Binsearch on matrix for the column in which the element may lie... use last element of the coloumn for comparisons \ then binsearch in the coloumn to find if the element is there or not -- 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. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- 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: sort array
Something like merge sort should do. On Sat, Jul 3, 2010 at 12:00 AM, ANKUR BHARDWAJ ankibha...@gmail.com wrote: Given an array of n elements and an integer k where kn. Elemnts {a[0].a[k] and a[k+1].a[n] are already sorted. Give an algorithm to sort in O(n) time and O(1) space. -- 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. -- Siddharth Prakash Singh http://www.spsneo.com -- 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: sort array
I think its similar to the merge operation which is used in merge sort... correct me if I am wrong.. Regards, Abhishek On Sat, Jul 3, 2010 at 12:00 AM, ANKUR BHARDWAJ ankibha...@gmail.comwrote: Given an array of n elements and an integer k where kn. Elemnts {a[0].a[k] and a[k+1].a[n] are already sorted. Give an algorithm to sort in O(n) time and O(1) space. -- 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] Binary trees with 3 nodes
catalan numbers.(2n)Cn/(n+1) On Sat, Jul 3, 2010 at 1:06 AM, Raj N rajn...@gmail.com wrote: How to find all the possible trees with 3 nodes from a given tree -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon: sort array
@anand: this code will not work when n is not power of 2. check for this example: {2, 4, 55, 25, 15} Output was: 0 4 0 2 1 3 0 1 2 3 2 4 25 55 15 0 0 0 ascending order -- 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.