Amazon Interview Question
Country: United States
Interview Type: Phone Interview
/*
Solution approach:
- it looks like a DP problem which seems to work
- How ever, I found it easier to think of it as a parsing problem:
- match first word, then progress to the next one, start with the smallest word
- store in a list the word-index or word length
- if we reach the end without being able to further match, obviously at some point
the matching was wrong, as long as we still have alternatives at some point, so
we go back one word and retry our luck, if that fails again, go back further
everytime, when coming back try with a longer word etc...
- We could think of it as a parser if it can't decide on the next temrinal which
production it is, so it does look ahead, here it does backtrack, which is the
passive version (try all possibilities and back track vs. try o find out be
looking ahead)
- Looking at it from a runtime perspective, one could argue, the natural language is
built to require little backtracking since if it accidentially finds a word that
is part of an other word as it progresses the possibility is getting very small
that it comes very far. Whereas in a language where all combintions of letters
lead to a valid word, this wouldn't be the case.
I find it a cool question!
*/
#include <vector>
#include <string>
#include <queue>
#include <iostream>
#include <sstream>
using namespace std;
const size_t MAX_WORD_LENGTH = 80;
const char* SAMPLES[] = { "thisisavalidsentence", "thisisavalidsentencewhichrequiresautomaticbacktrack"};
const char* WORD_TABLE[] {"this", "is", "a", "valid", "sentence", "auto", "automatic",
"with", "sample", "backtrack", "which", "requires",
"of", "the", "back", "track", "require", "sau"}; //"sau is pig in german :-)
// primitive and not performant, returns if [s, e) is a word
bool IsWord(const string& str, int s, int e)
{
string ss = str.substr(s, e - s);
for (auto w : WORD_TABLE)
if (ss.compare(w) == 0) return true;
return false;
}
// tries to find a word starting at s, with minimal length minl int the string str
// using IsWord function, returns the length of the found word which is the
// shortest matching word with length >= minl
int FindWord(const string& str, int s, int minl)
{
int maxl = min(str.length() - s + 1, MAX_WORD_LENGTH);
for (int l = minl; l < maxl; l++)
if (IsWord(str, s, s + l)) return l;
return 0;
}
// modifies the string str to contain spaces between words, throws exception
// (of type const char*) if failed to reconstruct whole string
void ReconstructSentence(string& str)
{
vector<int> wordl; // contains the found word lengths
int i = 0; // current position
int n = str.length();
int m = 1; // minimal word size to be matched
while (i < n)
{
int l = FindWord(str, i, m);
if (l > 0)
{ // found a word
wordl.push_back(l);
i += l;
m = 1;
}
else
{ // didn't find a word, need to backtrack
if (wordl.size() == 0) throw "can't find a solution";
m = wordl.back();
wordl.pop_back();
i -= m; // back track word length in string
m++; // word needs to be longer
}
}
i = 0;
for (int l : wordl)
{
i += l;
str.insert(i, " ");
i++;
}
}
int main()
{
for (auto s : SAMPLES)
{
string str(s);
ReconstructSentence(str);
cout << "sample :" << s << endl << "is: " << str << endl << endl;
}
getchar();
return 0;
}
var solution
function extractNextWord(s, A) {
if (s === "") {
return [s, A]
}
for (var i = 1; i <= s.length; ++i) {
var w = s.substring(0, i)
if (d(w)) {
A.push(w)
var retVal = extractNextWord(s.substring(i),
A.slice(0))
if (retVal && retVal[0] === "") {
solution = retVal[1]
break
}
}
}
if (solution) {
return solution.join(' ')
}
}
function d(s) {
var dictionary = ["this", "is", "a", "valid", "sentence"]
return dictionary.indexOf(s) !== -1
}
console.log(extractNextWord('thisisavalidsentence', []))
/*
*Basically using recursion to form every possible valid sentence
*
*
*/
import java.util.HashSet;
import java.util.Set;
public class FormValidSentence {
/*
* amazon-interview-questions Lets say someone accidentally deleted all the
* whitespaces from a sentence. Write a program to reconstruct the sentence
* from that stripped out string. Assume you have access to a dictionary
* function that returns if a given string is a valid word or not.
*
* Example input: thisisavalidsentence Output: this is a valid sentence
*
* If multiple solutions are possible, any one valid solution should be
* given. Assume there is always a valid solution. No invalid input will be
* given.
*/
private static Set<String> dictionary;
public static void main(String[] args) {
FormValidSentence fvs = new FormValidSentence();
String invalidSentances[] = { "thisisavalidsentence", "herewego" };
fvs.formValidSentences(invalidSentances);
}
private void formValidSentences(String[] invalidSentances) {
for (String string : invalidSentances) {
StackImpl<String> stack = new StackImpl<String>(string.length());
findSentences(string.toCharArray(), 0, stack);
}
}
private void findSentences(char[] charArray, int senIndex,
StackImpl<String> stack) {
String word = "";
if (senIndex == (charArray.length))
printStack(stack);
for (int i = senIndex; i < charArray.length; i++) {
word = word + charArray[i];
if (isValidWord(word)) {
stack.push(word);
findSentences(charArray, i+1, stack);
stack.pop();
}
}
}
private void printStack(StackImpl<String> stack) {
for (String word : stack) {
System.out.print(word + " ");
}
System.out.print("\n");
}
public static boolean isValidWord(String word) {
if (null == dictionary) {
dictionary = new HashSet<String>();
dictionary.add("here");
dictionary.add("we");
dictionary.add("he");
dictionary.add("go");
dictionary.add("this");
dictionary.add("is");
dictionary.add("a");
dictionary.add("valid");
dictionary.add("sentence");
dictionary.add("her");
}
return dictionary.contains(word) ? true : false;
}
}
iterative approach:
void reconstruct(string sentence, unordered_set<string>& dict)
{
vector<int> dp(sentence.size() + 1, -1);
dp[0] = 0;
for (int i = 1; i <= sentence.size(); i++) {
for (int j = 0; j < i; j++) {
if (dict.find(sentence.substr(j, i - j)) != dict.end() && dp[j] != -1) {
dp[i] = j;
}
}
}
int i = sentence.size();
vector<string> words;
while (i != 0) {
words.push_back(sentence.substr(dp[i], i - dp[i]));
i = dp[i];
}
for (int j = words.size() - 1; j >= 0; j--) {
cout << words[j] << (j != 0 ? " " : "");
}
}
List<string> dictionary = new List<string> { "this", "is", "a", "valid", "string", "thi" };
static string output = "";
static void Main(string[] args)
{
// string input = "betterline";
string input = "thisisavalidstring";
Program obj = new Program();
if (obj.GetWhitespacedString(input, 0, input.Length-1))
{
Console.WriteLine(output);
}
else
{
Console.WriteLine("Invalid string");
}
}
private bool CheckDictionary(string str)
{
return dictionary.Contains(str);
}
public bool GetWhitespacedString(string input, int start, int end)
{
if (start > end)
{
return true;
}
for (int i = start; i <= end; i++)
{
int len = i - start + 1;
string intermediate = input.Substring(start, len);
bool isValidword = CheckDictionary(intermediate);
if (isValidword)
{
bool found = GetWhitespacedString(input, i + 1, end);
if (found)
{
output = intermediate + " " + output;
return true;
}
}
}
return false;
}
public class Dictionary{
public boolean containsWord(String str){...}
}
public String getValidSentence(String str, Dictionary d){
ArrayList<String> ls = new ArrayList<String>();
boolean r = getSentence(0, str, ls, d);
return makeSentence(ls);
}
private boolean getSentence(int i, String s, ArrayList<String> ls, Dictionary d){
if(i == s.length()){
return true;
}
boolean r = false;
for(int idx = i+1; idx < s.length(); i++){
String sub = s.subtring(i, idx);
if(d.containsWord(sub))
{
ls.add(sub);
r = getSentence(idx, s, ls, d);
if(r){
break;
}else{
ls.remove(ls.size()-1);
}
}
}
return r;
}
//O(N^2)
public class ConstructFile {
public static void main(String args[]) throws IOException {
BufferedReader br=null;
br = new BufferedReader(new FileReader("/Users/priyagupta/sample"));
String line = null;
while((line = br.readLine()) != null) {
constructLine(line);
}
}
public static void constructLine(String line) {
boolean found = false;
int startIndex = 0;
int endIndex = line.length();
int i = 0;
String word = null;
while(!line.equals(".")) {
while(!found) {
word = line.substring(startIndex, endIndex);
found = checkInDictionary(word);
endIndex = line.length() - ++i;
}
System.out.print(word + " ");
found = false;
line = line.substring(word.length() , line.length());
endIndex = line.length();
i=0;
}
}
public static boolean checkInDictionary(String word) {
if(word.equals("here")) {
return true;
}
if(word.equals("we")) {
return true;
}
if(word.equals("go")) {
return true;
}
return false;
}
}
Here's my code:
bool dfs(string word, int startindex)
{
int length = word.length();
if(startindex == length)
{
return true;
}
int counter =1;
bool retval = false;
while(counter <= (length - startindex))
{
retval = find(std::string(word,startindex,counter));
if(retval)
{
bool iret = dfs(word,startindex+counter);
if(iret)
{
words.push_back(std::string(word,startindex,counter));
return true;
}
}
counter++;
}
return retval;
}
int main()
{
dfs("herewego",0);
return 0;
}
public class WordsFinderOnTree {
private final List<String> knownWords;
public WordsFinderOnTree(List<String> knownWords) {
this.knownWords = knownWords;
}
public List<String> splitLine(String wordsline) {
List<String> foundWords = new ArrayList<>();
WordNode wordNode = new WordNode(wordsline, new ArrayList());
List<WordNode> fringes = wordNode.getChildren(knownWords);
while(!fringes.isEmpty()) {
WordNode currentNode = fringes.get(0);
fringes.remove(0);
if(currentNode.isTextFullyFound()) {
return currentNode.getFoundWords();
} else {
fringes.addAll(currentNode.getChildren(knownWords));
}
}
return foundWords;
}
}
public class WordNode {
static final Integer MAX_WORD_CHAR = 30;
private String substring;
private List<String> foundWords;
public WordNode(String substring, List<String> foundWords)
{
this.substring = substring;
this.foundWords = foundWords;
}
public List<String> getFoundWords()
{
return foundWords;
}
public List<WordNode> getChildren(List<String> knownWords) {
List<WordNode> possibleWord = new ArrayList<>();
String newString = "";
for(Integer index=0; index<substring.length() && index < MAX_WORD_CHAR; index++) {
newString += substring.charAt(index);
if(knownWords.contains(newString)){
List<String> words = new ArrayList<>();
words.addAll(getFoundWords());
words.add(newString);
possibleWord.add(new WordNode(substring.substring(newString.length()), words));
}
}
return possibleWord;
}
public boolean isTextFullyFound()
{
return substring.isEmpty();
}
}
public class ReconstructAgainFromStrippedString
{
public static void main(String[] args)
{
String str ="thisisastrippedstring";
StringBuilder finalString = new StringBuilder();
int count = 1;
int initialCount = 0;
while(count < str.length()+1)
{
if(Dictionary.itPresent(str.substring(initialCount,count)))
{
finalString.append(str.substring(initialCount,count));
finalString.append(" ");
initialCount = count;
}
count++;
}
System.out.println("Final unstripped String is ::::\n '" + finalString.toString() + "'");
}
}
class Dictionary
{
static List<String> dictionary;
static
{
dictionary = new ArrayList<String>();
dictionary.add("this");
dictionary.add("is");
dictionary.add("a");
dictionary.add("stripped");
dictionary.add("string");
//dictionary.put("as", "");
}
public static boolean itPresent(String str)
{
if(dictionary.contains(str))
return true;
return false;
}
}
public static void findSentence(String s){
if(s.length()<=1)
return;
String finalStr="";
String past = "";
int index =0;
int pastIndex = index;
for (int i = 0; i < s.length(); i++) {
String str = s.substring(index,i+1);
if(isValidWord(str)){
finalStr = finalStr + str+" ";
past = str;
pastIndex = index;
index=i+1;
}else{
if(!past.equals("") && (i+1)==s.length()){
i = index-1;
index=pastIndex;
System.out.println(finalStr);
finalStr = finalStr.substring(0,finalStr.indexOf(past));
}
}
}
finalStr = finalStr.trim();
System.out.println("Final String: "+finalStr);
}
public static boolean isValidWord(String s){
//System.out.println("** " + s);
String[] arr = {"this","is","valid","word","he","we","go","here","a","stripped","string"};
for (int i = 0; i < arr.length; i++) {
if(arr[i].equals(s))
return true;
}
return false;
}
public static void findSentence(String s){
if(s.length()<=1)
return;
String finalStr="";
String past = "";
int index =0;
int pastIndex = index;
for (int i = 0; i < s.length(); i++) {
String str = s.substring(index,i+1);
if(isValidWord(str)){
finalStr = finalStr + str+" ";
past = str;
pastIndex = index;
index=i+1;
}else{
if(!past.equals("") && (i+1)==s.length()){
i = index-1;
index=pastIndex;
System.out.println(finalStr);
finalStr = finalStr.substring(0,finalStr.indexOf(past));
}
}
}
finalStr = finalStr.trim();
System.out.println("Final String: "+finalStr);
}
public static boolean isValidWord(String s){
//System.out.println("** " + s);
String[] arr = {"this","is","valid","word","he","we","go","here","a","stripped","string"};
for (int i = 0; i < arr.length; i++) {
if(arr[i].equals(s))
return true;
}
return false;
}
public static void findSentence(String s){
if(s.length()<=1)
return;
String finalStr="";
String past = "";
int index =0;
int pastIndex = index;
for (int i = 0; i < s.length(); i++) {
String str = s.substring(index,i+1);
if(isValidWord(str)){
finalStr = finalStr + str+" ";
past = str;
pastIndex = index;
index=i+1;
}else{
if(!past.equals("") && (i+1)==s.length()){
i = index-1;
index=pastIndex;
System.out.println(finalStr);
finalStr = finalStr.substring(0,finalStr.indexOf(past));
}
}
}
finalStr = finalStr.trim();
System.out.println("Final String: "+finalStr);
}
public static boolean isValidWord(String s){
//System.out.println("** " + s);
String[] arr = {"this","is","valid","word","he","we","go","here","a","stripped","string"};
for (int i = 0; i < arr.length; i++) {
if(arr[i].equals(s))
return true;
}
return false;
}
Java implementation:
import java.util.ArrayList;
public class InsertWhitespaces {
static ArrayList<String> dictionary = new ArrayList<String>();
public static void main(String[] args) {
// TODO Auto-generated method stub
dictionary.add("he");
dictionary.add("herew");
dictionary.add("we");
dictionary.add("go");
String str = "herewwego";
insertWhitespaces(str , 0 , str.length());
}
private static void insertWhitespaces(String str, int start, int end) {
// TODO Auto-generated method stub
if ( start == end) {
System.out.println(str);
return;
}
for ( int i = start+1 ; i <= end ; i++) {
if ( dictionary.contains(str.substring(start , i ))) {
insertWhitespaces( str.substring(0, start) + str.substring(start , i) + " " + str.substring(i , end), i+1, end+1);
}
}
}
}
public boolean construct(String s, List<String> list){
String str = ""+s.charAt(0);
boolean isWord = false;
for(int i=1;i<s.length();i++){
if(!isWord(str+s.charAt(i)){
isWord=false;
str+=s.charAt(i);
}else{
list.add(str);
isWord = true;
if(!construct(s.substring(i), list)){
list.remove(list.size()-1);
isWord=false;
}
}
}
return isWord;
}
I have another solution in mind:
- transform the dictionary into a prefix-treue
- use it to yield matching Preises
- use a stack to evaluate any candidate one by ohne from the ende
- memoize intermediate failures and intermediate points on success (Position as Keys)
- yield all tue successes along tue was
Should give O(n) performances + Cache retrieval
def validate(string,vocab, start=0, end=0):
word = ""
newstr = string[start:end]
for i in range(len(newstr)):
global valid
if newstr not in valid:
word += newstr[i]
print word
if word in vocab:
valid.append(word)
start = i + 1
end = len(newstr) + 1
word = ""
return validate(newstr,vocab, start, end)
if word:
word = valid.pop()
vocab.remove(word)
newstr=word+newstr
start = 0
end=len(newstr)
return validate(newstr,vocab,start,end)
return valid
valid=[]
li = ['he', 'she', 'it', 'this', 'is', 'a', 'valid', 'sentence', 'here', 'we', 'go']
val=validate("avalidsentence",li, 0, len("avalidsentence"))
print val
print " ".join(i for i in val)
def validate(string,vocab, start=0, end=0):
word = ""
newstr = string[start:end]
for i in range(len(newstr)):
global valid
if newstr not in valid:
word += newstr[i]
print word
if word in vocab:
valid.append(word)
start = i + 1
end = len(newstr) + 1
word = ""
return validate(newstr,vocab, start, end)
if word:
word = valid.pop()
vocab.remove(word)
newstr=word+newstr
start = 0
end=len(newstr)
return validate(newstr,vocab,start,end)
return valid
valid=[]
li = ['he', 'she', 'it', 'this', 'is', 'a', 'valid', 'sentence', 'here', 'we', 'go']
val=validate("avalidsentence",li, 0, len("avalidsentence"))
print val
print " ".join(i for i in val)
void recursiveParse(const string& str, int start , int end , int length, int actualCount)
{
if(actualCount >= length +1)
{
return;
}
//Get sub string with start end and check if it is part of dictionary
//if it matches ,then make start = end and end = end+1;
string subStr = str.substr(start, end);
cout << subStr << " " <<start << " "<< end<< endl;
if(myMap[subStr] == 1)
{
//Found string
output = output + " " +subStr;
cout << "pasting" << " " << output <<endl;
start = actualCount;
end = 0;
}
recursiveParse(str,start,end+1,length,actualCount+1);
}
Implemented with backtrack algorithm
public class BuildStringFromDeletedWhiteSpaces
{
private static List<String> DICTIONARY = Arrays.asList("this", "is", "a", "valid", "sent", "sentence");
public static void main(String args[])
{
String input = "thisisavalidsentence";
System.out.println(buildString(input));
}
public static List<String> buildString(String input)
{
List<String> result = new ArrayList<>();
buildString(input,0,result);
return result;
}
public static boolean buildString(String input, int index, List<String> result)
{
for(int i=index;i<input.length();i++)
{
String sub = input.substring(index,i+1);
if(DICTIONARY.contains(sub)){
result.add(sub);
if( input.length() <= (i+1) || buildString(input,i+1, result))
{
return true;
}
result.remove(result.size()-1);
}
}
return false;
}
}
We need to handle the situation where one word starts with another word.
For example,
input
Since "he" is a valid word, we don't want the program to fail after finding "he".
The output should be "here we go"
- shane030716 August 23, 2016public static String construct(String s) { if (s == null || s.isEmpty()) return null; List<String> result = construct(s, 0, 1); return StringUtils.join(result, " "); } public static List<String> construct(String s, int start, int end) { if (s == null || s.isEmpty()) return null; if (start > end) return null; if (end > s.length()) { if (end - start == 1) { return new ArrayList<String>(); } else { return null; } } String substring = s.substring(start, end); if (isAWord(substring)) { List<String> rest = construct(s, end, end + 1); if (rest != null) { rest.add(0, substring); return rest; } } return construct(s, start, end + 1); } public static boolean isAWord(String s) { // check if it's a valid word }