None Interview Question for Students


Country: India
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
0
of 0 vote

Python recursive to find all possible combinations.

def split_words(s, words):
    ret = []
    phrases = split_words_aux(s, words)
    for p in phrases:
        ret.append(' '.join(p))
    return ret

def split_words_aux(s, words):
    ret = []
    
    if not s:
        return []
    
    
    for w in words:
        if w == s:
            return [[w]]
        if len(w) <= len(s) and s[:len(w)] == w:
            
            sub_str_matches = split_words_aux(s[len(w):], words)
            for match in sub_str_matches:
                ret.append([w] + match)
    return ret

- CC February 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think the first for loop scanning through all words in dictionary is very slow, if the dictionary is big.
Should check isInDictionary() for substring of the input string only.

- ninhnnsoc February 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static string SplitWords(string S, HashSet<string> words)
{
if(string.IsNullOrEmpty(S)
throw new ArgumentNullException("S can't be null");

List<string> result = new List<string>();

if(!CoreSplitWords(S, words, 0, result))
{
throw new ArgumentException("There are set of words);
}

return string.Join(' ', result);
}

private static bool CoreSplitWords(
string S,
HashSet<string> words,
int start,
List<int> result)
{
if(start == S.Length)
return true;

for(int i = start; i < S.Length; i++)
{
string value = S.Substring(start, i - start);


if(words.Contains(value))
{
result.Add(value);
if(CoreSplitWords(S, words, i + 1, result))
{
return true;
}
}
}

return false;
}
}

- Nelson Perez February 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Perez: dynamic programming can solve this.
In fact (your) recursion also works fine.

PS: You can re-edit your answer, inserting 3{ and 3} for code to make it a better view.
(The edit function is back, as I requested to Gayle.)

- ninhnnsoc February 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This problem can be solved by dynamic programming, with O(L.M) time and O(L) space, where L is the length of the input string, and M is the length of the longest word in the dictionary.

The dynamic programming idea is the same/similar to this Valid String problem, described in this link capacode.com/?p=285

My friend gives DP solution for checking valid string at the above link. Using the computed DP table, we can easily output the sentence itself.

- ninhnnsoc February 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This link solves the problem completely: capacode.com/?p=335

- ninhnnsoc February 26, 2015 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More