Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
What if there could be a sentence in which more than one valid combination is possible????????/
For instance: Therestonecrushedspirit
1. The rest one crushed spirit
2. There stone crushed spirit
@VIK, I doubt we have to find all the sentences which can be framed with available valid words in given input. with my approach you will find "The rest one crushed spirit" as out put.
But yes we can think of extending solution to find all possible valid sentences.
void separateWords_rec(string text, int start_pos, string sentence)
{
for (int i = 1; i <= text.size() - start_pos; i++) {
string word = text.substr(start_pos, i);
if (isValidDictionaryWord(word)) {
if (i == text.size() - start_pos) { //solution
cout<<sentence<<" "<<word<<endl;
} else {
string new_sentence = sentence;
new_sentence.append(" ").append(word);
separateWords_rec(text, start_pos + i, new_sentence);
}
}
}
}
and call it with
separateWords_rec(text, 0, "");
Naive Recursive approach Approach..
Scan the string.. At every point you find a word. check if you can form a sentence from the rest of the charactors. if yes return 1 and the string formed.
else move on to the next charactor.
If you move till the end of the charactor return 0. -- A sentence cannot be formed.
int CheckSentence(char c[], char rest[], int l) {
char sentence[2 * strlen(c)];
char rest[2*strlen(c)];
if(l>=strelen(c))
return 1;
for (int i = l; c[i]!=0; i++) {
sentence[j] = c[i];
if (isWord(toWord(c,l, i)) && CheckSentence(c, rest,i+1)) {
strapp(sentence, ' ');
strapp(sentence, rest);
strapp(sentence,'\0');
strcpy(rest,sentence);
return 1;
}
}
return 0;
}
Maintain a Trie structure for dictionary of words.
Traverse the tree from root node as you parse and print each character in the string.
When trie tells you that you have successfully traversed a word, print space and start over from root for remaining characters.
public static boolean makesSentence(String remString,String consideredString,List <String> list)
{
int n = remString.length();
int p = consideredString.length();
if(n<0)
return false;
boolean b1=false;
boolean b2= false;
if(isValidDictionaryWord(consideredString))
{
if(n==0)
b1 =true;
else
b1= makesSentence(remString, "", list);
if(b1)
list.add(consideredString);
}
if(n>0)
b2 = makesSentence(remString.substring(1),consideredString+remString.charAt(0),list);
return b1||b2 ;
}
We have 2 use cases when a word matches
1.Either the next word starts from the next char
2.The word is part of a bigger word hence continue to check
some examples - timesofindia - we should match times of india
timesoftindia - time soft india.
Code below returns boolean of whether all words are part of dictionary
public static boolean validDictionarywords(String s, int startIndex, int endIndex){
boolean status = false;
for(int end = startIndex+1,start=startIndex ; end <= endIndex; end++){
if( isValidDictionaryword(s.substring(start, end))){
if(end == endIndex){
return true;
}
String newString = s.substring(end, endIndex);
status = validDictionarywords(newString, 0,newString.length() );
if(status){
return true;
}
}
}
return status;
}
Have a collection of linkedlists. These are global variables.
Find the first word. in the example it would be "the".
Put into linkedlist with its starting and ending index.
recursively call a new search from the ending index and then complete the original search.
The next word would be none for the recursive call.
delete the linkedlist starting with "the".
Comes back and gets to next word which is "there".
Put into linkedlist with ending index. Do same call.
Next word is is. starting index one more than ending index of one linkedlist. Add is to that linkdelist. Update ending index.
Also complete initial call which searches for one giant word. Any linkedlist which does not complete till end of string. (its ending index is smaller)... gets deleted.
The left linkedlists contain words in order that complete the sentence.
These are the solutions.
Worst case complexity: n squared time. Memory -- n^n, But unlikely.
import java.util.LinkedList;
public class TriesNode {
char data;
boolean end_of_string;
LinkedList<TriesNode> child;
public TriesNode(char c) {
this.data = c;
this.end_of_string = false;
this.child = new LinkedList<TriesNode>();
}
public TriesNode() {
this.end_of_string = false;
this.child = new LinkedList<TriesNode>();
}
public TriesNode subTriesNode(char c) {
if (this.getData() == c)
return this;
if (child != null) {
for (TriesNode node : child)
if (node.getData() == c)
return node;
}
return null;
}
public char getData() {
return data;
}
public void setData(char data) {
this.data = data;
}
public boolean isEnd_of_string() {
return end_of_string;
}
public void setEnd_of_string(boolean end_of_string) {
this.end_of_string = end_of_string;
}
public LinkedList<TriesNode> getChild() {
return child;
}
public void setChild(LinkedList<TriesNode> child) {
this.child = child;
}
}
public class Tries {
TriesNode root;
public Tries() {
}
void insert(String s) {
TriesNode cur = root;
if (s.length() == 0)
return;
if (s.length() == 1) {
if (cur == null) {
this.root = new TriesNode();
root.setData(s.charAt(0));
cur = root;
}
}
for (int i = 0; i < s.length(); i++) {
if (cur == null) {
this.root = new TriesNode();
root.setData(s.charAt(i));
cur = root;
} else {
TriesNode child = cur.subTriesNode(s.charAt(i));
if (child != null) {
cur = child;
}
else {
cur.child.add(new TriesNode(s.charAt(i)));
cur = cur.getChild().getFirst();
}
}
}
if (cur.isEnd_of_string() == false)
cur.setEnd_of_string(true);
}
boolean search(String s) {
TriesNode cur = root;
if (s.length() == 0)
return false;
for (int i = 0; i < s.length() - 1; i++) {
if (cur.getData() == s.charAt(i))
cur = cur.getChild().getFirst();
}
if (cur.isEnd_of_string() == true)
return true;
return false;
}
public static void main(String[] args) {
Tries tries = new Tries();
tries.insert("there");
tries.insert("is");
tries.insert("a");
tries.insert("stone");
tries.insert("on");
tries.insert("the");
tries.insert("road");
tries.search("thereisastoneontheroad");
}
}
Hi friendz..
We can also use the following approach instead of using stack for storing words. Extra space not required.
- Start with the first index, have two variables for eg. (int start=0; int end1=0;, int end2 = 0;)
- Then start with the first char and while moving ahead make the 'start' pointing to the first char and then increase 'end1' as we are moving ahead and see if the substring from (start, end1) is a valid word or not?
Case a: If Its a valid word, then we know (start, end1) index of valid sub string.
Case b: If not a valid word, then move the 'end1' further and look for the sub string valid/not valid.
If suppose, in the Case a, But we are interested in finding the largest valid word. So in that case, we have the first substring points (start, end1). So now start with 'end2 = end1' and increase 'end2' and see if the subString from (start, end2) is valid or not. If it is valid then change 'end1 = end2' and again cont.. Till the point, we found the largest valid word. Otherwise ,we are on the safe side, by getting the last largest word by getting (start, end1).
Repeat this...We will get the valid substring without extra space.
Please add, If I am missing something?
Thanks you...!!
Scala:
def isValidWord(w: String) = List("There", "is", "a" "stone", "on", "the" ,"road").contains(w)
def construct(s: String, sent: String, w: String): String = s.toList match {
case Nil => sent
case c :: rest if (isValidWord(w+c)) => construct(rest.mkString, sent+ " "+ w+c, "")
case c :: rest => construct(rest.mkString, sent, w+c)
}
public string findSent(String sentNoDelim)
{
if (sentNoDelim == null || sentNoDelim == "")
{
return "";
}
for (int i = 0; i<sentNoDelim.length;i++)
{
string tempWrd = sentNoDelim.subString(o,i);
if (isValidWord(tempWord))
{
return tempWrd + " " +
findSent(sentNoDelim.subString(i+1), sentNoDelim.length()));
}
}
}
This works :
using recursion.
The method is similar to what Sandeep has explained, so I wont bother.
This just does not use a stack.
private static final String ERROR_STRING="whatever the hell";
private static String getSpacedSenterce(String str) {
if ( isValidDictionaryword(str)){
return str;
}
for ( int i=0 ; i<str.length() ; i++ ){
if ( isValidDictionaryword(str.subSequence(0, i).toString())){
String result = getSpacedSenterce(str.substring(i));
if ( ! result.equals(ERROR_STRING)){
return str.substring(0,i)+" "+result;
}
}
}
return ERROR_STRING;
}
Very strange question. What's the big deal. There has to be atleast one word and the sentence should start from it. Start a linear traversal from beginning and keep on adding characters, for every character added see if the word formed so far is a well formed word. If NO add more characters. If Yes, print this valid word and repeat the process for the remaining sentence.
start loop
- Sandeep February 02, 2013find the first valid word put in stack
search for next valid word push to stack.
positive case all char will form valid case.
if after finding kth valid word, no word is getting formed
pop the kth word from stack find next word for which this popped word was subset. then keep moving ahead. Keep trying until correct set of words.
else pop the( k-1)th word and try the same above steps.
e.g "Hernameisjuli"
push "He"
then rest of the chars not making any words
pop "He"
push "Her"
push "name"
push "is"
push "juli" ( Provided juli is in dictionary ;))