Re: [algogeeks] Re: Adobe Ques
but mine was different , check kar liyo
On Thu, Jul 21, 2011 at 10:06 PM, Ankur Khurana wrote:
> Sorry , solution nahi dekha tha tera maine.
>
>
> On Thu, Jul 21, 2011 at 9:29 PM, Ankur Khurana
> wrote:
>
>> I gave an O(N) solution in a different thread by same author for this
>> question...
>>
>>
>> On Thu, Jul 21, 2011 at 6:08 PM, Abhi wrote:
>>
>>> My solution for this :
>>>
>>> #include
>>> int max(int a,int b)
>>> {
>>> return a>b?a:b;
>>> }
>>>
>>> int main()
>>> {
>>> char str[] = "abcdab";
>>> int count=0,max1=0;
>>> int i=0,j,k;
>>> int hash[26];
>>> for(i=0;i<26;i++)
>>> hash[i]=-1;
>>> for(i=0;i>> {
>>> count=0;
>>> for(j=i;hash[str[j]-'a']==-1;j++)
>>> {
>>>
>>> hash[str[j]-'a'] = 1;
>>> count++;
>>> }
>>>
>>> max1=max(count,max1);
>>> for(k=0;k<26;k++)
>>> hash[k]=-1;
>>>
>>>
>>> }
>>> printf("%d ",max1);
>>> getch();
>>> return 0;
>>> }
>>>
>>> Worst case running time : O(n^2) when string is of the form
>>> "abcdeabcde".
>>>
>>> Does there exist an O(n) solution for this?
>>>
>>> --
>>> 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/-/HoCrZFVsRh8J.
>>>
>>> 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.
>>>
>>
>>
>>
>> --
>> Ankur Khurana
>> Computer Science
>> Netaji Subhas Institute Of Technology
>> Delhi.
>>
>>
>
>
> --
> Ankur Khurana
> Computer Science
> Netaji Subhas Institute Of Technology
> Delhi.
>
>
--
Ankur Khurana
Computer Science
Netaji Subhas Institute Of Technology
Delhi.
--
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: Adobe Ques
Sorry , solution nahi dekha tha tera maine.
On Thu, Jul 21, 2011 at 9:29 PM, Ankur Khurana wrote:
> I gave an O(N) solution in a different thread by same author for this
> question...
>
>
> On Thu, Jul 21, 2011 at 6:08 PM, Abhi wrote:
>
>> My solution for this :
>>
>> #include
>> int max(int a,int b)
>> {
>> return a>b?a:b;
>> }
>>
>> int main()
>> {
>> char str[] = "abcdab";
>> int count=0,max1=0;
>> int i=0,j,k;
>> int hash[26];
>> for(i=0;i<26;i++)
>> hash[i]=-1;
>> for(i=0;i> {
>> count=0;
>> for(j=i;hash[str[j]-'a']==-1;j++)
>> {
>>
>> hash[str[j]-'a'] = 1;
>> count++;
>> }
>>
>> max1=max(count,max1);
>> for(k=0;k<26;k++)
>> hash[k]=-1;
>>
>>
>> }
>> printf("%d ",max1);
>> getch();
>> return 0;
>> }
>>
>> Worst case running time : O(n^2) when string is of the form "abcdeabcde".
>>
>> Does there exist an O(n) solution for this?
>>
>> --
>> 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/-/HoCrZFVsRh8J.
>>
>> 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.
>>
>
>
>
> --
> Ankur Khurana
> Computer Science
> Netaji Subhas Institute Of Technology
> Delhi.
>
>
--
Ankur Khurana
Computer Science
Netaji Subhas Institute Of Technology
Delhi.
--
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: Adobe Ques
I gave an O(N) solution in a different thread by same author for this
question...
On Thu, Jul 21, 2011 at 6:08 PM, Abhi wrote:
> My solution for this :
>
> #include
> int max(int a,int b)
> {
> return a>b?a:b;
> }
>
> int main()
> {
> char str[] = "abcdab";
> int count=0,max1=0;
> int i=0,j,k;
> int hash[26];
> for(i=0;i<26;i++)
> hash[i]=-1;
> for(i=0;i {
> count=0;
> for(j=i;hash[str[j]-'a']==-1;j++)
> {
>
> hash[str[j]-'a'] = 1;
> count++;
> }
>
> max1=max(count,max1);
> for(k=0;k<26;k++)
> hash[k]=-1;
>
>
> }
> printf("%d ",max1);
> getch();
> return 0;
> }
>
> Worst case running time : O(n^2) when string is of the form "abcdeabcde".
>
> Does there exist an O(n) solution for this?
>
> --
> 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/-/HoCrZFVsRh8J.
>
> 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.
>
--
Ankur Khurana
Computer Science
Netaji Subhas Institute Of Technology
Delhi.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Adobe Ques
My solution for this :
#include
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
char str[] = "abcdab";
int count=0,max1=0;
int i=0,j,k;
int hash[26];
for(i=0;i<26;i++)
hash[i]=-1;
for(i=0;ihttps://groups.google.com/d/msg/algogeeks/-/HoCrZFVsRh8J.
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: Adobe Ques
is this a permutation question or combination question, the example does not
give a hint that way...
the idea is to ensure that starting at position n, successively allow all
possible non-used character in position n, and then possible combinations
starting from position n+1 ensuring that the strin length to be printed is r
int length=strlen(pIn);
void permute(char *pOut, int Outindex,bool used[], int included)
{
if (included==r) printOutPutArray(pOut); return;
}
for (int i=0;i wrote:
> On Jul 14, 8:53 am, 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
>
> The problem has a nice recursive structure. To choose r items from a
> set of items numbered m..n, make a decision to choose one of these.
> Say it's i, where m <= i <= n. Then recur to find the rest of the
> (r-1) items from the subset i+1...n. The base case is r==0, which
> means you have found all the items you need and can print the result.
> (You can refine this a bit to get rid of some useless recursive calls.
> How?)
>
> Here is one approach of many possible to code this idea:
>
> #include
> #include
>
> typedef struct choice_s {
> struct choice_s *prev;
> int i;
> } CHOICE;
>
> void print_choices(char *set, CHOICE *choices)
> {
> if (choices) {
>print_choices(set, choices->prev);
>putchar(set[choices->i]);
> }
> }
>
> void print_combinations(char *set, int n, int r, CHOICE *choices)
> {
> if (r == 0) {
>print_choices(set, choices);
>putchar('\n');
> }
> else {
>CHOICE choice[1] = {{ choices }};
>for (choice->i = choices ? choices->i + 1 : 0; choice->i < n;
> choice->i++)
> print_combinations(set, n, r - 1, choice);
> }
> }
>
> int main(int argc, char *argv[])
> {
> int r;
> char *s;
>
> if (argc == 3 && sscanf(argv[2], "%d", &r) == 1 && strlen(argv[1])
> >= r)
>s = argv[1];
> else {
>s = "abcde";
>r = 3;
> }
> print_combinations(s, strlen(s), r, 0);
> return 0;
> }
>
> $ ./a.out
> abc
> abd
> abe
> acd
> ace
> ade
> bcd
> bce
> bde
> $
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Adobe Ques
On Jul 14, 8:53 am, 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
The problem has a nice recursive structure. To choose r items from a
set of items numbered m..n, make a decision to choose one of these.
Say it's i, where m <= i <= n. Then recur to find the rest of the
(r-1) items from the subset i+1...n. The base case is r==0, which
means you have found all the items you need and can print the result.
(You can refine this a bit to get rid of some useless recursive calls.
How?)
Here is one approach of many possible to code this idea:
#include
#include
typedef struct choice_s {
struct choice_s *prev;
int i;
} CHOICE;
void print_choices(char *set, CHOICE *choices)
{
if (choices) {
print_choices(set, choices->prev);
putchar(set[choices->i]);
}
}
void print_combinations(char *set, int n, int r, CHOICE *choices)
{
if (r == 0) {
print_choices(set, choices);
putchar('\n');
}
else {
CHOICE choice[1] = {{ choices }};
for (choice->i = choices ? choices->i + 1 : 0; choice->i < n;
choice->i++)
print_combinations(set, n, r - 1, choice);
}
}
int main(int argc, char *argv[])
{
int r;
char *s;
if (argc == 3 && sscanf(argv[2], "%d", &r) == 1 && strlen(argv[1])
>= r)
s = argv[1];
else {
s = "abcde";
r = 3;
}
print_combinations(s, strlen(s), r, 0);
return 0;
}
$ ./a.out
abc
abd
abe
acd
ace
ade
bcd
bce
bde
$
--
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.
