Facebook Interview Question for Software Engineer Interns


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
8
of 10 vote

import java.util.HashSet;

public class ConcantentationOfStrings {
	static String[] dic={"world","hello","super","hell"};


	static boolean isConcantentationOfOtherStrings(String word)
	{
		HashSet<String> hs=new HashSet<String>();
		
		for(String s: dic) hs.add(s);
		int len=word.length();

		boolean[] table=new boolean[len+1];	
		table[0]=true;	

		for(int i=0; i < len;i++)
		{
			for(int j=i; j >= 0;j--)
			{
				String subWord=word.substring(j,i+1);
				if(hs.contains(subWord))
				{
					if(table[j]) table[i+1]=true;
				}
			}
		}

		return table[len];
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(isConcantentationOfOtherStrings("hellworld"));

	}

}

- SadBoy October 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good thinking

- shukad333 October 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Great solution, but i believe minor optimization may be made - you want to check only subwords that starts at start of string or after soe concatenation and you don't need to continue after you found first concatenation to this symbol
So

if (table[j] || j == 0) {
					String subWord=word.substring(j,i+1);
					if(hs.contains(subWord))
						 table[i+1]=true;
					break;
				}

instead of

String subWord=word.substring(j,i+1);
				if(hs.contains(subWord))
				{
					if(table[j]) table[i+1]=true;
				}

- Anonymous October 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

substring is actually O(n) in several languages. this is an O(n^3) algorithm

- chanvn November 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

class StringDictionary{
public:
    bool checkConcatenation(unordered_set<string>& dictionary, string str){
        if(str.length() == 0)   return true;
        for(int i = 1; i <= str.length(); i ++){
            string t = str.substr(0,i);
            if(dictionary.find(t)!= dictionary.end()){
                if(checkConcatenation(dictionary, str.substr(i))){
                    return true;
                }
            }
        }
        return false;
    }
};

- wwu October 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You may use suffix tree to improve the efficiency...

- wwu October 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

public static boolean isKeyFromDic(String key, String[] words, int index) {
        if (key.length() > 0 && index == key.length()) return true;

        for (String word : words) {
            if (index + word.length() <= key.length()) {
                String subWord = key.substring(index, index + word.length());
                if (subWord.equals(word)) {
                    return isKeyFromDic(key, words, index + word.length());
                }
            }
        }

        return false;
    }

- drwho October 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

private static boolean isConcatenated(HashSet<String> dict, String input, int offset) {
		if (input.length() == offset) {
			return true; // nothing to process
		}
		for (int i=offset; i<input.length(); i++) {
			String sub = input.substring(offset, i+1);
			if (dict.contains(sub)) {
				boolean isConcatenated = isConcatenated(dict, input, i+1);
				if (isConcatenated) return true;
			}
		}
		return false;
	}

- Aziz November 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

def f(key,words): 
	if len(key) == 0: 
		return True 
	for word in words: 
		if key.beginswith(word) and f(key[len(word):], words): 
			return True 
	return False

- Quack October 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice solution (came up with a very similar one myself).
But it won't work for a corner case:

f('', words) != False

Also the substring comparison function is startswith() (not beginswith())

def check_dict(dictionary, word):
  for w in dictionary:
    if word.startswith(w):
      if len(w) == len(word):
        return True
      else:
        return check_dict(dictionary, word[len(w):])
  return False

- davide.guerri November 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you give the code wws for suffix tree . I need to use the dictionary structure .. should be done in 0(n) of the word...

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

public class Dictionary {
	
	private HashSet<String> dictionary;
	
	
	public static void main(String[] args)
	{
		Dictionary mDictionary = new Dictionary();
		String key = "hellohello2";
		System.out.println("===========================");
		mDictionary.findConcatenations(key);
		System.out.println("===========================");
		mDictionary.findConcatenations("hellhellhellhellhell");//yes
		System.out.println("===========================");
		mDictionary.findConcatenations("superman");//no
		System.out.println("===========================");
		mDictionary.findConcatenations("hellhelloohellohell");//yes
		System.out.println("===========================");
		mDictionary.findConcatenations("hellhelloowhellohell");//no
		
	}
	
	public Dictionary() {
		this.dictionary = new HashSet<String>(Arrays.asList("hello", "helloo", "hell", "super", "world"));
	}
	
