Microsoft Interview Question for SDE1s


Country: India




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

"Simplicity is always the key, but making things simple needs practice."

Just use a boolean array to keep track of what is used.

public boolean isPerm(String word, String[] dict){
    
        boolean[] used = new boolean[dict.length];
        
        for(int i = 0; i < dict.length; i++){
    
            if(word.length() > 0){
                if(!used[i]){
                    int idx = word.indexOf(dict[i]);
                    if(idx >= 0){
                        String temp = word.substring(0,idx);
                        temp += word.substring(idx+dict[i].length());
                        word = new String(temp);
                        
                        used[i] = true;
                    }
                }    
            } else {
                break;
            }
        }
        
        if(word.length() > 0) return false;
        
        return true;
    }

- samudra.agni December 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

O(n^2) algorithm.
Assumed that each word can be used no more than once (by the definition of the permutation).

bool strPermuteFrom(unordered_set<string> &dict, string &str, int pos)
{
  if(pos >= str.size())
    return true;

  if(dict.size() == 0)
    return false;

  for(int j = pos; j < str.size(); j++){
    string w = str.substr(pos, j - pos + 1);
    if(dict.find(w) != dict.end()){
      dict.erase(w);
      int status = strPermuteFrom(dict, str, j+1);
      dict.insert(w);
      if(status){
        if(pos > 0) str.insert(pos, " ");
        return status;
      }
    }
  }

  return false;
}


bool strPermute(unordered_set<string> &dict, string &str)
{
  return strPermuteFrom(dict, str, 0);
}

result:

dictionary = { acting, good, bad, actor, }
     badactorgoodact : notconstructible
  badactorgoodacting : constructible (bad actor good acting)
   badactorbadacting : notconstructible

- linuxchain October 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void swap(final String[] strings, final int pos1, final int pos2) {
		String temp = strings[pos1];
		strings[pos1] = strings[pos2];
		strings[pos2] = temp;
	}

	static void permString(String[] strings, int k, int n) {

		if (k == n) {
			StringBuffer buffer = new StringBuffer();
			for (String string : strings) {
				buffer.append(string);
			}
			set.add(buffer.toString());
			System.out.println(buffer.toString());

		} else {
			for (int i = k; i < n; i++) {
				swap(strings, i, k);
				permString(strings, k + 1, n);
				swap(strings, i, k);
			}
		}

	}
	
	public static Boolean isPermutate(String [] strings,String str){
		permString(strings, 0, strings.length);
		return set.contains(str);
	}

	public static void main(String[] args){
		String[] arr = {"bad", "actor", "good", "acting"};
		System.out.println(isPermutate(arr, "badactorgoodacting"));
	}

- Prajwal September 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I'm assuming if a character from a word is used than the entire words should be used.

Then:
1. Create an array of n hashtables that carry their initial value as well where n = length of dict;
2. Push each character from each word onto their hash table
3. Check if the long string can be created without any hash table bucket being negative.
4. Check that if current value < initial value, that each bucket is empty.
O(n) where n = sum of all of the characters in the words of dict[]

- evhiness September 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

d1 = {"bad", "actor", "good", "act"};
d2 = {"bad", "actor", "good", "acting"};

def isPerm(s, wordlist): 
	i = len(s)
	for j in xrange(i, -1, -1):
		if s[j:i+1] in wordlist:
			i = j - 1
	return True if i < 0 else False
	
print isPerm("badactorgoodacting", d1);
print isPerm("actingactor", d2);
print isPerm("badgoodactingactor", d2);
print isPerm("actactor", d2);
print isPerm("actactor", d1);

O(N^2): the for loop runs for N times, and the str[j:i+1] inside every run is O(N)

- anonymouse September 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

d1 = {"bad", "actor", "good", "act"};
d2 = {"bad", "actor", "good", "acting"};

def isPerm(s, wordlist): 
	i = len(s)
	for j in xrange(i, -1, -1):
		if s[j:i+1] in wordlist:
			i = j - 1
	return True if i < 0 else False
	
