Re: [algogeeks] Re: Median of two sorted arrays of different sizes
How is this code dealing with the scenario where two arrays have common
number. For example where two arrays are same. A[] = {1,2,3,4} and B[] =
{1,2,3,4}. Here the median position is not (4+4)/2 rather it is 4/2.
On Sun, Jun 9, 2013 at 3:12 PM, rahul sharma rahul23111...@gmail.comwrote:
@doncan u plz explain the approach used.I didnt get this.
On 4/25/13, Don dondod...@gmail.com wrote:
Let's say you have two arrays: A[x] and B[y].
The median is the (x+y)/2th value.
If A[i] is the median, then B[(x+y)/2-i] = A[i] and B[(x+y)/2-i+1] =
A[i].
You can use a binary search to find the point where that condition
occurs. Of course you want to search on the smaller array.
You'll need some logic at the end to determine if the median is in A
or in B.
// Input arrays A and B, sizeA = sizeB
int A[sizeA];
int B[sizeB];
int min = 0;
int max = sizeA;
const int medianPos = (sizeA + sizeB) / 2;
while(max = min)
{
i = (min + max) / 2;
j = medianPos-i;
if (B[j] A[i]) min = i+1;
else if (B[j+1] A[i]) max = i-1;
else break;
}
printf(Median is %d\n, (A[i] B[j]) ? A[i] : B[j]);
Don
On Apr 24, 1:19 pm, rahul sharma rahul23111...@gmail.com wrote:
IS this code correct?
float findMedianUtil( int A[], int N, int B[], int M )
{
// If the smaller array has only one element
if( N == 1 )
{
// Case 1: If the larger array also has one element, simply call
MO2()
if( M == 1 )
return MO2( A[0], B[0] );
// Case 2: If the larger array has odd number of elements, then
consider
// the middle 3 elements of larger array and the only element of
// smaller array. Take few examples like following
// A = {9}, B[] = {5, 8, 10, 20, 30} and
// A[] = {1}, B[] = {5, 8, 10, 20, 30}
if( M 1 )
return MO2( B[M/2], MO3(A[0], B[M/2 - 1], B[M/2 + 1]) );
// Case 3: If the larger array has even number of element, then
median
// will be one of the following 3 elements
// ... The middle two elements of larger array
// ... The only element of smaller array
return MO3( B[M/2], B[M/2 - 1], A[0] );
}
// If the smaller array has two elements
else if( N == 2 )
{
// Case 4: If the larger array also has two elements, simply
call
MO4()
if( M == 2 )
return MO4( A[0], A[1], B[0], B[1] );
// Case 5: If the larger array has odd number of elements, then
median
// will be one of the following 3 elements
// 1. Middle element of larger array
// 2. Max of first element of smaller array and element just
//before the middle in bigger array
// 3. Min of second element of smaller array and element just
//after the middle in bigger array
if( M 1 )
return MO3 ( B[M/2],
max( A[0], B[M/2 - 1] ),
min( A[1], B[M/2 + 1] )
);
// Case 6: If the larger array has even number of elements, then
// median will be one of the following 4 elements
// 1) 2) The middle two elements of larger array
// 3) Max of first element of smaller array and element
//just before the first middle element in bigger array
// 4. Min of second element of smaller array and element
//just after the second middle in bigger array
return MO4 ( B[M/2],
B[M/2 - 1],
max( A[0], B[M/2 - 2] ),
min( A[1], B[M/2 + 1] )
);
}
int idxA = ( N - 1 ) / 2;
int idxB = ( M - 1 ) / 2;
/* if A[idxA] = B[idxB], then median must exist in
A[idxA] and B[idxB] */
if( A[idxA] = B[idxB] )
return findMedianUtil( A + idxA, N / 2 + 1, B, M - idxA );
/* if A[idxA] B[idxB], then median must exist in
A[...idxA] and B[idxB] */
return findMedianUtil( A, N / 2 + 1, B + idxA, M - idxA );
}
In the end I suspect the following part:-
if( A[idxA] = B[idxB] )
return findMedianUtil( A + idxA, N / 2 + 1, B, M - idxA );
/* if A[idxA] B[idxB], then median must exist in
A[...idxA] and B[idxB] */
return findMedianUtil( A, N / 2 + 1, B + idxA, M - idxA );
plz comment
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it,
Re: [algogeeks] size of array
When malloc allocates memory it assigns a size field in the header to indicate the size of the memory it allocates at a stretch. Can we not use this information effectively? On Jan 31, 2013 11:44 PM, Piyush piyush.to...@gmail.com wrote: it will always work if array is statically allocated Not if dynamically allocated, say using malloc etc. On 30-Jan-13 1:55 PM, Prem Krishna Chettri wrote: @Piyush .. Never works.. @All there is no way to do the given requirement in pure C. On Wed, Jan 30, 2013 at 1:45 PM, Piyush piyush.to...@gmail.com wrote: sizeof(array)/sizeof(array[0]) On 28-Jan-13 3:44 PM, Anil Sharma wrote: How to calculate the size/lenght of an int array which is passed as an ONLY argument to a function??? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Android Project
If you have Android sdk setup then you can find samples in that only. If you haven't done that please find necessary information in http://developer.android.com/index.html - Abhirup On Tue, Jan 31, 2012 at 5:20 PM, saurabh singh saurab...@gmail.com wrote: Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Tue, Jan 31, 2012 at 5:16 PM, rahul sharma rahul23111...@gmail.com wrote: Anybody having small or demo project on android.I need it urgent.Or provide me with link where i can get compile and go project.thanx in advamce -- 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. -- 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] decimal to binary..c code....
I think you have to think about the manual way of doing it - how to handle the integer part and decimal part. You can find this in any standard book. Then try out the algorithm. On Mon, Jan 30, 2012 at 12:26 AM, Rahul Kumar rahul.cs.mn...@gmail.com wrote: ur subject is decimal to binary but in content u have written float to decimal... I don't get it On Sat, Jan 28, 2012 at 11:49 PM, rahul sharma rahul23111...@gmail.com wrote: it should be able to convert not only int but also float like 190.345 to decimalcan ny one suggest thnx in advance -- 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. -- 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] microsoft interview(numbers)
We can build a wrapper object having two fields one th actual integer in the array and the count o the integer in the given array. Then build an array of those objects. Range of this array can be found easily by finding max and min of the array in O(n) time. We can build the auxiliary array in O(n) time. Then we can sort that array on the basis of count field using counting sort in O(n). As counting sort is stable sort if two counts are equal then the sequence is maintained. So the whole process is done in O(n). But the space complexity is O(n) as two auxiliary arrays are needed. -Abhirup On Sun, Jul 4, 2010 at 3:20 AM, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: we can apply that case in the comparator or sort them after counting again in nlogn (with respect to number of occurrences and their first index) since the first occurrence of a number happens when it's not inserted in bst we can do this easily -- 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] Finding Duplicates in Random Array
How can you find smallest element in the array in O(logn) time? Can you please elaborate? -Abhirup On Fri, Jul 2, 2010 at 3:44 PM, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: 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.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. -- 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] lru cache
I think this can be implemented with queue data structure. Whenever an element is used, remove it from the queue use it and then again insert it in the queue at the back. So the front element in the queue is the least recently used one. -Abhirup On Fri, Jul 2, 2010 at 10:23 PM, jaladhi dave jaladhi.k.d...@gmail.com wrote: 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.com wrote: 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. -- 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] 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.