	public void findConcatenations(String key){
		
		System.out.println("For Key: " + key);
		boolean[] checkArray = new boolean[key.length()+1];
		
		int startPoint = 0;
		int iterator = 1;
		boolean wordMatched = false;
		
		while(iterator<=key.length())
		{
			String subWord = key.substring(startPoint, iterator);
			if(dictionary.contains(subWord))
				{
					checkArray[iterator] = true;
					wordMatched = true;
				}else if(wordMatched)
				{
					startPoint = --iterator;
					wordMatched = false;
				}
			iterator++;
		}

		
		if(checkArray[key.length()]==true)
			System.out.println("Answer: Perfect!");
		else
			System.out.println("Answer:  :(");
	}

}

- Parikksit October 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The above code has been written with the help of the first answer. It runs at O(n), which is better than the first answer's O(n^2). [if I'm not wrong, lol]

- Parikksit October 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Does it run correctly for this input: dictionary: "hell" "hellooo"; key: "hellooo"

- ninhnnsoc November 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be done in linear time using memoization. Here is a code in python:

class Solver:
	def __init__(self , d):
		self.dict = d
	
	def __check__(self , index):
		if index >= self.size:
			return index==self.size
		if self.lookup[index]!=-1:
			return self.lookup[index]==1
		for word in self.dict:
			if self.txt[index:].startswith(word) and self.__check__(index+len(word)):
				self.lookup[index] = 1
				return True
		self.lookup[index]==0
		return False
				
	
	def is_concatenation(self,s):
		self.size = len(s)
		self.txt  = s
		self.lookup = [-1 for _ in xrange(self.size)]
		return self.__check__(0)

Everytime __check__ is called on an index, it gets computes the valueonly if it was not computed earlier. This means that any computation happens at max once for very index, giving a linear time complexity.

- anantpushkar009 October 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Fully build able solution

#include <iostream>
#include <unordered_set>

using namespace std;

bool is_concat( string str, unordered_set<string> dict );

int main( int argc, char ** argv ){

	string in("Ilovepancakesbaconeggswaffles");
	unordered_set<string> dict({ "waffles", "pancakes", "bacon", "eggs", "love", "I" });

	cout << is_concat( in, dict ) << endl;

	return 0;
}

bool is_concat( string str, unordered_set<string> dict ){

	bool found_match = false;

	for( int i = 0; i < str.length(); ++i ){
		for( const auto & word : dict ){
			if( word[0] == str[i] ){
				if(word == str.substr(i, word.length())){
					cout << "word: " << word << "is in the string" << endl;
					i += word.length() - 1;
					found_match = true;
				}
			}
		}
		if(!found_match){
			return false;
		}
	}

	return true;

}

- Solver October 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

CSCOMS.java
-----------------------------

public class CSCOMS {

    private Set<String> stringSet;

    public CSCOMS(String dictionary[]){
        stringSet = new HashSet<String>();
        for(int i = 0; i < dictionary.length; i++){
            stringSet.add(dictionary[i]);
        }
    }

    public boolean checkIfComposedOfMultipleString(String entry){
        if(entry.length() == 0){
            return true;
        }
        boolean result = false;
        for(int i = 0; i < entry.length(); i++){
            String token = entry.substring(0, i + 1);
            if(stringSet.contains(token)){
                result = checkIfComposedOfMultipleString(entry.substring(i + 1));
            }
            if(result){
                break;
            }
        }
        return result;
    }

}

App.java
-----------------------------

public class App 
{
    public static void main( String[] args ){
        String dictionary[] = {"world", "hello", "super", "hell"};

        CSCOMS cscoms = new CSCOMS(dictionary);

        String values[] = {"helloworld", "superman", "hellohello", "superhell", "hellsuper"};

        System.out.print("Dictionary contents: ");
        for(int i = 0; i < dictionary.length; i++){
            System.out.print(dictionary[i] + " ");
        }
        System.out.println();

        for(int i = 0; i < values.length; i++) {
            System.out.println("\"" + values[i] + "\" --> " + cscoms.checkIfComposedOfMultipleString(values[i]));
        }
    }

}

- AbhishekB October 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

CSCOMS.java
-----------------------------

public class CSCOMS {

    private Set<String> stringSet;

    public CSCOMS(String dictionary[]){
        stringSet = new HashSet<String>();
        for(int i = 0; i < dictionary.length; i++){
            stringSet.add(dictionary[i]);
        }
    }

