Pinterest Interview Question
Senior Software Development EngineersTeam: general
Country: United States
Interview Type: Phone Interview
public static void stringIntoSentence(String seq, Set<String> dict) {
StringBuffer sb = new StringBuffer();
if (seq != null && seq.length() > 0 && dict != null && !dict.isEmpty()) {
while (seq.length() > 0) {
String helper = "";
String foundIt = "";
char[] _seq = seq.toCharArray();
for (int i = 0; i < _seq.length; i++) {
helper += String.valueOf(_seq[i]);
if (dict.contains(helper))
foundIt = helper;
}
if (foundIt.length() > 0) {
seq = seq.substring(foundIt.length());
sb.append(foundIt);
if (seq.length() > 0)
sb.append(" ");
} else return;
}
}
System.out.println("--> " + sb.toString());
}
This will not work if "aa" is also in the dictionary. The output then would be "aa a is a name" which is 5 words. The objective is to output minimum no of words.
Just tested it and it works.
public static void main(String[] args) {
// TODO code application logic here
Set<String> dict = new HashSet<String>();
dict.add("a");
dict.add("aa");
dict.add("aaa");
dict.add("is");
dict.add("name");
stringIntoSentence("aaaaisname", dict);
}
This can be solved using Trie.
Assuming we have a Trie data structure with all the dictionary words in it
Basic idea is for each character keep on tracking whether the prefix it covered is a valid word or not. If it is then we have 2 subproblems
a. substring upto i is valid but need to check validity of i+1 to length subsequence.
b. ignore validity of substring 0 to i instead keep on checking validity of the subsequence from 0 to i+1
if any of the two subproblems give a result true. Overall result will be true.
public static boolean isValidSequence(Trie trie, String sequence){
boolean rslt = false;
int length = sequence.length();
TrieNode node = trie.getRoot();
int i = 0;
for( i = 0; i < length; i++){
char ch = sequence.charAt(i);
int charIdx = ch - 'a';
TrieNode[] children = node.getChildren();
TrieNode charNode = children[charIdx];
if(charNode == null){
rslt = false;
break;
}
if(charNode.isEndsWord()){
String subSeq = sequence.substring(i+1);
boolean rsltOfNextSeq = isValidSequence(trie, subSeq);
if(rsltOfNextSeq){
rslt = true;
break;
}
}
node = charNode;
}
if((i == length) && (node.isEndsWord()))
rslt = true;
return rslt;
}
Not very efficient but it does the job when under the pressure and you forgot how to implement a trie
// O(n^2) running time
def wordSeparator2(dict:Set[String], s:String):List[String] = {
val chars = s.toCharArray
var words = List[String]()
var i = 0
var j = i
while(i < chars.size) {
val c = chars(i)
var word = ""
var unusedChars = ""
// be greedy and try to get the longest word
for(j <- i to chars.length - 1) {
if(dict.contains(word + unusedChars + chars(j))) {
word = word + unusedChars + chars(j)
unusedChars = ""
i = j
} else {
unusedChars = unusedChars + chars(j)
}
}
if(word != "")
words = word :: words
i = i +1
}
words
}
Naive backtrack solution
public static void main(String[] args) {
Set<String> dict = new HashSet<>();
dict.add("a"); dict.add("aaa"); dict.add("name"); dict.add("is");
String input = "aaaisaname";
List<String> res = formattedWordWithMinimumNumber(dict, input);
for(String s : res) {
System.out.println(s);
}
}
public static List<String> formattedWordWithMinimumNumber(Set<String> dict, String input) {
List<String> list = new ArrayList<>();
List<List<String>> res = new ArrayList<>();
formattWordWithMinimumNumber(dict, input, list, res);
List<String> minWordList = new ArrayList<>();
StringBuilder strBuilder = new StringBuilder();
int minNumOfWords = Integer.MAX_VALUE;
for(int i = 0; i < res.size(); i++) {
int listSize = res.get(i).size();
// System.out.println(listSize);
// if(listSize > 0)
minNumOfWords = Math.min(listSize, minNumOfWords);
}
for(int i = 0; i < res.size(); i++) {
if(res.get(i).size() == minNumOfWords) {
minWordList.add(formatListToStr(res.get(i)));
}
}
return minWordList;
}
public static String formatListToStr(List<String> list) {
StringBuilder strBuilder = new StringBuilder();
for(String s : list) {
strBuilder.append(s+" ");
}
strBuilder.setLength(strBuilder.length()-1); // remove last space
return strBuilder.toString();
}
public static void formattWordWithMinimumNumber(Set<String> dict, String input, List<String> list, List<List<String>> res) {
if(input.length() == 0) {
res.add(new ArrayList<>(list));
return;
}
for(int i = 1; i <= input.length(); i++) {
String current = input.substring(0,i);
if(dict.contains(current)) {
list.add(current);
formattWordWithMinimumNumber(dict, input.substring(i), list, res);
list.remove(list.size()-1);
}
}
}
Brute force approach in javascript.
function longest(input, dict) {
let res = [];
while (input.length > 0) {
let longest = "";
for (var i = 1; i <= input.length; i++) {
let test = input.substring(0, i);
if (dict.has(test)) {
longest = test;
}
}
if (longest.length == 0) {
throw new Error();
}
input = input.substring(longest.length);
res.push(longest);
}
return res;
}
import UIKit
final class PTTSolution {
static let words: Set = ["a", "aa", "is", "name"]
// static let words: Set = ["a"]
class func Verify(_ input:String?) -> String? {
guard let input = input, input.count > 0 else {
return nil;
}
var lengths: Set<Int> = []
words.forEach { word in
lengths.insert(word.count)
}
var result: Array<(i: Int, w: String)> = Array(repeating: (0, ""), count: input.count + 1)
result[0] = (i: 1, w: "")
for i in 1...input.count {
lengths.forEach { length in
let startIndex = i - length
if startIndex < 0 {
return
}
let steps = result[startIndex]
if steps.i == 0 {
return
}
let start = input.index(input.startIndex, offsetBy: startIndex)
let end = input.index(input.startIndex, offsetBy: i)
let substring = String(input[start..<end])
if !words.contains(substring) {
return
}
let fullWord = steps.w.count == 0 ? substring : steps.w + " " + substring;
if (result[i].i == 0) || (result[i].i > steps.i + 1) {
result[i] = (i: steps.i + 1, w: fullWord)
}
}
}
return result.last!.w;
}
}
let input = "aaaisaname";
print(PTTSolution.Verify(input) ?? "no result");
// O(w + n*l) - where w - is number of words, n - is a number of characters in the input, l - is different lengths of word in the dictionary
Can be solved by dynamic programming. Let
- kr.neerav February 06, 2014W(k) : no of words in the string from 0 to k. If there are incomplete words then the number is infinity
word(i,k) : returns 1 if a word formed from characters in the string from i to k exists in dict else return infinity
Recursion equation
W(k+1) = min [W(i) + word(i,k+1)] for i from 1 to k