Re: [algogeeks] Partition the array with equal average
I guess this is Subset minimization problem's Modification.. Algo.. 1> Get all the Subset of the particular array. Best Algo O(n2). 2> Now try to find the subsets having similar average. Again best algo known is O(n2). Anyone have better options?? BR, Prem On Fri, May 18, 2012 at 12:05 PM, payal gupta wrote: > How do you partition an array into 2 parts such that the two parts have > equal average?...each partition may contain elements that are > non-contiguous in the array... > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/fSAXqe-gkJcJ. > 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.
[algogeeks] Partition the array with equal average
How do you partition an array into 2 parts such that the two parts have equal average?...each partition may contain elements that are non-contiguous in the array... -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/fSAXqe-gkJcJ. 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] Re: validate bit pattern : MS question
i changed the last step to return (n == ~0);
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Fri, May 18, 2012 at 11:27 AM, Vishal Thanki wrote:
> On Sat, Apr 7, 2012 at 11:24 AM, Dave wrote:
> > @Ashgoel: Try this:
> >
> > bool OnesZerosOnes(unsigned int n)
> > {
> > if( !(n & 1) || !(n &= n+1) ) return 0;
> > n |= n-1;
> > return !(n & (n+1));
> > }
> >
> > Here is how it works:
> >
> > !(n & 1) is true if the number has trailing zeros.
> >
> > If the number has trailing ones, n &= n+1 replaces the trailing ones with
> > zeros.
> >
> > !(n &= n+1) is true if there are only trailing ones, i.e., the original
> > number was zeros followed by ones.
> >
> > n |= n-1 replaces trailing zeros with ones. Thus, if the original number
> is
> > ones followed by zeros followed by ones, the zeros have been changed to
> > ones.
> >
> > (n & (n+1)) replaces the trailing ones with zeros. If the number is now
> > zero, the number is valid, otherwise the number is invalid.
> >
> > Dave
> >
> >
>
> Superb, Dave!!
>
> > On Tuesday, April 3, 2012 7:00:36 PM UTC-5, ashgoel wrote:
> >>
> >> verify that the bits of a number are in format 1s followed by 0s
> followed
> >> by 1s like 1110001 is valid but 100100100 is not
> >>
> >> Best Regards
> >> Ashish Goel
> >> "Think positive and find fuel in failure"
> >> +919985813081
> >> +919966006652
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To view this discussion on the web visit
> > https://groups.google.com/d/msg/algogeeks/-/zBATGHVXUTAJ.
> >
> > 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] Interview Question based on histogram
//A <-area of the cell of histogram
// volarr[] <-holds the vol of water already present at particular index
void fn(int index,int volpoured)
{
int vcapacity=A*heightarr[index];
if(volpoured+volarr[index]vcapacity)
{
volpoured-=vcapacity-volarr[index];
volarr[index]=vcapacity;
// if the height of the adjacent left and right columns are both less then
equal amt of water overflows on either sides
if(heightarr[index-1]<=heightarr[index] &&
heightarr[index+1]<=heightarr[index])
{
fn(index+1,volpoured/2);
fn(index-1,volpoured/2);
}
//if the left column has height greater and left has lesser then entire amt
flows to left
else if(heightarr[index-1]>heightarr[index] &&
heightarr[index+1]<=heightarr[index]&& index!=n-1)
fn(index+1,volpoured);
//if the right column has height lesser and right has height greater then
entire amt flows to right
else if(heightarr[index+1]>heightarr[index] &&
heightarr[index-1]<=heightarr[index] && index!=0)
fn(index-1,volpoured);
//if both left and right have height greater then water overflows at the
same index
else
{
printf("overflow occurs at index %d\n",index);
return;
}
}
// sum of the all elemnts of volarr[] gives the water trapped
On Fri, May 18, 2012 at 10:36 AM, Prem Krishna Chettri
wrote:
> Algo Dear.. Algo.. implementation Anyone can Do..
>
> Req ppl to share their own algo.. No Someones Code Implementation..
>
> On Fri, May 18, 2012 at 9:54 AM, payal gupta wrote:
>
>> hope this works..
>> http://ideone.com/XSJRJ
>>
>>
>> On Fri, May 18, 2012 at 8:20 AM, Bhaskar Kushwaha <
>> bhaskar.kushwaha2...@gmail.com> wrote:
>>
>>> It depends on which column you are pouring the water.
>>> For example
>>> If you choose the shortest column to pour the water then only that
>>> column will be filled with water.
>>>
>>> Please correct me if I am wrong.
>>>
>>>
>>> On Thu, May 17, 2012 at 11:27 AM, Nikhil Agarwal <
>>> nikhil.bhoja...@gmail.com> wrote:
>>>
Imagine that you have an histogram stored in an array. Now imagine that
you can pour water on top of your histogram. Describe an algorithm that
computes the amount of water that remains trapped among the columns of the
graph. Clearly on the edges the water would fall off. Use the language or
the pseudocode you prefer.
--
Thanks & Regards
Nikhil Agarwal
B.Tech. in Computer Science & Engineering
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
http://beta.freshersworld.com/communities/nitd
--
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.
>>>
>>>
>>>
>>> --
>>> regards,
>>> Bhaskar Kushwaha
>>> Student
>>> CSE
>>> Third year
>>> M.N.N.I.T. Allahabad
>>>
>>>
>>> --
>>> 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.
>
--
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] Re: Algo for Search in a 2D Matrix
Anika, what you are talking about is finding a specific element, not the
kth largest or smallest element, can you give a walk through with an
example in case i have understood you incorrectly
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Thu, May 17, 2012 at 3:33 PM, Anika Jain wrote:
> there's a solution of O(log n) where 2D matrix has n rows and n columns.
> Apply binary search for the search on the diagonal. when you are left with
> just one element after the search apply binary search within that elements
> row and its column. you will get the element. O(log n+log n+log n). so
> O(log n).
>
>
> On Wed, May 16, 2012 at 6:36 PM, Prem Krishna Chettri
> wrote:
>
>> Well I hv got Something running in my mind buy ofcse need some cornor
>> case tuning.
>>
>> If we take sqrt() of the number (say K) than we can avoid looking into
>> sqrt(k)-1 and sqrt(k)+1 rows and column entirely, which literally means
>> that the final solution is possible in constant time (the time independent
>> of k or matrix values), which ofcourse can go upto O(n) in worst case where
>> N is the Matrix of N Rows and 1 Column as we cannot use the intelligence of
>> sqrt function to corner the value.
>>
>> Its seems okei logically to remove those rows and columns as we are
>> certain that they are sorted in both ways and avoid unnecessary time
>> looking for the place where it won't belong.
>>
>> Now the issue is so clear that we can say (sqrt(k)-1)*(sqrt(k)-1)> now keep on adding the value to sqrt(k)+1 till U reach k and get corner
>> that element.
>>
>> I guess it works..
>>
>>
>>
>> On Wed, May 16, 2012 at 1:17 PM, Ashish Goel wrote:
>>
>>> Vikas, can you suggest the logic of this also? I am a bit unclear on how
>>> the 2D arr is being used as a heap and how recursion is used to solve this
>>>
>>> Best Regards
>>> Ashish Goel
>>> "Think positive and find fuel in failure"
>>> +919985813081
>>> +919966006652
>>>
>>>
>>>
>>> On Thu, Oct 13, 2011 at 11:37 PM, vikas wrote:
>>>
@Sunny, good catch, k X k approach wont work
lets try to use matrix itself as heap
heapify(int cr, int cc, int Nr, int Nc){
mr = cr; mc = cc;
if(cr+1 < Nr)
mr = cr+1 mc = cc;
if(cc + 1 < Nc && min > A[cc+1][cr])
mr = cr; mc = cc+1;
if(A[cr][cc] > A[mr][mc]){
swap(&A[cr][cc] ,&A[mr][mc]);
heapify(mr, mc, Nr, Nc);
}
extract_min(){
swap(&A[0][0], &A[hr][hc]);
if(hc > 0) hc--;
else if(hr > 0){
hr --;
hc = N;
}
if(hr | hc)
heapify(0, 0, hr, hc);
}
}
On Oct 13, 12:18 pm, sunny agrawal wrote:
> Nopes
> Still it does not ensure that duplicates will not be there in the
priority
> queue
>
> what i mean is you cannot write directly
>
> do k times{
> data = pop()
> // let i,j are row and col of data
> push(i+1,j);
> push(i,j+1);
>
> }
>
> you need to add the following checks
>
> if((i+1,j) is not in the heap) push(i+1,j)
> if((i,j+1) is not in the heap) push(i,j+1)
> because heap does not automatically check for duplicates
>
> and to check for duplicates we need an extra data structure other
than heap,
> which stores that which (i+1,j) are already there in the heap map can
also
> be used so overall complexity will go O(k* lg^2K)
>
> On Thu, Oct 13, 2011 at 12:26 PM, anshu mishra <
anshumishra6...@gmail.com>wrote:
>
>
>
> > struct data
> > {
> > int row, col,
> > int val;
> > };
>
> > priority_queue heap;
>
> > now fine?
>
> > --
> > 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.
>
> --
> Sunny Aggrawal
> B.Tech. V year,CSI
> Indian Institute Of Technology,Roorkee
--
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
>
Re: [algogeeks] Re: storing URL's
Tiger Tree Hash Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Thu, May 17, 2012 at 11:16 PM, Prem Krishna Chettri wrote: > For the cases where Storing the Value is the only Concern and (Not the > Retrieval efficiency), I would Suggest Something called DFA Subset > minimization.. Google for it ... and after the final subset as said U can > use something called DAWG for the most Most Optimal solution.. > > > On Thu, May 17, 2012 at 2:58 PM, Prakash D wrote: > >> We can still improve this trie idea.. >> >> say we have urls like >> www.google.com >> www.goodbye.com >> www.google.com/transliterate >> www.goodstrain.com/good >> >> we can subdivide everything under "www.goo" >> I mean we can store each character as a node in a trie and call it >> like a "URL dictionary" >> >> >> On Wed, May 16, 2012 at 5:43 PM, omega9 >> wrote: >> > >> > >> > On May 16, 10:33 am, atul anand wrote: >> >> @amit : >> >> >> >> here is the reason :- >> >> >> >> each url sayhttp://www.geeksforgeeks.org >> >> >> >> you will hash following urlshttp://www.geeksforgeeks.orghttp:// >> www.geeksforgeeks.org/archiveshttp://www.geeksforgeeks.org/archives/19248http://www.geeksforgeeks.org/archives/http://www.geeksforgeeks.org/archives/19221http://www.geeksforgeeks.org/archives/19290http://www.geeksforgeeks.org/archives/1876http://www.geeksforgeeks.org/archives/1763 >> >> >> >> "http://www.geeksforgeeks.org"; is the redundant part in each url >> . it >> >> would unnecessary m/m to save all URLs. >> >> >> >> ok now say file have 20 million urls . .now what would you >> do.?? >> >> >> > >> > I think the trie suggestion was good. Have each domain (with the >> > protocol part) as a node and then have the subsequent directory >> > locations as a hierarchy under it. >> > >> > -- >> > 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. > -- 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] Re: validate bit pattern : MS question
On Sat, Apr 7, 2012 at 11:24 AM, Dave wrote:
> @Ashgoel: Try this:
>
> bool OnesZerosOnes(unsigned int n)
> {
> if( !(n & 1) || !(n &= n+1) ) return 0;
> n |= n-1;
> return !(n & (n+1));
> }
>
> Here is how it works:
>
> !(n & 1) is true if the number has trailing zeros.
>
> If the number has trailing ones, n &= n+1 replaces the trailing ones with
> zeros.
>
> !(n &= n+1) is true if there are only trailing ones, i.e., the original
> number was zeros followed by ones.
>
> n |= n-1 replaces trailing zeros with ones. Thus, if the original number is
> ones followed by zeros followed by ones, the zeros have been changed to
> ones.
>
> (n & (n+1)) replaces the trailing ones with zeros. If the number is now
> zero, the number is valid, otherwise the number is invalid.
>
> Dave
>
>
Superb, Dave!!
> On Tuesday, April 3, 2012 7:00:36 PM UTC-5, ashgoel wrote:
>>
>> verify that the bits of a number are in format 1s followed by 0s followed
>> by 1s like 1110001 is valid but 100100100 is not
>>
>> Best Regards
>> Ashish Goel
>> "Think positive and find fuel in failure"
>> +919985813081
>> +919966006652
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/zBATGHVXUTAJ.
>
> 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] Re: validate bit pattern : MS question
Hii Can anyone explain to me what this code is doing??
On 17 May 2012 20:36, Ashish Goel wrote:
> got it...super...
>
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
> On Thu, May 17, 2012 at 8:21 PM, Ashish Goel wrote:
>
>> Hello Dave,
>>
>> Was trying this
>>
>> bool OnesZerosOnes(unsigned int n)
>> {
>> if( !(n & 1) || !(n &= n+1) ) return 0; /*step1*/
>> n |= n-1;/*step 2*/
>> return !(n & (n+1)); /*step 3*/
>> }
>>
>>
>> for 1110011
>> after step 1 it becomes 1110011&1110100=111
>> after step2 it becomes 111|110=111(all ones)
>> on step 3 we return~(111&000) = 1
>>
>> for 1010011
>> after step 1 it becomes 1010011&1010100=101
>> after step2 it becomes 101|100=101
>> on step 3 we return~(101&110) = 0
>>
>>
>> what are we trying to do with step 3 here
>>
>> Best Regards
>> Ashish Goel
>> "Think positive and find fuel in failure"
>> +919985813081
>> +919966006652
>>
>>
>> On Sat, Apr 7, 2012 at 11:24 AM, Dave wrote:
>>
>>> bool OnesZerosOnes(unsigned int n)
>>> {
>>> if( !(n & 1) || !(n &= n+1) ) return 0;
>>> n |= n-1;
>>> return !(n & (n+1));
>>> }
>>>
>>
>>
> --
> 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.
>
--
*Piyush Khandelwal***
Mobile No: 91-8447229204
91-9808479765
--
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] Interview Question based on histogram
hope this works.. http://ideone.com/XSJRJ On Fri, May 18, 2012 at 8:20 AM, Bhaskar Kushwaha < bhaskar.kushwaha2...@gmail.com> wrote: > It depends on which column you are pouring the water. > For example > If you choose the shortest column to pour the water then only that column > will be filled with water. > > Please correct me if I am wrong. > > > On Thu, May 17, 2012 at 11:27 AM, Nikhil Agarwal < > nikhil.bhoja...@gmail.com> wrote: > >> Imagine that you have an histogram stored in an array. Now imagine that >> you can pour water on top of your histogram. Describe an algorithm that >> computes the amount of water that remains trapped among the columns of the >> graph. Clearly on the edges the water would fall off. Use the language or >> the pseudocode you prefer. >> >> -- >> Thanks & Regards >> Nikhil Agarwal >> B.Tech. in Computer Science & Engineering >> National Institute Of Technology, Durgapur,India >> http://tech-nikk.blogspot.com >> http://beta.freshersworld.com/communities/nitd >> >> >> -- >> 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. >> > > > > -- > regards, > Bhaskar Kushwaha > Student > CSE > Third year > M.N.N.I.T. Allahabad > > > -- > 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] Interview Question based on histogram
It depends on which column you are pouring the water. For example If you choose the shortest column to pour the water then only that column will be filled with water. Please correct me if I am wrong. On Thu, May 17, 2012 at 11:27 AM, Nikhil Agarwal wrote: > Imagine that you have an histogram stored in an array. Now imagine that > you can pour water on top of your histogram. Describe an algorithm that > computes the amount of water that remains trapped among the columns of the > graph. Clearly on the edges the water would fall off. Use the language or > the pseudocode you prefer. > > -- > Thanks & Regards > Nikhil Agarwal > B.Tech. in Computer Science & Engineering > National Institute Of Technology, Durgapur,India > http://tech-nikk.blogspot.com > http://beta.freshersworld.com/communities/nitd > > > -- > 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. > -- regards, Bhaskar Kushwaha Student CSE Third year M.N.N.I.T. Allahabad -- 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] Re: storing URL's
For the cases where Storing the Value is the only Concern and (Not the Retrieval efficiency), I would Suggest Something called DFA Subset minimization.. Google for it ... and after the final subset as said U can use something called DAWG for the most Most Optimal solution.. On Thu, May 17, 2012 at 2:58 PM, Prakash D wrote: > We can still improve this trie idea.. > > say we have urls like > www.google.com > www.goodbye.com > www.google.com/transliterate > www.goodstrain.com/good > > we can subdivide everything under "www.goo" > I mean we can store each character as a node in a trie and call it > like a "URL dictionary" > > > On Wed, May 16, 2012 at 5:43 PM, omega9 wrote: > > > > > > On May 16, 10:33 am, atul anand wrote: > >> @amit : > >> > >> here is the reason :- > >> > >> each url sayhttp://www.geeksforgeeks.org > >> > >> you will hash following urlshttp://www.geeksforgeeks.orghttp:// > www.geeksforgeeks.org/archiveshttp://www.geeksforgeeks.org/archives/19248http://www.geeksforgeeks.org/archives/http://www.geeksforgeeks.org/archives/19221http://www.geeksforgeeks.org/archives/19290http://www.geeksforgeeks.org/archives/1876http://www.geeksforgeeks.org/archives/1763 > >> > >> "http://www.geeksforgeeks.org"; is the redundant part in each url . > it > >> would unnecessary m/m to save all URLs. > >> > >> ok now say file have 20 million urls . .now what would you do.?? > >> > > > > I think the trie suggestion was good. Have each domain (with the > > protocol part) as a node and then have the subsequent directory > > locations as a hierarchy under it. > > > > -- > > 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] Re: Find Power(N,N),
@ pankaj joshi: Hi ... The following code will do it for you. Go through
the code, execute it, if u dont get the logic revert back to me.
// code begins..
#include
#define MAX 1
void factorialof(int);
void multiply(int);
int length = 0;
int fact[MAX];
int main(){
int num;
int i;
printf("Enter any integer number : ");
scanf("%d",&num);
fact[0]=1;
factorialof(num);
printf("Result is : ");
for(i=length;i>=0;i--){
printf("%d",fact[i]);
}
return 0;
}
void factorialof(int num){
int i;
for(i=1;i<=num;i++){
multiply(num);
}
}
void multiply(int num){
long i,r=0;
int arr[MAX];
for(i=0;i<=length;i++){
arr[i]=fact[i];
}
for(i=0;i<=length;i++){
fact[i] = (arr[i]*num + r)%10;
r = (arr[i]*num + r)/10;
//printf("%d ",r);
}
if(r!=0){
while(r!=0){
fact[i]=r%10;
r= r/10;
i++;
}
}
length = i-1;
}
// code terminates..
On 17 May 2012 11:12, Prem Krishna Chettri wrote:
> Yes U are Correct.. in Such cases the Compiler itself has overcome ( or
> tried to overcome) the architecture limitations to some extends but what
> will happen if U need say 128 or 256 or more values??
>
> Again U hv your compiler restricted limitation right? So that what I
> am talking about is.. Write a code which accept all the value yet fits in
> 8/16/32 bit compiler and architecture...
>
> Yes I am talking more optimistic way as I am talking about embedded
> technologies.But there will be one limitationl which can't be overcome and
> that is the maximum registers available.
>
> When your code finally runs it will be using assembly language.. where the
> operation like R1=M[SP+8] kinda operation happens.. Now the more advance
> processors will hv this register of 32 bit ( Guess intel i7 ships 64 bit as
> well). but these registers are limited..unlike memories in heap.
>
>
> So if M talking about 8085/6 processor, there are 8/16 of these 8 bit
> registers.. So the max U can really force your calculation to have is
> 8*8=64 bit operation or 8*16=128 bit operation. singly.
>
> but with latest intel i7's it can go much higher.. that why these
> processors are expensive :)
>
>
> On Thu, May 17, 2012 at 10:41 AM, pankaj joshi wrote:
>
>> @Victor: - hi i have tried with 2 array but the complexity will increases
>> as the n grows.
>> So can you please share your code, if you have done this
>> already.
>> @Prem:- Actually the ALU does only 32 bit calculation, but if i am
>> telling about VC++(or can be any compiler)
>> support the calulation long long (8 byte , 64 bit), then
>> the compiler will do the calculation such a way that
>> the result of the calculation save in two memory locations.
>> ( i think, please correct me if i am wrong),
>> @don: - Don actually the problem wants the full value not the truncated
>> double values .
>> but anyway thanks for exp(log(n)*n) :)
>>
>> On Thu, May 17, 2012 at 4:52 AM, Don wrote:
>>
>>> How about
>>>
>>> exp(log(n)*n);
>>>
>>> Don
>>>
>>> On May 14, 10:58 pm, pankaj joshi wrote:
>>> > Hi All,
>>> >
>>> > I have written a program to find out n^n(n power n),
>>> >
>>> > long long unsigned int power(int n, int i)
>>> > {
>>> > if(i == 1)
>>> > {
>>> > return n;}
>>> >
>>> > else
>>> > {
>>> > if(i%2 != 1)
>>> > {
>>> > long long unsigned int mul;
>>> > mul = power(n,i/2);
>>> > return mul*mul;}
>>> >
>>> > else
>>> > {
>>> > return (power(n,i-1)*n);
>>> >
>>> > }
>>> > }
>>> > }
>>> >
>>> > This program is working fine for power(15,15), but it is overflow for
>>> > power(16,16), as long long unsigned int is 2^64.
>>> >
>>> > Please tell me how to store the values more than 2^64,
>>> > i had thing to store in array.
>>> > Please suggest me .
>>> >
>>> > thanks ..
>>> >
>>> > --
>>> > Regards,
>>> >
>>> > Pankaj Kumar Joshi
>>>
>>> --
>>> 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.
>>>
>>>
>>
>>
>> --
>> Regards,
>>
>> Pankaj Kumar Joshi
>>
>> --
>> 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
Re: [algogeeks] Re: storing URL's
We can still improve this trie idea.. say we have urls like www.google.com www.goodbye.com www.google.com/transliterate www.goodstrain.com/good we can subdivide everything under "www.goo" I mean we can store each character as a node in a trie and call it like a "URL dictionary" On Wed, May 16, 2012 at 5:43 PM, omega9 wrote: > > > On May 16, 10:33 am, atul anand wrote: >> @amit : >> >> here is the reason :- >> >> each url sayhttp://www.geeksforgeeks.org >> >> you will hash following >> urlshttp://www.geeksforgeeks.orghttp://www.geeksforgeeks.org/archiveshttp://www.geeksforgeeks.org/archives/19248http://www.geeksforgeeks.org/archives/http://www.geeksforgeeks.org/archives/19221http://www.geeksforgeeks.org/archives/19290http://www.geeksforgeeks.org/archives/1876http://www.geeksforgeeks.org/archives/1763 >> >> "http://www.geeksforgeeks.org"; is the redundant part in each url . it >> would unnecessary m/m to save all URLs. >> >> ok now say file have 20 million urls . .now what would you do.?? >> > > I think the trie suggestion was good. Have each domain (with the > protocol part) as a node and then have the subsequent directory > locations as a hierarchy under it. > > -- > 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] Amazon off campus telephonic interview
Usual data structures and algorithmic questions. They love the guys who can do actual coding, instead of blurting it out in pseudo-codes, since its a telephonic interview, I think its going to be different for you. On Wed, May 16, 2012 at 6:37 PM, rishabh shukla wrote: > Anyone recently appeared in Amazon telephonic interview...plzz tell what > sort of question they asked ?? > > -- > Rishabh Shukla > B.Tech Final Year > 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 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] Re: validate bit pattern : MS question
got it...super...
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Thu, May 17, 2012 at 8:21 PM, Ashish Goel wrote:
> Hello Dave,
>
> Was trying this
>
> bool OnesZerosOnes(unsigned int n)
> {
> if( !(n & 1) || !(n &= n+1) ) return 0; /*step1*/
> n |= n-1;/*step 2*/
> return !(n & (n+1)); /*step 3*/
> }
>
>
> for 1110011
> after step 1 it becomes 1110011&1110100=111
> after step2 it becomes 111|110=111(all ones)
> on step 3 we return~(111&000) = 1
>
> for 1010011
> after step 1 it becomes 1010011&1010100=101
> after step2 it becomes 101|100=101
> on step 3 we return~(101&110) = 0
>
>
> what are we trying to do with step 3 here
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
> On Sat, Apr 7, 2012 at 11:24 AM, Dave wrote:
>
>> bool OnesZerosOnes(unsigned int n)
>> {
>> if( !(n & 1) || !(n &= n+1) ) return 0;
>> n |= n-1;
>> return !(n & (n+1));
>> }
>>
>
>
--
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] Re: validate bit pattern : MS question
Hello Dave,
Was trying this
bool OnesZerosOnes(unsigned int n)
{
if( !(n & 1) || !(n &= n+1) ) return 0; /*step1*/
n |= n-1;/*step 2*/
return !(n & (n+1)); /*step 3*/
}
for 1110011
after step 1 it becomes 1110011&1110100=111
after step2 it becomes 111|110=111(all ones)
on step 3 we return~(111&000) = 1
for 1010011
after step 1 it becomes 1010011&1010100=101
after step2 it becomes 101|100=101
on step 3 we return~(101&110) = 0
what are we trying to do with step 3 here
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Sat, Apr 7, 2012 at 11:24 AM, Dave wrote:
> bool OnesZerosOnes(unsigned int n)
> {
> if( !(n & 1) || !(n &= n+1) ) return 0;
> n |= n-1;
> return !(n & (n+1));
> }
>
--
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] Re: Algo for Search in a 2D Matrix
there's a solution of O(log n) where 2D matrix has n rows and n columns.
Apply binary search for the search on the diagonal. when you are left with
just one element after the search apply binary search within that elements
row and its column. you will get the element. O(log n+log n+log n). so
O(log n).
On Wed, May 16, 2012 at 6:36 PM, Prem Krishna Chettri wrote:
> Well I hv got Something running in my mind buy ofcse need some cornor case
> tuning.
>
> If we take sqrt() of the number (say K) than we can avoid looking into
> sqrt(k)-1 and sqrt(k)+1 rows and column entirely, which literally means
> that the final solution is possible in constant time (the time independent
> of k or matrix values), which ofcourse can go upto O(n) in worst case where
> N is the Matrix of N Rows and 1 Column as we cannot use the intelligence of
> sqrt function to corner the value.
>
> Its seems okei logically to remove those rows and columns as we are
> certain that they are sorted in both ways and avoid unnecessary time
> looking for the place where it won't belong.
>
> Now the issue is so clear that we can say (sqrt(k)-1)*(sqrt(k)-1) now keep on adding the value to sqrt(k)+1 till U reach k and get corner
> that element.
>
> I guess it works..
>
>
>
> On Wed, May 16, 2012 at 1:17 PM, Ashish Goel wrote:
>
>> Vikas, can you suggest the logic of this also? I am a bit unclear on how
>> the 2D arr is being used as a heap and how recursion is used to solve this
>>
>> Best Regards
>> Ashish Goel
>> "Think positive and find fuel in failure"
>> +919985813081
>> +919966006652
>>
>>
>>
>> On Thu, Oct 13, 2011 at 11:37 PM, vikas wrote:
>>
>>> @Sunny, good catch, k X k approach wont work
>>>
>>> lets try to use matrix itself as heap
>>>
>>> heapify(int cr, int cc, int Nr, int Nc){
>>> mr = cr; mc = cc;
>>> if(cr+1 < Nr)
>>>mr = cr+1 mc = cc;
>>> if(cc + 1 < Nc && min > A[cc+1][cr])
>>> mr = cr; mc = cc+1;
>>> if(A[cr][cc] > A[mr][mc]){
>>> swap(&A[cr][cc] ,&A[mr][mc]);
>>> heapify(mr, mc, Nr, Nc);
>>> }
>>>
>>> extract_min(){
>>> swap(&A[0][0], &A[hr][hc]);
>>> if(hc > 0) hc--;
>>> else if(hr > 0){
>>> hr --;
>>> hc = N;
>>> }
>>> if(hr | hc)
>>> heapify(0, 0, hr, hc);
>>> }
>>>
>>>
>>> }
>>>
>>>
>>> On Oct 13, 12:18 pm, sunny agrawal wrote:
>>> > Nopes
>>> > Still it does not ensure that duplicates will not be there in the
>>> priority
>>> > queue
>>> >
>>> > what i mean is you cannot write directly
>>> >
>>> > do k times{
>>> > data = pop()
>>> > // let i,j are row and col of data
>>> > push(i+1,j);
>>> > push(i,j+1);
>>> >
>>> > }
>>> >
>>> > you need to add the following checks
>>> >
>>> > if((i+1,j) is not in the heap) push(i+1,j)
>>> > if((i,j+1) is not in the heap) push(i,j+1)
>>> > because heap does not automatically check for duplicates
>>> >
>>> > and to check for duplicates we need an extra data structure other than
>>> heap,
>>> > which stores that which (i+1,j) are already there in the heap map can
>>> also
>>> > be used so overall complexity will go O(k* lg^2K)
>>> >
>>> > On Thu, Oct 13, 2011 at 12:26 PM, anshu mishra <
>>> anshumishra6...@gmail.com>wrote:
>>> >
>>> >
>>> >
>>> > > struct data
>>> > > {
>>> > > int row, col,
>>> > > int val;
>>> > > };
>>> >
>>> > > priority_queue heap;
>>> >
>>> > > now fine?
>>> >
>>> > > --
>>> > > 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.
>>> >
>>> > --
>>> > Sunny Aggrawal
>>> > B.Tech. V year,CSI
>>> > Indian Institute Of Technology,Roorkee
>>>
>>> --
>>> 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.
>
--
Regards
Anika Jain
--
You received this message because you are subscribed to the