    public boolean checkIfComposedOfMultipleString(String entry){
        if(entry.length() == 0){
            return true;
        }
        boolean result = false;
        for(int i = 0; i < entry.length(); i++){
            String token = entry.substring(0, i + 1);
            if(stringSet.contains(token)){
                result = checkIfComposedOfMultipleString(entry.substring(i + 1));
            }
            if(result){
                break;
            }
        }
        return result;
    }

}

App.java
-----------------------------

public class App 
{
    public static void main( String[] args ){
        String dictionary[] = {"world", "hello", "super", "hell"};

        CSCOMS cscoms = new CSCOMS(dictionary);

        String values[] = {"helloworld", "superman", "hellohello", "superhell", "hellsuper"};

        System.out.print("Dictionary contents: ");
        for(int i = 0; i < dictionary.length; i++){
            System.out.print(dictionary[i] + " ");
        }
        System.out.println();

        for(int i = 0; i < values.length; i++) {
            System.out.println("\"" + values[i] + "\" --> " + cscoms.checkIfComposedOfMultipleString(values[i]));
        }
    }

}

- AbhishekB October 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

class Main{
	
	public static void main(String[] args){
		Set<String> dictionary = new HashSet<String>();
		
		dictionary.add("back");
		dictionary.add("new");
		dictionary.add("golf");
		dictionary.add("run");
		dictionary.add("o");
		dictionary.add("omaha");
		dictionary.add("nebraska");
		dictionary.add("page");
		
		List<String> testStrings = new ArrayList<String>();
		
		//True cases.
		testStrings.add("newback");
		testStrings.add("nebraska");
		testStrings.add("o");
		testStrings.add("backnewgolfrunoomahanebraskapage");
		testStrings.add("oomahapageo");
		
		//False cases
		testStrings.add("car");
		testStrings.add("zap");
		testStrings.add("oomahe");
		testStrings.add("pages");
		testStrings.add("backnewgolfrunoomahanebraskapages");
		
		for(String testString : testStrings){
			System.out.println(testString + " - " + isComposed(testString, dictionary));
		}
		
	}
	
	private static boolean isComposed(String key, Set<String> dictionary){
		int length = key.length();
		
		LinkedList<SearchNode> searchNodes = new LinkedList<SearchNode>();
		searchNodes.add(new SearchNode(0));
		
		Map<String, LinkedList<String>> shortcutMap = new HashMap<String, LinkedList<String>>();
		for(String word : dictionary){
			String newKey = word.substring(0, 1);
			if(!shortcutMap.containsKey(newKey)){
				shortcutMap.put(newKey, new LinkedList<String>());
			}
			shortcutMap.get(newKey).add(word);
		}
		
		//printShortcutmap(shortcutMap);
		
		while(!searchNodes.isEmpty()){
			int ptrOrig = searchNodes.getFirst().getPtr();
			int ptr = ptrOrig;
			searchNodes.removeFirst();
			
			String ltr = key.substring(ptr, ptr + 1);
			if(!shortcutMap.containsKey(ltr)){
				continue;
			}
			
			LinkedList<String> subDic = shortcutMap.get(ltr);
			for(String wrd : subDic){
				ptr = ptrOrig;
				int wrdLen = wrd.length();
				if(wrdLen == 1){
					if(ptr + 1 == length){
						return true;
					}
					searchNodes.add(new SearchNode(ptr + 1));
					continue;
				}
	
				ptr++;
				boolean match = false;
				if(length - ptr >= wrdLen - 2){
					match = true;
					for(int i = 1; i < wrdLen && ptr < length ; i++){
						if(!key.substring(ptr, ptr + 1).equals(wrd.substring(i, i + 1))){
							match = false;
							break;
						}
						ptr++;
					}
				}
	
				if(match){
					if(ptr == length){
						return true;
					}
					searchNodes.add(new SearchNode(ptr));
				}
			}
		}
		
		return false;
	}

	private static void printShortcutmap(Map<String, LinkedList<String>> map){
		for(Map.Entry<String, LinkedList<String>> entry : map.entrySet()){
			System.out.println(entry.getKey());
			for(String word : entry.getValue()){
				System.out.println("    " + word);
			}
			System.out.println();
		}
	}
	
	private static class SearchNode{
		int ptr;
		
		public SearchNode(int ptr){
			this.ptr = ptr;
		}
		
		public int getPtr(){
			return ptr;
		}
	}

}

