[algogeeks] Re: Amazon Job openings

[immanuel kingston]

Please send a note to me on king...@amazon.com

Thanks,
Kingston

On Fri, Jul 16, 2021 at 11:16 AM immanuel kingston <
kingston.imman...@gmail.com> wrote:

> Hi all,
>
> I am a hiring manager at Amazon. We are hiring for SDE and Applied Science
> roles in my team. Please send a short note about yourself, the role you
> wish to apply for and your updated CV.
>
> Thanks,
> Kingston
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/algogeeks/CACOkDGdqjf%2BCUbBEoZcBQUpOsGwyJ8SMq0gDf89tZYiS0K-H-Q%40mail.gmail.com.

[algogeeks] Amazon Job openings

[immanuel kingston]

Hi all,

I am a hiring manager at Amazon. We are hiring for SDE and Applied Science
roles in my team. Please send a short note about yourself, the role you
wish to apply for and your updated CV.

Thanks,
Kingston

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/algogeeks/CACOkDGfuoUubqU6TKrb%3DehEA6sHMwE8S-_a_7Qj2S8V7iz9HVw%40mail.gmail.com.

[algogeeks] Openings at Amazon - SDE IIs

[immanuel kingston]

My team is hiring Software Development Engineers!


More about the team

"Come join the platform team that develops components and services used to
support repeat delivery programs like Subscribe & Save for customers and
Recurring Delivery for businesses.

Our systems enable Amazon to launch high-profile, customer-facing programs
that span Amazon categories, technologies, and countries."


Please feel to send me your resumes at kingston.imman...@gmail.com

Thanks,
Kingston

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

[algogeeks] Amazon Hiring SDE-Is, SDE-IIs, SDM and QAE-1

[immanuel kingston]

There are openings in my team for SDE-Is, SDE-IIs, SDM and QAE-1.
Please send me resumes if you or your friends are interested in any of
these roles.

Thanks,
Kingston

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

Re: [algogeeks] Re: Intersection of 2 rectangles

[immanuel kingston]

@Dave.Thanks, I got your counter-example. And the Separating Axis test is
the way to go for finding the intersection of any two polygons.

The Separating Axis test does not apply if one of the polygons is not
convex.

Thanks,
Immanuel


On Sun, Aug 7, 2011 at 12:18 AM, Dave  wrote:

> @Immanuel: First, TopLeft and BottomRight or the alternative are
> insufficient to specify non-axis-aligned rectangles.
>
> Second, what we can say is that if the rectangles overlap then the
> shadows will overlap, but we cannot say that if the shadows overlap
> then the rectangles overlap; e.g., take the rectangles [(0,0), (0,3),
> (3,3), (3,0)] and [(2,5), (5,2), (7,4), (4,7)].
>
> The standard test is the Separating Axis Test. You can find this with
> google.
>
> Dave
>
> On Aug 6, 11:38 am, immanuel kingston 
> wrote:
> > Algo goes something like this.
> >
> > Rectangles are represented by two points TopLeft and bottomRight or
> > BottomLeft and TopRight
> >
> > 1. Choose  Xmin and Xmax from Rectangle A. Check if any of the
> x-coordinates
> > of rectangle B fall in between Xmin and Xmax of A.
> > 2. choose Ymin and Ymax from Rectangle A. Check if any of the
> y-coordinates
> > of rectangle B fall in between Ymin and Ymax of A.
> >
> > If both the above conditions are satisfied, then the rectangles intersect
> > else not.
> >
> > Basically the above algo is based on Shadow of a rectangle on the x and y
> > axes.
> > If the rectangles intersect, then the shadows on the x and y axes
> overlay.
> >
> > code as follows:
> >
> > class Rectangle{
> > Point topRight;
> > Point bottomLeft;}
> >
> > class Point{
> > int x;
> > int y;
> >
> > }
> >
> > boolean isIntersecting(Rectangle A, Rectangle B){
> > int x0 = Math.min(A.topRight.x, A.bottomLeft.x);
> > int x1 = Math.max(A.topRight.x, A.bottomLeft.x);
> > int y0 = Math.min(A.topRight.y, A.bottomLeft.y);
> > int y1 = Math.max(A.topRight.y, A.bottomLeft.y);
> > return ((x0 < B.topRight.x && b.topRight.x < x1) || (x0 <
> B.bottomLeft.x
> > && b.bottomLeft.x < x1)) && ((y0 < B.topRight.y && b.topRight.y < y1) ||
> (y0
> > < B.bottomLeft.y && b.bottomLeft.y < y1))}
> >
> > boolean intersects(Rectangle A, Rectangle B) {
> > return isIntersecting(A,B) || isIntersecting(B,A);
> >
> > }
> >
> > Pls correct me if i am wrong.
> >
> > Thanks,
> > Immanuel
> >
> > On Sat, Aug 6, 2011 at 9:26 PM, Aditya Virmani  >wrote:
> >
> >
> >
> > > compare the relative positions of the coordinates
> >
> > > On Sat, Aug 6, 2011 at 9:10 PM, Algo Lover 
> wrote:
> >
> > >> Given 2 rectangles not necessary parallel to co-ordinate axis. How
> > >> would you find if the rectangles intersect and if they do find the
> > >> intersection points
> >
> > >> --
> > >> You received this message because you are subscribed to the Google
> Groups
> > >> "Algorithm Geeks" group.
> > >> To post to this group, send email to algogeeks@googlegroups.com.
> > >> To unsubscribe from this group, send email to
> > >> algogeeks+unsubscr...@googlegroups.com.
> > >> For more options, visit this group at
> > >>http://groups.google.com/group/algogeeks?hl=en.
> >
> > >  --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: nlogn, in-place, iterative mergesort?

[immanuel kingston]

@DK and Amit, thanks for correcting my understanding.



On Sun, Aug 7, 2011 at 3:51 PM, amit karmakar wrote:

> @DK
> Hmm, i do understand what you said. Maybe, i should make it clear that
> i just wanted to tell that implementing a non-recursive merge-sort
> will not require explicit stacks and is actually easier to implement.
> This was because someone mentioned using stacks to remove recursion. I
> didn't mean to tell anything more than that. :)
>
> On Aug 7, 3:07 pm, DK  wrote:
> > @Amit and @Immanuel: You're not getting the point. Merge sort is not
> > in-place because it requires an extra O(N) array during the merge step.
> > The problem asks not to remove the recursive nature of the merge-sort but
> to
> > remove the non-in-place nature of merge sort by removing the need for
> that
> > extra array. This is a research problem that has been solved and there
> have
> > been multiple papers on the topic. I've posted the earliest one that
> forms
> > the basis of this field.
> >
> > --
> > DK
> >
> >
> http://gplus.to/divyekapoorhttp://twitter.com/divyekapoorhttp://www.divye.in
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] nlogn, in-place, iterative mergesort?

[immanuel kingston]

Yes. just remove the recursive part using 2 stacks.

Thanks,
Immanuel

On Fri, Aug 5, 2011 at 6:51 PM, Nitin Nizhawan wrote:

>  does anyone know of any in-place, iterative mergesort algorithm with nlogN
> worst case complexity? It would be good if it is stable also.
>
> TIA
> Nitin
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Intersection of 2 rectangles

[immanuel kingston]

Algo goes something like this.

Rectangles are represented by two points TopLeft and bottomRight or
BottomLeft and TopRight

1. Choose  Xmin and Xmax from Rectangle A. Check if any of the x-coordinates
of rectangle B fall in between Xmin and Xmax of A.
2. choose Ymin and Ymax from Rectangle A. Check if any of the y-coordinates
of rectangle B fall in between Ymin and Ymax of A.

If both the above conditions are satisfied, then the rectangles intersect
else not.

Basically the above algo is based on Shadow of a rectangle on the x and y
axes.
If the rectangles intersect, then the shadows on the x and y axes overlay.

code as follows:

class Rectangle{
Point topRight;
Point bottomLeft;
}
class Point{
int x;
int y;
}

boolean isIntersecting(Rectangle A, Rectangle B){
int x0 = Math.min(A.topRight.x, A.bottomLeft.x);
int x1 = Math.max(A.topRight.x, A.bottomLeft.x);
int y0 = Math.min(A.topRight.y, A.bottomLeft.y);
int y1 = Math.max(A.topRight.y, A.bottomLeft.y);
return ((x0 < B.topRight.x && b.topRight.x < x1) || (x0 < B.bottomLeft.x
&& b.bottomLeft.x < x1)) && ((y0 < B.topRight.y && b.topRight.y < y1) || (y0
< B.bottomLeft.y && b.bottomLeft.y < y1))
}
boolean intersects(Rectangle A, Rectangle B) {
return isIntersecting(A,B) || isIntersecting(B,A);
}

Pls correct me if i am wrong.

Thanks,
Immanuel

On Sat, Aug 6, 2011 at 9:26 PM, Aditya Virmani wrote:

> compare the relative positions of the coordinates
>
>
> On Sat, Aug 6, 2011 at 9:10 PM, Algo Lover  wrote:
>
>> Given 2 rectangles not necessary parallel to co-ordinate axis. How
>> would you find if the rectangles intersect and if they do find the
>> intersection points
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Interleaving two strings using recursion

[immanuel kingston]

