sec
BAN USER
Comments (2)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
C implementation which takes O(M + N)
static int checkword(char *str1, char *str2)
{
int i, j;
char table1[255];
char table2[255];
memset(table1, 0x0, sizeof(table1));
memset(table2, 0x0, sizeof(table2));
/* this will take O(M) */
for (i = 0; str1[i]; i++)
table1[str1[i]] += 1;
/* remaining loops will take O(N) */
for (j = 0; j < i && str2[j]; j++)
table2[str2[j]] += 1;
while (memcmp(table1, table2, sizeof(table1))) {
if (!str2[j]) return 0;
table2[str2[j]] += 1;
table2[str2[j - i]] -= 1;
j++;
}
return 1;
}
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
IMO, this question seems to be asking the union-find algorithm, which allows us to identify disjoint-set relationship.
- sec October 10, 2017