Pinterest Interview Question for Senior Software Development Engineers

Team: general
Country: United States
Interview Type: Phone Interview

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

Can be solved by dynamic programming. Let
W(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

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

``````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());
}``````

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

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.

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

Just tested it and it works.

public static void main(String[] args) {
// TODO code application logic here
Set<String> dict = new HashSet<String>();

stringIntoSentence("aaaaisname", dict);

}

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

doesn't work for:
public static void main(String[] args) {
// TODO code application logic here
Set<String> dict = new HashSet<String>();

stringIntoSentence("aaaaisname", dict);
}

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

def segment(str: String, dict: List[String], output: List[String]) {
if (str == "") println(output.mkString(" "))
else {
dict.foreach { word =>
if (str.startsWith(word)) {
segment(str.substring(word.length), dict, output :+ word)
}
}
}
}

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

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;

}``````

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

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

}``````

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

``````class Solution:
def wordBreak(self, s, wordDict):
#word[i] means minimum number of words in the string s[:i+1]
w = [float('inf')] * (len(s) + 1)
w[0]  = 0

for i in range(len(s)):
for j in range(i, len(s)):
if s[i:j+1] in wordDict:
w[j+1] = min(w[j+1], w[i] + 1)

return w[-1]``````

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

Naive backtrack solution

``````public static void main(String[] args) {
Set<String> dict = new HashSet<>();
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) {
}
}
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) {
return;
}
for(int i = 1; i <= input.length(); i++) {
String current = input.substring(0,i);
if(dict.contains(current)) {
formattWordWithMinimumNumber(dict, input.substring(i), list, res);
list.remove(list.size()-1);
}
}
}``````

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

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;
}``````

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

Word break problem but more like coin change during solution.

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

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

Comment hidden because of low score. Click to expand.
-2
of 2 vote

asd

Comment hidden because of low score. Click to expand.

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.

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.