Re: [algogeeks] Re: In place sorting
Since the composite of two arrays would result in almost sorted arrays, insertion sort can be used here. On Wed, Dec 29, 2010 at 2:55 PM, monty 1987 <1986mo...@gmail.com> wrote: > hi , > this is not a research kind of problem i expect a simple answer. > > > On Wed, Dec 29, 2010 at 2:33 PM, juver++ wrote: > >> Use inplace merge algorithms along with merge sort. >> http://www.logiccoder.com/Downloads/krnrd20.pdf >> >> -- >> 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] Do This
Wouldn't the address of the fourth pointer be the link pointer in the current 3rd element. On Wed, Oct 6, 2010 at 10:44 PM, shoban babu wrote: > In a linked list how to insert an element at 3rd position given a pointer > to 4th position. > > -- > Shoban babu.B > M.E.,CSA, > IISc. > > -- > 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] Re: BST in BT
@Prodigy As per your example, 8 15 20 25 which is the is indeed the maximum binary search tree in this binary tree is only a solution to smaller problem used to solve a bigger problem. The solution to smaller problem can be translated directly to the solution of the bigger problem. On Mon, Sep 27, 2010 at 8:28 AM, prodigy <1abhishekshu...@gmail.com> wrote: > 15 > /\ > 8 25 > /\ > 20 22 > > > On Sep 26, 10:45 am, Chonku wrote: > > This can also be done if we do an inorder traversal of the binary tree > and > > look for the longest continuous sequence of numbers in ascending order. > > Your idea will fail for above case. > > In Order => 8 15 20 25 22 > longest continuous sequence of numbers in ascending order => 8 15 20 > 25 > > But that's not the answer (I hope you realize what correct output > would be ) > > > > > > -- > 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] Re: BST in BT
This can also be done if we do an inorder traversal of the binary tree and look for the longest continuous sequence of numbers in ascending order. On Sun, Sep 26, 2010 at 11:10 AM, mac adobe wrote: > No parody .. that would be another doubt :( > > > On Sat, Sep 25, 2010 at 11:03 PM, prodigy <1abhishekshu...@gmail.com>wrote: > >> By maintaining a current maximum and a global maximum. You do know how >> to verify a BT is BST . >> >> http://pastebin.com/xwXXTEnP >> >> On Sep 25, 9:04 pm, mac adobe wrote: >> > How would you identify a binary search tree of maximum nodes in a 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. >> >> > -- > 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] Yahoo Question
Use k way merging On Wed, Sep 15, 2010 at 3:30 PM, bittu wrote: > You are given k sorted lists with total n inputs in all the lists > devise a algorithm to merge them into one single sorted list in O(n > logk) > > > > Regard's > Shashank Mani Narayan " Don't Be Evil U Can Earn While U learn" > Computer Science & Engineering > Birla Institute of Technology,Mesra > Cell No. +91-9166674831 > > -- > 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] Re: Amazon intern Question
Does similarity here refer to similarity in strings or similar to items in same category ? If its similarity to strings then edit distance can be used here. But if its the latter, then how will edit distance help ? It would probably be only looking for items in the same category. On Thu, Sep 2, 2010 at 7:10 AM, Gene wrote: > Even if you're only matching words, there are different kinds of > similarity. Check out the soundex algorithm, for example. Levenshtein > distance. The Hungarian algorithm. What does "50% similarity" mean > anyway? I know of no accepted meaning. > > My point is that if you're in an interview situation and you ask > intelligent questions about the question you're asked, you are more > likely to get the job. At least I would be more likely to give it to > you. I've been responsible for hiring quite a few people. > > On Sep 1, 11:52 am, Chakravarthi Muppalla wrote: > > @Gene, it isn't about related words, its abt matching words! > > > > On Wed, Sep 1, 2010 at 8:26 PM, saurabh singh >wrote: > > > > > I think DS will be somewhere between suffix and trie DS > > > > > On Wed, Sep 1, 2010 at 9:35 AM, jaladhi dave >wrote: > > > > >> trie > > > > >> On Wed, Sep 1, 2010 at 5:45 PM, Arun wrote: > > > > >>> You are given the amazon.com database which consists of names of > > >>> millions of products. When a user enters a search query for > particular > > >>> object with the keyword say "foo" , output all the products which > have > > >>> names having 50% or more similarity with the given keyword ie "foo" > > > > >>> Write the most efficient algorithm for the same. > > > > >>> -- > > >>> 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. > > > > > -- > > > Thanks & Regards, > > > Saurabh > > > > > -- > > > 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. > > > > -- > > Thanks & Regards, > > Chakravarthi. > > -- > 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] Re: Binary tree to LL
@albert I am not forming a separate list. My assumption was that next pointer is present in the node. But I will try to post a solution with only left and right pointers. On Mon, Aug 30, 2010 at 12:10 AM, albert theboss wrote: > @Chonku: > > you cant use "next" pointer in that... > > you have to make link list such that right ptr points to next node > > and left pointer to prev node > > Am i right??? > correct me if i am wrong. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Binary tree to LL
Made some changes.
flattenTree(TreeNode node,TreeNode previous) {
if (node is leaf) {
previous = node
return;
}
flattenTree(node->left,previous);
if (previous != null) {
previous->next = node;
previous=node;
}
flattenTree(node->right,previous);
}//End-flattenTree
On Sat, Aug 28, 2010 at 9:03 PM, Giri wrote:
> @Chonku:
> yours is wrong. consider the given ex,.
>50
> / \
> 25 60
> / \ / \
> 530 55 75
>
> 5 will become head. 5->next=25. 25->next=30. then 25 will be returned
> up.
> so 25->next=50. which is wrong
>
> On Aug 26, 11:36 pm, Chonku wrote:
> > At first, store the pointer to the first node in inorder traversal (in
> this
> > case 5) because its going to be the head of the list.
> > Then use the following logic.
> >
> > flattenTree(TreeNode node) {
> > if (node is leaf node)
> >return node;
> >
> > if (node.left exists) then
> > flattenTree(node.left)->next = node;
> >
> > if (node.right exists) then
> > node->next = flattenTree(node.right);
> >
> > return node;
> >
> > }
> >
> > On Thu, Aug 26, 2010 at 11:07 PM, Yan Wang >wrote:
> >
> >
> >
> > > I can only figure out the inorder traversal...
> >
> > > On Thu, Aug 26, 2010 at 9:59 AM, krazee koder
> > > wrote:
> > > > Give all possible methods to flatten a binary tree to a linked list.
> >
> > > > for eg.
> >
> > > > 50
> > > > / \
> > > > 25 60
> > > > / \ / \
> > > > 530 55 75
> >
> > > > should be flattened to 5->25->30->50->55->60->75
> >
> > > > PS: note that the tree should be converted to the LL and no separate
> > > > LL should be formed.
> >
> > > > --
> > > > 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.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Binary tree to LL
At first, store the pointer to the first node in inorder traversal (in this
case 5) because its going to be the head of the list.
Then use the following logic.
flattenTree(TreeNode node) {
if (node is leaf node)
return node;
if (node.left exists) then
flattenTree(node.left)->next = node;
if (node.right exists) then
node->next = flattenTree(node.right);
return node;
}
On Thu, Aug 26, 2010 at 11:07 PM, Yan Wang wrote:
> I can only figure out the inorder traversal...
>
> On Thu, Aug 26, 2010 at 9:59 AM, krazee koder
> wrote:
> > Give all possible methods to flatten a binary tree to a linked list.
> >
> > for eg.
> >
> > 50
> > / \
> > 25 60
> > / \ / \
> > 530 55 75
> >
> >
> > should be flattened to 5->25->30->50->55->60->75
> >
> > PS: note that the tree should be converted to the LL and no separate
> > LL should be formed.
> >
> > --
> > 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] Re: National Instruments: linked list subtraction
We can take the two's complement of the smaller number and add it to the
first.
a) Get Number from 1st linked List. - num1
b) Get Number from 2nd Linked List - num2
c) Get Two's complement of smaller number and add it to the larger number.
d) Create a linked list of the result.
On Thu, Aug 26, 2010 at 8:28 AM, Gene wrote:
> This is close, but more complicated than necessary. After you know
> how many leading zeros are needed before B, just act like they're
> present and use recursion to process right-to-left:
>
> #include
> #include
>
> typedef struct digit_s {
> struct digit_s *next;
> int val;
> } DIGIT;
>
> DIGIT *new_digit(int val, DIGIT *next)
> {
> DIGIT *d = malloc(sizeof *d);
> d->val = val;
> d->next = next;
> return d;
> }
>
> int length(DIGIT *d)
> {
> int n = 0;
> while (d) {
>n++;
>d = d->next;
> }
> return n;
> }
>
> void print(DIGIT *d)
> {
> while (d) {
>printf("%d", d->val);
>d = d->next;
> }
> }
>
> static DIGIT *
> do_sub(DIGIT *a, int n_leading_zeros, DIGIT *b, int *borrow)
> {
> DIGIT *rtn;
> int b_val, val;
>
> if (a == NULL) { // b is NULL, too
>*borrow = 0;
>return NULL;
> }
> if (n_leading_zeros > 0) {
>rtn = do_sub(a->next, n_leading_zeros - 1, b, borrow);
>b_val = 0;
> }
> else {
>rtn = do_sub(a->next, 0, b->next, borrow);
>b_val = b->val;
> }
> // Subtract including borrow from previous.
> val = a->val - b_val - *borrow;
> // See if we need to borrow from the next digit.
> if (val < 0) {
>val += 10;
>*borrow = 1;
> }
> else {
>*borrow = 0;
> }
> return new_digit(val, rtn);
> }
>
> DIGIT *subtract(DIGIT *a, DIGIT *b)
> {
> int borrow;
> return do_sub(a, length(a) - length(b), b, &borrow);
> }
>
> int main(void)
> {
> DIGIT *a =
>new_digit(5,
>new_digit(4,
>new_digit(2,
>new_digit(0,
>new_digit(0,
>new_digit(9,
>new_digit(0,
>new_digit(0, NULL;
>
> DIGIT *b =
>new_digit(1,
>new_digit(9,
>new_digit(9, NULL)));
>
> DIGIT *r = subtract(a, b);
>
> print(a); printf(" - "); print(b);
> printf(" = "); print(r); printf("\n");
> return 0;
> }
>
>
> On Aug 25, 8:25 am, Terence wrote:
> > 1. Calculate the length of both list (A, B).
> > 2. Find the position in the longer list corresponding to the head of
> > shorter list, and copy the previous digits to output list C.
> > (Or for simplicity, appending 0 to the shorter list so as to get the
> > same length as the longer one)
> > 3. Add the two lists into list C without performing carry.
> > 4. Perform carries. For each digit x in sum C, and the previous digit px.
> > a) if x < 9, no change to x and px;
> > b) if x > 9, x = x - 10, px = px + 1;
> > c) if x ==9, continue to next digit until you come to a digit x'
> > not equal to 9 (or the end of list)
> > if x' > 9, x' = x' - 10, px = px + 1, and change all
> > the 9's in between to 0.
> > else, keep all those digits untouched.
> >
> > step 3 and 4 can be merged into one pass.
> >
> > On 2010-8-25 17:54, Raj N wrote:
> >
> >
> >
> > > Input : Two large singly linked lists representing numbers with most
> > > significant digit as head and least significant as last node.
> > > Output: Difference between the numbers as a third linked list with
> > > Most significant digit as the head.
> > > Eg:
> > > ---
> > > Input:
> > > A = 5->4->2->0->0->9->0->0
> > > B = 1->9->9
> > > Output:
> > > C = 5->4->2->0->0->7->0->1
> > > Required complexity :
> > > O(n)
> > > Constraint:
> > > Reversing linked list is NOT allowed
>
> --
> 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] Re: Algorithm to find all subsets of size K
Though the approach is correct, but I think it should say that Generate all
bit strings of size n with k bits set. Where n is the
number of elements in the set and k is the number of 1's in the string.
On Sun, Aug 22, 2010 at 2:08 PM, R.ARAVINDH wrote:
> @raj
>
>
> really cool
>
> On Aug 22, 1:08 pm, Raj N wrote:
> > Generate all binary strings of length k. For eg: S={1,2,3,4,5} generate
> all
> > binary strings of length 5. 0 represents that particular number is absent
> > and 1 for the presence of the number.
> >
> >
> >
> > On Fri, Aug 13, 2010 at 11:35 PM, asdf wrote:
> > > Most efficient algorithm to find all subsets of size K??
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algoge...@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.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] Re: 0's and 1's yet again!!!
@Ashutosh
I think a single pass would mean that you look at the element only once. But
in your algorithm you are looking at some elements multiple times using the
tail pointer. Does it then qualify the requirements ? Moreover, you are
indeed using extra memory.
On Sun, Aug 22, 2010 at 6:46 PM, Dave wrote:
> @Aravind: The intent was to do it in in one pass without extra memory,
> and leave the input unchanged if the number of zeros does not equal
> the number of ones. It seems to me that the combination of
> requirements is tough.
>
> Dave
>
> On Aug 21, 10:22 pm, Aravind Prasad wrote:
> > if the intention of the problem is to do it in O(n)..
> >
> > then we can do 2 passses.. one to find the no of 0 and 1..
> >
> > then in 2nd pass,, put 0 in even and 1 in odd and leave the rest of
> > the array as such..
> >
> > O(n)+O(n)=O(n).
> >
> > On Aug 20, 5:40 pm, Ashutosh Tamhankar wrote:
> >
> >
> >
> > > Here is a C++ version of the algorithm to solve this problem.
> >
> > > #include
> > > #define TRUE 1
> > > #define FALSE 0
> > > typedef struct Binarr{
> > > int iNumber;
> >
> > > };
> >
> > > class binaryarr{
> > > Binarr * arr;
> >
> > > public:
> > > int iHead;
> > > int iSize;
> > > int iZeroes;
> > > int iOnes;
> > > int iTail;
> > > binaryarr(void);
> > > ~binaryarr(void);
> > > bool Rearrange(void);
> > > bool IsOdd(int iNumber);
> > > bool IsZero(int iNumber);
> > > bool SwapElements(int iUnexpected, int iCurrTail, int iExpected);
> > > bool ZeroOneBalanced(void);
> > > void Display(void);
> >
> > > };
> >
> > > void binaryarr:: Display(void){
> > > std::cout << std::endl << "Contents of the arr are";
> > > for(int j=0; j > > std::cout << std::endl<< arr[j].iNumber;
> >
> > > }
> >
> > > bool binaryarr:: ZeroOneBalanced(void){
> > > int iTotal = -1;
> > > iTotal = iOnes + iZeroes;
> > > if (iTotal == iSize && iOnes != iZeroes){
> > > std::cout << std::endl<<"Number of Ones =
> > > "< > > std::cin >> iSize;
> >
> > > if(iSize != 0){
> > > if ((iSize % 2) == 0)
> > > {
> > > std::cout << std::endl<<"Enter each zero or one and press
> > > enter"< > > arr = (Binarr *) malloc(iSize-1);
> > > for (iIndex = 0 ; iIndex < iSize ; iIndex ++ )
> > > std::cin >> arr[iIndex].iNumber;
> > > iHead = 0;
> > > iTail = iSize-1;
> > > iZeroes = 0;
> > > iOnes = 0;
> > > }
> > > else
> > > {
> > > std::cout << "The size of the arr cant fit equal number of
> zeros
> > > and ones\n";
> > > iHead = -1;
> > > }
> > > }
> > > else
> > > {
> > > std::cout << "The size of the arr cant fit equal number of
> zeros
> > > and ones\n";
> > > iHead = -1;
> > > }
> >
> > > }
> >
> > > // Free the memory
> > > binaryarr::~binaryarr(void){
> > > /*if (iHead != -1)
> > > free(arr);*/
> >
> > > }
> >
> > > // is the given number odd or even
> > > bool binaryarr::IsOdd(int iNumber){
> > > if ( (iNumber == 0 ) )
> > > return TRUE;
> > > else
> > > if (( (iNumber % 2) == 0 ) && (iNumber!=1) )
> > > return TRUE;
> > > else
> > > return FALSE;
> >
> > > }
> >
> > > // is the given number zero or one
> > > bool binaryarr::IsZero(int iNumber){
> >
> > > if (arr[iNumber].iNumber == 0){
> > > iZeroes = iZeroes + 1;
> > > return TRUE;
> > > }
> > > else
> > > {
> > > iOnes = iOnes + 1;
> > > return FALSE;
> > > }
> >
> > > }
> >
> > > bool binaryarr:: SwapElements(int iUnexpected, int iCurrTail, int
> > > iExpected){
> > > int iTemp = -1;
> > > int iFound = -1;
> > > /*while !((IsZero(iUnexpected)) && iExpected){
> > > iCurrTail = iCurrTail - 1;
> > > iFound = 1;
> > > }*/
> > > for (int iDecr = iCurrTail; iDecr >= iUnexpected; iDecr--)
> > > {
> > > if((IsZero(iDecr)) && (iExpected == 0) || (!(IsZero(iDecr))) &&
> > > (iExpected == 1))
> > > {
> > > iFound = 1;
> > > iTail = iDecr; // Reposition current tail.
> > > iTemp = arr[iUnexpected].iNumber;
> > > arr[iUnexpected].iNumber = arr[iDecr].iNumber;
> > > arr[iDecr].iNumber = iTemp;
> > > return TRUE;
> > > }
> > > }
> > > //
> >
> > > if ((iFound == -1) || (iOnes != iZeroes))
> > > {
> > > std::cout << std::endl << "binaryarr:: SwapElements: Mismatch
> or
> > > mismatch in num of zeros : ones. Expected = "< =
> > > "< > > return FALSE;
> > > }
> >
> > > }
> >
> > > // sort the input arr such that every odd position has a 1 and even
> position
> > > a zero.
> > > bool binaryarr::Rearrange(void){
> >
> > > for (iHead = 0; iHead < iTail; iHead++) {
> > > if (IsOdd(iHead)) // Determine if
Re: [algogeeks] Re: Longest Palindromic Substring
You use a trie when you want to model a number of strings. Suffix Tree is used only when you have one string in your model. Suffix Tree is a type of trie, but the difference lies in the intent. On Sat, Aug 21, 2010 at 7:22 PM, Chi wrote: > Isn't that by definition a compressed trie, i.e patricia-tree, crit- > bit tree (suffix-tree)? Or what is the difference? > > On Aug 20, 5:17 pm, Nikhil Jindal wrote: > > @chonku > > As i understand, a trie is used when we have a lot of strings (such as a > > dictionary). > > Here we just have a single string. The resultant trie will be: > > > > a > > \ > > b > >\ > > c > > \ > > l > >\ > > e > > \ > > v > >\ > > e > > \ > > l > >\ > > a > > \ > > b > >\ > > c > > > > We get a similar trie for the reverse string. > > > > So why are you using a trie here? I cant see any advantage of it here. > > > > > > > > > > > > On Fri, Aug 20, 2010 at 8:36 AM, Chonku wrote: > > > Can we use a trie here. > > > Make first pass from left to right and construct the trie. > > > Make second pass from right to left and look for the trie branch with > > > maximum nodes that match the characters. > > > > > On Thu, Aug 19, 2010 at 7:46 PM, Nikhil Jindal >wrote: > > > > >> Hi All, > > > > >> Givan a string, you have to find the longest palindromic substring. > > >> For ex: Longest Palindromic substring for abclevelabc is level. > > > > >> What is the most optimised solution possible? > > > > >> Please access the attached hyperlink for an important electronic > communications disclaimer: > http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php > > > > >> -- > > > > >> You received this message because you are subscribed to the Google > Groups "Algorithm Geeks" group. > > > > >> To post to this group, send email toalgoge...@googlegroups.com. > > > > >> To unsubscribe from this group, send email > toalgogeeks+unsubscr...@googlegroups.com > > >. > > > > >> For more options, visit this group athttp:// > 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 > toalgoge...@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. > > > > Please access the attached hyperlink for an important electronic > communications disclaimer: > http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php > > -- > 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] Permutation of Array.
Treat each number as string and make a trie out of it. For the first input [55,31,312,33], it would look like the following . /\ 3/ 5\ 1/ 3\5\ 31/ 2\ 33\ \55 312\ Once we have a trie, just print it out by based on the smallest number first. In this case, the print would go as follows. 313123355 On Sat, Aug 21, 2010 at 12:53 PM, Nikhil Agarwal wrote: > Suppose the test is like: > > 21 71 217 > after sorting and msb appending we get: 217 712 217 > sort: 217 217 712 > > here we have 2 same elements 217 and 217 so we remove the 7 from the > following logic: > > 1.if msb > lsb we delete from the 2nd 217.else > 2.we delete 7 from 1st one. > > so this gives 2121771 > > if it wud have been 41 200 412->412 200 412->200 412 412 > here we will remove 2 from last one.giving 20041241 instead of 20041412 . > > On Sat, Aug 21, 2010 at 12:26 PM, BALARUKESH SIVARAMAN < > sbalarukesh1...@gmail.com> wrote: > >> @Nikhil >> I am clear with your first 2 algos but not with the change u introduced >> ie., adding a check. please give a working example >> >> -- >> 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. >> > > > > -- > Thanks & Regards > Nikhil Agarwal > Senior Undergraduate > 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 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] Longest Palindromic Substring
I definitely meant a suffix Tree and not a trie. Apologize for that. :) On Fri, Aug 20, 2010 at 8:47 PM, Nikhil Jindal wrote: > @chonku > As i understand, a trie is used when we have a lot of strings (such as a > dictionary). > Here we just have a single string. The resultant trie will be: > > a > \ > b >\ > c > \ > l >\ > e > \ > v >\ > e > \ > l >\ > a > \ > b >\ > c > > We get a similar trie for the reverse string. > > So why are you using a trie here? I cant see any advantage of it here. > > On Fri, Aug 20, 2010 at 8:36 AM, Chonku wrote: > >> Can we use a trie here. >> Make first pass from left to right and construct the trie. >> Make second pass from right to left and look for the trie branch with >> maximum nodes that match the characters. >> >> On Thu, Aug 19, 2010 at 7:46 PM, Nikhil Jindal >> wrote: >> >>> Hi All, >>> >>> Givan a string, you have to find the longest palindromic substring. >>> For ex: Longest Palindromic substring for abclevelabc is level. >>> >>> What is the most optimised solution possible? >>> >>> Please access the attached hyperlink for an important electronic >>> communications disclaimer: >>> http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php >>> >>> >>> >>> >>> -- >>> >>> 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. >> > > Please access the attached hyperlink for an important electronic > communications disclaimer: > http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php > > > > -- > > 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] Re: Array Problem
Its easier to look at a property of numbers. It will be interesting to
evaluate/prove if two different arrays have same value for sum of elements
and sum of squares of the elements.
On Fri, Aug 20, 2010 at 9:38 AM, Nikhil Agarwal
wrote:
> Check this new algo: plz provide counter eg.(if any)
>
> step 1 : count the no. of elements,0s,1s,2s,3s in arr1 and arry2.if yes
> proceed to step 2 else print fail
> step2: if(sum of the elements and product of the non zero elements are
> same in both arrays ) print arrays are same else print fail.
>
>
> On Fri, Aug 20, 2010 at 4:26 AM, Dave wrote:
>
>> @Saikat: Rather than challenging everyone to keep coming up with
>> counterexamples, please provide a rationale as to why an algorithm
>> such as this should work. It looks as if you have two equations in 2N
>> unknowns and are trying to assert that the only solution is A_1 =
>> B_1,
>> A_2 = B_2, etc. (where I have assumed that each array is sorted).
>> Usually, it takes 2N equations to determine 2N unknowns, although
>> other information about the solutions can lessen that number in
>> certain circumstances.
>>
>> At least if you are going to propose something, do so only after you
>> have tested it on all of the combinations of up to four numbers
>> between -5 and 5.
>>
>> Dave
>>
>> On Aug 19, 11:52 am, Saikat Debnath wrote:
>> > 1. Add sum of squares of all numbers in respective groups, if equal
>> > goto step 2.
>> > 2. XOR all elements of both groups, (if==0) elements are same.
>> >
>> > On Aug 19, 9:21 pm, Dave wrote:
>> >
>> >
>> >
>> > > @Nikhil Jindal: What you say is true for 2 numbers, but not for more
>> > > than 2.
>> > > 1 + 6 + 6 = 2 + 2 + 9 = 13, and 1 * 6 * 6 = 2 * 2 * 9 = 36.
>> >
>> > > Dave
>> >
>> > > On Aug 19, 6:00 am, Nikhil Jindal wrote:
>> >
>> > > > Nikhil's algo is correct if the following is always true:
>> >
>> > > > Given: x + y = S, x * y = M
>> > > > and x' + y' = S', x' * y' = M'
>> >
>> > > > If: S' = S and M' = M, then x = x' and y = y'
>> > > > i.e for given sum and product, the elements are unique.
>> >
>> > > > On Thu, Aug 19, 2010 at 12:54 PM, Nikhil Agarwal
>> > > > wrote:
>> >
>> > > > > @Dave : my algo won't fail for {0,1,-1} and {0,2,-2} .
>> >
>> > > > > S1=0;S2=0;
>> > > > > M1=-1 and M2 =-4 (excluding 0 multiplication which i had
>> corrected)
>> > > > > M1!=M2 there fore it is correct.
>> >
>> > > > > Code:
>> >
>> > > > > bool check_arrays(vector v1,vector v2){
>> > > > > if(v1.size()!=v2.size())
>> > > > > return 0;
>> > > > > if(v1.size()==0&&v2.size()==0)
>> > > > > return 1;
>> > > > > int sum,product1,product2;
>> > > > > sum=0;product1=1;product2=1;
>> > > > > for(int i=0;i> > > > > sum+=v1[i];
>> > > > > sum-=v2[i];
>> > > > > if(v1[i]!=0)
>> > > > > product1*=v1[i];
>> > > > > if(v2[i]!=0)
>> > > > > product2*=v2[i];
>> > > > > }
>> > > > > if(sum==0&&(product1==product2))
>> > > > > return 1;
>> > > > > return 0;
>> > > > > }
>> > > > > On Thu, Aug 19, 2010 at 11:26 AM, Dave
>> wrote:
>> >
>> > > > >> @Srinivas, Make that: Your algorithm seems to fail on A =
>> {0,1,-2), B
>> > > > >> =
>> > > > >> (0,2,-3). I was thinking ones-complement arithmetic instead of
>> twos-
>> > > > >> complement.
>> >
>> > > > >> Dave
>> >
>> > > > >> On Aug 18, 11:59 pm, Dave wrote:
>> > > > >> > @Srinivas, Your algorithm seems to fail on A = {0,1,-1), B =
>> > > > >> > (0,2,-2).
>> >
>> > > > >> > Dave
>> >
>> > > > >> > On Aug 18, 10:53 pm, srinivas reddy
>> wrote:
>> >
>> > > > >> > > add one more thing to the solution suggested by nikhil
>> i.e;count the
>> > > > >> number
>> > > > >> > > of elements in array 1 an
Re: [algogeeks] Longest Palindromic Substring
Can we use a trie here. Make first pass from left to right and construct the trie. Make second pass from right to left and look for the trie branch with maximum nodes that match the characters. On Thu, Aug 19, 2010 at 7:46 PM, Nikhil Jindal wrote: > Hi All, > > Givan a string, you have to find the longest palindromic substring. > For ex: Longest Palindromic substring for abclevelabc is level. > > What is the most optimised solution possible? > > Please access the attached hyperlink for an important electronic > communications disclaimer: > http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php > > > > -- > > 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] Array Problem
How about combining sum and multiplication in the first step. As in perform
both sum and multiplication or may be sum of squares.
On Wed, Aug 18, 2010 at 8:50 PM, Rais Khan wrote:
> @Chonku: Your algo seems to fail with following input.
> Arr1[]= {1,6}
> Arr2[]={7}
>
>
>
>
> On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan wrote:
>
>> @Nikhil: Your algo seems to fail with following input. What do you say?
>> Arr1[]= {1,2,3}
>> Arr2[]={6}
>>
>>
>>
>>
>> On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal <
>> nikhil.bhoja...@gmail.com> wrote:
>>
>>> Sum all the elements of both the arrays..let it be s1 and s2
>>> Multiply the elements and call as m1 and m2
>>> if(s1==s2) &&(m1==m2)
>>> return 1;else
>>> return 0;
>>>
>>> O(n)
>>>
>>> On Tue, Aug 17, 2010 at 11:33 PM, amit wrote:
>>>
>>>> Given two arrays of numbers, find if each of the two arrays have the
>>>> same set of integers ? Suggest an algo which can run faster than NlogN
>>>> without extra space?
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To post to this group, send email to algoge...@googlegroups.com.
>>>> To unsubscribe from this group, send email to
>>>> algogeeks+unsubscr...@googlegroups.com
>>>> .
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>>
>>>
>>>
>>> --
>>> Thanks & Regards
>>> Nikhil Agarwal
>>> Senior Undergraduate
>>> 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 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] Array Problem
1. Sum all the elements of both arrays. If the sum are same then perform step 2. If the sum is not different, then arrays are different. 2. Xor elements of first array and then xor the result with elements of second array. If result is zero, then the arrays are same. On Tue, Aug 17, 2010 at 11:33 PM, amit wrote: > Given two arrays of numbers, find if each of the two arrays have the > same set of integers ? Suggest an algo which can run faster than NlogN > without extra space? > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- 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] Generate all bit strings of length n
Start with number 1. It will have a binary representation of 00...1 (Total of n-bits) Keeping adding 1 to it until you reach a number with all 1's in its binary representation. On Thu, Aug 12, 2010 at 2:00 PM, Raj N wrote: > Hi, > Can someone gimme the code to generate all possible bit strings of > length n recursively ? > > -- > 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] How will you find the page with most incoming links from billions of web-pages
Construct a graph of these pages Run a BFS/DFS. The vertex with maximum incoming connections would be the page which is referenced most. On Thu, Aug 12, 2010 at 11:41 AM, vijay wrote: > How will you find the page with most incoming links from billions of > web-pages > > -- > 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] Singly to doubly....
You could use XOR Linked List concept here. It has space of one data and one node pointer. So you don't change the structure of the list. On Tue, Aug 10, 2010 at 11:57 AM, UMESH KUMAR wrote: > How to convert Singly link list to Doubly link list without converting > the Structure of the list ,so possible or not if possible then explain > soon. > > -- > 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] Array Problem
Since the arrays are sorted, you should be able to do this in O(n) time.
a[1..n], b[1..n]
output a[n], b[n]
int count=1;
while (i > 0 and j > 0 and count < n)
Begin
if (a[i-1] * b[j] >= a[i] * b[j-1])
Begin
Output a[i-1] & b[j]
i=i-1;
End
else
Begin
Output a[i] & b[j-1]
j = j-1;
End
++count;
End
On Mon, Aug 9, 2010 at 6:36 PM, amit wrote:
> Given two sorted positive integer arrays A(n) and B(n), we define a
> set S = {(a,b) | a \in A and b
> \in B}. Obviously there are n2 elements in S. The value of such a pair
> is defined as Val(a,b) = a +
> b. Now we want to get the n pairs from S with largest values.
>
> How to do this in O(nlogn) time.
>
> --
> 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] Re: BST Problem
Two inorders would achieve the same thing without using an array. One pointer running inorder with LDR and other pointer running inorder with RDL. Compare the sum at the two nodes and then adjust them accordingly. On Fri, Aug 6, 2010 at 2:11 PM, Manjunath Manohar wrote: > the solution elegant..but is there any on the fly method by just exploiting > the BST propertyby using left and right pointers > > -- > 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] Re: Sapient Interview Question
We can store the employees as a list. Since each employee is managed by 1 boss, we can store the pointer to boss in the child. To calculate getCostToCompany(char* bossName), we can scan the list and look for those records where bossName matches those employees who have boss with . This would bw O(n). To add a record, first we find the boss pointer and then insert the record at the end of the list using the boss pointer. On Thu, Aug 5, 2010 at 5:13 AM, Anand wrote: > 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. > -- 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] adobe problem---array
Just to clarify, when you say repeating 1 time means 2 occurences. Similarly, repeating 2 times means 3, etc. ? On Mon, Jul 5, 2010 at 7:18 PM, jalaj jaiswal wrote: > Given an array of integers where some numbers repeat 1 time, some numbers > repeat 2 times and only one number repeats 3 times, how do you find the > number that repeat 3 times. > > can xor do something here ?? > > -- > 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] unique number in an array
xor all the elements. Similar elements would become 0. Remaining would be
unique element.
On Mon, Jun 14, 2010 at 12:14 AM, jalaj jaiswal
wrote:
> give an algo to find a unique number in an array
>
> for eg a[]={1,3,4,1,4,5,6,1,5}
>
> here 3 is the unique number as it occur only once... moreover array
> contains only 1 unique number
>
>
>
> --
> 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] tower of hanoi variation
Create a recurrence and then the algorithm. On Mon, Jun 14, 2010 at 2:31 AM, jalaj jaiswal wrote: > give the algorithm for toi if... the a disk can be placed on top the disk > just larger then it and on the ground.. > > -- > 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] Re: Interview question.Provide the solution as per the constraints.
Can we do this ?
We use one pointer 'a' to point to the root of the tree.
An integer 'b'.
Another pointer 'c' to perform inorder traversal and count the number of
nodes. Calculate median which will be ceil(n/2). and using 'c' perform
inorder traversal again, until we have scanned ceil(n/2) nodes. In total of
4 variables. So complexity is still O(n) and memory requirement is O(1).
On Mon, Mar 8, 2010 at 8:11 PM, Ralph Boland wrote:
> This can be done without the parent pointer though the method
> may not be wise. As you traverse the tree downward you set
> the child pointer you traverse to point to the parent (grandparent
> of the child). When you
> traverse upward you reset the pointer of the node you traverse
> to point to its original child. Now no parent pointers are needed
> and no recursion either. The catch is that if your code does
> not complete for any reason the tree is cooked.
> Charcoal anyone?
>
> On Mar 8, 5:37 am, Terence wrote:
> > What is the storage structure of your BST?
> > If each node contains pointers to its left child, right child and
> > parent, then we can traverse through the tree without recursive or stack.
> >
> > in_order_traverse()
> > {
> > p = root;
> > last = root->parent = NULL;
> >while(p) {
> > if (last == p->parent) { // enter
> >if(p->left) {
> > last = p; p = p->left;
> >} else if(p->right) {
> > process(p);
> > last = p; p = p->right;
> >} else {
> > process(p);
> > last = p; p = p->parent;
> >}
> > } else if (last == p->left) {
> > process(p);
> > if(p->right) {
> > last = p; p = p->right;
> >} else if(p->right) {
> > last = p; p = p->parent;
> >}
> > } else {
> > last = p; p = p->parent;
> > }
> >}
> >
> > }
> >
> > Combine this with Rahul Singh's algorithm lead to a solution with O(n)
> > time and O(1) memory
> >
> > On 2010-3-8 15:11, Nikhil Agarwal wrote:
> >
> > > @all: you cannot traverse through the tree recursively because it has
> > > been mentioned that no extra memory (in recursive calls or stack ) is
> > > allowed.
> >
> > > On Mon, Mar 8, 2010 at 8:42 AM, gaurav gupta
> > > <1989.gau...@googlemail.com >
> wrote:
> >
> > > Median of BST means : median of Sorted array of elements? is it?
> >
> > > Convert BST into Hight Balance Search Tree then root node will be
> > > your median.
> >
> > > On Sun, Mar 7, 2010 at 2:42 AM, Nik_nitdgp
> > > mailto:nikhil.bhoja...@gmail.com>>
> wrote:
> >
> > > Given a BST (Binary search Tree) how will you find median in
> that?
> > > Constraints:
> > > -No extra memory.
> > > Algorithm should be efficient in terms of complexity.
> > > Write a solid secure code for it.
> >
> > > No extra memory--u cannot use stacks to avoid recursion.
> > > No static,global--u cannot use recursion and keep track of the
> > > elements visited so far in inorder.
> >
> > > --
> > > 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.
> >
> > > --
> > > Thanks & Regards
> > > Nikhil Agarwal
> > > Junior Undergraduate
> > > Computer Science & Engineering,
> > > National Institute Of Technology, Durgapur,India
> > >http://tech-nikk.blogspot.com
> >
> > > --
> > > You received this message because you are subscribed to the Google
> > > Groups "Algorithm Geeks" group.
> > > To post to this group, send email to algoge...@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com
> .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> 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 unsubscr
[algogeeks] Re: birthday panga
I think a linked list structure should suffice for this. Since insertions/deletions will not be too frequent. Memory consumption will also be optimum. On Thu, Aug 27, 2009 at 2:49 PM, ankur aggarwal wrote: > Implement the birthday diary calendar to keep records of all birthdays of > your friends > 1) what underlying data structure(s) you will use so that the memory > consumption should be optimum [i.e if you have only 12 birthday entries you > should not hold memory for all 365 days of the year]. > > 2) You should be able view the data (birthdays) with closest birthday first > [i.e 7th July should come before 11 Aug]. > > 3) How will you keep this data sorted (for question 2)everytime you insert > a new birthday entry. This sorting should be as optimum as possible > [mergesort etc will not be very beneficial bcoz ideally you won't have > thousands or millions of birthday] > > 4) How will you handle 2 or N number of birthdays on same day > > > > --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: programming problem
You could do this too... 1. Sort the words based on length. Max Time: O(nlogn) 2. Now, Create a tree similar to a state transition diagram. For each word in the tree, store their start and end pointers. 3. If a word comprises of another word, then the main word would only store start and end pointers for the enclosed word. For example in the tree , the word catsdogcats, will stored as original cats+pointer to start and end of dog+pointer to start and end of cats Even if all the words are different, this construction will not take you more then O(n*w) time where w is the maximum length of any word. 4. Finding the longest word which can be constructed using other words can either be done online i.e. while constructing the tree or after constructing the tree, we do it for each unique branch of the tree. Max Time: O(n*I) Hence. total time: O(n log n) On Tue, May 20, 2008 at 1:56 PM, anshu <[EMAIL PROTECTED]> wrote: > > This question aint clear > So, for example in above list hippopotamuses is also in the list of > word in the file. > So this word includes itself and is 14 characters. > where is a condition that concatenation is a must? > > > > On May 20, 3:39 am, greg <[EMAIL PROTECTED]> wrote: > > Write a program that reads a file containing a sorted list of > > words (one word per line, no spaces, all lower case), then identifies > > the > > longest word in the file that can be constructed by concatenating > > copies of > > shorter words also found in the file. > > > > For example, if the file contained: > > > > cat > > cats > > catsdogcats > > catxdogcatsrat > > dog > > dogcatsdog > > hippopotamuses > > rat > > ratcatdogcat > > > > The answer would be 'ratcatdogcat' - at 12 letters, it is the longest > > word made up of other words in the list. > > > > I'm having trouble coming up with anything other than starting with > > the longest word in the list and checking for each of the other words > > in the list, which seems incredibly inefficient, any ideas or > > suggestions of things to look at? > > > --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: generating a random number having uniform distribution using random coin flips
What you need to generate is a random number between a & b using random(0,1). I think a hint should be enough for you. Any given number n can be represented using log n bits. On 4/14/08, Vishal <[EMAIL PROTECTED]> wrote: > > If RANDOM(0,1) gives you only 0 or 1, then RANDOM(a,b) is expected to give > you a or b. > > On 4/14/08, deeepanshu shukla <[EMAIL PROTECTED]> wrote: > > > > thanks for the reply , > > but this will give only two nos. as Random(0,1) gives only o or 1 so > > your algo gives either a or b .. > > > > but i hv got the right one > > see first generate a generator using Random(0,1) which gives uniform > > distribution between 0 and 1 > > (generatinga bit string ad normalizing it) > > > > then multiplying by b-a... > > enjoy > > > > On 4/14/08, Karthik Singaram Lakshmanan <[EMAIL PROTECTED]> > > wrote: > > > > > > > > > RANDOM(0,1)*(b-a)+a > > > > > > > > > On Mon, Apr 14, 2008 at 10:15 AM, deeepanshu shukla > > > <[EMAIL PROTECTED]> wrote: > > > > hello everybody ... > > > > can anyone help me solving this > > > > > > > > Describe an implementation of the procedure RANDOM(a, b) that only > > > makes > > > > calls to > > > > RANDOM(0, 1). What is the expected running time of your procedure, > > > as a > > > > function of a and > > > > b? > > > > -- > > > > Deepanshu Shukla > > > > 3rd year , Mathematics and Computing, > > > > I.T.-B.H.U. , > > > > Varanasi,India > > > > > > > > > > > > > > > > > > > > > > --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Finding a single repeated element in an array
I think the only faster way I know off is by using a hashset which uses O(nlog(n/m)) time but the value comes out to be numerically closer to O(nlogn). On 8/16/07, dsha <[EMAIL PROTECTED]> wrote: > > Hi there, > > I'm interested in the following problem: there is an array of integers > that contains each element only once except for one element that > occurs exactly twice. Is there a way to find this element faster than > O(n*log n) and with constant extra memory? If no, how can I prove it? > > Thanks in advance for ideas. > > > > > --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: String
I think it could be 2^n - (n-k+1) * 2^(n-k)) On 8/8/07, mohamad momenian <[EMAIL PROTECTED]> wrote: > > Hi > > this is the problem : > > How many strings with length "N" that contains Only "0" and "1" exist > that not contains a specific pattern with length "K" >input is " a string with length k" and "k" and "N" . > > thanks and Good luck ;) > > > > --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
