Re: [algogeeks] Dynamic Programming Problem on Strings
>
>
> void dyckWords(int index, int open, int close)
> {
> static int dyck=0;
> if (index == 2 *n)
> {
> printf("%s\n", out);
> return ;
> }
>
> out[index] = '('; //or A
> if ((open + 1) <= n && open >= close)
>
>
> {
> dyckWords(index + 1, open + 1, close);
> }
> out[index] = ')';//or B
> if ((close + 1) <= n && open >= close)
> {
> dyckWords(index + 1, open, close + 1);
> }
> }
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
> On Mon, Jul 19, 2010 at 1:25 AM, Amir hossein Shahriari <
> amir.hossein.shahri...@gmail.com> wrote:
>
>> @ashish: AAA is the prefix of the string and it is valid as a prefix and
>> it's only used for strings with length >= 6 (where it is a valid prefix)
>> actually only dp[i][j] where i==j counts the number of such strings and
>> otherwise there is no string where i!=j and it that case dp[i][j] counts the
>> number of valid prefixes for string
>> dp[0][0]=1 does satisfy both properties because 0=0 so the number of As &
>> Bs are the same
>> the logic behind n/2 is that if the length of the string is n this means
>> that it has n/2 As and n/2 Bs (n must be even)
>> the dp for n=4 doesn't look like that! this is how it looks (i just
>> compiled the code and checked values of dp):
>> 1 0 0
>> 1 1 0
>> 1 2 2
>> so dp[2][2]=2 which means the number of strings with 2 As and 2 Bs is 2
>>
>>
>> --
>> 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] Dynamic Programming Problem on Strings
void dyckWords(int index, int open, int close)
{
static int dyck=0;
if (index == 2 *n)
{
printf("%s\n", out);
return ;
}
out[index] = '('; //or A
if ((open + 1) <= n && open >= close)
{
dyckWords(index + 1, open + 1, close);
}
out[level] = ')';//or B
if ((close + 1) <= n && open >= close)
{
dyckWords(index + 1, open, close + 1);
}
}
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Mon, Jul 19, 2010 at 1:25 AM, Amir hossein Shahriari <
amir.hossein.shahri...@gmail.com> wrote:
> @ashish: AAA is the prefix of the string and it is valid as a prefix and
> it's only used for strings with length >= 6 (where it is a valid prefix)
> actually only dp[i][j] where i==j counts the number of such strings and
> otherwise there is no string where i!=j and it that case dp[i][j] counts the
> number of valid prefixes for string
> dp[0][0]=1 does satisfy both properties because 0=0 so the number of As &
> Bs are the same
> the logic behind n/2 is that if the length of the string is n this means
> that it has n/2 As and n/2 Bs (n must be even)
> the dp for n=4 doesn't look like that! this is how it looks (i just
> compiled the code and checked values of dp):
> 1 0 0
> 1 1 0
> 1 2 2
> so dp[2][2]=2 which means the number of strings with 2 As and 2 Bs is 2
>
>
> --
> 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] Associativity...............
Both are unary operators and hence the associativity is from right to left. On Wed, Aug 4, 2010 at 8:31 AM, UMESH KUMAR wrote: > How to decide associativity of the operation on operand > so a simple Ex:- > *ptr++ and ++*ptr > how to work both ? > > -- > 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] 1's counting
it is
3*2^12 + 15*2^8 + 3*2^4 + 3
so it becomes
3<<12 + 15<<8 + 3<<4 +3.. let this equal to n
take
while(n){
2010/8/4 Seçkin Can Şahin
> either count it with a for loop or if you are using C, use
> __builtin_popcount(int x)
>
> or
>
> x is given
> int count = 0;
> for(int i=0; i<32;i++) count += (x & (1<
>
> On Tue, Aug 3, 2010 at 12:04 PM, amit wrote:
>
>> (3*4096+15*256+3*16+3). How many 1's are there in the binary
>> representation of the result.
>>
>> Is there a quick way to count the number of set bits in this number
>> manually???
>>
>> --
>> 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.
Re: [algogeeks] 1's counting
Hi Amit, If you are answer this question orally then the format you have given is just a hexadecimal number. Its value would be 0x3f33. So the number of 1's would be simply 2+4+2+2 = 10. Programatically whatever solution Sahin has given seems to be good enough. 2010/8/4 Seçkin Can Şahin > either count it with a for loop or if you are using C, use > __builtin_popcount(int x) > > or > > x is given > int count = 0; > for(int i=0; i<32;i++) count += (x & (1< > > On Tue, Aug 3, 2010 at 12:04 PM, amit wrote: > >> (3*4096+15*256+3*16+3). How many 1's are there in the binary >> representation of the result. >> >> Is there a quick way to count the number of set bits in this number >> manually??? >> >> -- >> 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. > -- Regards Bhanu Mobile +91 9886738496 -- 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] Initialization list
Can someone tell me why the order of initialization in the initialization list of constructor, the order of declaration of data members in C++ ? -- 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: interesting c++ questions
1) Yes ofcourse 2) yes you can 3) yes ofcourse 4) yes 5) i dont think . May we our default constructor def not matching ;) On Aug 3, 8:42 pm, Raj N wrote: > 1) Can a constructor call another constructor to initialize the same > object? > 2) Can a struct variable be assigned to another if the structure > contains an array as a field? > 3) Can we pass a private member by reference to a non member function? > 4) Can the destructor be called explicitly? > 5) Can copy constructor be the default constructor of a class? -- 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] 1's counting
it is
3*2^12 + 15*2^8 + 3*2^4 + 3
so it becomes
3<<12 + 15<<8 + 3<<4 +3.. let this equal to n
take a int count=0;
while(n){
n=n&(n-1);
count++;
}
return count;
2010/8/4 Seçkin Can Şahin
> either count it with a for loop or if you are using C, use
> __builtin_popcount(int x)
>
> or
>
> x is given
> int count = 0;
> for(int i=0; i<32;i++) count += (x & (1<
>
> On Tue, Aug 3, 2010 at 12:04 PM, amit wrote:
>
>> (3*4096+15*256+3*16+3). How many 1's are there in the binary
>> representation of the result.
>>
>> Is there a quick way to count the number of set bits in this number
>> manually???
>>
>> --
>> 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.
Re: [algogeeks] Re: Sapient Interview Question
As per the problem it seems to be that there is one root node (CEO) and all employees are child node. B'cos iin the question it is mentioned that each employee is led by only 1 person except for the CEO (who has no boss). Correct me if I am wrong. On Wed, Aug 4, 2010 at 4:32 PM, Gene wrote: > This is a nice question for them because the idea is simple, but they > have given you a data structure that is not good for the problem. If > each employee records had a list of people the employee leads, it > would be trivially easy. But it doesn't. So in the interview you can > show how smart you are by discussing the pros and cons of defining a > parallel data structure (since you're apparently not allowed to change > this one) to contain child pointers. Or computing all the costs in a > single pass through the whole list of employees and updating these > appropriately as employees are added, deleted, get raises, etc. > > > On Jul 27, 7:57 am, aparichith wrote: > > A company has many employees & each employee is led by only 1 person > > except for the CEO (who has no boss). The cost to the company of an > > employee is the sum of his salary plus the cost to the company of all > > the people led by him. Given is the following structure : > > > > Employee > > > > Data members: > > > > Name > > > > Salary > > > > isBoss > > > > nameOfBoss > > > > Methods: > > > > getSalary > > > > getName > > > > a) Define the class/structure > > > > b) Write a function getCostToCompany() to calculate the cost to > > the company of an employee whose name is passed as a parameter to the > > function getCostToCompany() > > > > public float getCostToCompany(String name) > > > > Note: Don’t write any input functions such as main() & assume that the > > data structures have already been defined > > -- > 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.
[algogeeks] Re: Sapient Interview Question
This is a nice question for them because the idea is simple, but they have given you a data structure that is not good for the problem. If each employee records had a list of people the employee leads, it would be trivially easy. But it doesn't. So in the interview you can show how smart you are by discussing the pros and cons of defining a parallel data structure (since you're apparently not allowed to change this one) to contain child pointers. Or computing all the costs in a single pass through the whole list of employees and updating these appropriately as employees are added, deleted, get raises, etc. On Jul 27, 7:57 am, aparichith wrote: > A company has many employees & each employee is led by only 1 person > except for the CEO (who has no boss). The cost to the company of an > employee is the sum of his salary plus the cost to the company of all > the people led by him. Given is the following structure : > > Employee > > Data members: > > Name > > Salary > > isBoss > > nameOfBoss > > Methods: > > getSalary > > getName > > a) Define the class/structure > > b) Write a function getCostToCompany() to calculate the cost to > the company of an employee whose name is passed as a parameter to the > function getCostToCompany() > > public float getCostToCompany(String name) > > Note: Don’t write any input functions such as main() & assume that the > data structures have already been defined -- 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: algorithm
I posted a more complete solution but it seems to have disappeared. Set up 2 heaps Lo and Hi where Lo has the max at its root and Hi has the min. I.e., Lo is a max heap and Hi is a min heap. Also maintain a variable M. Establish the invariants: 1. N(Lo) = N(Hi) where N(H) is the number of elements in H. 2. max(Lo) <= min(Hi) 3. If M is not empty, then max(Lo) <= M <= min(Hi) >From these you can conclude the following: 1. If M is empty and we have already read some elements, then: Median = (max(Lo) + min(Hi)) / 2. 2. Else M is not empty, then: Median = M Certainly all these inveriants are true when Lo, Hi, and M are all empty. Now it turns out that every time you read a new element, you can add it to one of Lo, Hi, or M and then adjust everything so that the invariants are re-established. This can be accomplished with only a constant number of O(log n) operations. The cases to figure out are: M is not empty and A > M. M is not empty and A = M. M is not empty and A < M. M is empty and the new element A > min(Hi) M is empty and the new element A < max(Lo) M is empty and max(Lo) <= A <= min(Hi). This covers all possible cases, so if you can work out what to do for each one, you are done. I'm not going to spoil the rest of the fun for you. On Aug 3, 1:37 am, bujji wrote: > Can you please explain how keeping two heaps min heap and max heap > help in findingmedianin O(1) time? > > Regards, > Bujji > > On Aug 3, 7:29 am, Gene wrote: > > > > > This is a great solution. > > > On Jul 28, 3:09 am, janak wrote: > > > > How about keeping heap? > > > Have two heaps 1. max heap and 2. min heap > > > keep them equal size all the time and shift top element from one to > > > other when required... > > > > On Wed, Jul 28, 2010 at 7:46 AM, Gene wrote: > > > > I think you have confused the statement of this problem. The "(in > > > > sorted order)" comment makes no sense because amedianis exactly one > > > > number. One number is always sorted. > > > > > After every stream element is read, you want to be able to get the > > > >medianof all elements read so far. > > > > > You're correct that the way to do this is maintain the elements in > > > > some kind of sorted data structure where you have O(1) access to the > > > > middle element. An array or list will work fine, but each stream > > > > element will require O(n) to insert in the sorted order (just as you'd > > > > do for insertion sort). It's easy to use a balanced tree instead. > > > > This reduces the processing time for each element to O(log n). You > > > > must maintain the invariant that the root of the tree is themedian, > > > > so access time is still O(1). When a new element is read, it goes in > > > > either the left or right subtree of the root. This may cause the > > > >medianto shift by 0 or 1 position in either direction. In this case, > > > > you'll always be able to pull the successor or predecessor of the > > > > root--whichever is the newmedian--up to the root by using e.g. AVL > > > > rotations. You'd have to prove that this does not make the tree too > > > > unbalanced so that the O(log n) insertion is hurt, but I don't think > > > > this would be hard. > > > > > On Jul 24, 10:32 am, jalaj jaiswal wrote: > > > >> You are given a stream of numbers which can be positive or negative. > > > >> You are > > > >> required to provide an operation FINDMEDIAN..which when invoked should > > > >> be > > > >> able return themedianof the numbers in stream (in sorted order) in O(1) > > > >> time. > > > > >> Eg: 0 1 2 3 4 > > > >> Right FINDMEDIANreturns 2 asmedian > > > > >> Now input is -2 -4 > > > >> So Stream = 0 1 2 3 -2 -2 -4 > > > >> Sorted Stream would be -4 -2 0 1 2 3 4 and FINDMEDIANreturns 1 > > > > >> -- > > > >> 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 > > > > athttp://groups.google.com/group/algogeeks?hl=en.-Hide quoted text - > > > - Show quoted text -- 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] Re: interesting c++ questions
Can a struct variable be assigned to another if the structure contains an array as a field? You can. But it will be like a shallow copy. if the structure has a pointer variables those memory need to be assigned explicitly. 3) Can we pass a private member by reference to a non member function? No we cannot, otherwise member being private is longer valid. On Wed, Aug 4, 2010 at 11:35 AM, RITESH SRIVASTAV wrote: > 1) A constructor can call another constructor but not for the same > object if we are talking just the precise meaning > of object and not considering the raw storage as Objects. > > 4) Destructor can be called explicitly .This is generally used when u > have used your own new operator so that objects are allocated at some > absolute address and so u can not use delete operator for cleanup. > > On Aug 3, 8:42 pm, Raj N wrote: > > 1) Can a constructor call another constructor to initialize the same > > object? > > 2) Can a struct variable be assigned to another if the structure > > contains an array as a field? > > 3) Can we pass a private member by reference to a non member function? > > 4) Can the destructor be called explicitly? > > 5) Can copy constructor be the default constructor of a class? > > -- > 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.
[algogeeks] Re: interesting c++ questions
1) A constructor can call another constructor but not for the same object if we are talking just the precise meaning of object and not considering the raw storage as Objects. 4) Destructor can be called explicitly .This is generally used when u have used your own new operator so that objects are allocated at some absolute address and so u can not use delete operator for cleanup. On Aug 3, 8:42 pm, Raj N wrote: > 1) Can a constructor call another constructor to initialize the same > object? > 2) Can a struct variable be assigned to another if the structure > contains an array as a field? > 3) Can we pass a private member by reference to a non member function? > 4) Can the destructor be called explicitly? > 5) Can copy constructor be the default constructor of a class? -- 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: Diff b\w BST and binary tree............
See http://en.wikipedia.org/wiki/Binary_search_tree#Insertion Dave On Aug 4, 9:56 am, UMESH KUMAR wrote: > On Tue, Aug 3, 2010 at 11:22 PM, Anand wrote: > > While creating BST we follow the rule that element on the left hand side of > > the root should be less than or equal to the root element and element on the > > right hand side of the root should be greater than or equal to the root > > element. For binary tree we don't follow any rule for creating it. > > > Data structure for both BST & binary tree: we use a simple structure that > > holds a data value and pointer to its left and right child. > > > On Tue, Aug 3, 2010 at 10:18 AM, UMESH KUMAR > > wrote: > > >> what is the main difference b/w BST and Binary tree for the > >> purpose of implementation . > >> and what is the Data structure of that. > > >> -- > >> 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. > > In BST left subTree data is less than or equal to root data and right > Subtree data is greater than or equal to root data then > how to possible Insertion in the Tree .if possible then please send any > C/C++ code > for BST and Binary Tree.- 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: 1's counting
The straightforward way is simply to write the number out in binary and count the one-bits. It works for any number. In this specific case, since the multiplications are by powers of 2, resulting in shifts, and the resulting binary numbers don't overlap, the number of bits is bitcount(3*4096) + bitcount(15*256) + bitcount(3*16) + bitcount(3) = bitcount(3) + bitcount(15) + bitcount(3) + bitcount(3) = 2 + 4 + 2 + 2 = 10. Dave On Aug 3, 2:04 pm, amit wrote: > (3*4096+15*256+3*16+3). How many 1's are there in the binary > representation of the result. > > Is there a quick way to count the number of set bits in this number > manually??? -- 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] 1's counting
wait a sec. Manually!!! you don't want an algo/code ? And all the number has a power of two as multiple. Is it a co-incidence or intended? 2010/8/4 Seçkin Can Şahin > either count it with a for loop or if you are using C, use > __builtin_popcount(int x) > > or > > x is given > int count = 0; > for(int i=0; i<32;i++) count += (x & (1< > > On Tue, Aug 3, 2010 at 12:04 PM, amit wrote: > >> (3*4096+15*256+3*16+3). How many 1's are there in the binary >> representation of the result. >> >> Is there a quick way to count the number of set bits in this number >> manually??? >> >> -- >> 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.
[algogeeks] Associativity...............
How to decide associativity of the operation on operand so a simple Ex:- *ptr++ and ++*ptr how to work both ? -- 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] Diff b\w BST and binary tree............
On Tue, Aug 3, 2010 at 11:22 PM, Anand wrote: > While creating BST we follow the rule that element on the left hand side of > the root should be less than or equal to the root element and element on the > right hand side of the root should be greater than or equal to the root > element. For binary tree we don't follow any rule for creating it. > > Data structure for both BST & binary tree: we use a simple structure that > holds a data value and pointer to its left and right child. > > > On Tue, Aug 3, 2010 at 10:18 AM, UMESH KUMAR wrote: > >> what is the main difference b/w BST and Binary tree for the >> purpose of implementation . >> and what is the Data structure of that. >> >> -- >> 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. > In BST left subTree data is less than or equal to root data and right Subtree data is greater than or equal to root data then how to possible Insertion in the Tree .if possible then please send any C/C++ code for BST and Binary 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] Re: Amazon Placement Question
this code should fail, the recursion backtracking will not work
here(ignoring the return type basic error of this code where on void a not
null root is returned)
take the case when root is leaf and hence leaf is returned so leaf's sibling
(take case where only left leaf is there not the right one) is set using
root->sibling->..whereas the root's siblingh as not been set so far and
hence this is not a stack problem, it is a queue problem
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Mon, Aug 2, 2010 at 7:09 PM, padmanaban sahadevan
wrote:
> try this code guys
>
> i think there is redundancy in condition checking.
>
> if so correct me...
>
> #include
> struct node
> {
> int data;
> struct node* left;
> struct node* right;
> struct node* sibling;
> };
> void connectHorizontal(struct node* root)
> {
> if(root == NULL)
> return root;
> else if(root->left==NULL && root->right ==NULL)
> return root;//return type is void???
> else
> {
> if(root->left !=NULL)
> connectHorizontal(root->left);
> if(root->right!=NULL)
> connectHorizontal(root->right);
> if(root->left!=NULL)
> {
> root->left->sibling = (root->right ? root->right :
> (root->sibling->left ? root->sibling->left : (root->sibling->right ?
> root->sibling->right : NULL)));
> }
> if(root->right!=NULL)
> {
> root->right->sibling = (root->sibling->left ?
> root->sibling->left : (root->sibling->right ? root->sibling->right : NULL));
> }
> }
> }
>
> --
> 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] 1's counting
either count it with a for loop or if you are using C, use __builtin_popcount(int x) or x is given int count = 0; for(int i=0; i<32;i++) count += (x & (1< wrote: > (3*4096+15*256+3*16+3). How many 1's are there in the binary > representation of the result. > > Is there a quick way to count the number of set bits in this number > manually??? > > -- > 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.
[algogeeks] Re: Amazon Placement Question
@ Ashish: make a balanced binary tree of depth >3 and try the approach, u need to save the pointers somewhere if they are in different subtrees and at same level. Stack will be most appropriate one to use for this purpose. On Aug 2, 7:34 pm, Ashish Goel wrote: > why stack? that is DFS > > it would need a queue and a null node inserted as a level is traversed > > something similar to find max width in a tree > > the only differnece is as you move along a level, make the connections > > Best Regards > Ashish Goel > "Think positive and find fuel in failure" > +919985813081 > +919966006652 > > > > On Fri, Jul 30, 2010 at 3:38 AM, Minotauraus wrote: > > Yeah use BFS, push the nodes on a stack and make them point to each > > other. > > > How they point depends on the question, which needs clarification. > > Should they ALL be connected to each other as in A to B and A to C and > > B to C or > > just A to B and B to C. Either way, the above approach should work > > fine. > > > -Minotauraus > > > > > On Thu, Jul 29, 2010 at 11:35 PM, ashish agarwal < > > > > ashish.cooldude...@gmail.com> wrote: > > > > >> please explain q ..i didnt understand > > > > >> On Thu, Jul 29, 2010 at 11:01 AM, irfan > > wrote: > > > > >>> I attended Amazon placement test today . There was a question where i > > > >>> got confused.It is as follows. > > > > >>> Give an algorithm to connect all nodes in one level of a binary tree > > . > > > > >>> 5 > > > >>> 5 > > > >>> / > > > >>> \ / \ > > > >>> 8 2 > 8 > > > >>> > 2 > > > >>> / \ / / > > > >>> \ / > > > >>> 1 2 6 1 ---> 2 > > -->6 > > > > >>> -- > > > >>> 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. > > > > > Sorry for that. I attached a jpg file showing what shud the algo do . > > > > Question is that, we are given a tree. algo shud connect all the nodes > > > > which are in same level. > > > > > -- > > > > 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.-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.- 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] 1's counting
(3*4096+15*256+3*16+3). How many 1's are there in the binary representation of the result. Is there a quick way to count the number of set bits in this number manually??? -- 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: interview-question
@ritesh..you dnt have to output v.. you have to output the minimum number of flips so that your tree evaluates to v(v is either 0 or 1) and if it alreday evaluates to v then return 0(no flips required) if not possible return -1 On Wed, Aug 4, 2010 at 12:11 AM, RITESH SRIVASTAV wrote: > level of the tree is given or not ? > and where do we have to output V , just at the node we get it or at > the root ? > > On Aug 3, 1:56 pm, jalaj jaiswal wrote: > > given a complete binary tree (either a node is a leaf node or has two > > children) > > every leaf node has value 0 or 1. > > every internal node has value as the AND gate or OR gate. > > you are given with the tree and a value V. > > you have to output the minimum number of flips (AND to OR or OR to AND) > if > > the evaluated value is not equal to V, if it is equal return 0, if not > > possible return -1. > > you can just change the value of internal nodes i.e can make and to or , > or > > to and to get the desired output > > give the minimum number of flips required to get the desired output. > > > > -- > > -- > 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.
[algogeeks] interesting c++ questions
1) Can a constructor call another constructor to initialize the same object? 2) Can a struct variable be assigned to another if the structure contains an array as a field? 3) Can we pass a private member by reference to a non member function? 4) Can the destructor be called explicitly? 5) Can copy constructor be the default constructor of a class? -- 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] Copy Constructor and reference
If it isn't passed by reference it goes to an infinite recursion. On Wed, Jul 21, 2010 at 12:08 AM, mallesh wrote: > In C++ Why is it that copy constructor uses only reference as > parameter and not the actual class? > I was given a hint that it has got something to do with stack. I think > it has got something to do with reentrant functions. > > In C also., I think the same thing happens when we pass struct as > parameter to a function, instead of copying the whole structure on to > stack, it takes struct variable's address. > > Can you please explain why this is so? > > -Thanks and regards, > Mallesh > > -- > 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.
[algogeeks] Re: sorting range of numbers in O(n)
Radix uses the count sort..that is why its running time 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.
