Facebook Interview Question


Country: United States




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

Its not clear from your examples and description what is the real problem. How is the answer to your first example Yes, it should be No since you can't words "ab":2. Something is missing here or I am not following your question/description.

- Mukul July 20, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I solved this problem in varies ways [ we can also use trie to solve this ]

public class BuildStringWordsInDictionary {

    public static void main(String args[]) {
        test1();
        test2();
        test3();
        test4();
        test5();


    }

    //false
    private static void test5() {
        String s = "abcabab";
        HashMap<String, Integer> wordCount = new HashMap<>();
        wordCount.put("abc", 3);
        wordCount.put("ab", 1);


        System.out.println("\nGiven String : " + s + " Expected output :" + false);
        System.out.println("SolutionDFSByStringWords ->" + SolutionDFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords2 -> " + SolutionDFSByStringWords.wordBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionBFSByStringWords -> " + SolutionBFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords -> " + SolutionDFSByMapWords.canBreak(s, new HashMap<>(wordCount)));

    }

    //true
    private static void test4() {
        String s = "abcabab";
        HashMap<String, Integer> wordCount = new HashMap<>();
        wordCount.put("abc", 3);
        wordCount.put("ab", 2);

        System.out.println("\nGiven String : " + s + " Expected output :" + true);
        System.out.println("SolutionDFSByStringWords ->" + SolutionDFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords2 -> " + SolutionDFSByStringWords.wordBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionBFSByStringWords -> " + SolutionBFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords -> " + SolutionDFSByMapWords.canBreak(s, new HashMap<>(wordCount)));
    }

    //false
    private static void test3() {
        String s = "abcx";
        HashMap<String, Integer> wordCount = new HashMap<>();
        wordCount.put("abc", 3);
        wordCount.put("ab", 2);
        wordCount.put("abca", 1);

        System.out.println("\nGiven String : " + s + " Expected output :" + false);
        System.out.println("SolutionDFSByStringWords ->" + SolutionDFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords2 -> " + SolutionDFSByStringWords.wordBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionBFSByStringWords -> " + SolutionBFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords -> " + SolutionDFSByMapWords.canBreak(s, new HashMap<>(wordCount)));
    }

    //true
    private static void test1() {

        String s = "abcabcabcabca";
        HashMap<String, Integer> wordCount = new HashMap<>();
        wordCount.put("abc", 3);
        wordCount.put("ab", 2);
        wordCount.put("abca", 1);

        System.out.println("\nGiven String : " + s + " Expected output :" + true);
        System.out.println("SolutionDFSByStringWords ->" + SolutionDFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords2 -> " + SolutionDFSByStringWords.wordBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionBFSByStringWords -> " + SolutionBFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords -> " + SolutionDFSByMapWords.canBreak(s, new HashMap<>(wordCount)));
    }


    //true
    private static void test2() {

        String s = "abcabcaabbc";
        HashMap<String, Integer> wordCount = new HashMap<>();
        wordCount.put("abc", 3);
        wordCount.put("ab", 1);
        wordCount.put("abca", 1);

        System.out.println("\nGiven String : " + s + " Expected output :" + true);
        System.out.println("SolutionDFSByStringWords ->" + SolutionDFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords2 -> " + SolutionDFSByStringWords.wordBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionBFSByStringWords -> " + SolutionBFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords -> " + SolutionDFSByMapWords.canBreak(s, new HashMap<>(wordCount)));


    }


}


/**
 * NOTE: Not working
 */
class SolutionBFSByStringWords {


    public static boolean canBreak(String str, Map<String, Integer> wordCount) {

        if (str.isEmpty())
            return true;

        return canBreakBFS(str, wordCount);


    }

    private static boolean canBreakBFS(String str, Map<String, Integer> wordCount) {

        int n = str.length();
        final Queue<Integer> queue = new LinkedList<>();

        final Map<String, Integer> visited = new HashMap<>();

        queue.offer(0);

        while (!queue.isEmpty()) {

            int start = queue.poll();

            for (int i = start ; i < str.length(); i++) {

                //Try this word : forward ->
                String temp = str.substring(start, i + 1);

                if (!visited.containsKey(temp))
                    visited.put(temp, 0);

                //Check is this possible ?
                if (wordCount.containsKey(temp) && wordCount.get(temp) > visited.get(temp)) {

                    visited.put(temp, visited.get(temp) + 1);

                    //if possible,the remove this string and recurse for rest of the string;
                    wordCount.put(temp, wordCount.get(temp) - 1);

                    //recurse for rest of the string;
                    queue.offer(i);

                    if (i == str.length())
                        return true;


                }
            }

        }


        return false;
    }
}

/**
 * This solution won't handle the cases when you can remove the word in-between and form a new workd by ends
 * Example:
 * s = "abcabcaabbc";
 * {"abc": 3, "ab": 1, "abca": 1}
 * <p>
 * Your code produce False where it is possible ;
 * abcabcaabbc -> aabbc [remove two "abc"] {"abc": 1, "ab": 1, "abca": 1}
 * aabbc -> abc [remove one "ab" ] {"abc": 1, "ab": 0, "abca": 1} [**** This is not supported ***]
 * abc -> "" [ remove one "abc" ] {"abc": 0, "ab": 1, "abca": 1}
 */
class SolutionDFSByStringWords {


    /**
     * DFS 1:
     * By keeping the index of recursion
     *
     * @param str
     * @param wordCount
     * @return
     */
    public static boolean canBreak(String str, Map<String, Integer> wordCount) {

        if (str.isEmpty())
            return true;

        return canBreakRec(str, wordCount, 0);


    }

    /**
     * Keep taking a sub-string from given string specified by "start" index and keep checking does this is possible break
     * which leads to a solution
     *
     * @param str
     * @param wordCount
     * @param start
     * @return
     */
    private static boolean canBreakRec(String str, Map<String, Integer> wordCount, int start) {

        //If we have remove all the chars, then success
        if (start == str.length())
            return true;

        for (int i = start; i < str.length(); i++) {

            //Try this word : forward ->
            String temp = str.substring(start, i + 1);

            //Check is this possible ?
            if (wordCount.getOrDefault(temp, -1) > 0) {

                //if possible,the remove this string and recurse for rest of the string;
                wordCount.put(temp, wordCount.get(temp) - 1);

                //recurse for rest of the string;
                if (canBreakRec(str, wordCount, i + 1)) {
                    return true;
                }
                //Couldn't find the solution, backtrack
                wordCount.put(temp, wordCount.get(temp) + 1);

            }


        }

        return false;
    }


    /**
     * DFS 2
     * By breaking string into sub-strings
     *
     * @param word
     * @param map
     * @return
     */

    public static boolean wordBreak(String word, Map<String, Integer> map) {
        int len = word.length();
        if (len <= 0) return true;
        for (int i = 1; i < len + 1; i++) {
            String a = word.substring(0, i);
            Integer I = map.get(a);
            if (I == null || I <= 0)
                continue;

            map.put(a, I - 1);

            if (i <= len && wordBreak(word.substring(i, len), map))
                return true;

            map.put(a, I);
        }
        return false;
    }
}


class SolutionDFSByMapWords {


    public static boolean canBreak(String str, Map<String, Integer> wordCount) {

        if (str.isEmpty())
            return true;

        return canBreakRec(str, wordCount);


    }

    /**
     * DFS the tree.
     * check using current count in map of a word, does string can be broken ?
     * if yes, then decrease the number of counts and recurse for further. Try all
     *
     * @param str
     * @param wordCount
     * @return
     */
    private static boolean canBreakRec(String str, Map<String, Integer> wordCount) {
        if (str.isEmpty())
            return true;

        /**
         * find all the keys present in str and remove them as many times as said
         */
        for (String key : wordCount.keySet()) {


            int count = wordCount.get(key);

            //Can we still use this word from dict?
            if (count > 0) {

                int oldCount = count;

                String oldString = str;

                //Find and remove the occurrence
                while (str.contains(key) && count > 0) {
                    str = str.replaceFirst(key, "");
                    count--;
                }

                //if we tried to remove but no occurrence found for given key in string, then continue to next word in map
                if (count == wordCount.get(key))
                    continue;
                else {

                    //decrease the count of occurrence
                    wordCount.put(key, count);

                    //Recurse
                    if (canBreakRec(str, wordCount)) {
                        return true;
                    }

                    //Put back: Backtrack
                    str = oldString;
                    wordCount.put(key, oldCount);

                }


            }

        }
        return false;
    }

}

- nitinguptaiit July 18, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

test and show how is this working

- Anonymous July 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

asdf

- Anonymous July 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Your second example is incorrect (abcabab : ['abc', 'ab', 'ab']). You did
not mention that not all words/occurencies need to be exhausted.

def SplitSubstring(s, n, word_fr, curr_split):
    if n == len(s):
        print("%s : %s" % (s, curr_split))
        return
    for i in range(n, len(s)):
        ss = s[n:i+1] 
        if ss in word_fr and word_fr[ss] > 0:
            word_fr[ss] -= 1
            curr_split.append(ss)
            SplitSubstring(s, i + 1, word_fr, curr_split)
            curr_split.pop()
            word_fr[ss] += 1
    
word_fr = {"abc":3, "ab":2, "abca":1}
SplitSubstring("abcabcabcabca", 0, word_fr, [])
SplitSubstring("abcx", 0, word_fr, [])

word_fr =  {"abc":3, "ab":2}
SplitSubstring("abcabab", 0, word_fr, [])

- hb July 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

public class BreakWord{
    static boolean ans = false;
    public static void main(String[] args){
        Map<String, Integer> map = new HashMap<>();
        //map.put("abc", 3);
        //map.put("ab", 2);
        //map.put("abca", 1);
        map.put("abc", 3);
        map.put("ab", 2);
        String str = "abcabcabcabca";
        //String str = "abcabab";

        Set<String> set = new HashSet<>();
        for(String s : map.keySet()){
            set.add(s);
        }

        dfs(map, set, str, 0);
        System.out.println(ans);
    }

    public static void  dfs(Map<String, Integer> map, Set<String> set, String str, int start){
        if(start == str.length()){
            ans = true;
            return;
        }
        for(int i=start; i<str.length(); i++){
            String ss = str.substring(start, i+1);
            if(!set.contains(ss))
                continue;
            if(map.get(ss) == 0){
                continue;
            }
            map.put(ss, map.get(ss)-1);
            dfs(map, set, str, i+1);
            map.put(ss, map.get(ss)+1);
        }
    }
}

- xzhan211@binghamton.edu July 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This (the above java code) fails for the case "abcabab". the code is really simple, and I like it, but it doesn't catch this case. although I admit the question is poorly worded.

- Eric H Frazer October 09, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

DP solution similar to Word break maintaining Map with count

/*
 * Break string into the word provided by given hashmap
 * Ex:1
 *      HashMap: {"abc":3, "ab":2, "abca":1}
 *      Word: abcabcabca
 * Output: true
 * */

#include <bits/stdc++.h>
using namespace std;
string s;
map<string, int> HashMap;

int DP[11111];
bool solve(int id)
{
    if(id >= s.size()) {
        return true;
    }

    if(DP[id] != -1) {
        return DP[id];
    }

    int ans = false;
    for(int i = 1; i <= s.size() - id; i++) {
        string temp = s.substr(id, i);
        // If found
        if(HashMap.find(temp) != HashMap.end()) {
            if(HashMap[temp] != 0) {
                HashMap[temp]--;
                ans = ans | solve(id + i);
                HashMap[temp]++;
            }
        }
        if(ans == true) {
            DP[id] = ans;
            return DP[id];
        }
    }
    return DP[id] = ans;
}

int main()
{
    cin >> s;
    memset(DP, -1, sizeof DP);
    // Create HashMap of size N
    int N;
    cin >> N;
    for(int i = 0; i < N; i++) {
        string t;
        int cnt;
        cin >> t >> cnt;
        HashMap[t] = cnt;
    }
    cout << solve(0);
}

- shaktirajpandey1996 August 29, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Not sure if this is optimal, but here is a DP solution that requires what is likely a significant amount of space.

DP Solution:

T[i,j,k,l] = True if there is a partition of S[i..j] using the i^th substring at most k times.

If T[i,j,k,l] is true, then some substring must be a prefix of S[i..j], so just check all possible prefixes.

Fill in table in increasing order of abs(i-j), and increasing order of k and l.

- Matt September 11, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive solution:

#include <iostream>
using namespace std;

struct dict
{
  string w;
  int c;
};

// To execute C++, please define "int main()"
bool findwords(string str,dict d[],string& words)
{
  if (str.length()==0)
    return true;
  else
    for (int wo=0;wo<3;wo++)
    {
      int d_length=d[wo].w.length();
      //cout<<str.substr(0,d_length)<<endl;
      
      if (str.substr(0,d_length) == d[wo].w )
      {
        
        //d[wo].c--;
        if (findwords(str.substr(d_length,str.length()),d,words))
        {
         // cout<<d[wo].w<<" ";
          
          d[wo].c--;
          if (d[wo].c>=0)
          {
            words=d[wo].w+" "+words;
            return true;
          }
        }
        //d[wo].c++;
      }
    }
  return false;
}

int main() {
  
  dict d[3];
  
  d[0].w="abc";
  d[1].w="ab";
  d[2].w="abca";
  
  d[0].c=2;
  d[1].c=2;
  d[2].c=1;
  string words;
  
  if (findwords("abcaababcab",d,words))
    cout<<"True"<< " "<<words<<endl;
  else
    cout << "No Words Found"<<endl;
  
  
 
  //cout<<words<<endl;
  
  
  
  
  return 0;
}

- Sohaib September 25, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive Solution

#include <iostream>
using namespace std;

struct dict
{
  string w;
  int c;
};

// To execute C++, please define "int main()"
bool findwords(string str,dict d[],string& words)
{
  if (str.length()==0)
    return true;
  else
    for (int wo=0;wo<3;wo++)
    {
      int d_length=d[wo].w.length();
      //cout<<str.substr(0,d_length)<<endl;
      
      if (str.substr(0,d_length) == d[wo].w )
      {
        
        //d[wo].c--;
        if (findwords(str.substr(d_length,str.length()),d,words))
        {
         // cout<<d[wo].w<<" ";
          
          d[wo].c--;
          if (d[wo].c>=0)
          {
            words=d[wo].w+" "+words;
            return true;
          }
        }
        //d[wo].c++;
      }
    }
  return false;
}

int main() {
  
  dict d[3];
  
  d[0].w="abc";
  d[1].w="ab";
  d[2].w="abca";
  
  d[0].c=2;
  d[1].c=2;
  d[2].c=1;
  string words;
  
  if (findwords("abcaababcab",d,words))
    cout<<"True"<< " "<<words<<endl;
  else
    cout << "No Words Found"<<endl;
  
  
 
  //cout<<words<<endl;
  
  
  
  
  return 0;
}

- Sohaib Kiani September 25, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You could flatten out the hash map and then generate the power set. Then map each element in the power set to an array of permutations of the original array that are then joined together as strings.

Then collect all of these generated strings, this is your solution space. Check if the input exists in the space.

- Anonymous October 06, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

here's my VS 2019 C# entry

static List<string> l = new List<string>( );
        static Dictionary<string,int> dict = new Dictionary<string, int>( );

        static void FindString( string szFind, int szFindLen, List<string> szRemainingWords, ref bool bFound, ref string szOut )
        {
            if( szFind == "" )
            {
                bFound = true;
                return;
            }

            string szOutOriginal = szOut;

            for( int i = 0 ; i < szRemainingWords.Count ; i++ )
            {
                string s = szRemainingWords[i];
                if ( szFind.StartsWith( s ) )
                {
                    szOut += s + " ";
                    int len = s.Length;

                    szRemainingWords [i] = "*" + szRemainingWords [i];
                    FindString( szFind.Substring( len ), szFindLen - len, szRemainingWords, ref bFound, ref szOut );
                    szRemainingWords [i] = szRemainingWords [i].Substring( 1 );

                    if ( bFound )
                    {
                        break;
                    }
                }
            }

            if( !bFound )
            {
                szOut = szOutOriginal;
            }
        }

        static bool DoesWordAppearNTimes( string szWholeString, string szFindWord, int n )
        {
            int offset = 0;
            while ( n > 0 )
            {
                int i = szWholeString.Substring( offset ).IndexOf( szFindWord );
                if ( i == -1 )
                {
                    return false;
                }
                offset = i;
                n--;
            }
            return true;
        }

        static void Main( string [] args )
        {
            l.Add( "abc" );
            l.Add( "abc" );
            l.Add( "abc" );
            l.Add( "ab" );
            l.Add( "ab" );
            l.Add( "abca" );
            dict.Add( "abc", 3 );
            dict.Add( "ab", 2 );
            dict.Add( "abca", 1 );

            bool bFound = false;
            string szOut = "";
            string szFind = "abcabab";

            FindString( szFind, szFind.Length, l, ref bFound, ref szOut);
            if ( bFound )
            {
                foreach ( KeyValuePair<string, int> kvp in dict )
                {
                    if( !DoesWordAppearNTimes( szFind, kvp.Key, kvp.Value ) )
                    {
                        bFound = false;
                        break;
                    }
                }
            }
            Console.WriteLine( "Find = " + szFind + ", found = " + bFound.ToString( ) + ", string = " + szOut );

        }

- Eric H Frazer October 09, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool break1(string& s, std::unordered_map<string, int>& countMap) {
    int size = s.size();
    std::unordered_map<int, vector<vector<string>>> table;
    
    for (int i = 0; i < size; ++i) {
        
        vector<vector<string>> entry;
        
        for (int j = 0; j <= i; ++j) {
            
            //"abcabcabcabababca"
            
            string str1 = s.substr(0, j);
            
            string str2 = s.substr(j, i - j + 1);
            
            if (j == 0) {
            
                if (countMap.find(str2) != countMap.end()) {
                    vector<string> vec1;
                    vec1.push_back(str2);
                    entry.push_back(vec1);
                }
                
            }
            else {
                if (table[j-1].size() > 0 && countMap.find(str2) != countMap.end()) {
                    for (auto iter = table[j-1].begin(); iter != table[j-1].end(); ++iter) {
                        auto vec = *iter;
                        vec.push_back(str2);
                        entry.push_back(vec);
                    }
                    
                }
            }
//            else {
//                if (countMap.find(str2) != countMap.end()) {
//                    vector<string> vec;
//                    vec.push_back(str2);
//                    entry.push_back(vec);
//                }
//            }
        }// for (int j = 0; j <= i; ++j)
        
        table[i] = entry;
    }// for (int i = 0; i < size; ++i)
    
    for (auto iter = table.begin(); iter != table.end(); ++iter) {
        int i = iter->first;
        vector<vector<string>> entry = iter->second;
        if (entry.size() > 0) {
            std::cout << "index is " << i << "\n";
        }
        
        for (auto iter1 = entry.begin(); iter1 != entry.end(); ++iter1) {
            for (auto iter2 = (*iter1).begin(); iter2 != (*iter1).end(); ++iter2) {
                std::cout << *iter2 << "\t";
            }
            
            std::cout << "\n";
        }
        
        std::cout << "\n";
    }
    
    
    vector<vector<string>> solutions = table[size - 1];
    
    while (solutions.size() > 0) {
        auto copyCountMap = countMap;
        vector<string> vec = solutions.back();
        solutions.pop_back();
        
        for (auto iter = vec.begin(); iter != vec.end(); ++iter) {
            copyCountMap[*iter]--;
            if (copyCountMap[*iter] == 0) copyCountMap.erase(*iter);
        }
        
        if (copyCountMap.size() == 0) return true;
        
    }
    
    return false;
}

- Prashant October 11, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

const myFunc = (str, strMap) => {


	let origStr = str;
	let outputArray = [];
  let mapArray = [];
  
  // create subArrays of hashmaps
  
  for (let key in strMap) {
  	let count = strMap[key];
    let tokenArray = [...Array(count)].map((_, i) => key);
    mapArray.push(tokenArray);
  }
  
  // order arrays by subArray length
  
	const sortedArrays = mapArray.sort((a, b) => {
  	return b.length - a.length;
  });
	
  // check for matches
  
  for(let hashArray of sortedArrays) {
  	let pattern = hashArray.join('');
    if (str.includes(pattern)) {
      outputArray = outputArray.concat(hashArray);
      str = str.replace(pattern, '');
    }
  }
  
  // format output
  
  if (str.length ===0 && outputArray.length > 0) {
    return `
HashMap -> ${JSON.stringify(strMap)}
String: ${origStr}
output: Yes;[${outputArray}]`;
  } else {
    return `
HashMap -> ${JSON.stringify(strMap)}
String: ${origStr}
output: No`;
  }
}

let string = 'abcabcabcabca'
let stringMap = {
  'abc': 3,
  'ab': 2,
  'abca': 1
}

console.log(myFunc('abcabcabcabca', {'abc':3, 'ab':2, 'abca':1}));
console.log(myFunc('abcabab', {'abc':3, 'ab':2}));
console.log(myFunc('abcx', {'abc':3, 'ab':2, 'abca':1}));

- Anonymous October 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

const myFunc = (str, strMap) => {


	let origStr = str;
	let outputArray = [];
  let mapArray = [];
  
  // create subArrays of hashmaps
  
  for (let key in strMap) {
  	let count = strMap[key];
    let tokenArray = [...Array(count)].map((_, i) => key);
    mapArray.push(tokenArray);
  }
  
  // order arrays by subArray length
  
	const sortedArrays = mapArray.sort((a, b) => {
  	return b.length - a.length;
  });
	
  // check for matches
  
  for(let hashArray of sortedArrays) {
  	let pattern = hashArray.join('');
    if (str.includes(pattern)) {
      outputArray = outputArray.concat(hashArray);
      str = str.replace(pattern, '');
    }
  }
  
  // format output
  
  if (str.length ===0 && outputArray.length > 0) {
    return `
HashMap -> ${JSON.stringify(strMap)}
String: ${origStr}
output: Yes;[${outputArray}]`;
  } else {
    return `
HashMap -> ${JSON.stringify(strMap)}
String: ${origStr}
output: No`;
  }
}

let string = 'abcabcabcabca'
let stringMap = {
  'abc': 3,
  'ab': 2,
  'abca': 1
}

console.log(myFunc('abcabcabcabca', {'abc':3, 'ab':2, 'abca':1}));
console.log(myFunc('abcabab', {'abc':3, 'ab':2}));
console.log(myFunc('abcx', {'abc':3, 'ab':2, 'abca':1}));

- pdiesel October 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

how about javascript?

- pdiesel October 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

const myFunc = (str, strMap) => {


	let origStr = str;
	let outputArray = [];
  let mapArray = [];
  
  // create subArrays of hashmaps
  
  for (let key in strMap) {
  	let count = strMap[key];
    let tokenArray = [...Array(count)].map((_, i) => key);
    mapArray.push(tokenArray);
  }
  
  // order arrays by subArray length
  
	const sortedArrays = mapArray.sort((a, b) => {
  	return b.length - a.length;
  });
	
  // check for matches
  
  for(let hashArray of sortedArrays) {
  	let pattern = hashArray.join('');
    if (str.includes(pattern)) {
      outputArray = outputArray.concat(hashArray);
      str = str.replace(pattern, '');
    }
  }
  
  // format output
  
  if (str.length ===0 && outputArray.length > 0) {
    return `
HashMap -> ${JSON.stringify(strMap)}
String: ${origStr}
output: Yes;[${outputArray}]`;
  } else {
    return `
HashMap -> ${JSON.stringify(strMap)}
String: ${origStr}
output: No`;
  }
}

let string = 'abcabcabcabca'
let stringMap = {
  'abc': 3,
  'ab': 2,
  'abca': 1
}

console.log(myFunc('abcabcabcabca', {'abc':3, 'ab':2, 'abca':1}));
console.log(myFunc('abcabab', {'abc':3, 'ab':2}));
console.log(myFunc('abcx', {'abc':3, 'ab':2, 'abca':1}));

- Anonymous October 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

test

- rwar October 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my solution

It has a complexity of O(H * CK) where H is the number of the items in the given hash key and CK is the maximum number of words frequency across all the hashes

let inputString = 'abcabcabcabca';
var validationHash = { "abc": 3, "ab": 2, "abca": 1 };

const breakTheStringIntoWords = (inputString, validationHash) => {
    var replacer = '';
    var words = [], tempWords = [], ii;

    Object.keys(validationHash).map(compareKey => {
        replacer = '';
        tempWords = [];

        for (ii = 0; ii < validationHash[compareKey]; ii++) {
            tempWords.push(compareKey);
            replacer += compareKey;
        }

        if (inputString.indexOf(replacer) > -1) {
            inputString = inputString.replace(replacer, '');
            words = words.concat(tempWords);
            tempWords = [];
        }
    });

    if (inputString.trim() === '') {
        return words;
    } else {
        return [];
    }
};

const returnedWord = breakTheStringIntoWords(inputString, validationHash);

if(returnedWord.length > 0){
    console.log('Yes;', returnedWord);
} else {
    console.log('No');
}

- Mohannad.ElQadi October 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

// Given { "abc": 3, "ab": 2, "abca": 1 }
// abcabcabcabca => [abc, abc, abc, abca]
// abcabab => [abc, ab, ab]
// abcx => []


function findLongestPrefix(str, index, dict, maxPrefixLen) {
  
  var dictCopy = Object.assign({}, dict);
  
  if (index >= str.length)
    return [];
  
  for (var i = maxPrefixLen; i > 0; i--) {
    var candidate = str.substr(index, i);
    
    if (dictCopy[candidate]) {
      dictCopy[candidate]--;
      
      try {
        var rest = findLongestPrefix(str, index + candidate.length, dictCopy, maxPrefixLen);
        return [candidate].concat(rest);
      } catch(err) {
        dictCopy[candidate]++;
      }
    }
  }

  throw error('E_INVALID_CHARS')
  
}

function breakWords(str, dict) {
  // Get the max lengths of keys
  var keys = Object.keys(dict);
  var maxPrefixLen = 1;
  for (var i = 0; i < keys.length; i++ ) {
    if (keys[i].length > maxPrefixLen) {
      maxPrefixLen = keys[i].length;
    }
  }
  
  try {
    return findLongestPrefix(str, 0, dict, maxPrefixLen)
  } catch(error) {
    return []
  }
}

var words = breakWords("abcabcabcabca", { "abc": 3, "ab": 2, "abca": 1 })
console.log(words)


words = breakWords("abcabab", { "abc": 3, "ab": 2 })
console.log( words)

words = breakWords("abcx", { "abc": 3, "ab": 2, "abca": 1 })
console.log( words)

words = breakWords("abca", { "abc": 3, "ab": 2, "abca": 1 })
console.log(words)

- Anonymous August 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

// Given { "abc": 3, "ab": 2, "abca": 1 }
// abcabcabcabca => [abc, abc, abc, abca]
// abcabab => [abc, ab, ab]
// abcx => []


function findLongestPrefix(str, index, dict, maxPrefixLen) {
  
  var dictCopy = Object.assign({}, dict);
  
  if (index >= str.length)
    return [];
  
  for (var i = maxPrefixLen; i > 0; i--) {
    var candidate = str.substr(index, i);
    
    if (dictCopy[candidate]) {
      dictCopy[candidate]--;
      
      try {
        var rest = findLongestPrefix(str, index + candidate.length, dictCopy, maxPrefixLen);
        return [candidate].concat(rest);
      } catch(err) {
        dictCopy[candidate]++;
      }
    }
  }

  throw error('E_INVALID_CHARS')
  
}

function breakWords(str, dict) {
  // Get the max lengths of keys
  var keys = Object.keys(dict);
  var maxPrefixLen = 1;
  for (var i = 0; i < keys.length; i++ ) {
    if (keys[i].length > maxPrefixLen) {
      maxPrefixLen = keys[i].length;
    }
  }
  
  try {
    return findLongestPrefix(str, 0, dict, maxPrefixLen)
  } catch(error) {
    return []
  }
}

var words = breakWords("abcabcabcabca", { "abc": 3, "ab": 2, "abca": 1 })
console.log(words)


words = breakWords("abcabab", { "abc": 3, "ab": 2 })
console.log( words)

words = breakWords("abcx", { "abc": 3, "ab": 2, "abca": 1 })
console.log( words)

words = breakWords("abca", { "abc": 3, "ab": 2, "abca": 1 })
console.log(words)

- my thought August 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

// Given { "abc": 3, "ab": 2, "abca": 1 }
// abcabcabcabca => [abc, abc, abc, abca]
// abcabab => [abc, ab, ab]
// abcx => []


function findLongestPrefix(str, index, dict, maxPrefixLen) {
  
  var dictCopy = Object.assign({}, dict);
  
  if (index >= str.length)
    return [];
  
  for (var i = maxPrefixLen; i > 0; i--) {
    var candidate = str.substr(index, i);
    
    if (dictCopy[candidate]) {
      dictCopy[candidate]--;
      
      try {
        var rest = findLongestPrefix(str, index + candidate.length, dictCopy, maxPrefixLen);
        return [candidate].concat(rest);
      } catch(err) {
        dictCopy[candidate]++;
      }
    }
  }

  throw error('E_INVALID_CHARS')
  
}

function breakWords(str, dict) {
  // Get the max lengths of keys
  var keys = Object.keys(dict);
  var maxPrefixLen = 1;
  for (var i = 0; i < keys.length; i++ ) {
    if (keys[i].length > maxPrefixLen) {
      maxPrefixLen = keys[i].length;
    }
  }
  
  try {
    return findLongestPrefix(str, 0, dict, maxPrefixLen)
  } catch(error) {
    return []
  }
}

var words = breakWords("abcabcabcabca", { "abc": 3, "ab": 2, "abca": 1 })
console.log(words)


words = breakWords("abcabab", { "abc": 3, "ab": 2 })
console.log( words)

words = breakWords("abcx", { "abc": 3, "ab": 2, "abca": 1 })
console.log( words)

words = breakWords("abca", { "abc": 3, "ab": 2, "abca": 1 })
console.log(words)

- sheng August 21, 2019 | Flag Reply


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