Re: [algogeeks] Re: linked lists
I think we can use KMP string matching algorithm. On Fri, Oct 8, 2010 at 6:40 PM, shashank jain wrote: > there are 2 unsorted array we have to want a third array in sorted > form in mininmum time complexicity > > answer can like be this merge the two array in 3rd array then sort the > array > > or > sort the individual array and then merge > > if feel first one is better > > can any one can help > > > On 10/8/10, snehal jain wrote: > > @ligerdave > > m nt getting ur algo..can u explain with an example > > > > > > On 10/8/10, snehal jain wrote: > >> > >> @neeraj > >> ur worst case complexity will be O(mn) > >> > >> > >> On 10/8/10, snehal jain wrote: > >>> > >>> @tech > >>> the ouput will be abhgrtsghgrthswert as no suffix of 1st matches with > >>> prefix of 2nd > >>> > >>> > >>> On 10/7/10, ligerdave wrote: > > use pointer. shift to left if one more leading char has been found. > any unmatched char resets the pointer to first char > > once you went through the entire list(first one), the pointer on the > second list tells you where to concatenate > > that gives you O(n) where n is the length of first list > > On Oct 7, 3:52 am, snehal jain wrote: > > There are two linked list, both containing a character in each node. > > > > If one linked list contain characters o x e n c and second contain > > characters e n c a r t a then the final linked list should contain o > x > > e n c a r t ai.e. if the end of one list is same as the start of > > second then those characters should come only once. > > > > can we do it in O(n+m) where n and m are the length of list. both > are > > singly link list. > > -- > You received this message because you are subscribed to the Google > Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > > > > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > >>> > >> > > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com > . > > For more options, visit this group at > > http://groups.google.com/group/algogeeks?hl=en. > > > > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Microsoft interview question
@Mohit: I dont think it really matters here.We just have to validate the snapshot of the game board.Number of players should not have any relevance here. On Sat, Sep 25, 2010 at 2:46 PM, mohit ranjan wrote: > @Ashita, > > Your logic is fine for one vs one game, but as per question it's "one vs > many game" > Any idea what is that ? > > > Mohit > > On Sat, Sep 25, 2010 at 1:18 PM, ashita dadlani wrote: > >> 1.The soldiers are initially placed at row 2 or row 7th(each-one of white >> and either of black).Also let white ones be at row 2.So they can never be at >> row 1st.Incase it is so in the game,its not a valid game. >> 2.There are Bishops.Each color has one of its Bishop which moves >> diagonally on all white squares,and the other on all black squares.Incase it >> is not so,the game cannot be valid. >> 3.Now suppose,no black soldier ever moved.That is,all the black soldiers >> are at row 7th.This means that the elephant(i am sorry,I generally mess up >> with their names..:P) of any other player(except horse) cannot be in any row >> but 8th one. >> >> I know only 3 test cases.Incase any one has more,please elaborate. >> PS:Vrinda,I also got the same question..:P >> >> >> On Sat, Sep 25, 2010 at 2:49 AM, Gene wrote: >> >>> Valid must mean that you can get from an initial board to the the >>> current game state by a series of legal moves. >>> >>> This is a classic branch and bound game tree search problem. You >>> could search either from a starting configuration and try to "find" >>> the current game state. Or start from the current state, use >>> 'backward' moves, and try to find the initial configuration. In this >>> case, you'd have to include backward moves that 'untake' pieces that >>> are missing from the current state. >>> >>> Or you could do a simultaneous search from both ends, looking for >>> common states in the middle. >>> >>> You'd generally use a heuristic search. Problems like this often work >>> well with A-Star. The heuristic evaluator would favor states closer >>> to the desired end (either start or current). >>> >>> Gene >>> >>> On Sep 24, 6:26 am, vrinda vasishth wrote: >>> > Asked in microsoft interview >>> > >>> > "Given a snapshot of an ongoing chess game, which probably is a one vs >>> many >>> > game, identify whether it is a valid game or not." >>> > >>> > It would be great if someone would clarify on what conditions does >>> > "validity" of the game depend.. >>> > >>> > --Vrinda >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Microsoft interview question
1.The soldiers are initially placed at row 2 or row 7th(each-one of white and either of black).Also let white ones be at row 2.So they can never be at row 1st.Incase it is so in the game,its not a valid game. 2.There are Bishops.Each color has one of its Bishop which moves diagonally on all white squares,and the other on all black squares.Incase it is not so,the game cannot be valid. 3.Now suppose,no black soldier ever moved.That is,all the black soldiers are at row 7th.This means that the elephant(i am sorry,I generally mess up with their names..:P) of any other player(except horse) cannot be in any row but 8th one. I know only 3 test cases.Incase any one has more,please elaborate. PS:Vrinda,I also got the same question..:P On Sat, Sep 25, 2010 at 2:49 AM, Gene wrote: > Valid must mean that you can get from an initial board to the the > current game state by a series of legal moves. > > This is a classic branch and bound game tree search problem. You > could search either from a starting configuration and try to "find" > the current game state. Or start from the current state, use > 'backward' moves, and try to find the initial configuration. In this > case, you'd have to include backward moves that 'untake' pieces that > are missing from the current state. > > Or you could do a simultaneous search from both ends, looking for > common states in the middle. > > You'd generally use a heuristic search. Problems like this often work > well with A-Star. The heuristic evaluator would favor states closer > to the desired end (either start or current). > > Gene > > On Sep 24, 6:26 am, vrinda vasishth wrote: > > Asked in microsoft interview > > > > "Given a snapshot of an ongoing chess game, which probably is a one vs > many > > game, identify whether it is a valid game or not." > > > > It would be great if someone would clarify on what conditions does > > "validity" of the game depend.. > > > > --Vrinda > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Write a C program to sort a stack in ascending order.
@Srinivas:
Sorry for the confusion.
But if we have a stack {5,8,3,4,2} with 5 as the last input,ie,top,
do we have to arrange the stack such that s={2,3,4,5,8}with 2 as the top?
if I am getting it correct,then shouldn't your algo be modified slightly as
follows:?
reverse(stack *s){
IsEmpty(s)
return;
top = pop(s);
reverse(s);
ascending(s, top);
}
ascending(stack *s, int top){
IsEmpty(s){
push(top);
return;
}
i = pop(s);
if(i > top){
push(top);
}
else{
ascending(s, top);
push(i);
}
}
On Sat, Sep 11, 2010 at 7:04 PM, ashita dadlani wrote:
> @Srinivas:
> shouldn't it be:
>
> i = pop(s);
> if(i > top){
> ascending(s, i);
> push(top);
> }
> else{
>
> ascending(s, top);
> push(i);
> }
>
>
> On Sat, Sep 11, 2010 at 6:52 PM, ashita dadlani wrote:
>
>>
>> else{
>> ascending(s, i);
>> push(top);
>> }
>> }
>> @swinivas:why have you used ascending(s,i) here?
>> On Sat, Sep 11, 2010 at 6:40 PM, Srinivas
>> wrote:
>>
>>> reverse(stack *s){
>>> IsEmpty(s)
>>>return;
>>> top = pop(s);
>>> reverse(s);
>>> ascending(s, top);
>>> }
>>> ascending(stack *s, int top){
>>> IsEmpty(s){
>>> push(top);
>>> return;
>>> }
>>> i = pop(s);
>>> if(i > top){
>>> ascending(s, top);
>>> push(i);
>>> }
>>> else{
>>> ascending(s, i);
>>> push(top);
>>> }
>>> }
>>>
>>> Please let me know if it wont work..thanks
>>>
>>> On Jul 18, 6:58 am, xyombie wrote:
>>> > What about a quick sort O(log n)
>>> >
>>> > void sort_stack(Stack *src, Stack *dst)
>>> > {
>>> > if(! src->IsEmpty() )
>>> > {
>>> > Stack smaller, larger;
>>> > int pivot = src->Pop();
>>> >
>>> > while(! src->IsEmpty() )
>>> > {
>>> > int tmp = src->Pop();
>>> > if(tmp < pivot)
>>> > smaller->Push(tmp);
>>> > else
>>> > larger->Push(tmp);
>>> > }
>>> >
>>> > sort_stack(smaller, dst);
>>> > dst->Push(pivot);
>>> > sort_stack(larger, dst);
>>> > }
>>> >
>>> > }
>>> >
>>> > On Jul 17, 9:28 am, vijay wrote:
>>> >
>>> > > Write a C program to sort a stack in ascending order. You should not
>>> > > make any assumptions about how the stack is implemented. The
>>> following
>>> > > are the only
>>> > > functions that should be used to write this program:
>>> > > Push | Pop | Top | IsEmpty | IsFull
>>> > > The algorithm is O(N^2) and appears below.
>>> > > Do we have any other better solution which is less than O(n * n) ?
>>> >
>>> > > void sort_stack(Stack * src, Stack * dest)
>>> > > {
>>> > > while (!src->IsEmpty())
>>> > > {
>>> > >Int tmp = src->Pop();
>>> > >while(!dest->IsEmpty() && dest->Top() > tmp)
>>> > > {
>>> > >src->Push(dest->Pop());
>>> > > }
>>> > >dest->Push(tmp);
>>> > > }
>>> >
>>> > > }
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Write a C program to sort a stack in ascending order.
@Srinivas:
shouldn't it be:
i = pop(s);
if(i > top){
ascending(s, i);
push(top);
}
else{
ascending(s, top);
push(i);
}
On Sat, Sep 11, 2010 at 6:52 PM, ashita dadlani wrote:
>
> else{
> ascending(s, i);
> push(top);
> }
> }
> @swinivas:why have you used ascending(s,i) here?
> On Sat, Sep 11, 2010 at 6:40 PM, Srinivas
> wrote:
>
>> reverse(stack *s){
>> IsEmpty(s)
>>return;
>> top = pop(s);
>> reverse(s);
>> ascending(s, top);
>> }
>> ascending(stack *s, int top){
>> IsEmpty(s){
>> push(top);
>> return;
>> }
>> i = pop(s);
>> if(i > top){
>> ascending(s, top);
>> push(i);
>> }
>> else{
>> ascending(s, i);
>> push(top);
>> }
>> }
>>
>> Please let me know if it wont work..thanks
>>
>> On Jul 18, 6:58 am, xyombie wrote:
>> > What about a quick sort O(log n)
>> >
>> > void sort_stack(Stack *src, Stack *dst)
>> > {
>> > if(! src->IsEmpty() )
>> > {
>> > Stack smaller, larger;
>> > int pivot = src->Pop();
>> >
>> > while(! src->IsEmpty() )
>> > {
>> > int tmp = src->Pop();
>> > if(tmp < pivot)
>> > smaller->Push(tmp);
>> > else
>> > larger->Push(tmp);
>> > }
>> >
>> > sort_stack(smaller, dst);
>> > dst->Push(pivot);
>> > sort_stack(larger, dst);
>> > }
>> >
>> > }
>> >
>> > On Jul 17, 9:28 am, vijay wrote:
>> >
>> > > Write a C program to sort a stack in ascending order. You should not
>> > > make any assumptions about how the stack is implemented. The following
>> > > are the only
>> > > functions that should be used to write this program:
>> > > Push | Pop | Top | IsEmpty | IsFull
>> > > The algorithm is O(N^2) and appears below.
>> > > Do we have any other better solution which is less than O(n * n) ?
>> >
>> > > void sort_stack(Stack * src, Stack * dest)
>> > > {
>> > > while (!src->IsEmpty())
>> > > {
>> > >Int tmp = src->Pop();
>> > >while(!dest->IsEmpty() && dest->Top() > tmp)
>> > > {
>> > >src->Push(dest->Pop());
>> > > }
>> > >dest->Push(tmp);
>> > > }
>> >
>> > > }
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Write a C program to sort a stack in ascending order.
else{
ascending(s, i);
push(top);
}
}
@swinivas:why have you used ascending(s,i) here?
On Sat, Sep 11, 2010 at 6:40 PM, Srinivas wrote:
> reverse(stack *s){
> IsEmpty(s)
>return;
> top = pop(s);
> reverse(s);
> ascending(s, top);
> }
> ascending(stack *s, int top){
> IsEmpty(s){
> push(top);
> return;
> }
> i = pop(s);
> if(i > top){
> ascending(s, top);
> push(i);
> }
> else{
> ascending(s, i);
> push(top);
> }
> }
>
> Please let me know if it wont work..thanks
>
> On Jul 18, 6:58 am, xyombie wrote:
> > What about a quick sort O(log n)
> >
> > void sort_stack(Stack *src, Stack *dst)
> > {
> > if(! src->IsEmpty() )
> > {
> > Stack smaller, larger;
> > int pivot = src->Pop();
> >
> > while(! src->IsEmpty() )
> > {
> > int tmp = src->Pop();
> > if(tmp < pivot)
> > smaller->Push(tmp);
> > else
> > larger->Push(tmp);
> > }
> >
> > sort_stack(smaller, dst);
> > dst->Push(pivot);
> > sort_stack(larger, dst);
> > }
> >
> > }
> >
> > On Jul 17, 9:28 am, vijay wrote:
> >
> > > Write a C program to sort a stack in ascending order. You should not
> > > make any assumptions about how the stack is implemented. The following
> > > are the only
> > > functions that should be used to write this program:
> > > Push | Pop | Top | IsEmpty | IsFull
> > > The algorithm is O(N^2) and appears below.
> > > Do we have any other better solution which is less than O(n * n) ?
> >
> > > void sort_stack(Stack * src, Stack * dest)
> > > {
> > > while (!src->IsEmpty())
> > > {
> > >Int tmp = src->Pop();
> > >while(!dest->IsEmpty() && dest->Top() > tmp)
> > > {
> > >src->Push(dest->Pop());
> > > }
> > >dest->Push(tmp);
> > > }
> >
> > > }
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Yahoo Question:Greatest Sub-sequential sum
http://codepad.org/Jui20xme
<http://codepad.org/Jui20xme>a little modification over anand's code.
On Sat, Sep 11, 2010 at 2:33 PM, ashita dadlani wrote:
> @anand:
> the maximum sum obtained from your solution is correct.
> However,the subarray printed is not correct for the following case:
> {-2,3,4,17,-8}
> -8 is also getting printed which is not a part of thw subsequence.
>
>
> On Sat, Sep 11, 2010 at 2:00 PM, ashita dadlani wrote:
>
>> @ashish:
>> what if the array is {-2,3,4,17,-8,9}?
>>
>>
>> On Wed, Sep 8, 2010 at 8:52 AM, Anand wrote:
>>
>>> Maximum Value Contiguous Subsequence problem in O(n).
>>> http://codepad.org/BhYxSlp4
>>>
>>>
>>> On Tue, Sep 7, 2010 at 2:40 PM, ashish agarwal <
>>> ashish.cooldude...@gmail.com> wrote:
>>>
>>>> yeah..it will be i=j+1;
>>>> it was misprinted
>>>>
>>>>
>>>> On Tue, Sep 7, 2010 at 10:57 AM, Sahana Gururaj wrote:
>>>>
>>>>> In the else if condition, the increment of the end index i should be
>>>>> i=j+1, not i=j+i; Otherwise the algo is right, follows the principles of
>>>>> Kadane's algo :
>>>>> http://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane.27s_algorithm
>>>>>
>>>>> On Mon, Sep 6, 2010 at 3:50 PM, ashish agarwal <
>>>>> ashish.cooldude...@gmail.com> wrote:
>>>>>
>>>>>> int max=0,sum=0,begin=0,end=0,i=0;
>>>>>> for(int j=0 to n){
>>>>>> sum+=a[j];
>>>>>> if(max>>>>> max=sum;
>>>>>> begin=i;
>>>>>> end=j;
>>>>>> }
>>>>>> else if(sum<0){
>>>>>> i=j+i;
>>>>>> sum=0;
>>>>>> }
>>>>>>
>>>>>> return sum;
>>>>>> i will tell the starting index and j will tell ending index;
>>>>>> o(n);
>>>>>> correct me if i am wrong
>>>>>>
>>>>>>
>>>>>>
>>>>>> On Mon, Sep 6, 2010 at 1:42 PM, bittu wrote:
>>>>>>
>>>>>>> Given a sequence of integers, find a continuous subsequence which
>>>>>>> maximizes the sum of its elements, that is, the elements of no other
>>>>>>> single subsequence add up to a value larger than this one. An empty
>>>>>>> subsequence is considered to have the sum 0; thus if all elements are
>>>>>>> negative, the result must be the empty sequence.
>>>>>>>
>>>>>>>
>>>>>>> Solution:O(n^2) i want O(nlogn)...???
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> #include
>>>>>>> #include
>>>>>>> #include
>>>>>>> #include
>>>>>>> int main()
>>>>>>> {
>>>>>>>int a[] = {-1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1};
>>>>>>>int length = 11;
>>>>>>>
>>>>>>>int begin, end, beginmax, endmax, maxsum, sum, i;
>>>>>>>
>>>>>>>sum = 0;
>>>>>>>beginmax = 0;
>>>>>>>endmax = -1;
>>>>>>>maxsum = 0;
>>>>>>>
>>>>>>>
>>>>>>>for (begin=0; begin>>>>>>sum = 0;
>>>>>>>for(end=begin; end>>>>>>sum += a[end];
>>>>>>>if(sum > maxsum) {
>>>>>>>maxsum = sum;
>>>>>>>beginmax = begin;
>>>>>>>endmax = end;
>>>>>>>}
>>>>>>>
>>>>>>>}
>>>>>>> cout<>>>>>>}
>>>>>>> cout<>>>>>>for(i=beginmax; i<=endmax; i++) {
>>>>>>>printf("%d\n", a[i]);
>>>>>>>}
>>>>>>>
>>>>>>>getch();
>>>>>>> }
>>>>>&
Re: [algogeeks] Yahoo Question:Greatest Sub-sequential sum
@anand:
the maximum sum obtained from your solution is correct.
However,the subarray printed is not correct for the following case:
{-2,3,4,17,-8}
-8 is also getting printed which is not a part of thw subsequence.
On Sat, Sep 11, 2010 at 2:00 PM, ashita dadlani wrote:
> @ashish:
> what if the array is {-2,3,4,17,-8,9}?
>
>
> On Wed, Sep 8, 2010 at 8:52 AM, Anand wrote:
>
>> Maximum Value Contiguous Subsequence problem in O(n).
>> http://codepad.org/BhYxSlp4
>>
>>
>> On Tue, Sep 7, 2010 at 2:40 PM, ashish agarwal <
>> ashish.cooldude...@gmail.com> wrote:
>>
>>> yeah..it will be i=j+1;
>>> it was misprinted
>>>
>>>
>>> On Tue, Sep 7, 2010 at 10:57 AM, Sahana Gururaj wrote:
>>>
>>>> In the else if condition, the increment of the end index i should be
>>>> i=j+1, not i=j+i; Otherwise the algo is right, follows the principles of
>>>> Kadane's algo :
>>>> http://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane.27s_algorithm
>>>>
>>>> On Mon, Sep 6, 2010 at 3:50 PM, ashish agarwal <
>>>> ashish.cooldude...@gmail.com> wrote:
>>>>
>>>>> int max=0,sum=0,begin=0,end=0,i=0;
>>>>> for(int j=0 to n){
>>>>> sum+=a[j];
>>>>> if(max>>>> max=sum;
>>>>> begin=i;
>>>>> end=j;
>>>>> }
>>>>> else if(sum<0){
>>>>> i=j+i;
>>>>> sum=0;
>>>>> }
>>>>>
>>>>> return sum;
>>>>> i will tell the starting index and j will tell ending index;
>>>>> o(n);
>>>>> correct me if i am wrong
>>>>>
>>>>>
>>>>>
>>>>> On Mon, Sep 6, 2010 at 1:42 PM, bittu wrote:
>>>>>
>>>>>> Given a sequence of integers, find a continuous subsequence which
>>>>>> maximizes the sum of its elements, that is, the elements of no other
>>>>>> single subsequence add up to a value larger than this one. An empty
>>>>>> subsequence is considered to have the sum 0; thus if all elements are
>>>>>> negative, the result must be the empty sequence.
>>>>>>
>>>>>>
>>>>>> Solution:O(n^2) i want O(nlogn)...???
>>>>>>
>>>>>>
>>>>>>
>>>>>> #include
>>>>>> #include
>>>>>> #include
>>>>>> #include
>>>>>> int main()
>>>>>> {
>>>>>>int a[] = {-1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1};
>>>>>>int length = 11;
>>>>>>
>>>>>>int begin, end, beginmax, endmax, maxsum, sum, i;
>>>>>>
>>>>>>sum = 0;
>>>>>>beginmax = 0;
>>>>>>endmax = -1;
>>>>>>maxsum = 0;
>>>>>>
>>>>>>
>>>>>>for (begin=0; begin>>>>>sum = 0;
>>>>>>for(end=begin; end>>>>>sum += a[end];
>>>>>>if(sum > maxsum) {
>>>>>>maxsum = sum;
>>>>>>beginmax = begin;
>>>>>>endmax = end;
>>>>>>}
>>>>>>
>>>>>>}
>>>>>> cout<>>>>>}
>>>>>> cout<>>>>>for(i=beginmax; i<=endmax; i++) {
>>>>>>printf("%d\n", a[i]);
>>>>>>}
>>>>>>
>>>>>>getch();
>>>>>> }
>>>>>>
>>>>>>
>>>>>> its has time complexity O(n^2) ..does better solution exist
>>>>>>
>>>>>> --
>>>>>> You received this message because you are subscribed to the Google
>>>>>> Groups "Algorithm Geeks" group.
>>>>>> To post to this group, send email to algoge...@googlegroups.com.
>>>>>> To unsubscribe from this group, send email to
>>>>>> algogeeks+unsubscr...@googlegroups.com
>>>>>> .
>>>>>>
Re: [algogeeks] Yahoo Question:Greatest Sub-sequential sum
@ashish:
what if the array is {-2,3,4,17,-8,9}?
On Wed, Sep 8, 2010 at 8:52 AM, Anand wrote:
> Maximum Value Contiguous Subsequence problem in O(n).
> http://codepad.org/BhYxSlp4
>
>
> On Tue, Sep 7, 2010 at 2:40 PM, ashish agarwal <
> ashish.cooldude...@gmail.com> wrote:
>
>> yeah..it will be i=j+1;
>> it was misprinted
>>
>>
>> On Tue, Sep 7, 2010 at 10:57 AM, Sahana Gururaj wrote:
>>
>>> In the else if condition, the increment of the end index i should be
>>> i=j+1, not i=j+i; Otherwise the algo is right, follows the principles of
>>> Kadane's algo :
>>> http://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane.27s_algorithm
>>>
>>> On Mon, Sep 6, 2010 at 3:50 PM, ashish agarwal <
>>> ashish.cooldude...@gmail.com> wrote:
>>>
int max=0,sum=0,begin=0,end=0,i=0;
for(int j=0 to n){
sum+=a[j];
if(max>>> max=sum;
begin=i;
end=j;
}
else if(sum<0){
i=j+i;
sum=0;
}
return sum;
i will tell the starting index and j will tell ending index;
o(n);
correct me if i am wrong
On Mon, Sep 6, 2010 at 1:42 PM, bittu wrote:
> Given a sequence of integers, find a continuous subsequence which
> maximizes the sum of its elements, that is, the elements of no other
> single subsequence add up to a value larger than this one. An empty
> subsequence is considered to have the sum 0; thus if all elements are
> negative, the result must be the empty sequence.
>
>
> Solution:O(n^2) i want O(nlogn)...???
>
>
>
> #include
> #include
> #include
> #include
> int main()
> {
>int a[] = {-1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1};
>int length = 11;
>
>int begin, end, beginmax, endmax, maxsum, sum, i;
>
>sum = 0;
>beginmax = 0;
>endmax = -1;
>maxsum = 0;
>
>
>for (begin=0; beginsum = 0;
>for(end=begin; endsum += a[end];
>if(sum > maxsum) {
>maxsum = sum;
>beginmax = begin;
>endmax = end;
>}
>
>}
> cout<}
> coutprintf("%d\n", a[i]);
>}
>
>getch();
> }
>
>
> its has time complexity O(n^2) ..does better solution exist
>
> --
> You received this message because you are subscribed to the Google
> Groups "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google
Groups "Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>>>
>>> --
>>> Sahana Gururaj
>>>
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem
a={1,2,2,3,4}
b={1,2,3,3,4}
in this case???
elements are not equal but they certainly consist equal set of
integers(1,2,3,4) which is what question says.
On Sun, Aug 22, 2010 at 7:53 AM, UMarius wrote:
> @Nikhil : I considered the array to be a linked list. xoring the
> indexes helps when you don't know how many elements you have.
>
> Marius.
>
> On Aug 22, 5:04 am, Nikhil Agarwal wrote:
> > @marius Why are you xorring the indexes along with nos.?any special
> reason?
> >
> >
> >
> >
> >
> >
> >
> >
> >
> > On Sun, Aug 22, 2010 at 7:19 AM, UMarius wrote:
> > > @Dave: I read the question correctly and for A = { 1 , 2} B = { 2 , 1}
> > > the output is correct.
> > > Maybe I didn't explain the steps correctly. This is the code:
> >
> > > for(int i = 0 ; i < arr1.Length ; i++)
> > >{
> > >arr1XOR ^= arr1[i];
> > >arr1XOR ^= i;
> >
> > >arr1SUM += arr1[i];
> > >arr1MUL *= arr1[i];
> > >}
> >
> > >for (int i = 0; i < arr2.Length; i++)
> > >{
> > >arr2XOR ^= arr2[i];
> > >arr2XOR ^= i;
> >
> > >arr2SUM += arr2[i];
> > >arr2MUL *= arr2[i];
> > >}
> >
> > >if(arr1XOR == arr2XOR && arr1SUM == arr2SUM && arr1MUL ==
> > > arr2MUL)
> > >{
> > >//SAME VALUES - IDENTICAL ARRAYS
> > >}
> > >else
> > >{
> > >//NOT IDENTICAL
> > >}
> >
> > > Please correct me if I'm wrong.
> >
> > > Marius.
> >
> > > On Aug 22, 3:45 am, Dave wrote:
> > > > @UMarius: A = {1,2}, B = {2,1} fails your test. If you reread the
> > > > original problem, you see that the question is not whether the arrays
> > > > are identical (which is easily determined by simply comparing them
> > > > element-by-element in O(n)), but whether they contain the same
> values,
> > > > possibly in a different order.
> >
> > > > Dave
> >
> > > > On Aug 21, 11:01 am, UMarius wrote:
> >
> > > > > What about this?
> >
> > > > > 1. xor all elements of each array and their corresponding indexes &
> > > > > sum all the elements of each array & mul all elements of each array
> > > > > 2. if all results are the same then the arrays are identical
> >
> > > > > Nice to "meet" you all, I just joined and this is my first post :)
> ...
> >
> > > > > > Given two arrays of numbers, find if each of the two arrays have
> the
> > > > > > same set of integers ? Suggest an algo which can run faster than
> > > NlogN
> > > > > > without extra space?- Hide quoted text -
> >
> > > > > - Show quoted text -
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algoge...@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com
>
> > > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
> >
> > --
> > Thanks & Regards
> > Nikhil Agarwal
> > Senior Undergraduate
> > Computer Science & Engineering,
> > National Institute Of Technology,
> Durgapur,Indiahttp://tech-nikk.blogspot.comhttp://
> beta.freshersworld.com/communities/nitd
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks]
write the test cases for rectangle overlap. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks]
You have a string say "foobarfoo" in which "fo" and "oo" aree repeated twice.You have to find all such repeated pairs in O(n) time,The string can only have alphanumeric elements in it. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Modified Binary Search
first of all Gene..this is not "he" but "she" :P and secondly,can you please mention the details you are talking about so that we can reach to a solution? On Sun, Aug 8, 2010 at 7:48 PM, Gene wrote: > Well, then, you must say that in the problem! To to find k, ashita > dadlani's solution works fine, except he has left out important > details. This binary search is a bit tricker that the one to find a > value. > > On Aug 8, 2:34 am, Manjunath Manohar wrote: > > hey wait a sec,.. we wont be given the k value.. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Modified Binary Search
its possible.first apply binary search to find the index where the array is rotated. eg.a=[8,9,1,2,3,4,56,7] first apply binary search to find the value i=2. now we have 2 sub sorted arrays,ie, from i=0 to i=1 and from i=2 to i=8. apply binary search to these sub sorted arrays each of which will take time logn. hence total time:O(3logn)=O(logn) On Sun, Aug 8, 2010 at 12:04 PM, Manjunath Manohar wrote: > hey wait a sec,.. we wont be given the k value.. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Adobe Ques
@ashish:yours is not a generalized solution.Here you are assuming that u
know r=3.
What if we need to generalize the solution?
On Wed, Jul 14, 2010 at 11:58 PM, Ashish Goel wrote:
> for (int i=0;i printf("%c%c%c ", a[i],a[i+1],a[i+2]);
>
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
>
> On Wed, Jul 14, 2010 at 6:23 PM, ankit mahendru > wrote:
>
>> Write the code to print combinations of a given array (n& r were given)
>> e.g for abcde .r=3 ...print " abc", "bcd' "cde" etc
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