- cubed November 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean checkConcatenations(String S){
		
		boolean isStringConcatenationsOfStrings = false;
		HashSet<String> dictionary = new HashSet<String>();
		dictionary.add("world");
		dictionary.add("hello");
		dictionary.add("super");
		dictionary.add("hell");
		
		ArrayList<String> foundMatch = new ArrayList<String>();
		int stringLength = S.length();
		String subString = "";
		
		for ( int index = 0 ; index < stringLength; index++){
			subString += S.charAt(index);
			int lenOfArray = foundMatch.size();
			
			if ( lenOfArray > 0){
				if(dictionary.contains(subString)){
					foundMatch.add(subString);
					subString = "";
				}
				String temp = subString;
				for (int j = lenOfArray-1; j >= 0 && subString != "" ; j--){
					temp = foundMatch.get(j) + temp;
					
					if (dictionary.contains(temp)){
						foundMatch.add(subString);
						subString = "";
					}	
				
				}
			
			}
			else if (dictionary.contains(subString)){
				foundMatch.add(subString);
				subString = "";
			}
		}
		
		String result = "";
		for (int index = 0; index < foundMatch.size(); index++){
			result += foundMatch.get(index);
		}
		
		if (result.equals(S)){
			isStringConcatenationsOfStrings = true;
		}
		
		return isStringConcatenationsOfStrings;		
	}

- chaitutvk25 November 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

dictionary = {'world':'', 'hello':'', 'super':'', "hell":''}

def isValidConcatination(string):
	if len(string) == 0:
		return True
	for i in range(len(string)+1):
		if string[:i] in dictionary:
			if isValidConcatination(string[i:]):
				return True
	return False

O(n^2)

- Python November 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Perfect!

- pythongeek November 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

A DP solution.
Let T(i) denotes if s.substr(i) can be split into words of the dict, then
T(i) = false || T(i + W1) || T(i + W2) || ... , if s.substr(i, Wi) is a valid word.

bool wordBreak(string s, unordered_set<string> &dict) {
    if(s.empty())
        return true;
    if(dict.empty())
        return false;
    size_t maxlen = 0, minlen = -1;
    for(const auto & w : dict){
        maxlen = max(maxlen, w.size());
        minlen = min(minlen, w.size());
    }
    vector<bool> dp(s.size() + 1);
    dp[0] = true;
    for(size_t i = 0;i < s.size();++i){
        for(size_t j = minlen;j <= i + 1 && j <= maxlen;++j){
            if(!dp[i + 1 - j])
                continue;
            if(dict.count(s.substr(i + 1 - j, j)) > 0){
                dp[i + 1] = true;
                break;
            }
        }
    }
    return dp.back();
}

- DoZerg November 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using regex (python)

import re

def check_dict(dictionary, word):
  regex = '^(' + '|'.join(dictionary) + ')+$'
  return re.match(regex, word) != None

- davide.guerri November 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Test
public void testWordsFromDict() {

String[] dict = {"hell", "world", "hello", "super" };
Integer total = 0;

assertFalse(removePrefix("hellworl", dict));
assertTrue(removePrefix("hellworld", dict));
assertTrue(removePrefix("helloworld", dict));
assertFalse(removePrefix("helloworl", dict));
assertTrue(removePrefix("hellohello", dict));
assertTrue(removePrefix("hellohelloworld", dict));

assertFalse(removePrefix("superman", dict));
assertFalse(removePrefix("asuperman", dict));
assertTrue(removePrefix("super", dict));
}

public boolean removePrefix(String key,String[] dict) {

if (key.length() == 0) {
return true;
}

List<String> existingWords = new ArrayList<String>();

for (String word : dict) {
System.out.println("1");
if (key.startsWith(word)) {
existingWords.add(word);
}
}

int total = 0;
for (String word : existingWords) {
System.out.println("2");
if (removePrefix(key.substring(word.length()), dict)) {
total += 1;
}
}

return total > 0;
}