print isPerm("badactorgoodacting", d1);
print isPerm("actingactor", d2);
print isPerm("badgoodactingactor", d2);
print isPerm("actactor", d2);
print isPerm("actactor", d1);

# O(N^2) because of the str[i:j+1] construction every time

- Anonymous September 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package StringArray;

/**
 * Created by brajesh.k on 21/09/16.
 */
public class DictPermutation {
    public static boolean isPermutation(String left, String[] dict) {
        if (left == null || left.length() == 0) {
            return true;
        }
        for (String word : dict) {
            if (left.startsWith(word)) {
                return isPermutation(left.substring(word.length()), dict);
            }
        }
        return false;
    }

    public static void main(String[] args) {
        String[] dict = {"actor", "bad", "acting", "good"};
        System.out.println(isPermutation("badactorgoodacting", dict));
    }
}

- Brajesh Kumar September 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
 * Created by brajesh.k on 21/09/16.
 */
public class DictPermutation {
    public static boolean isPermutation(String left, String[] dict) {
        if (left == null || left.length() == 0) {
            return true;
        }
        for (String word : dict) {
            if (left.startsWith(word)) {
                return isPermutation(left.substring(word.length()), dict);
            }
        }
        return false;
    }

    public static void main(String[] args) {
        String[] dict = {"actor", "bad", "acting", "good"};
        System.out.println(isPermutation("badactorgoodacting", dict));
    }
}

- Brajesh Kumar September 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package StringArray;

/**
* Created by brajesh.k on 21/09/16.
*/
public class DictPermutation {
public static boolean isPermutation(String left, String[] dict) {
if (left == null || left.length() == 0) {
return true;
}
for (String word : dict) {
if (left.startsWith(word)) {
return isPermutation(left.substring(word.length()), dict);
}
}
return false;
}

public static void main(String[] args) {
String[] dict = {"actor", "bad", "acting", "good"};
System.out.println(isPermutation("badactorgoodacting", dict));
}
}

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

package StringArray;

/**
 * Created by brajesh.k on 21/09/16.
 */
public class DictPermutation {
    public static boolean isPermutation(String left, String[] dict) {
        if (left == null || left.length() == 0) {
            return true;
        }
        for (String word : dict) {
            if (left.startsWith(word)) {
                return isPermutation(left.substring(word.length()), dict);
            }
        }
        return false;
    }

    public static void main(String[] args) {
        String[] dict = {"actor", "bad", "acting", "good"};
        System.out.println(isPermutation("badactorgoodacting", dict));
    }

}

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

A solution based on Trie data structure is implemented in C++ and Python.
C++: cpluspluslearning-petert.blogspot.co.uk/2016/09/data-structure-and-algorithm-detect.html
Python: pythonlearning-petert.blogspot.co.uk/2016/09/data-structure-and-algorithm-detect.html

- peter tang September 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class CheckPermutation
    {
        static string[] array = {"actor", "bad", "acting", "good","man"};
        private static string value = "actorbadactinggood";

        public static void Main()
        {
            Console.WriteLine("Executing..");
            bool x = IsPermutationOfTheString(value, array, 0);
            Console.WriteLine(x);
            Console.ReadLine();
        }

        public static bool IsPermutationOfTheString(string text, string[] arr, int i)
        {
            if (text.Length == 0)
            {
                return true;
            }

            if (i == arr.Length && text.Length != 0)
            {
                return false;
            }
            string newText = "";
            if (text.Contains(arr[i]))
            {
                int k = text.IndexOf(arr[i], StringComparison.CurrentCulture);
                newText = text.Remove(k, arr[i].Length);
                return IsPermutationOfTheString(newText, arr, i + 1);
            }
            return IsPermutationOfTheString(text, arr, i + 1);
        }

}

- Manjula Atapattu October 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python code with depth first traversal

def check(string_ans, list_of_word, check_word = ""):
	if check_word == string_ans:
			return True
	for key, val in enumerate(list_of_word):
			# print check_word + val
			b = check(string_ans, list_of_word[0:key] + list_of_word[key+1:], check_word + val)
			if b == True:
				return True
	return False