I am thinking the following algo will work. Please correct me if i am wrong.
void interleaveAndPrint(char * result, char * str1, char * str2, int i ) {
if (*str1 == '\0' && *str2 == '\0') {
result[i] = '\0';
printf("%s\n", result);
return;
}
if (*str1 == '\0'} {
// copy str2 to result
printf("%s", result);
return;
}
if (*str2 == '\0') {
// copy str1 to result
printf("%s", result);
return;
}
result[i] = *str1;
interleaveAndPrint(result, str1 + 1, str2, i + 1);
result[i] = *str2;
interleaveAndPrint(result, str1, str2 + 1, i + 1);
}
char * interleave(char * str1, char * str2) {
   if (str1 == null || str2 == null) {
   return str1 == null ? str2 : str1;
   } else {
   char * result = (char *) malloc(strlen(str1) + strlen(str2) + 1);
   interleaveAndPrint(result, str1, str2, 0);
   }
}

Thanks,
Immanuel

On Sun, Jul 24, 2011 at 8:55 AM, BL  wrote:

> Hi,
> Given two strings s and t of distinct characters print out all
> interleavings of the characters in the two strings using recursion.
> Does anybody know a suitable algorithm that could be used for this
> task?
>
> Thank you in advance.
> BL
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] MS Written Test

[immanuel kingston]

Trie is better in terms of scalability and performance.

With Hashtable there is a problem of rehashing when all buckets are full and
rehashing takes O(N). Although it happens once in a blue moon. That can
impact the performance in a production environment.

With trie you dont have that problem.

Thanks,
Immanuel

On Sun, Jul 24, 2011 at 12:43 AM, hary rathor wrote:

> no aditional data structure is required , if we search in directly on input
> stream.
> by using Boyer-Moore string search 
> algorithm.
> it take Ω(n/m) or O(n).
> so we do it on the fly.
>
> Hash function has also some prolem in where target word are anagram of src
> word.
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] DE Shaw Q

[immanuel kingston]

yep true.

The difficult part is trying to find when Player 1 can win with heaps of
size 1.

Thanks,
Immanuel

On Wed, Jun 15, 2011 at 6:59 PM, sunny agrawal wrote:

> i think solution depends on no of heaps having single coin
> if there are even number of such heaps player 1 will win
> if there are odd number of such heaps player 2 will win
>
>
> On Wed, Jun 15, 2011 at 6:49 PM, Nitish Garg wrote:
>
>> Player 1 can still win in this case: Player 1 can take 1 from the first
>> heap forcing Player 2 to take the remaining 1. Then Player 1 can take the 2
>> coins from the second heap and win.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/ySC2db2MEkkJ.
>>
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Sunny Aggrawal
> B-Tech IV year,CSI
> Indian Institute Of Technology,Roorkee
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] DE Shaw Q

[immanuel kingston]

@Nitish,
I think it fails for this condition

4 heaps with 1,2,1,2

Player 1 starts first with picking 1 coin from heap 1
Player 2 picks 2 coins from heap 2
Player 1 picks 1 coin from heap 3
Player 2 picks 2 coins from heap 4.

Player 2 wins but XOR of the number of coins in each heap is 0(if that is
what you meant).

Thanks,
Immanuel

On Wed, Jun 15, 2011 at 6:40 PM, Nitish Garg wrote:

> I think that when the XOR of all the coins is zero Player 1 can always win.
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/EQtViYQFACMJ.
>
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] DE Shaw Q

[immanuel kingston]

Player 1 will take 1 coin from heap 1
Player 2 has to take the other coin from heap1.

Player 1 will take both the coins in heap 2.

Thanks,
Immanuel


On Wed, Jun 15, 2011 at 6:33 PM, sunny agrawal wrote:

> check out this case
> n = 2
> both heaps having 2 coins
> player 2 will win i think
>
>
> On Wed, Jun 15, 2011 at 6:26 PM, immanuel kingston <
> kingston.imman...@gmail.com> wrote:
>
>> Yes. I am wrong. As per the example, Player 2 will win if he plays
>> efficiently.
>>
>> Let me put my solution this way,
>>
>> If all the the heaps are of size > 1 the Player 1 can win always.
>>
>> Thanks,
>> Immanuel
>>
>>
>> On Wed, Jun 15, 2011 at 5:36 PM, sunny agrawal 
>> wrote:
>>
>>> consider the case.
>>> n = 2;
>>> heap 1 -> no of coins 1
>>> heap 2 -> no of coins 2
>>>
>>>
>>> On Wed, Jun 15, 2011 at 5:34 PM, sunny agrawal 
>>> wrote:
>>>
>>>> i think u r wrong
>>>> what if heap size -1 is 0
>>>> i think one should pick atleast one coin else game will draw
>>>>
>>>>
>>>> On Wed, Jun 15, 2011 at 5:17 PM, immanuel kingston <
>>>> kingston.imman...@gmail.com> wrote:
>>>>
>>>>> First Player can always win.
>>>>>
>>>>> For each heap
>>>>>Pick heap-size - 1 coins if this is not the n-1th heap
>>>>>Pick all coins from the heap if this the n-1th heap.
>>>>>
>>>>> Please correct me if i am wrong.
>>>>>
>>>>> Thanks,
>>>>> Immanuel
>>>>>
>>>>> On Wed, Jun 15, 2011 at 3:13 PM, Piyush Sinha <
>>>>> ecstasy.piy...@gmail.com> wrote:
>>>>>
>>>>>> *There are n heaps of coin(numbered from 0 to n-1) with atleast 1
>>>>>> coin in each heap. There are 2 players. First player can pick any no. of
>>>>>> coins from the least numbered heap, then the second player can pick any 
>>>>>> no.
>>>>>> of coins from the least numbered heap. Unless it is emptied, the player 
>>>>>> cant
>>>>>> move on to the next heap. The player who picks the last coin wins. 
>>>>>> Design an
>>>>>> algorithm for predicting the winner.*
>>>>>>
>>>>>>
>>>>>> --
>>>>>> *Piyush Sinha*
>>>>>> *IIIT, Allahabad*
>>>>>> *+91-8792136657*
>>>>>> *+91-7483122727*
>>>>>> *https://www.facebook.com/profile.php?id=10655377926 *
>>>>>>
>>>>>>  --
>>>>>> 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.
>>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> Sunny Aggrawal
>>>> B-Tech IV year,CSI
>>>> Indian Institute Of Technology,Roorkee
>>>>
>>>>
>>>
>>>
>>> --
>>> Sunny Aggrawal
>>> B-Tech IV year,CSI
>>> Indian Institute Of Technology,Roorkee
>>>
>>>  --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Sunny Aggrawal
> B-Tech IV year,CSI
> Indian Institute Of Technology,Roorkee
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] DE Shaw Q

[immanuel kingston]

Yes. I am wrong. As per the example, Player 2 will win if he plays
efficiently.

Let me put my solution this way,

If all the the heaps are of size > 1 the Player 1 can win always.

Thanks,
Immanuel

On Wed, Jun 15, 2011 at 5:36 PM, sunny agrawal wrote:

> consider the case.
> n = 2;
> heap 1 -> no of coins 1
> heap 2 -> no of coins 2
>
>
> On Wed, Jun 15, 2011 at 5:34 PM, sunny agrawal wrote:
>
>> i think u r wrong
>> what if heap size -1 is 0
>> i think one should pick atleast one coin else game will draw
>>
>>
>> On Wed, Jun 15, 2011 at 5:17 PM, immanuel kingston <
>> kingston.imman...@gmail.com> wrote:
>>
>>> First Player can always win.
>>>
>>> For each heap
>>>Pick heap-size - 1 coins if this is not the n-1th heap
>>>Pick all coins from the heap if this the n-1th heap.
>>>
>>> Please correct me if i am wrong.
>>>
>>> Thanks,
>>> Immanuel
>>>
>>> On Wed, Jun 15, 2011 at 3:13 PM, Piyush Sinha 
>>> wrote:
>>>
>>>> *There are n heaps of coin(numbered from 0 to n-1) with atleast 1 coin
>>>> in each heap. There are 2 players. First player can pick any no. of coins
>>>> from the least numbered heap, then the second player can pick any no. of
>>>> coins from the least numbered heap. Unless it is emptied, the player cant
>>>> move on to the next heap. The player who picks the last coin wins. Design 
>>>> an
>>>> algorithm for predicting the winner.*
>>>>
>>>>
>>>> --
>>>> *Piyush Sinha*
>>>> *IIIT, Allahabad*
>>>> *+91-8792136657*
>>>> *+91-7483122727*
>>>> *https://www.facebook.com/profile.php?id=10655377926 *
>>>>
>>>>  --
>>>> 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.
>>>
>>
>>
>>
>> --
>> Sunny Aggrawal
>> B-Tech IV year,CSI
>> Indian Institute Of Technology,Roorkee
>>
>>
>
>
> --
> Sunny Aggrawal
> B-Tech IV year,CSI
> Indian Institute Of Technology,Roorkee
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Adobe Q

[immanuel kingston]

The following is for LCA for 2 nodes in a n-ary tree.

A more tougher problem is to find the LCA for n nodes in the same n-ary
tree.

Node * findLCA (Node *root, Node * l, Node * r, int n) {
if (l == null || r == null) return root;
if (root == null) return null;
if (isChild(root,l) || isChild(root, r)) {
return root;
}
Node * arr[n];
int count = 0;
Node * notNull;
for (int i = 0 ; i < n ; i ++ ) {
arr[i] = findLCA(root->children[i], l, r);
if ( arr[i] != null ) {
count ++; notNull = arr[i];
}
}
if (count == 0) {
return null;
} else if (count == 2) {
return root;
} else {
return notNull;
}
}