- Sean November 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class WordsFromDictTest {

@Test
public void testWordsFromDict() {

String[] dict = {"hell", "world", "hello", "super"};

assertFalse(removePrefix("hellworl", dict));
assertTrue(removePrefix("hellworld", dict));
assertTrue(removePrefix("helloworld", dict));
assertFalse(removePrefix("helloworl", dict));
assertTrue(removePrefix("hellohello", dict));
assertTrue(removePrefix("hellohelloworld", dict));

assertFalse(removePrefix("man", dict));
assertFalse(removePrefix("superman", dict));
assertFalse(removePrefix("asuperman", dict));
assertTrue(removePrefix("super", dict));
}

public boolean removePrefix(String key,String[] dict) {

List<String> existingWords = new ArrayList<String>();

for (String word : dict) {
if (key.startsWith(word)) {
existingWords.add(word);
}
}

int total = 0;
for (String word : existingWords) {
if (key.substring(word.length()).length() > 0) {
if (removePrefix(key.substring(word.length()), dict)) {
total += 1;
}
}
else {
total += 1;
}
}

return total > 0;
}

}

- Sean November 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class WordsFromDictTest {
	
	@Test
	public void testWordsFromDict() {
		
		String[] dict = {"hell", "world", "hello", "super"};
		
		assertFalse(removePrefix("hellworl", dict));
		assertTrue(removePrefix("hellworld", dict));
		assertTrue(removePrefix("helloworld", dict));
		assertFalse(removePrefix("helloworl", dict));
		assertTrue(removePrefix("hellohello", dict));
		assertTrue(removePrefix("hellohelloworld", dict));
		
		assertFalse(removePrefix("man", dict));
		assertFalse(removePrefix("superman", dict));
		assertFalse(removePrefix("asuperman", dict));
		assertTrue(removePrefix("super", dict));		
	}
	
	public boolean removePrefix(String key,String[] dict) {
		
		List<String> existingWords = new ArrayList<String>();
		
		for (String word : dict) {
			if (key.startsWith(word)) {
				existingWords.add(word);
			}
		}
		
		int total = 0;
		for (String word : existingWords) {
			if (key.substring(word.length()).length() > 0) {
				if (removePrefix(key.substring(word.length()), dict)) {
					total += 1;
				}
			}
			else {
				total += 1;
			}
		}
		
		return total > 0;
	}

}

- Sean November 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Check {
	public boolean checkIt(String[] dict, String str) {
		int length = str.length();
		int newLenth = 0;
		for (int i = 0; i <= dict.length - 1; i++) {
			while (true) {
				if (str.contains(dict[i])) {
					newLenth = newLenth + dict[i].length();
					int value = str.indexOf(dict[i]);
					if (value == 0) {
						if (str.length() == dict[i].length()) {
							str = "";
						} else {
							str = str.substring(dict[i].length(), str.length());
						}

					} else {
						if (value + dict[i].length() >= length) {
							str = str.substring(0, value);
						} else {
							str = str.substring(0, value)
									+ str.substring(value + dict[i].length(),
											str.length());
						}
					}
					if (newLenth == length) {
						return true;
					}
				} else {
					break;
				}
			}
		}
		return false;
	}
}

public class CheckKey {
	public static void main(String[] args) {
		Check check = new Check();
		String[] dict = { "world", "hello", "super", "hell" };
		System.out.println(check.checkIt(dict, "helloworld"));
	}

}

- a.md.kamil November 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def isKeyConcat(key, dictionary):
	temp = ""
	found = False

	for letter in key:
		temp = temp + letter
		if temp in dictionary:
			found = True

			rest = key[len(temp):]
			res = isKeyConcat(rest, dictionary)
			if res:
				return True
			else:
				pass
		else:
			found = False
	
	return found

d = {"world", "hello", "super", "hell"}

print("helloworld: %s" % str(isKeyConcat("helloworld", d)))
print("superman: %s" % str(isKeyConcat("superman", d)))
print("hellohello: %s" % str(isKeyConcat("hellohello", d)))

- Nadeem November 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I see that many people only considered to be only a concatenation of two words but the specifications states that can be composed of an arbitrary number of words in the dictionary.

public static boo l IsComposed(Hashset<string> dictionary, string word)
{
		// Validate input
		ValidateInput(dictionary, word);
		
		// Call recursibly
		return CoreIsComposed(dictionary, word, 0);
}