- Roshan Thapaliya October 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Depth first search solution with python

def check(string_ans, list_of_word, check_word = ""):
	if check_word == string_ans:
			return True
	for key, val in enumerate(list_of_word):
			# print check_word + val
			b = check(string_ans, list_of_word[0:key] + list_of_word[key+1:], check_word + val)
			if b == True:
				return True
	return False

- Roshan Thapaliya October 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Depth first search solution with python

def check(string_ans, list_of_word, check_word = ""):
	if check_word == string_ans:
			return True
	for key, val in enumerate(list_of_word):
			# print check_word + val
			b = check(string_ans, list_of_word[0:key] + list_of_word[key+1:], check_word + val)
			if b == True:
				return True
	return False

- Roshan Thapaliya October 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def check(string_ans, list_of_word, check_word = ""):
	if check_word == string_ans:
			return True
	for key, val in enumerate(list_of_word):
			# print check_word + val
			b = check(string_ans, list_of_word[0:key] + list_of_word[key+1:], check_word + val)
			if b == True:
				return True
	return False

- Roshan Thapaliya October 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def check(string_ans, list_of_word, check_word = ""):
	if check_word == string_ans:
			return True
	for key, val in enumerate(list_of_word):
			# print check_word + val
			b = check(string_ans, list_of_word[0:key] + list_of_word[key+1:], check_word + val)
			if b == True:
				return True
	return False

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

def check(string_ans, list_of_word, check_word = ""):
	if check_word == string_ans:
			return True
	for key, val in enumerate(list_of_word):
			# print check_word + val
			b = check(string_ans, list_of_word[0:key] + list_of_word[key+1:], check_word + val)
			if b == True:
				return True
	return False

- Roshan Thapaliya October 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The best possible solution would be one that traverses the big string only once. This requires list of words to be indexed in a structure that can be transversed linearly, in parallel with the big string, in one pass, achieving a final complexity of O(n).

Trie data structure can be used to solve the problem.
1. First build the trie using the list of words.
2. Now go through the bigger string one by one word and see if it matches with the trie nodes
3.If any point no match is found, return false.
4. If we reach the end of string return true.

- arindamc October 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void permutation(String word, ArrayList<String> prefix, ArrayList<String> dict)
	{
		int n = dict.size();
		if(n == 0 && prefix.size() > 0)
		{
			String word_ = "";
			for(int i = 0; i < prefix.size(); i++)
			{
				word_ = word_.concat(prefix.get(i));
			}
			if(word.equals(word_))
				System.out.println("true");
		}
		else
		{
			ArrayList<String> prefix_;
			ArrayList<String> str = Code.clone(dict);
			ArrayList<String> str_;
			for(int i = 0; i < n; i++)
			{
				str_ = new ArrayList<String>();
				str_.addAll(str.subList(0,i));
				str_.addAll(str.subList(i+1,n));
				prefix_ = Code.clone(prefix);
				prefix_.add(dict.get(i));
				permutation(word, prefix_, str_);
			}
		}
	}
	private static ArrayList<String> clone(ArrayList<String> words)
	{
		ArrayList<String> clone = new ArrayList<String>();
		for(int i=0; i< words.size(); i++)
		{
			clone.add(words.get(i));
		}
		return clone;
	}
	public static void isPermuted(String word, ArrayList<String> dict)
	{
		permutation(word, new ArrayList<String>(), dict);
	}