On Wed, Jun 15, 2011 at 2:59 PM, Piyush Sinha wrote:

> WAP to find the LCA in a n-ary tree.
>
> --
> *Piyush Sinha*
> *IIIT, Allahabad*
> *+91-8792136657*
> *+91-7483122727*
> *https://www.facebook.com/profile.php?id=10655377926 *
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] MSFT Q

[immanuel kingston]

Use a trie data structure and pre-load it with all the words of a
dictionary.

Thanks,
Immanuel


On Wed, Jun 15, 2011 at 3:06 PM, Piyush Sinha wrote:

> *How will you design a SpellChecker for an e-mail application?*
>
>
> --
> *Piyush Sinha*
> *IIIT, Allahabad*
> *+91-8792136657*
> *+91-7483122727*
> *https://www.facebook.com/profile.php?id=10655377926 *
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] DE Shaw Q

[immanuel kingston]

First Player can always win.

For each heap
   Pick heap-size - 1 coins if this is not the n-1th heap
   Pick all coins from the heap if this the n-1th heap.

Please correct me if i am wrong.

Thanks,
Immanuel

On Wed, Jun 15, 2011 at 3:13 PM, Piyush Sinha wrote:

> *There are n heaps of coin(numbered from 0 to n-1) with atleast 1 coin in
> each heap. There are 2 players. First player can pick any no. of coins from
> the least numbered heap, then the second player can pick any no. of coins
> from the least numbered heap. Unless it is emptied, the player cant move on
> to the next heap. The player who picks the last coin wins. Design an
> algorithm for predicting the winner.*
>
>
> --
> *Piyush Sinha*
> *IIIT, Allahabad*
> *+91-8792136657*
> *+91-7483122727*
> *https://www.facebook.com/profile.php?id=10655377926 *
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Array Merge Problem

[immanuel kingston]

@Ankit, The input should be 2 sorted arrays

Thanks,
Immanuel

On Sun, May 29, 2011 at 10:48 AM, ankit sambyal wrote:

> @sravanreddy: it won't work.   Try 3,91,9   and   90,1,8,2,5   .  correct
> me if i m wrong.
>
> Thanks,
> Ankit Sambyal
>
> On Sat, May 28, 2011 at 9:16 PM, ross  wrote:
>
>> @sravanreddy:
>> Hey, Nice Solution :) cool!
>>
>> On May 29, 7:44 am, sravanreddy001  wrote:
>> > Maintain a pointer A_end = m-1;
>> > doing a comparision something similar to merge sort
>> >
>> > int i=0;j=0;
>> > while (i< m){
>> >  if (a[i] < b[j])
>> >   i++;
>> >  else{
>> >   swap(a[A_end],b[j])
>> >   A_end --;
>> >   j++;
>> >  }
>> >
>> > }
>> >
>> > This runs in O(m) time and no extra space, also the sort order is not
>> > guarenteed.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Find min after rotating an array

[immanuel kingston]

Modified Piyush's soln to handle the above case.

int get_pivot(int a [ ],int low, int high)
{
   if (low < high)
   {
   int mid = (low+high)/2;
   if(a[mid]>a[mid+1])
 return mid+1;
   if(a[low]>a[mid])
 return (get_pivot(a,low,mid-1));
   else
 return(get_pivot(a,mid+1,high);
   }
   return -1; // ie no pivot exists. so rotation must be 0

);

int getMin(int a[], int n) {
int min = get_pivot(a,0,n);
if (min > 0) return a[min];
else return a[0]
}

Thanks,
Immanuel

On Sat, May 28, 2011 at 11:01 PM, Dumanshu  wrote:

> It won't work if we rotate the array by 0. So is that the xtra case do
> we have to consider???
>
> On May 28, 7:18 pm, Piyush Sinha  wrote:
> > The main idea is to get the point at which the the rotation is
> > made...It can be done in O(lgN) time complexity...
> >
> > int get_pivot(int a [ ],int low, int high)
> > {
> > int mid = (low+high)/2;
> > if(a[mid]>a[mid+1])
> >   return (a[mid+1]);
> >  if(a[low]>a[mid])
> >return (get_pivot(a,low,mid-1));
> >  else
> >return(get_pivot(a,mid+1,high));
> >
> > }
> >
> > On 5/28/11, Dumanshu  wrote:
> >
> > > Find an elegant way of getting the minimum value in a sorted array but
> > > it has been rotated by some number.
> > > say u had the array as 4 , 5, 6, 7, 8,9 and u rotate it by 2. u get
> > > 6,7,8,9,4,5. Now u have to find minimum number in this modified array.
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
> >
> > --
> > *Piyush Sinha*
> > *IIIT, Allahabad*
> > *+91-8792136657*
> > *+91-7483122727*
> > *https://www.facebook.com/profile.php?id=10655377926*
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] [brain teaser ] Mystery Puzzle Sherlock Holmes 26 may

[immanuel kingston]

Mark

On Thu, May 26, 2011 at 1:05 PM, Lavesh Rawat wrote:

> *Mystery Puzzle Sherlock Holmes
>  *
> *
> *
> **
> *One snowy night, Sherlock Holmes was in his house sitting by a fire. All
> of a sudden a snowball came crashing through his window, breaking it.
> Holmes got up and looked out the window just in time to see three
> neighborhood kids who were brothers run around a corner. Their names were
> John Crimson, Mark Crimson and Paul Crimson.
> The next day Holmes got a note on his door that read '? Crimson. He broke
> your window.'
> Which of the three Crimson brothers should Sherlock Holmes question about
> the incident?
> *
>
> *Update Your Answers at* : Click 
> Here
>
>
> Solution:
> Will be updated after 1 day
>
>
>
> --
>
> "Never explain yourself. Your friends don’t need it and
> your enemies won’t believe it" .
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Arrays

[immanuel kingston]

Brute force Approach would be


int checkForTriangle(int a, int b, int c) {
 return (a + b > c) && (b + c > a) && (a + c > b);
}

int triangle (int a[], int n) {
 if (a == null || n <= 0) return 0;

 for (int i=0 ; i < n ; i++) {
 for (int j=i + 1; j < n; j++ ) {
 for (int k=j + 1; k < n; k++ ) {
 if (checkForTriangle(a[i], a[j], a[k])) return 1;
  }
 }
}
 return 0;
}

Thanks,
Immanuel

On Wed, May 25, 2011 at 11:23 PM, Piyush Sinha wrote:

> Write a function
>
> int triangle( int A [ ] )
>
> that given a zero-indexed array A consisting of N integers returns 1
> if there exists a triple (P, Q, R) such that 0 <= P < Q < R < N and
> A[P] + A[Q] > A[R],
> A[Q] + A[R] > A[P],
> A[R] + A[P] > A[Q].
> The function should return 0 if such triple does not exist.
>
> For example, given array A such that
>
> A[0]=10, A[1]=2, A[2]=5, A[3]=1, A[4]=8, A[5]=20
>
> the function should return 1, because the triple (0, 2, 4) fulfills
> all of the required conditions.
>
> For array A such that
>
> A[0]=10, A[1]=50, A[2]=5, A[3]=1
>
> the function should return 0
>
> --
> *Piyush Sinha*
> *IIIT, Allahabad*
> *+91-8792136657*
> *+91-7483122727*
> *https://www.facebook.com/profile.php?id=10655377926 *
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Edit distance

[immanuel kingston]

http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance


On Wed, May 25, 2011 at 11:50 AM, Akshata Sharma
wrote:

> still not getting!!  :(
>
>
> On Wed, May 25, 2011 at 11:38 AM, Aakash Johari wrote:
>
>> Sorry, it can't be because of the preferences :(...
>>
>>
>> On Tue, May 24, 2011 at 11:07 PM, Aakash Johari wrote:
>>
>>> I think, it is because of the preference of operations. I have also
>>> implemented it and it's returning 5. Try for some modifications in the
>>> algorithm.
>>>
>>> On Tue, May 24, 2011 at 10:47 PM, Akshata Sharma <
>>> akshatasharm...@gmail.com> wrote:
>>>
 @Akash:
 I have implemented Demarau-Levenshtein algorithm but for the eg. I gave
 above, it outputs 5 instead of 4. For some inputs it is giving the correct
 output.
 I think the demarau-levenshtein algo is just:

 if(I>0 && J>0 && s1[I]==s2[J-1] && s1[I-1]==s2[J])
  table[i][j] =
 min(min(table[i-1][j]+1,table[i][j-1]+1),min(table[i-1][j-1]+1,table[i-2][j-2]+1));
 else
  table[i][j] =
 min(min(table[i-1][j]+1,table[i][j-1]+1),table[i-1][j-1]+1);




 On Wed, May 25, 2011 at 10:55 AM, Aakash Johari 
 wrote:

> Use Demarau-Levenshtein for this purpose :)
>
> On Tue, May 24, 2011 at 10:24 PM, Akshata Sharma <
> akshatasharm...@gmail.com> wrote:
>
>> what changes should we make in the edit distance algorithm to include
>> the swapping of adjacent elements so as to get min edit distance?
>>
>> eg. "pantera" can be converted into "aorta" by 4 edits.
>> "pantera” >>> “antera” >>> “antra” >>> “aotra” >>> “aorta”
>>
>> --
>> 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.
>>
>
>
>
> --
> -Aakash Johari
> (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 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.

>>>
>>>
>>>
>>> --
>>> -Aakash Johari
>>> (IIIT Allahabad)
>>>
>>>
>>>
>>>
>>>
>>
>>
>> --
>> -Aakash Johari
>> (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 algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] one constructor problem

[immanuel kingston]

http://www.java2s.com/Tutorial/Cpp/0180__Class/Initializeanarrayofobjectsbyreferencingtheconstructordirectly.htm

http://www.java2s.com/Tutorial/Cpp/0180__Class/Initializeanarrayofobjectswithoutreferencingtheconstructordirectly.htm

Thanks,
Immanuel


On Wed, May 25, 2011 at 7:34 AM, D.N.Vishwakarma@IITR wrote:

> There is a class A which contains just one parameterized constructor
> A(int a). How would you initialize an array of objects of this class.
>
> --
> **With Regards
> Deoki Nandan Vishwakarma
> IITR MCA
> Mathematics Department*
> *
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: AMAZON Q

[immanuel kingston]

int fibArray[INTEGER_MAX_VALUE] = {0};
int fibonacci (int n) {
if (n <= 0) {
return 0;
} else if ( n > 0 && fibArray[n] != 0) {
return fibArray[n];
}  else {
if (n == 1) return (fibArray[n] = 1);
return (fibArray[n] = fibonacci(n - 1) + fibonacci(n-2));
}
}

int findNearestFibLessthanK(int k) {

 int upper = INTEGER_MAX_VALUE;
 int lower = 0;
 int incr = 1;
 int fibLower = 0;
 while (lower < upper) {
 fibLower = fibonacci(lower + incr);
 if (fibLower < k) {
  incr <<= 1;
 } else if (fibLower == k) {
 return fibLower;
 } else {
 upper = incr;
 lower += incr >> 1;
 incr = 1;
}
}
return fibLower;
}

Thanks,
Immanuel
On Tue, May 24, 2011 at 8:09 PM, Aakash Johari wrote:

> search OEIS.. and tell if you find something interesting :)
>
>
> On Tue, May 24, 2011 at 7:37 AM, Piyush Sinha wrote:
>
>> U r using he same approach which I mentioned it before...I knew about
>> this approach but it sounded to me too naive solution...so I was
>> thinking whether there exists any shortcurt method/mathematical
>> formulae for it or not..
>>
>> On 5/24/11, bittu  wrote:
>> > @all geeks
>> >
>> > I have already posted it 2-3 forums..here  let me post it again its
>> > O(n) but the basic idea is clear if got the problem stmt correct then
>> > we have to find out the largest Fibonacci number that is small then
>> > given number n so say if n=10 then should be 8
>> > for n=13 i=8
>> > n=14 i=13 similarly for all n>13 & n <21 i will 13 & so on i don't why
>> > so confusion ?? It Will Cover All Test Cases
>> >
>> > #include
>> >
>> > int fib(int n)
>> > {
>> >
>> >   int final=0,i,c,a=0,b=1;
>> >
>> >   for(i=2;i> >   {
>> > c=a+b;
>> > a=b;
>> > b=c;
>> > if(c> >final=c;
>> >   }
>> >
>> >   return final;
>> >
>> > }
>> >
>> > int main()
>> > {
>> >   int n=14;
>> >   printf( " %d ", fib(n));
>> >
>> > }
>> >
>> > TC O(n)
>> > SC O(1)
>> > Run Here https://ideone.com/aCli7
>> >
>> >
>> >
>> > Optimization: To get the answer in O(logn) we can use matrix
>> > representation of Fibonacci number check wiki..& if you wants O(logn)
>> > then i can also post that..I hope m clear ..There are already 6 Way
>> > Known to me to find nth Fibonacci Number
>> >
>> > only thing necessary is that optmization .. Correct me if anything
>> > wrong ???
>> >
>> > Thanks
>> > Shashank>>" the Best Way To Escape From The problem is To Solve It"
>> > CSE,BIT Mesra
>> > Reach Me +91-9739002481
>> >
>> > --
>> > You received this message because you are subscribed to the Google
>> Groups
>> > "Algorithm Geeks" group.
>> > To post to this group, send email to algogeeks@googlegroups.com.
>> > To unsubscribe from this group, send email to
>> > algogeeks+unsubscr...@googlegroups.com.
>> > For more options, visit this group at
>> > http://groups.google.com/group/algogeeks?hl=en.
>> >
>> >
>>
>>
>> --
>> *Piyush Sinha*
>> *IIIT, Allahabad*
>> *+91-8792136657*
>> *+91-7483122727*
>> *https://www.facebook.com/profile.php?id=10655377926 *
>>
>> --
>> 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.
>>
>>
>
>
> --
> -Aakash Johari
> (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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Facebook Interview Question from glassdoor

[immanuel kingston]

@sravan,
What i meant was get the jth digit in the representation of i to the base
NUM_PER_DIGIT. ie 3rd digit of (2137)8 which is 2.. 7 is the 0th digit, 3
being 1st digit, 1 being 2nd digit and 2 being 3rd digit.Here 2137 is a base
8 representation.

Thanks,
Immanuel

On Tue, May 24, 2011 at 6:37 PM, sravanreddy001 wrote:

> @Immanuel:
> In the iteretive approach, can you tell me what you meant by this function.
> A code is not required, but, how are we going to calculate? the method name
> is little confusing.
>
> The recursive is good.. but.. I'm looking at the iterative approach.
>
> ---> getJthDigitinItotheBaseNumPerDigit(NUM_PER_DIGIT,i,j);
>
> Thanks
> Sravan.
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] how to convert a floating point number into binary representation.

[immanuel kingston]

correct me if I am wrong.

String convertFloatToBinary(float num) {
   String str = "";
   int numBeforeDecimal = (int)num;
   float decimalPart = num - (float)numBeforeDecimal;
   int sign=1;
   if (numBeforeDecimal < 0 ) sign = -1;
   if (sign < 0) str[str.length] = '-';
   while(numBeforeDecimal > 0) {
 str[str.length] = numBeforeDecimal % 2 + '0';
 numBeforeDecimal /= 2;
   }
   str[str.length] = '.';
   while (decimalPart > 0 && decimalPart < 1 && str.length < 64) {
decimalPart *= 2;
str[str.length] = (decimalPart - 0) + '0';
   }
   return str;
}

Thanks,
Immanuel

On Tue, May 24, 2011 at 12:15 PM, Naveen Kumar
wrote:

> http://kipirvine.com/asm/workbook/floating_tut.htm
>
>
>
> On Tue, May 24, 2011 at 12:09 PM, saurabh agrawal wrote:
>
>>
>>  --
>> 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.
>>
>
>
>
> --
> Cheers
> Naveen Kumar
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks]

[immanuel kingston]

@Piyush, yes true. and thanks for the clarification.

int getIthBit(int n, int i) {
  return (n & 1<> i;
}
bool isPalindrome(int num) {
 int i=0;
 int j= MAX_BITS_FOR_INT - 1;
 *while(getIthBit(num, j)) j--;*
 while (i < j) {
   int ithbit = getIthBit(num, i);
   int jthbit = getIthBit(num, j);
   if ( ithbit ^ jthbit) return false;
   i++;j--;
 }
 return true;
}


On Tue, May 24, 2011 at 1:23 PM, Piyush Sinha wrote:

> @immanuelthe question doesn't require you to check with the whole
> 32 bit number...
>
> For example, taking 10's binary representation as 1010...according to
> question it wil be a palindrome...but according to ur algo it will
> return false...
>
> On 5/24/11, immanuel kingston  wrote:
> > #define MAX_BITS_FOR_INT=32;
> >
> > int getIthBit(int n, int i) {
> >  return (n & 1<> i;
> > }
> > bool isPalindrome(int num) {
> > int i=0;
> > int j= MAX_BITS_FOR_INT - 1;
> > while (i < j) {
> >   int ithbit = getIthBit(num, i);
> >   int jthbit = getIthBit(num, j);
> >   if ( ithbit ^ jthbit) return false;
> >   i++;j--;
> > }
> > return true;
> > }
> >
> > Thanks,
> > Immanuel
> >
> > On Tue, May 24, 2011 at 12:42 AM, Piyush Sinha
> > wrote:
> >
> >> Constraint is no extra space and the complexity should be as efficient
> >> as possible.
> >>
> >> On 5/24/11, Piyush Sinha  wrote:
> >> > Find whether the binary representation of a number is palindrome or
> >> > not. The input begins with integer N.
> >> > --
> >> > *Piyush Sinha*
> >> > *IIIT, Allahabad*
> >> > *+91-8792136657*
> >> > *+91-7483122727*
> >> > *https://www.facebook.com/profile.php?id=10655377926 *
> >> >
> >> > --
> >> > You received this message because you are subscribed to the Google
> >> > Groups
> >> > "Algorithm Geeks" group.
> >> > To post to this group, send email to algogeeks@googlegroups.com.
> >> > To unsubscribe from this group, send email to
> >> > algogeeks+unsubscr...@googlegroups.com.
> >> > For more options, visit this group at
> >> > http://groups.google.com/group/algogeeks?hl=en.
> >> >
> >> >
> >>
> >>
> >> --
> >> *Piyush Sinha*
> >> *IIIT, Allahabad*
> >> *+91-8792136657*
> >> *+91-7483122727*
> >> *https://www.facebook.com/profile.php?id=10655377926 *
> >>
> >> --
> >> 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.
> >
> >
>
>
> --
> *Piyush Sinha*
> *IIIT, Allahabad*
> *+91-8792136657*
> *+91-7483122727*
> *https://www.facebook.com/profile.php?id=10655377926 *
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks]

[immanuel kingston]

#define MAX_BITS_FOR_INT=32;

int getIthBit(int n, int i) {
 return (n & 1<> i;
}
bool isPalindrome(int num) {
int i=0;
int j= MAX_BITS_FOR_INT - 1;
while (i < j) {
  int ithbit = getIthBit(num, i);
  int jthbit = getIthBit(num, j);
  if ( ithbit ^ jthbit) return false;
  i++;j--;
}
return true;
}

Thanks,
Immanuel

On Tue, May 24, 2011 at 12:42 AM, Piyush Sinha wrote:

> Constraint is no extra space and the complexity should be as efficient
> as possible.
>
> On 5/24/11, Piyush Sinha  wrote:
> > Find whether the binary representation of a number is palindrome or
> > not. The input begins with integer N.
> > --
> > *Piyush Sinha*
> > *IIIT, Allahabad*
> > *+91-8792136657*
> > *+91-7483122727*
> > *https://www.facebook.com/profile.php?id=10655377926 *
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> > http://groups.google.com/group/algogeeks?hl=en.
> >
> >
>
>
> --
> *Piyush Sinha*
> *IIIT, Allahabad*
> *+91-8792136657*
> *+91-7483122727*
> *https://www.facebook.com/profile.php?id=10655377926 *
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Facebook Interview Question from glassdoor

[immanuel kingston]

@Anuj, true.This will optimise the solution by reducing the amount of stack
space used for recursion.


NUM_PER_DIGIT = 3
char c[][NUM_PER_DIGIT] = {"abc","def",...};

char n[] = 2156169 (number is pressed);
int k=7;
char * s = (char *) malloc(sizeof(char) * k);

void printAllCombinations (int k, char *s, int count) {
if (count >= k - 1) {
s[k] = '\0';
print (s);
} else {
for (i =0; i< NUM_PER_DIGIT; i++) {
s[i] = c[n[count]][i];
printAllCombinations(k,s, count+1);
}
}
}
printAllCombinations (k,s,0);

Thanks,
Immanuel


On Mon, May 23, 2011 at 10:41 PM, anuj agarwal wrote:

> Immanuel,
> We can keep c and n arrays as global variable as they are not part of state
> of the recursion.
>
> Anuj Agarwal
> Engineering is the art of making what you want from things you can get.
>
>
>
> On Mon, May 23, 2011 at 10:04 PM, immanuel kingston <
> kingston.imman...@gmail.com> wrote:
>
>> small correction
>>
>> On Mon, May 23, 2011 at 9:46 PM, immanuel kingston <
>> kingston.imman...@gmail.com> wrote:
>>
>>> A Recursive soln:
>>>
>>>
>>> NUM_PER_DIGIT = 3
>>> char c[][NUM_PER_DIGIT] = {"abc","def",...};
>>>
>>> char n[] = 2156169 (number is pressed);
>>> int k=7;
>>> char * s = (char *) malloc(sizeof(char) * k);
>>>
>>> void printAllCombinations (char c[][], char n[], int k, char *s, int
>>> count) {
>>> if (count >= k - 1) {
>>> s[k] = '\0';
>>> print (s);
>>> } else {
>>> for (i =0; i< NUM_PER_DIGIT; i++) {
>>>  *s[i] = c[n[count]][i];*
>>>
>>> printAllCombinations(c,n,k,s, count+1);
>>> }
>>> }
>>> }
>>> printAllCombinations (c,n,k,s,0);
>>>
>>> Please correct me if my understanding is wrong.
>>>
>>> Thanks,
>>> Immanuel
>>>
>>>
>>> On Mon, May 23, 2011 at 9:33 PM, immanuel kingston <
>>> kingston.imman...@gmail.com> wrote:
>>>
>>>> Extending the above soln:
>>>>
>>>> NUM_PER_DIGIT = 3
>>>> char c[][NUM_PER_DIGIT] = {"abc","def",...};
>>>>
>>>> char n[] = 2156169 (number is pressed);
>>>> int k=7;
>>>>
>>>> for i <-- 0 to  NUM_PER_DIGIT ^ k
>>>> String s="";
>>>> for j <-- 0 to k
>>>> int index =
>>>> getJthDigitinItotheBaseNumPerDigit(NUM_PER_DIGIT,i,j); // ie get 1st digit
>>>> in (022)3 returns 2
>>>> s += c[n[j]][index];
>>>> print(s);
>>>>
>>>>
>>>> Time Complexity: O((NUM_PER_DIGIT^k)*k^2);
>>>>
>>>>
>>>> On Mon, May 23, 2011 at 7:32 PM, anshu mishra <
>>>> anshumishra6...@gmail.com> wrote:
>>>>
>>>>> the same question i have asked in microsoft interview. (if it is the
>>>>> same :P)
>>>>>
>>>>> for 12 perutation are (ad, ae, af, bd, be, bf, cd, ce ,cf);
>>>>> i have given them 3 solution(recusrsive, stack based) and the last one
>>>>> what they wanted.
>>>>>
>>>>> take a tertiary number(n) = 3^(number of digits) in case of 12 it is
>>>>> equals to 2;
>>>>>
>>>>> i m solving the save problem. assuming on every key there are only 2
>>>>> alphabets.
>>>>>
>>>>> char c[][2] = {ab , cd, ..};
>>>>>
>>>>> char n[] = 2156169 (number is pressed);
>>>>> so k = 7;
>>>>> for (i = 0; i < (1<>>>> string s = "";
>>>>>  for (j = 0; j < k; j++){
>>>>>  s += c[n[j]][i & (1<>>>> }
>>>>> print(s);
>>>>> }
>>>>>
>>>>> same logic u can use for tertiary too.
>>>>>
>>>>>  --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>>> To unsubscribe from this group, send email to
>>>>> algogeeks+unsubscr...@googlegroups.com.
>>>>> For more options, visit this group at
>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>
>>>>
>>>>
>>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Facebook Interview Question from glassdoor

[immanuel kingston]

small correction

On Mon, May 23, 2011 at 9:46 PM, immanuel kingston <
kingston.imman...@gmail.com> wrote:

> A Recursive soln:
>
>
> NUM_PER_DIGIT = 3
> char c[][NUM_PER_DIGIT] = {"abc","def",...};
>
> char n[] = 2156169 (number is pressed);
> int k=7;
> char * s = (char *) malloc(sizeof(char) * k);
>
> void printAllCombinations (char c[][], char n[], int k, char *s, int count)
> {
> if (count >= k - 1) {
> s[k] = '\0';
> print (s);
> } else {
> for (i =0; i< NUM_PER_DIGIT; i++) {
> *s[i] = c[n[count]][i];*
> printAllCombinations(c,n,k,s, count+1);
> }
> }
> }
> printAllCombinations (c,n,k,s,0);
>
> Please correct me if my understanding is wrong.
>
> Thanks,
> Immanuel
>
>
> On Mon, May 23, 2011 at 9:33 PM, immanuel kingston <
> kingston.imman...@gmail.com> wrote:
>
>> Extending the above soln:
>>
>> NUM_PER_DIGIT = 3
>> char c[][NUM_PER_DIGIT] = {"abc","def",...};
>>
>> char n[] = 2156169 (number is pressed);
>> int k=7;
>>
>> for i <-- 0 to  NUM_PER_DIGIT ^ k
>> String s="";
>> for j <-- 0 to k
>> int index = getJthDigitinItotheBaseNumPerDigit(NUM_PER_DIGIT,i,j);
>> // ie get 1st digit in (022)3 returns 2
>> s += c[n[j]][index];
>> print(s);
>>
>>
>> Time Complexity: O((NUM_PER_DIGIT^k)*k^2);
>>
>>
>> On Mon, May 23, 2011 at 7:32 PM, anshu mishra 
>> wrote:
>>
>>> the same question i have asked in microsoft interview. (if it is the same
>>> :P)
>>>
>>> for 12 perutation are (ad, ae, af, bd, be, bf, cd, ce ,cf);
>>> i have given them 3 solution(recusrsive, stack based) and the last one
>>> what they wanted.
>>>
>>> take a tertiary number(n) = 3^(number of digits) in case of 12 it is
>>> equals to 2;
>>>
>>> i m solving the save problem. assuming on every key there are only 2
>>> alphabets.
>>>
>>> char c[][2] = {ab , cd, ..};
>>>
>>> char n[] = 2156169 (number is pressed);
>>> so k = 7;
>>> for (i = 0; i < (1<>> string s = "";
>>>  for (j = 0; j < k; j++){
>>>  s += c[n[j]][i & (1<>> }
>>> print(s);
>>> }
>>>
>>> same logic u can use for tertiary too.
>>>
>>>  --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Facebook Interview Question from glassdoor

[immanuel kingston]

A Recursive soln:

NUM_PER_DIGIT = 3
char c[][NUM_PER_DIGIT] = {"abc","def",...};

char n[] = 2156169 (number is pressed);
int k=7;
char * s = (char *) malloc(sizeof(char) * k);

void printAllCombinations (char c[][], char n[], int k, char *s, int count)
{
if (count >= k - 1) {
s[k] = '\0';
print (s);
} else {
for (i =0; i< NUM_PER_DIGIT; i++) {
s[i] = c[count][i];
printAllCombinations(c,n,k,s, count+1);
}
}
}
printAllCombinations (c,n,k,s,0);

Please correct me if my understanding is wrong.

Thanks,
Immanuel

On Mon, May 23, 2011 at 9:33 PM, immanuel kingston <
kingston.imman...@gmail.com> wrote:

> Extending the above soln:
>
> NUM_PER_DIGIT = 3
> char c[][NUM_PER_DIGIT] = {"abc","def",...};
>
> char n[] = 2156169 (number is pressed);
> int k=7;
>
> for i <-- 0 to  NUM_PER_DIGIT ^ k
> String s="";
> for j <-- 0 to k
> int index = getJthDigitinItotheBaseNumPerDigit(NUM_PER_DIGIT,i,j);
> // ie get 1st digit in (022)3 returns 2
> s += c[n[j]][index];
> print(s);
>
>
> Time Complexity: O((NUM_PER_DIGIT^k)*k^2);
>
>
> On Mon, May 23, 2011 at 7:32 PM, anshu mishra 
> wrote:
>
>> the same question i have asked in microsoft interview. (if it is the same
>> :P)
>>
>> for 12 perutation are (ad, ae, af, bd, be, bf, cd, ce ,cf);
>> i have given them 3 solution(recusrsive, stack based) and the last one
>> what they wanted.
>>
>> take a tertiary number(n) = 3^(number of digits) in case of 12 it is
>> equals to 2;
>>
>> i m solving the save problem. assuming on every key there are only 2
>> alphabets.
>>
>> char c[][2] = {ab , cd, ..};
>>
>> char n[] = 2156169 (number is pressed);
>> so k = 7;
>> for (i = 0; i < (1<> string s = "";
>>  for (j = 0; j < k; j++){
>>  s += c[n[j]][i & (1<> }
>> print(s);
>> }
>>
>> same logic u can use for tertiary too.
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Facebook Interview Question from glassdoor

[immanuel kingston]

Extending the above soln:

NUM_PER_DIGIT = 3
char c[][NUM_PER_DIGIT] = {"abc","def",...};
char n[] = 2156169 (number is pressed);
int k=7;

for i <-- 0 to  NUM_PER_DIGIT ^ k
String s="";
for j <-- 0 to k
int index = getJthDigitinItotheBaseNumPerDigit(NUM_PER_DIGIT,i,j);
// ie get 1st digit in (022)3 returns 2
s += c[n[j]][index];
print(s);


Time Complexity: O((NUM_PER_DIGIT^k)*k^2);

On Mon, May 23, 2011 at 7:32 PM, anshu mishra wrote:

> the same question i have asked in microsoft interview. (if it is the same
> :P)
>
> for 12 perutation are (ad, ae, af, bd, be, bf, cd, ce ,cf);
> i have given them 3 solution(recusrsive, stack based) and the last one what
> they wanted.
>
> take a tertiary number(n) = 3^(number of digits) in case of 12 it is equals
> to 2;
>
> i m solving the save problem. assuming on every key there are only 2
> alphabets.
>
> char c[][2] = {ab , cd, ..};
>
> char n[] = 2156169 (number is pressed);
> so k = 7;
> for (i = 0; i < (1< string s = "";
>  for (j = 0; j < k; j++){
>  s += c[n[j]][i & (1< }
> print(s);
> }
>
> same logic u can use for tertiary too.
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Kingdom Of MapleWood

[immanuel kingston]

Since the number of islands is even, either the sum of areas of islands in
the even position have a greater area or the ones in the odd position have
greater area.

Eric can start from the 1st island if the sum of areas of the islands at the
odd position is greater than that of even ones.or can start from the nth
island(since n is even) if the sum of areas of the islands at the even
position is greater than that of odd ones.

Following the same approach he can get a larger area than Finn for sure.
This approach will always ensure that Eric ends up getting the larger area
but may not be the optimal solution.

Thanks,
Immanuel

On Tue, May 3, 2011 at 7:28 AM, abhishekriyer wrote:

> Kingdom of Maplewood is a beautiful country comprising of a lot of
> small islands of different areas. All the islands are in a straight
> row. King Rosewood is getting old and has decided to divide the
> islands among his two sons - Eric and Finn. Luckily, the total number
> of islands is even. He has also decided a few rules for the division
> of islands:
>
> i) Eric and Finn will be given alternate turns to choose the islands
> ii) They can only choose one island at a time from either the
> beginning or the end of the row of islands.
> iii) Once an island is chosen by someone,it cannot be chosen by other
> person.
> Suppose you are Eric and you are given the first choice. Find out the
> maximum area you are sure you can pick.
>
>
> I dont want the solution but the logic of doing this ... I googled and
> understood its a DP problem but was unable to proceed further. Any
> help is appreciated ...
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Need help on Divide and Conquer Algorithm

[immanuel kingston]

Solution:

int majorityElement(int a[], int n) {
if (a == null || a.length == 0 || n<=0) return -1;
int mElement = a[0];
int count=1;
for (int i=1; i < n; i++) {
if (a[i] == mElement) {
count++;
} else {
count--;
}
if (count <= 0) {
count = 1;
mElement = a[i];
}
}
count =0;
for (int i=0; i= n/2) ? mElement : -1;
}



On Thu, May 12, 2011 at 10:38 PM, pacific :-)  wrote:

> a sort and another traversal would also do the same job in o( nlogn + n )
> ??
>
>
> On Fri, Apr 15, 2011 at 12:49 AM, vishwakarma  > wrote:
>
>> complexity : O(n) + O(nlogn)
>>
>> Sweety wrote:
>> > Question :Let A[1..n] be an array of integers. Design an efficient
>> > divide and conquer algorithm to determine if A contains a majority
>> > element, i.e an element appears more than n/2 times in A. What is the
>> > time complexity of your algorithm?
>> >
>> > Answer:
>> > a[1..n] is an array
>> > int majorityElement(int a[], int first, int last)
>> > {
>> >  If (first = = last)
>> > {
>> >return a[first]; // Array has one element and its count =
>> 1
>> > and it is major element
>> >  }
>> > mid= (first+last)/2;
>> >
>> >(majorL,countL)= majorityElement(a,first,mid);
>> >(majorR,countR)= majorityElement(a,mid
>> > +1,last);
>> > n = total elements in an array;
>> >   If(majorL==majorR)
>> > return(countL+countR);
>> >  else
>> >  {
>> >If(countL>countR)
>> > return(majorL,countL);
>> >   elseif(countL< countR)
>> > return(majorR,countR);
>> >   else
>> >return(majorL,majorR);
>> >   }
>> >  if(countL>n/2)
>> > temp1=majorL;
>> >   if(countR>n/2)
>> >  temp2=majorR;
>> >
>> >If(temp1 = = temp2)
>> >   return temp1;
>> >   elseif(countL>countR)
>> >  return temp1;
>> >  else (countR>countL)
>> > return temp2;
>> > else
>> >   return -1;
>> > }
>> >
>> > int main()
>> > {
>> >   int a[8] = {2,3,2,2,4,2,2,2};
>> >   int first =1;
>> >   int last=8;   //change the value of last when the array
>> > increases or decreases in size
>> >   int x = majorityElement(a,first,last);
>> >   if(x= = -1)
>> > printf(“No Majority Element”)
>> >   else
>> >   Majority element = x;
>> >  }
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
>
> --
> regards,
> chinna.
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Print Subsets

[immanuel kingston]

@Piyush, yep You are right. it looks correct.

On Sat, May 21, 2011 at 1:25 PM, Piyush Sinha wrote:

> @immanuel...i don't think it will..even if u think it does, provide
> any sample test case
>
> On 5/21/11, immanuel kingston  wrote:
> > I think your soln will print repetitions also.
> >
> >
> > On Mon, May 16, 2011 at 2:34 PM, Piyush Sinha
> > wrote:
> >
> >>
> >>
> >> *int ref[] = {2,3,6,7,8};*
> >> *void printcombination(int n,int index,int i)
> >> {
> >>  static int a[100];
> >>  int j;
> >>  if (n == 0)
> >>  {
> >>  for(j=0;j >>   printf("%d  ",a[j]);
> >>  printf("\n");
> >>  }
> >>  else if(n>0)
> >>  {
> >>  for(j=i;j<5;j++)
> >>  {
> >>  a[index]=ref[j];
> >>  printcombination(n-ref[j],index+1,j);
> >>  }
> >>  }
> >> }  *
> >> *main()
> >> {
> >> int n;
> >> printf("enter value of n :");
> >> scanf("%d",&n);
> >> printcombination(n,0,0);
> >> }
> >> *
> >> On Fri, May 13, 2011 at 2:40 AM, amit  wrote:
> >>
> >>> Given a set of numbers eg:{2,3,6,7,8} . any one who is playing the
> >>> game can score points only from this set using the numbers in that
> >>> set. given a number, print all the possible ways of scoring that many
> >>> points. Repetition of combinations are not allowed.
> >>>
> >>> eg:
> >>> 1. 6 points can be scored as
> >>> 6
> >>> 3+3
> >>> 2+2+2
> >>>
> >>> 2. 7 can be scored as
> >>> 7
> >>> 2+2+3
> >>> but 2+3+2 and 3+2+2 is not allowed as they are repetitions of 2+2+3
> >>>
> >>> --
> >>> You received this message because you are subscribed to the Google
> Groups
> >>> "Algorithm Geeks" group.
> >>> To post to this group, send email to algogeeks@googlegroups.com.
> >>> To unsubscribe from this group, send email to
> >>> algogeeks+unsubscr...@googlegroups.com.
> >>> For more options, visit this group at
> >>> http://groups.google.com/group/algogeeks?hl=en.
> >>>
> >>>
> >>
> >>
> >> --
> >> PIYUSH SINHA
> >> 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 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.
> >
> >
>
>
> --
> *Piyush Sinha*
> *IIIT, Allahabad*
> *+91-8792136657*
> *+91-7483122727*
> *https://www.facebook.com/profile.php?id=10655377926 *
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Print Subsets

[immanuel kingston]

I think your soln will print repetitions also.


On Mon, May 16, 2011 at 2:34 PM, Piyush Sinha wrote:

>
>
> *int ref[] = {2,3,6,7,8};*
> *void printcombination(int n,int index,int i)
> {
>  static int a[100];
>  int j;
>  if (n == 0)
>  {
>  for(j=0;j   printf("%d  ",a[j]);
>  printf("\n");
>  }
>  else if(n>0)
>  {
>  for(j=i;j<5;j++)
>  {
>  a[index]=ref[j];
>  printcombination(n-ref[j],index+1,j);
>  }
>  }
> }  *
> *main()
> {
> int n;
> printf("enter value of n :");
> scanf("%d",&n);
> printcombination(n,0,0);
> }
> *
> On Fri, May 13, 2011 at 2:40 AM, amit  wrote:
>
>> Given a set of numbers eg:{2,3,6,7,8} . any one who is playing the
>> game can score points only from this set using the numbers in that
>> set. given a number, print all the possible ways of scoring that many
>> points. Repetition of combinations are not allowed.
>>
>> eg:
>> 1. 6 points can be scored as
>> 6
>> 3+3
>> 2+2+2
>>
>> 2. 7 can be scored as
>> 7
>> 2+2+3
>> but 2+3+2 and 3+2+2 is not allowed as they are repetitions of 2+2+3
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
>
> --
> PIYUSH SINHA
> 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: nearest neighbour

[immanuel kingston]

@Dave:

Sorry my bad. Yes in that case, I cant think of a solution in O(n). I guess
your solution of sorting O(nlogn) is the best one in that case.

Thanks,
Immanuel

On Sat, May 21, 2011 at 2:20 AM, Dave  wrote:

> @Immanuel: It still looks like you are finding the nearest neighbors
> of only one point, while the problem was to find the neighbors of
> _each_ of the given points.
>
> Dave
>
> On May 20, 3:07 pm, immanuel kingston 
> wrote:
> > I guess a  solution exists.
> >
> > Have a maxHeap of k elements in our case its 3.
> >
> > Iterate through the array, compare the (difference between the position
> > along a number
> > line between ) and the top element of the maxHeap. It it happens to be
> > lesser than the top element, pop off the top element and push the current
> > element into the maxHeap. Proceeding till the end of the array we will be
> > getting the 3 friends of a given person.
> >
> > Hope I am not wrong.
> >
> > Thanks,
> > Immanuel
> >
> >
> >
> > On Thu, May 19, 2011 at 7:33 PM, Dave  wrote:
> > > @Sravanreddy001: You are to find _each_ person's friends. Can you do
> > > that in O(n)?
> >
> > > Dave
> >
> > > On May 19, 8:59 am, sravanreddy001  wrote:
> > > > Also, I think there is no need for sorting the number, its still okey
> if
> > > the
> > > > 3rd person is standing 1st and has the lowest number line value.
> >
> > > > And, finding the closest 3 number takes, 3*n time.. so.. its O(n)
> running
> > > > time..
> >
> > > > @Dave.. good catch.. :)
> >
> > > --
> > > 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.- 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: how to find a smallest prime bigger than a given number

[immanuel kingston]

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes


On Thu, May 19, 2011 at 1:47 AM, Don  wrote:

> Yes. Use a sieve.
> Don
>
> On May 17, 11:36 pm, wujin chen  wrote:
> > @Dave， thanks for your reply.
> > i know that, i can only check  from 6*n - 1 and 6*n + 1..
> > assume that, n=1 , and  we begin from k=1667, the number needed to
> check
> > is 10001,10003
> > but to determin 10001 is prime or not costs a lot, right?
> > when the n is huge, it will be not feasible.
> >
> > is there some math principle to solve this problem easily?
> >
> > 2011/5/18 Dave 
> >
> > > @Wujin: Well, obviously, you don't have to check _every_ number one-by-
> > > one. If n > 1, you can ignore every even number. Furthermore, if n >
> > > 3, you can ignore every odd multiple of 3. That means that you need to
> > > check only numbers of the form 6*n - 1 and 6*n + 1.
> >
> > > Dave
> >
> > > On May 17, 9:09 pm, wujin chen  wrote:
> > > > given a number n, compute the smallest prime that is bigger than n.
> > > > for example, n=8, then the smallest prime that bigger than 8 is 11.
> >
> > > > i wonder whether there is an effective way, rather than check every
> > > number
> > > > bigger than n one by one.
> >
> > > > thanks.
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
> >
> >
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: nearest neighbour

[immanuel kingston]

I guess a  solution exists.

Have a maxHeap of k elements in our case its 3.

Iterate through the array, compare the (difference between the position
along a number
line between ) and the top element of the maxHeap. It it happens to be
lesser than the top element, pop off the top element and push the current
element into the maxHeap. Proceeding till the end of the array we will be
getting the 3 friends of a given person.

Hope I am not wrong.

Thanks,
Immanuel

On Thu, May 19, 2011 at 7:33 PM, Dave  wrote:

> @Sravanreddy001: You are to find _each_ person's friends. Can you do
> that in O(n)?
>
> Dave
>
> On May 19, 8:59 am, sravanreddy001  wrote:
> > Also, I think there is no need for sorting the number, its still okey if
> the
> > 3rd person is standing 1st and has the lowest number line value.
> >
> > And, finding the closest 3 number takes, 3*n time.. so.. its O(n) running
> > time..
> >
> > @Dave.. good catch.. :)
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: GOOGLE Q

[immanuel kingston]

Preprocess the Dictionary into a hash table where the key is the sorted
string of each word and the value being the A list that contains that
particular word.(O(nlogn * linked list insertion time some k)  )

Now for each given word, sort it(O(nlogn)) and find get the list of words
that are anagrams to the given word by looking up the HashTable(O(1)).

Thanks,
Immanuel

On Thu, May 19, 2011 at 11:11 PM, pacific :-)  wrote:

> If we were given two strings and asked to check if they have the same
> characters (anagrams) :
>
> @ gene : you are sorting them both ,and trying to match.
> cost : sort the first string + sort the second string + compare i.e k * k +
> k * k + k .. k is the length of the string.
> I presume that bubble sort is nearly optimal for smaller strings if u
> consider the overall performance ( its O(n^2) but smaller constants than the
> O(nlogn) with larger constants in say quicksort.
>
> Rather i would suggest , take each character and check that in the other
> string. O( k * k) ..in the average case you might do even less than nearly
> O(k * k/ 2) if the two strings are not same.
>
> On Wed, May 18, 2011 at 10:31 AM, anuj agarwal wrote:
>
>> Same method as Gene told.
>> Only enhancement u can made is start from the word nearer to sorted string
>> and compare till the nearest word of the reverse of sorted string.
>> You don't need to check the whole dictionary.
>>
>> Anuj Agarwal
>>
>> Engineering is the art of making what you want from things you can get.
>>
>>
>>
>> On Wed, May 18, 2011 at 6:01 AM, Gene  wrote:
>>
>>> Sort the characters in the string. Go through the dictionary sorting the
>>> characters in each word in turn.  Print the words whose sorted versions
>>> match the sorted string.
>>>
>>> You can quickly print all equivalence classes of anagrams in the
>>> dictionary by hashing with the sorted strings as keys. It only takes a few
>>> seconds to get them all this way with a 2-line perl or ruby script.
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> regards,
> chinna.
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: strings

[immanuel kingston]

Even my recursive solution will not work. :). Nice catch.!!.

int interleaved(char *s1, char *s2, char *s3) {
 if (s1 == null && s2== null && s3==null) return 1;
 if (s3==null) return 0;
 if (s1 != null && *s1 == *s3 && s2 != null && *s2 == *s3) return
interleaved(s1+1,s2,s3+1) || return interleaved(s1, s2+1,s3+1);
 if (s1 != null && *s1 == *s3) return interleaved(s1+1,s2,s3+1);
 else if (s2 != null && *s2 == *s3) return interleaved(s1, s2+1,s3+1);
 return 0;
}

int interleaved(char *s1, char *s2, char *s3) {
  if (s1 == null && s2== null && s3==null) return 1;
  if (s3==null) return 0;
  while (*s3) {
  // Added code here. So now its no more a iterative solution.
  if (s1 != null && *s1 == *s3 && s2 != null && *s2 == *s3)  return
interleaved(s1+1,s2,s3+1) || return interleaved(s1, s2+1,s3+1);
  if (s1 != null && *s1 == *s3) {
  s1++;
  }
  else if (s2 != null && *s2 == *s3) {
  s2++;
  } else {
  return 0;
  }
s3++;
}
return (s1 == null) && (s2 == null) && (s3 == null);
}

On Sat, May 21, 2011 at 1:05 AM, Don  wrote:

> Your iterative solution does not work in cases where both s1 and s2
> have the next character in s3, but only choosing the s2 character next
> will result in correct interleaving.
>
> s1 = "ab"
> s2 = "axb"
> s3 = "axabb"
>
> Your iterative solution will say that these are not interleaved, but
> they really are.
>
> Don
>
> On May 20, 2:21 pm, immanuel kingston 
> wrote:
> > A Recursive solution:
> >
> > int interleaved(char *s1, char *s2, char *s3) {
> >  if (s1 == null && s2== null && s3==null) return 1;
> >  if (s3==null) return 0;
> >  if (s1 != null && *s1 == *s3) return interleaved(s1+1,s2,s3+1);
> >  else if (s2 != null && *s2 == *s3) return interleaved(s1,
> s2+1,s3+1);
> >  return 0;
> >
> > }
> >
> > Iterative solution:
> > int interleaved(char *s1, char *s2, char *s3) {
> >  if (s1 == null && s2== null && s3==null) return 1;
> >  if (s3==null) return 0;
> >  while (*s3) {
> >  if (s1 != null && *s1 == *s3) {
> >  s1++;
> >  }
> >  else if (s2 != null && *s2 == *s3) {
> >  s2++;
> >  } else {
> >  return 0;
> >  }
> >  s3++;
> >  }
> >  return (s1 == null) && (s2 == null) && (s3 == null);
> >
> > }
> >
> > Thanks,
> > Immanuel
> >
> > On Fri, May 20, 2011 at 8:42 PM, Don  wrote:
> > > This is the same algorithm as my previous solution. Both produce the
> > > correct result, but this one does not have tail recursion, so it will
> > > run faster.
> >
> > > bool interleaved2(char *s1, char *s2, char *s3)
> > > {
> > >  while(1)
> > >  {
> > >if (!s1[0] && !s2[0] && !s3[0]) return true;
> > >if (s1[0] == s3[0])
> > >{
> > >  if (s2[0] == s3[0])
> > >  {
> > >if (interleaved2(s1+1, s2++,s3+1)) return true;
> > >  }
> > >  else ++s1;
> > >}
> > >else
> > >{
> > >  if (s2[0] == s3[0]) ++s2;
> > >  else return false;
> > >}
> > >++s3;
> > >   }
> > > }
> >
> > > On May 19, 1:33 pm, Piyush Sinha  wrote:
> > > > Design an algorithm to find whether a given string is formed by the
> > > > interleaving of two given strings or not. e.g. s1= aabccabc s2=
> dbbabc
> > > s3=
> > > > aabdbbccababcc Given s1,s2,s3 design an efficient algorithm to find
> > > whether
> > > > s3 is formed from the interleaving of s1 and s2
> >
> > > > --
> > > > *Piyush Sinha*
> > > > *IIIT, Allahabad*
> > > > *+91-8792136657*
> > > > *+91-7483122727*
> > > > *https://www.facebook.com/profile.php?id=10655377926*
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
> >
> >
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: strings

[immanuel kingston]

A Recursive solution:

int interleaved(char *s1, char *s2, char *s3) {
 if (s1 == null && s2== null && s3==null) return 1;
 if (s3==null) return 0;
 if (s1 != null && *s1 == *s3) return interleaved(s1+1,s2,s3+1);
 else if (s2 != null && *s2 == *s3) return interleaved(s1, s2+1,s3+1);
 return 0;
}

Iterative solution:
int interleaved(char *s1, char *s2, char *s3) {
 if (s1 == null && s2== null && s3==null) return 1;
 if (s3==null) return 0;
 while (*s3) {
 if (s1 != null && *s1 == *s3) {
 s1++;
 }
 else if (s2 != null && *s2 == *s3) {
 s2++;
 } else {
 return 0;
 }
 s3++;
 }
 return (s1 == null) && (s2 == null) && (s3 == null);
}

Thanks,
Immanuel

On Fri, May 20, 2011 at 8:42 PM, Don  wrote:

> This is the same algorithm as my previous solution. Both produce the
> correct result, but this one does not have tail recursion, so it will
> run faster.
>
> bool interleaved2(char *s1, char *s2, char *s3)
> {
>  while(1)
>  {
>if (!s1[0] && !s2[0] && !s3[0]) return true;
>if (s1[0] == s3[0])
>{
>  if (s2[0] == s3[0])
>  {
>if (interleaved2(s1+1, s2++,s3+1)) return true;
>  }
>  else ++s1;
>}
>else
>{
>  if (s2[0] == s3[0]) ++s2;
>  else return false;
>}
>++s3;
>   }
> }
>
> On May 19, 1:33 pm, Piyush Sinha  wrote:
> > Design an algorithm to find whether a given string is formed by the
> > interleaving of two given strings or not. e.g. s1= aabccabc s2= dbbabc
> s3=
> > aabdbbccababcc Given s1,s2,s3 design an efficient algorithm to find
> whether
> > s3 is formed from the interleaving of s1 and s2
> >
> > --
> > *Piyush Sinha*
> > *IIIT, Allahabad*
> > *+91-8792136657*
> > *+91-7483122727*
> > *https://www.facebook.com/profile.php?id=10655377926*
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Google Q

[immanuel kingston]

Adding to Dave's Explanation.

Algo goes something like this,

while Adding a random number
- Have two heaps ie a MaxHeap(For storing numbers less than the median) and
a MinHeap(for numbers > the median).
- We will make sure that the median is the top element in the maxHeap
meaning that the MaxHeap will always be one greater than or equal to the
size of the minHeap
- If the size of the two heaps are equal and if the random number is greater
than the value in the min heap,remove the top element from the min heap and
push it to the max heap and push the random number into the minHeap. else
push the random number into the maxHeap
- If the size of the two heaps are not equal(assuming that the maxHeap has
one more than the minHeap) and if the random number is greater than or equal
to the value in the min heap, push it to the maxHeap else, remove the top
element from the maxHeap and push it to the minHeap and push the random
number into the minHeap.

getMedian():
- if the size of the two heaps are equal, select the average of the top
elements of the two heaps.
- if the size of the two heaps are equal, select the top element from the
heap with more elements.

Thanks,
Immanuel





On Fri, May 20, 2011 at 10:55 PM, Anand  wrote:

> @ Dave. Nice explanation
>
>
> On Fri, May 20, 2011 at 6:06 AM, saurabh agrawal wrote:
>
>> Thanks Dave.
>>
>> On Wed, May 18, 2011 at 8:01 PM, Dave  wrote:
>>
>>> @Saurabh: You look at the top elements in the two heaps. If the new
>>> number is between the values of the top of the heaps, you add it to
>>> the shorter of the two heaps, or to either heap if they are of equal
>>> length. If the new number is larger than the min of the min-heap, you
>>> add it to the min-heap. If it is smaller than the max of the max-heap,
>>> you add it to the max heap. If the resulting two heaps differ in
>>> length by more than one element, you move the top element from the
>>> longer heap into the shorter heap. Since the heaps start off empty and
>>> you add only one number at a time, the result of a step of the
>>> algorithm is that the two heaps will differ in size by at most one
>>> element. Thus, the smaller half of the numbers will be in the max-heap
>>> and the larger half will be in the min-heap.
>>>
>>> Dave
>>>
>>> On May 18, 8:29 am, saurabh agrawal  wrote:
>>> > Dave,
>>> > u said:" a max-heap of the smallest
>>> > half of the elements"
>>> > but if the number are randomply generated, then how will you get to
>>> know
>>> > whether a number belongs to smallest half OR lager half..
>>> > i didnt got it...
>>> >
>>> >
>>> >
>>> > On Sat, May 14, 2011 at 9:10 PM, Dave  wrote:
>>> > > @Ashish: The idea is to keep two heaps, a max-heap of the smallest
>>> > > half of the elements and a min-heap of the largest elements. You
>>> > > insert incoming elements into the appropriate heap. If the result is
>>> > > that the number of elements in the two heaps differs by more than 1,
>>> > > then you move the top element from the longer heap into the other
>>> one,
>>> > > thereby equalzing the number of elements. Thus, inserting an element
>>> > > is an O(log n) operation. To get the median, it is the top element of
>>> > > the longer heap, or, if the heaps are of equal length, it is the
>>> > > average of the two top elements. This is O(1).
>>> >
>>> > > Dave
>>> >
>>> > > On May 14, 8:34 am, Ashish Goel  wrote:
>>> > > > not clear, can u elaborate..
>>> >
>>> > > > Best Regards
>>> > > > Ashish Goel
>>> > > > "Think positive and find fuel in failure"
>>> > > > +919985813081
>>> > > > +919966006652
>>> >
>>> > > > On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal <
>>> agr.bhav...@gmail.com
>>> > > >wrote:
>>> >
>>> > > > > This problem can be solved using 2 heaps and the median can
>>> always be
>>> > > > > accessed in O(1) time ,the first node.
>>> >
>>> > > > > --
>>> > > > > 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.-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 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.- 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 algogeeks@googlegroups.com.
>>> To unsubscrib