private static void ValidateInput(Hashset<string> dictionary, string word)
{
				if(dictionary == null)
					throw ArgumentNullException("dictionary");
		if(string.IsNullOrEmpty(word)
			throw ArgumentNull Exception("word");
}

private static bool CoreIsComposed(Hashset<string> dictionary, string word, int start)
{
		if(word.Length == start) return true;
		for(int i = start + 1; i < word.Length; i++)
		{
			if(IsWord(dictionary, word.Subsctring(start, i-start)) &&
				 	CoreIsComposed(dictionary, word, start + 1))
					{
							return true;
					}
		}

		return false;
}

private static bool IsWord(Hashset<string> dictionary, string word)
{
		return dictionary.Contains(word);
}

- Nelson Perez December 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For my solution, I stored the dictionary as a map of lists, where the key is the first letter of the word, and the list contains all the words that start with that letter.
Using the first letter in the input word, I grab the list from my map, and iterate until I find one that matches. If I find it, I recursively call the same function over the remainder of the input string, until there is no remainder left.

#include <iostream>
#include <vector>
#include <map>
#include <string>

using namespace std;

map<char, vector<string> > dict;

bool constructible(string word)
{
	if (word.length() == 0)
		return true;

	vector<string> &list = dict[word[0]];
	for (string &w : list)
	{
		if (word.compare(0, w.length(), w) == 0 
		  && constructible(word.substr(w.length())))
			return true;
	}
	return false;
}

int main()
{
	string dictinput[] = {"world","hello","super","hell"};
	for (string str : dictinput)
	{
		dict[str[0]].push_back(str);
	}
	string input[] = {"helloworld","superman","hellohello"};
	for (string str : input)
	{
		cout << str << " : " << constructible(str) << endl;
	}
}

Output:

helloworld : 1
superman : 0
hellohello : 1

- Nick January 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// construct the substring character by character from start to end, if we find a match, then check the remaining
// if the remaining doesn't match, we backtrack and continue
public static boolean doesExist(IDictionary dictionary, String key) {
    return doesExist(dictionary, key, 0);
}

private static boolean doesExist(IDictionary dictionary, String key, int start) {
    if(dictionary.contains(key)) return true;
    for(int i = start; i < key.length(); i++) {
        String subString = key.subString(start, i);
        if(dictionary.exists(subString)) {
            if(doesExist(dictionary, s, i + 1)) return true;
        }
    }
    return false;
}

- Anonymous January 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Position
{
    int indexTest,no;
    Position(int indexTest,int no)
    {
        this.indexTest=indexTest;
        this.no=no;
    }
}
class RandomWordCombo
{
    static boolean isCombo(String[] dict,String test)
    {
        HashMap<String,ArrayList<String>> dic=new HashMap<String,ArrayList<String>>();
        Stack<Position> pos=new Stack<Position>();
        for(String each:dict)
        {
            if(dic.containsKey(""+each.charAt(0)))
            {
                //System.out.println("=========it is here");
                ArrayList<String> temp=dic.get(""+each.charAt(0));
                temp.add(each);
                dic.put(""+each.charAt(0),temp);
            }
            else
            {
                ArrayList<String> temp=new ArrayList<String>();
                temp.add(each);
                dic.put(""+each.charAt(0),temp);
            }
        }
        Iterator it = dic.entrySet().iterator();
    while (it.hasNext()) {
        Map.Entry pair = (Map.Entry)it.next();
        System.out.println("key: "+pair.getKey());
        for(String str:(ArrayList<String>)pair.getValue())
        {
            System.out.print(str);
        }
    }
        pos.push(new Position(0,0));
        while(!pos.isEmpty())
        {
            Position position=pos.pop();
            System.out.println("position index: "+position.indexTest+" no: "+position.no);
            if(dic.containsKey(""+test.charAt(position.indexTest)))
            {
                ArrayList<String> strings=dic.get(""+test.charAt(position.indexTest)); 
                if(strings.size()>1&&position.no<strings.size()-1)
                     pos.push(new Position(position.indexTest,position.no+1));
                String str=strings.get(position.no);
                if(position.indexTest+str.length()==test.length())
                    return true;
                pos.push(new Position(position.indexTest+str.length(),0));
            }
        }
        return false;
    }
    public static void main(String[] st)
    {
        String[] dic={"world","hello","super","hell"};
        System.out.println("is 'hellworld' a combo: "+isCombo(dic,"superman"));
    }
}

- kandarp2516 March 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the C++ solution running in O(K^3), where K i s the length of the keyword.

#include <set>
#include <string>
#include <iostream>
using namespace std;

#include <set>
#include <string>
#include <iostream>
using namespace std;

bool find_words(set<string>& hashtable, string& target)
{
	int next = INT_MIN;	
	set<string>::iterator iter;
	if (target.length() == 0)
		return true;

	bool *m = new bool[target.length()+1];
	m[0] = true;

	for (int i = 0; i < target.length(); i++)
	{	for (int j = i; j >=0; j--)
	{
		string sub = target.substr(j, i-j+1);
		if (hashtable.find(sub) != hashtable.end())
		{
			if (m[j]) m[i+1] = true;
		}
	}
	}
	return m[target.length()]== true;
}

bool FindInDic(string* words, int N, string input)
{
	set<string> hashtable;
	for (int i =0; i <N; i++)
		hashtable.insert(words[i]);

	return find_words(hashtable, input);
}

- hankm2004 September 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static boolean findTwoConcatString (String [] listOfStrings , String str){

Set<String> set = new HashSet<>();

for (String s : listOfStrings){
set.add(s);
}

for(int i=1 ; i<str.length() ; i++){
String s1 = str.substring(0,i);
String s2 = str.substring(i);
if(set.contains(s1) && set.contains(s2)){
return true;
}
}
return false;
}

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

static boolean findTwoConcatString (String [] listOfStrings , String  str){

        Set<String> set = new HashSet<>();

        for (String s : listOfStrings){
            set.add(s);
        }

        for(int i=1 ; i<str.length() ; i++){
            String s1 = str.substring(0,i);
            String s2 = str.substring(i);
            if(set.contains(s1) && set.contains(s2)){
                return true;
            }
        }
        return false;
    }

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

Python:
def f(key,words):
if len(key) == 0:
return True
for word in words:
if key.beginswith(word) and f(key[len(word):], words):
return True
return False

- quack October 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

static String[] dictionary = {"world", "hello", "super", "hell"};
    
    public static boolean isConcatenation(String key) {
        StringBuilder currentString = new StringBuilder();
        for (int i = 0; i < key.length(); i++) {
            currentString.append(key.charAt(i));

            int dictIndex = 0;
            boolean found = false;
            while (!found && dictIndex < dictionary.length) {

                if (dictionary[dictIndex].equals(currentString.toString())) {
                    found = true;
                }

                dictIndex++;
            }

            if (found) {
                String restOfTheWord = key.substring(i + 1);

                int dictIndex_2 = 0;

                while (dictIndex_2 < dictionary.length) {
                    if (restOfTheWord.equals(dictionary[dictIndex_2])) {

                        return true;
                    }

                    dictIndex_2++;
                }
            }
        }


        return false;
    }

- IgorBrown31 October 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This is a better performing code than the upvoted answer. Linear in time. Not that it matters a lot for smaller strings, but if the string expands, this one will work better.

- Parikksit October 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

def is_arb_concat_substring(lists, key):
        for w in lista:
                if w in key:
                        key = key.replace(w, "")
        if "" == key:
                return True
        else:
                return False

lista = ["world", "hello", "super", "hell"]
print is_arb_concat_substring(lista, "helloworld")
print is_arb_concat_substring(lista, "superman")
print is_arb_concat_substring(lista, "hellohello")

- Anonymous October 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

def is_arb_concat_substring(lists, key):
        for w in lista:
                if w in key:
                        key = key.replace(w, "")
        if "" == key:
                return True
        else:
                return False

lista = ["world", "hello", "super", "hell"]
print is_arb_concat_substring(lista, "helloworld")
print is_arb_concat_substring(lista, "superman")
print is_arb_concat_substring(lista, "hellohello")

- Anonymous October 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Fully build able solution

#include <iostream>
#include <unordered_set>

using namespace std;

bool is_concat( string str, unordered_set<string> dict );

int main( int argc, char ** argv ){

	string in("Ilovepancakesbaconeggswaffles");
	unordered_set<string> dict({ "waffles", "pancakes", "bacon", "eggs", "love", "I" });

	cout << is_concat( in, dict ) << endl;

	return 0;
}

bool is_concat( string str, unordered_set<string> dict ){

	bool found_match = false;

	for( int i = 0; i < str.length(); ++i ){
		for( const auto & word : dict ){
			if( word[0] == str[i] ){
				if(word == str.substr(i, word.length())){
					cout << "word: " << word << "is in the string" << endl;
					i += word.length() - 1;
					found_match = true;
				}
			}
		}
		if(!found_match){
			return false;
		}
	}

	return true;

}

- Anonymous October 31, 2014 | 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