CareerCup

Option 1:
-> take an array of a[26], count the occurrences of all characters in the text you need and the total number of letters.
-> now while parsing the magazine just access a[character] and reduce it by 1 only if a[character] > 0 and --totalNumOfLetters. when totalNumLetters == 0 you got the answer

Option 2:
-> Learn Muay Thai and beat the s**t out of the gunman

Option 3:
-> Kiss the gunman and Kick his b**ls

This would probably work with an assumption that the character set is ascii

public boolean ransom(String note, String magazine){
		int[] hash = new int[256];
		char[] mag = magazine.toCharArray();
		char[] noteArr = note.toCharArray();
		for(char alphabet : mag){
			hash[alphabet]++;
		}
		
		for(char check : noteArr){
			if(hash[check] <= 0){
				return false;
			}
			else {
				hash[check]--;
			}
		}
		
		return true;
	}

1) Start traversing the ransom note and text simultaneously.
2) Maintain an ASCII character map for magazine text.
3) For each character in ransom note (except space) check if we have found the character from text by checking it's count (>=1). If it is (>=1) decrement it by 1 and move to next character in text.
4) If we haven't found the char in magazine text yet, keep parsing it (magazine) and keep adding newly found characters to map until you find the character you were looking for.

The worst case complexity will be O(m+n) when we can't make ransom out of text or if we are unlucky otherwise we would not have to traverse entire magazine and will be done much earlier. For ex: I ran the following code on a pattern of length 50 and text 1000, I had to parse only 204 characters (out of 1000) before reaching the answer.

bool makeRansomNote(string ransomNote, string text)
{
   int ASCII[26]={0};
   std::transform(ransomNote.begin(), ransomNote.end(),ransomNote.begin(),::tolower);
   std::transform(text.begin(), text.end(),text.begin(),::tolower);

   int pos=0;
   for(int i=0; i<ransomNote.length(); i++)
   {
        if(ransomNote[i]!= ' ')
        {
                while(pos<text.length() && ASCII[ransomNote[i]-97]==0)
                {
                        if(text[pos]==' ') { pos++; continue;}
                        ASCII[text[pos++]-97]++;
                }
                if(ASCII[ransomNote[i]-97]>=1 && pos<text.length())
                {
                        ASCII[ransomNote[i]-97]-=1;
                }
                else return false;
        }
   }
   return true;
}

^^ Its A is a subsequence of D , not substring

Use trie.
cost of populating the Trie is O(m* log|x|) where m is the distinct number of words in the magazine. |X| = avg length of words in the magazine

cost of finding the match of the words of the input sentence is n*log(|X|) where n = number of words in the input sentence.

This is Longest subsequence problem.
Longest subsequence should be of size of sentence.

a fancy(retarded?) way of asking 'Is A a sub-string of B'... sighh these D-bag interviewers! **rolls eyes**

1, create linklist for all distinct characters in the sentence, and keep track the number of them;
2, for the incoming magazine string, only keep track the occurring number of the characters in the previous link list;
3, if all corresponding numbers form the magazine are greater or equal to the previous linklist, report success.