CareerCup

If string only has characters, assign all the a to z one prime number.
a = 1, b = 2, c = 3, d = 5 ...
Multiply all the characters of string 1.
For eg. abc == 1 * 2 * 3 = 6
and string 2 also.
Find remainder mul(string1) / mul(string2). If it is 0; than string 2 is in string 1, otherwise no.
(Not works for bigger inputs)

Assume ASCII.
I'd use two arrays T of size 128 and foreach string T[s[i]]=1: O(n + m);
Then match the values from each array. if T1[i] == 1 && T2[i] == 0, the second does not have the (i+1)'th ASCII character; return false(or something).
Return true.

My solution:

1. Keep the First string's Characters to a HashSet - O(n)
2. Check for each character from Second String in the HashSet. If any character didn't match, return false - O(m)

Total Time Complexity - O(m+n)
Space Complexity -O(n)

two steps to solve:
1) sort the B string
2) Do a linear search for the characters of A strings

Create a 26bit array. Now go through source and fill it using string B. Go through A and check if those bits are already set. That will be O(n).

first sort both string O(log(m+n))
then traverse through second string O(m)

any one with code for this question?

void print(char *mainstr, char *refstring)
{
  int *refstringmap = (int*)malloc(sizeof(int)*26);//just assuming string has only                      alphabets

for(int i=0; *(refstring+i);i++)
{
  refstringmap[*(refstring+i)] = 1;
  refcount++;
}

for(int j=0;*(mainstring+j);j++)
{
  if(refstringmap[*(mainstring+j)]
     maincount++;
}

if(refcount == maincount)
   return true;
else 
   return false;

I think this should work:

bool sameChars(const char* p1, const char* p2)
{
  if (!p1 || !p2) return false;
  int aryHit[256] = {0};
  int nCharCount = 0;
  int nSize = strlen(p1);
  for (int i = 0; i < nSize; ++i)
  {
    if (aryHit[p1[i]] == 0) ++nCharCount;
    ++aryHit[p1[i]];
  }
  nSize = strlen(p2);
  int nFoundCount = 0;
  for (int i = 0; i < nSize; ++i)
  {
    if (aryHit[p2[i]] > 0)
    {
      --aryHit[p2[i]];
      if (aryHit[p2[i]] == 0) ++nFoundCount;
      if (nFoundCount == nCharCount)
      {
        return true;
      }
    }
  }
  return false;
}

This is just a pseudocode. It may have syntactical errors.

void fillArr(char countarr[], char* Astr)
{

   while(Astr)
   {
     int i=0;
     countarr[*Astr[i]] +=1;
   }
}

ProcessStr(char* Astr, char*Bstr)
{
   int i=0;
   while(*Bstr+i)
   {
      temp = *Bstr+i;
      if(countarr[temp]>0) countarr[temp]--;
      i++;
   }   
}

Then, check the count array if it has any value for those characters in string A. If it is all 0, then it means those characters were all present in the B string and hence the function would return a true. Else, the function would return a false.

Why not just use String b.contentEquals(String a) ????

use a hash table....
for each element it has 2 counts...cnt1 and cnt2
initialize both counts with 0
now traverse both strings and put it in hash table and maintain their respective counts
after traversing both stings if cnt1>=cnt2 (in entire hash table) means that string2 is in string1....

use a hash table....
for each element it has 2 counts...cnt1 and cnt2
initialize both counts with 0
now traverse both strings and put it in hash table and maintain their respective counts
after traversing both stings if cnt1>=cnt2 (in entire hash table) means that string2 is in string1....