Kallu
BAN USERIs it not ambiguity problem. Let's say the sentence has a word "output" then dictionary has two words "out" and "put". So, how do we interpret output word.
Let us there is no ambiguity then it is not simple as follows: Start with first char and check whether that is in dictionary or not (say I) . If it is then just add space after that. If not then check with two chars and if not check 3 chars and so on.
Algorithm:
1. Search the first char of S1 in S2 (from last). If S1 prefix has consecutive duplicates (AAAB) then move backwards (from the position we just found) in S2 until we different char.
2. Now, compare S1 from beginning and in S2 from the point we got in step 1.
3. Compare till we found mismatch or end of the string(s). If we are end of S2 then the traversed string is longest sub string.
Example:
S1 = "abcdef" and S2 = "xyxabc"
1. after first step the s2 pointer points to s[3] i.e a
2. Now start compare from s1[0] and s2[3]
Since our search ends at end of S2 the longest sub string is 'abc'
Let me know, If I am missing any cases.
If we observe grid carefully, they are in sorted order (rows an columns individually). So, I guess, interviewer is expecting binary search on row wise and/or column wise.
Forgive me, if somebody is already noticed this point and above programs are already have this logic (little lazy to read all programs :))
Is the question correct (might be typo)? If we need to find out the words with length n in string of n length then always only one string is possible. I guess, the question is find all words with length m (m <= n), then more words are possible in output. Please clarify.
- Kallu October 06, 2013The best solution I can think of is we should go with hash/map to get it done in O(n). But, people are doing it in two steps (1. prepare map with elements frequencies, 2. Iterate through map to find max frequency number). Actually, we can avoid second step, if we maintain (and update) num of frequencies/majority elements in first iteration itself, then no need to go over map again. Below is working code in C++:
int MajorityFindProblem(int * a, uint size) {
if(size < 1)
return -1;
ulong MajorityElement = a[0];
uint NoOfOccurences = 0;
map<int, uint> m;
map<int, uint>::iterator itr;
pair<int, uint> p;
// loop through the array and prepare a mao (Key is element and value is num of occurences)
// At the same time, maintain MajorityElement also, so that NO NEED to traverse map again for largest element
for(int i =0; i < size; i++) {
itr = m.find(a[i]);
if(itr != m.end()) { // increase num of occurences and also update MajorityElement (if required)
itr->second++;
if(itr->second > NoOfOccurences) {
MajorityElement = itr->first;
NoOfOccurences++;
}
} else { // this is new element
m[a[i]] = 1;
}
}
return MajorityElement;
}
-ve comments (if any) are most welcome.
- Kallu September 23, 2013
Repmarktrejjo, Data Engineer at Accolite software
I’m Mark.I believe life is too short to be serious all the time, so if you cannot laugh ...
Repdavisjerryh, Backend Developer at Abs india pvt. ltd.
For the last two years, I am Effectively managing the team’s performance, conducting regular performance reviews and appraisals, and ...
Somebody has already made excellent point "If the inorder traversal of the tree is sorted, the tree is BST else not."
- Kallu October 28, 2013Didn't get why people are still trying for other implementations?