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

- kr.neerav February 06, 2014 | Flag Reply
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());
    }

- george.maggessy April 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- punkrokr911 April 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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);

}

- george.maggessy September 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

doesn't work for:
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");
dict.add("aaisname");

stringIntoSentence("aaaaisname", dict);
}

- Anonymous November 23, 2014 | Flag
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)
}
}
}
}

- scala code August 12, 2014 | Flag Reply
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;
		
	}

- anshulzunke September 29, 2014 | Flag Reply
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

  }

- flipCoder December 16, 2014 | Flag Reply
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]

- codemuncher February 22, 2016 | Flag Reply
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<>();
        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);
            }
        }
    }

- Richard Luo October 20, 2017 | Flag Reply
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;
}

- Anonymous April 18, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Word break problem but more like coin change during solution.

- Pegasi October 01, 2019 | Flag Reply
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

- mvdizel February 29, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

asd

- Anonymous February 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.


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