Get Sentence from raw text

String getSentence(String text, Set<String> dictionary);

// text is a string without spaces, you need to insert spaces into text, so each word seperated by the space in the resulting string exists in the dictionary, return the resulting string

// getSentence("iamastudentfromwaterloo", {"from, "waterloo", "hi", "am", "yes", "i", "a", "student"}) -> "i am a student from waterloo"


Approach:
String [] tokens = {"from", "waterloo", "hi", "am", "as", "stud", "yes", "i", "a", "student"};
String text = "iamastudentfromwaterloo";


Lets create a hashtable named tokenMap which will contain all the token of tokens array.

We will also have 2 stacks, lets say indexStack to keep track of starting index of all the matched tokens in text (this will become clear below .. keep on reading :))
And another stack resultStack which will store all the tokens of the final expected sentence.

We will also have a StringBuffer sb which will keep track of substring from text which would be a candinate token (we will verify that by checking in hashtable tokenMap)

Now,
We will read one character at a time from "text"
StringBuffer sb = "i";
Our start index = 0
Lets push index onto indextStack
sb = "i" is present in the hashtable tokenMap, so now we have following
indexStack = 0 -> null
resultStack = "i" -> null

we now reset sb = "";
Next we see sb = "a"
"a" is in tokenMap so now we have following
indexStack = 1 -> 0 -> null;
resultStack = "a" -> "i" -> null

Now things get interesting as we keep on reading the characters from text and appending to sb but the string is not there in hashtable tokenMap
like sb = "mastudent" ...
So we need to decide to backtrack in such case (logic can be if sb length goes beyond max length of any of the given tokens in tokens array)

So when we backtrack we pop the stacks and reset StringBuffer sb
indexStack = 0 -> null
resultStack = "i" -> null
sb = "";

now again we start appending characters to sb till sb has a match in tokenMap HashTable

We keep repeating the above steps till we have constructed our sentence or till we decide its NOT possible to do so.

Input:

String [] tokens = {"from", "waterloo", "hi", "am", "as", "stud", "yes", "i", "a", "student"};
String text = "iamastudentfromwaterloo";

Output:

Max Token Length: 8
Sentence is: i am a student from waterloo

Is Rotation

Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (i.e., “waterbottle” is a rotation of “erbottlewat”).



Approach:
Let S1 = "waterbottle";
S2 = "erbott";

concatanate S1 with itself
So we have S3 = S1 + S1 = "waterbottle" + "waterbottle" ;
S3 = "waterbottlewaterbottle";

Now we need to check if the S2 is a substring of S1.

if (s2.isSubstring(s3)) then return true;
else return false;

String A contains a substring which is anagram of String B ?

you are given two arrays. A of size n, B of size m. m is a very very small number compared to n. find out if A contains a substring which is anagram of B.


Approach1:
1. Sort B
2. maintain a window of length m and slide it along A
3. for each window do:
3.1 Sort the window O(mlogm)
3.2 Compare the sorted window with sorted B
3.3 If equal anagram found


T(n) = O(n*mlogm) but since m<<n T(n)~O(n)




Approach 2:
A = "dropoffprogrammingisgoodforhealth"
B = "ford"


find all the indices of characters in B string in A.
f = 5,6,24
o = 2,4,9,21,22,25
r = 1,8,11,26
d = 0,23


now find the indices for "f", "o", "r" and "d" such that they are consecutive.


In the above example we have 23, 24, 25, 26 - hence A contains a substring which is anagram of B.


If we can not find consecutive indices for all the characters in B, then A does not contain substring which is anagram of B.


What if B contains duplicate characters ? ie what if B = "fordo" in the above example ?


time complexity for above solution = O(n)

Dynamic Programming: Edit Distance problem.

The edit distance of two strings, s1 and s2, is defined as the minimum number of point mutations required to change s1 into s2, where a point mutation is one of:

change a letter,
insert a letter, or
delete a letter

The following recurrence relations define the edit distance, d(s1,s2), of two strings s1 and s2:

d('', '') = 0               -- '' = empty string
d(s, '')  = d('', s) = |s|  -- i.e. length of s
d(s1+ch1, s2+ch2)
  = min( d(s1, s2) + if ch1=ch2 then 0 else 1 fi,
         d(s1+ch1, s2) + 1,
         d(s1, s2+ch2) + 1 )

Code output:

S1: partnership
S2: markesshep
Edit Distance: 5

Remove Pattern String from Text String.

Given string input1, input2, remove wherever the occurrence of input2 in input1.
e.g: 
input1: skjthshetheshetesm
input2: she
input1 will become "skjththetesm" 


Code output:

Text: skjthshetheshetesm
Pattern: she
After removing pattern from text: skjththetesm
Text: abababa
Pattern: aba
After removing pattern from text: b

Put Spaces in a String.

Let's say you have a phrase without any spaces - eg. "thisisawesome". Given a dictionary, how would you add spaces in this string?


OR


When people search at Google, they often type two words without space. For example, instead of typing "binary tree", someone can type "binarytree". Given an input, what is a good way of finding if it is a combination of two valid words?


Input:
thisisaninterestingsentence
Output:
this is an interesting sentence


Approach for the phrase problem:
1. Lets say the length of the string is n and init phrase String as empty.
2. Now for every substring S[i,j] (0<=i<=j<n), check if its a valid word - check against the dictionary.
3. If we get a valid word then append it to the previously calculated and running phrase with a space.


Approach for the "two words wothout the space" problem.
1. Split the given string S[0..n] at the i (0<=i<n) positions. - For every split at ith index you will get 2 substrings S[left] and S[right]
2. Check if S[left] and S[right] are valid words.

Count words in a sentence. Words can be separated by more than one space.

Count words in a sentence. Words can be separated by more than one space.


Input: "  an b  c   d";
output: 4

First Non-Repeated Character in the String.

Given a String, find the first non-repeated character in the string.


Input:
abcdeecbkbala
Output:
Input String:
abcdeecbkbala
First non-repeated char in the string: d


Code:

Multiply long numbers.

Write a function to take two arbitrarily long numbers in the form of Strings and multiply them, returning another String with the product.
Input:
2839745624
8769342123
Output:
2839745624 x 8769342123 = 24902700919148119752


Code:

Index of substring match.

Method to return the index of first matching instance of pattern string in a text string.

Reverse String

Method to reverse the words in a string.
"who are you" -> "you are who"

Remove Duplicate characters from String

Function that removes duplicate characters from a string.

Binary String Sum

Function that takes in two binary strings and returns their sum (also a binary string).
Approach:
1. Reverse the strings, and pad the smaller string so that length of the strings are equal.
2. Calculate the binary sum by reading each character of the string starting from index 0 and keeping track of the carry.
3. Reverse the resultant string to get the final binary string sum.


Code (*edge cases are not handled):

Permutation of String.

Permutation of n characters - Recursive approach.



Alternative Approach:

Check if 2 strings are anagrams

Method to check if two given strings are anagrams or not.
public boolean isAnagram(String first, String second) {
if (null == first || null == second) {
return false;
}
int firstLen = first.length();
int secondLen = second.length();

if (firstLen != secondLen) {
return false;
}

char [] firstArr = first.toLowerCase().toCharArray();
char [] secondArr = second.toLowerCase().toCharArray();

Arrays.sort(firstArr);
Arrays.sort(secondArr);

for (int i=0; i<firstLen; i++) {
if (firstArr[i] != secondArr[i]) {
return false;
}
}
return true;
}