- MKL December 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void permutation(String word, ArrayList<String> prefix, ArrayList<String> dict)
	{
		int n = dict.size();
		if(n == 0 && prefix.size() > 0)
		{
			String word_ = "";
			for(int i = 0; i < prefix.size(); i++)
			{
				word_ = word_.concat(prefix.get(i));
			}
			if(word.equals(word_))
				System.out.println("true");
		}
		else
		{
			ArrayList<String> prefix_;
			ArrayList<String> str = Code.clone(dict);
			ArrayList<String> str_;
			for(int i = 0; i < n; i++)
			{
				str_ = new ArrayList<String>();
				str_.addAll(str.subList(0,i));
				str_.addAll(str.subList(i+1,n));
				prefix_ = Code.clone(prefix);
				prefix_.add(dict.get(i));
				permutation(word, prefix_, str_);
			}
		}
	}
	private static ArrayList<String> clone(ArrayList<String> words)
	{
		ArrayList<String> clone = new ArrayList<String>();
		for(int i=0; i< words.size(); i++)
		{
			clone.add(words.get(i));
		}
		return clone;
	}
	public static void isPermuted(String word, ArrayList<String> dict)
	{
		permutation(word, new ArrayList<String>(), dict);
	}

- mkl December 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

May I know how the following case can be handled
dict = {bad, badda, day, ya}
word = "baddaya"
Answer - true {badda, ya}

- Hari January 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def isPermutaion(s,dict):
    for each in dict:
        s=s.replace(each,'')

    return s ==''

- sumitgaur.iiita January 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public static void main(String[] args) {
		String[] d1 = {"bad", "actor", "good", "act"};
		String[] d2 = {"bad", "actor", "good", "acting"};
		System.out.println(isPermutation("badactorgoodacting", d1));
		System.out.println(isPermutation("badactorgoodacting", d2));
		
		String[] d1b = {"bad", "good", "actor", "acting", "action"};
		String[] d2b = {"best", "better", "actor", "acting", "movie"};
		System.out.println(isPermutation("badgoodaction", d1b));
		System.out.println(isPermutation("badgoodactionr", d1b));
		System.out.println(isPermutation("betteractingactormovie", d2b));
	}
	
	public static boolean isPermutation(String s, String[] w) {
		Map<Character, List<String>> mapStrings = new HashMap<>();
		for (int i = 0; i < w.length; i++) {
			Character key = Character.valueOf(w[i].charAt(0));
			if (mapStrings.get(key) != null) {
				mapStrings.get(key).add(w[i]);
			} else {
				List<String> list = new ArrayList<>();
				list.add(w[i]);
				mapStrings.put(key, list);
			}
		}
		return isPermutation(s, 0, new StringBuilder(), mapStrings, new HashSet<>());
	}

	public static boolean isPermutation(String s, int start, StringBuilder t, Map<Character, List<String>> w, HashSet<String> usedStrings) {
		for (int i = start; i < s.length(); i++) {
			if(w.containsKey(s.charAt(i))) {
				List<String> l = w.get(s.charAt(i));
				Iterator<String> iter = l.iterator();
				while (iter.hasNext()) {
					String str = iter.next();
					// if string fits in remaining length 
					if (!usedStrings.contains(str) && str.length() <= s.length() - i && s.substring(i, i + str.length()).equals(str)) { 
						t.append(str);
						usedStrings.add(str);
						if (t.length() == s.length()) {
							return true;
						} else if (t.length() < s.length()) {
							if(isPermutation(s, i + str.length(), t, w, usedStrings)) {
								return true;
							}
						}
						
						// if no match found using this string prefix remove it 
						int lastIndex = s.lastIndexOf(str.charAt(0));
						if (lastIndex != -1 && lastIndex + str.length() <= t.length() &&
								t.substring(lastIndex, lastIndex + str.length()).equals(str)) {
							t.delete(lastIndex, lastIndex + str.length());							
						}						
						usedStrings.remove(str);
					}
				}
			}
		}
		
		return false;
	}
}
/*
output:
false
true
true
false
true
*/

- guilhebl September 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

s = "badactorgoodacting"
list1 = ['actor', 'bad', 'acting', 'good']
for x in list1:
    if x in s:
        s = s.replace(x, "")
if s == "":
    print("true")
else:
    print("false")

- Jagannathan R September 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

s = "badactorgoodacting"
list1 = ['actor', 'bad', 'acting', 'good']
for x in list1:
    if x in s:
        s = s.replace(x, "")
if s == "":
    print("true")
else:
    print("false")

- Jagannathan R September 18, 2016 | 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