Microsoft Interview Question for SDE-2s


Country: United States
Interview Type: In-Person




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

ZoomBA Guy (NoOne):

I don't think this is the most efficient way in this case. I believe the # of possible permutations of sorted characters grows at a faster rate as length of character array increases (n!) than the dictionary likely would (which probably has max 50,60,100K words).

I propose this, which is O(p*(n +m)) where p is the length of the dictionary, n is the length of the character array, and m is the average word length of the dictionary.

function valid (chars, dict) {
  var spellables = []
  for (var j = 0; j < dict.length; ++j) {
    var map = {}
    for (var i = 0; i < chars.length; ++i) {
      if (map[chars[i]]) {
        map[chars[i]] += 1
      } else {
        map[chars[i]] = 1
      }
    }
    var bool = true
    for (var k = 0; k < dict[j].length; ++k) {
      if (!map[dict[j].charAt(k)]) {
        bool = false
        break
      } else {
        map[dict[j].charAt(k)]--
      }
    }
    if (bool) {
      spellables.push(dict[j])
    }
  }
  console.log(spellables)

}

valid(['e', 'o', 'b', 'a', 'm', 'g', 'l'], [
  'go',
  'bat',
  'me',
  'eat',
  'goal',
  'boy',
  'run'
]);

- srterpe December 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

srterpe very cleverly inverted the problem. I love the idea. Hats off.

Instead of finding all possible words (sub sequences)
a string can generate, which is my stupid idea,

srterpe is counting the no of characters on each word,
and is a word can be made by taking / loaning characters from the string.

Very very clever.
My code has no chance surviving in more then 24 letter strings - he will win hand down for any string with size more than 20 ish - which is the size of a dictionary ( 2^20 ) .

srterpe is slightly off on the complexity, my algo runs with a complexity of Theta(2^n) where n is the size of the input string, it is close to n! where srterpe is correct.

No matter how large the string becomes, srterpe's method would be on size of the dictionary * no of char in the word.

See more on [ en.wikipedia.org/wiki/Longest_word_in_English ]
Here is to srterpe :

DICT = [ "go","bat","me","eat","goal", "boy", "run" ]
list_of_msets = list ( DICT ) -> {  [ mset( $.o.value ) , $.o ] }
LETTERS = [ _'e' , _'o' , _'b', _'a' , _'m', _'g' , _'l' ]
mset_letters = mset( LETTERS )
words = select( list_of_msets ) :: {  $.left <= mset_letters } -> { $.right }
println( words )

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

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Date;
import java.util.List;

public class Dictionary {

	public static void main(String[] args) {
		long startTime = new Date().getTime();
		char[] arr = {'e','o','b','a','m','g','l'};
		List<String> dictionary = new ArrayList<String>(Arrays.asList("go","bat","me","eat","goal","boy","run"));
		List<String> match = new ArrayList<String>();
		
		for(int maxWordLength = 2; maxWordLength <= arr.length; maxWordLength++){
			 possibleStrings(maxWordLength, arr,"",match,dictionary);
		}
		
		System.out.println(match);
		long endTime = new Date().getTime();
		System.out.println(endTime - startTime);
	}
	
	public static void possibleStrings(int maxLength, char[] alphabet, String curr,List<String> match, List<String> dictionary) {

        // If the current string has reached it's maximum length
        if(curr.length() == maxLength) {
//            System.out.println(curr);
            if(dictionary.contains(curr)){
            	match.add(curr);
            }

        // Else add each letter from the alphabet to new strings and process these new strings again
        } else {
            for(int i = 0; i < alphabet.length; i++) {
                String oldCurr = curr;
                curr += alphabet[i];
                possibleStrings(maxLength,alphabet,curr,match,dictionary);
                curr = oldCurr;
            }
        }
    }

}

- pradeep.aramalla December 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

I created custom class called StringWithCount which will have String word, length and occurance variable.

I am using Hashtable to map charater to the List<StringWithOccurance>.

Then I read the dictionary and create StringWithCount from each string where word and length are explicit, and occurance as 0. For each character in that string, I attach those StringWithCount in that characters list in Hashtable.

This is all my pre-computation. Now when you get the character array, read each character and increment occurance of each StringWithCount for that character in Hashtable. When for any StringWithCount occurance is same as length, add that to answer list.

import java.io.*;
import java.util.*;

/*
 * To execute Java, please define "static void main" on a class
 * named Solution.
 *
 * If you need more classes, simply define them inline.
 */

class StringWithCount
{
  public String word;
  public int len;
  public int occurance;
  
  public StringWithCount(String w, int l)
  {
    word=w;
    len=l;
    occurance=0;
  }
}

class Solution 
{  
  public static void main(String[] args) 
  {
    String[] dict = {"meo","got","mov","aaa","cvc","cvf","fbb","wersc"};
    Hashtable<Character, ArrayList<StringWithCount>> hst = new Hashtable<>();
    
    for(String word : dict)
    {
      int len=word.length();
      StringWithCount sc = new StringWithCount(word, len);
      for(int i=0;i<len;i++)
      {
        ArrayList<StringWithCount> temp;
        char ch=word.charAt(i);
        if(hst.containsKey(ch))
        {
          temp = hst.get(ch);
          temp.add(sc);
        }
        else
        {
          temp = new ArrayList<StringWithCount>();
          temp.add(sc);
          hst.put(ch, temp);
        }
      }
    }
    
    char[] charlist = {'a','b','v','c','m','o','f'};
    
    for(char c : charlist)
    {
      ArrayList<StringWithCount> tem;
      if(hst.containsKey(c))
      {
        tem=hst.get(c);
        for(StringWithCount sc : tem)
        {
          sc.occurance++;
          if(sc.occurance==sc.len)
          {
            System.out.println(sc.word);
          }
        }
      }
    }
  }
}

- Maunik Shah December 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.io.*;
import java.util.*;

/*
 * To execute Java, please define "static void main" on a class
 * named Solution.
 *
 * If you need more classes, simply define them inline.
 */

class StringWithCount
{
  public String word;
  public int len;
  public int occurance;
  
  public StringWithCount(String w, int l)
  {
    word=w;
    len=l;
    occurance=0;
  }
}

class Solution 
{  
  public static void main(String[] args) 
  {
    String[] dict = {"meo","got","mov","aaa","cvc","cvf","fbb","wersc"};
    Hashtable<Character, ArrayList<StringWithCount>> hst = new Hashtable<>();
    
    for(String word : dict)
    {
      int len=word.length();
      StringWithCount sc = new StringWithCount(word, len);
      for(int i=0;i<len;i++)
      {
        ArrayList<StringWithCount> temp;
        char ch=word.charAt(i);
        if(hst.containsKey(ch))
        {
          temp = hst.get(ch);
          temp.add(sc);
        }
        else
        {
          temp = new ArrayList<StringWithCount>();
          temp.add(sc);
          hst.put(ch, temp);
        }
      }
    }
    
    char[] charlist = {'a','b','v','c','m','o','f'};
    
    for(char c : charlist)
    {
      ArrayList<StringWithCount> tem;
      if(hst.containsKey(c))
      {
        tem=hst.get(c);
        for(StringWithCount sc : tem)
        {
          sc.occurance++;
          if(sc.occurance==sc.len)
          {
            System.out.println(sc.word);
          }
        }
      }
    }
  }
}

- Maunik Shah December 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is how you go about it.
First the theory, and then the ZoomBA dance.

/*
 The problem can be solved by first
 making the given dictionary a dictionary with :
 key -> sorted letters of a word as string
 values -> all words who are permutations of the same key

 Thus, given an array of letters:
 1. we should sort it first.
 2. Find all possible sub sequences of the same sorted array
 3. For each sub sequence (which would be sorted)
   we should check existence as key in the dictionary
   and if it does exist, print all words (values) for that key
*/

DICT = [ "go","bat","me","eat","goal", "boy", "run" ]
sorted_dict = mset( DICT ) -> { x = $.o.toCharArray ; sorta( x ) ; str(x,'') }
LETTERS = [ 'e' ,'o' , 'b' ,'a' ,'m' ,'g' , 'l' ]
sorta(LETTERS)
for ( sequences ( LETTERS ) ) {
  key = str( $,'')
  if( key @ sorted_dict ){
    println ( sorted_dict[key] )
  }
}

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

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class Class1
    {
        static void Main(string[] args)
        {
            GetWords();

        }

        public static void GetWords()
        {
            char[] charArr = { 'e', 'o', 'b', 'a', 'm', 'g', 'l' };

            string[] arryOfWords = { "go", "bat", "me", "eat", "goal", "boy", "run" };
           // List<String> listOfWords = new List<string>();
           // listOfWords.AddRange(arryOfWords);
            List<String> match = new List<String>();
            List<string> Words = new List<string>();

            foreach (var item in arryOfWords)
            {
                bool flag = false;
                char[] ch = item.ToCharArray();
                foreach (var chitem in ch)
                {

                    flag = false;
                    foreach (var charArrItems in charArr)
                    {
                        if (chitem == charArrItems)
                        {
                            flag = true;
                            break;
                        }
                    }
                    
                }
                if (flag)
                    Words.Add(item);
            }
            foreach (var item in Words)
            {
                Console.WriteLine(item);
            }
            Console.ReadLine();
        }
    }
}

- Sachin Srivastava December 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
class Class1
{
static void Main(string[] args)
{
GetWords();

}

public static void GetWords()
{
char[] charArr = { 'e', 'o', 'b', 'a', 'm', 'g', 'l' };

string[] arryOfWords = { "go", "bat", "me", "eat", "goal", "boy", "run" };
// List<String> listOfWords = new List<string>();
// listOfWords.AddRange(arryOfWords);
List<String> match = new List<String>();
List<string> Words = new List<string>();

foreach (var item in arryOfWords)
{
bool flag = false;
char[] ch = item.ToCharArray();
foreach (var chitem in ch)
{

flag = false;
foreach (var charArrItems in charArr)
{
if (chitem == charArrItems)
{
flag = true;
break;
}
}

}
if (flag)
Words.Add(item);
}
foreach (var item in Words)
{
Console.WriteLine(item);
}
Console.ReadLine();
}
}
}

- Sachin Srivastava December 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Dictionary {

public static void main(String[] args) {
        String[] wordsToDic = {"go", "bat", "eat", "goal", "boy", "run","me"};
        char[] letters = {'e','o','l','b','a','m','g', '\n'};
        Dictionary dic = new Dictionary();
        
        dic.build(wordsToDic);
        
        dic.printAllWordsFromArray(letters);
    }

    boolean word;
    Dictionary[] child;
    
    public Dictionary(){
        child = new Dictionary[26];
        word = false;
    }

    private int validChar(int asc) {
        if (asc > 96 && asc < 123) {
            return asc;
        } else if (asc > 64 && asc < 91) {
            return asc + 32;
        } else {
            return -1;
        }
    }

    public void build(String[] words) {

        for (String w : words) {
            add(w);
        }
    }

    private void add(String w) {
        Dictionary current = this;
        for (char c : w.toCharArray()) {
            if(validChar(c)== -1){
                continue;
            }
            if (current.child[c - 97] == null) {
                current.child[c - 97] = new Dictionary();
                current = current.child[c - 97];
            } else {
                current = current.child[c - 97];
            }
        }
        current.word = true;
    }

    public void printAllWordsFromArray(char[] letters) {
        StringBuilder let = new StringBuilder();
        for(char c: letters){
            if(validChar(c)!= -1){
                let.append(c);
            }
        }
        letters = let.toString().toCharArray();
        for(char c: letters){
            if(child[c-97] != null){
                child[c-97].findWords(letters, ""+c);
            }
        }
    }

    private void findWords(char[] letters, String string) {
        if(word){
            System.out.println(string);
        }
        for(char c:letters){
            if(child[c-97]!= null){
                child[c-97].findWords(letters, string+c);
            }
        }
    }

}

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

One way could be to create a trie of the char array and traverse the tree to find if strings generated match any of the dictionary.

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

public class DictionaryWordCheck {
	public static void main(String[] args) {
		char[] arr = {'e','o','b', 'a','m','g', 'l'}; 

		List<String> strs = new ArrayList<>();
		strs.add("go");
		strs.add("bat");
		strs.add("me");
		strs.add("eat");
		strs.add("goal"); 
		strs.add("boy");
		strs.add("run");
		
		printList(getDictWordsInArray(arr, strs));
	}

	private static void printList(List<String> dictWordsInArray) {
		for (String string : dictWordsInArray) {
			System.out.println(string);
		}
	}

	private static List<String> getDictWordsInArray(char[] arr, List<String> strs) {		
		List<String> results = new ArrayList<>();		
		HashSet<Character> setChars = new HashSet<>();
		for (int i = 0; i < arr.length; i++) {
			setChars.add(arr[i]);
		}		
		for (String string : strs) {
			char[] chars = string.toCharArray();
			int i = 0;
			while(i < chars.length && setChars.contains(chars[i])) {
				i++;
			}
			if (i == chars.length) {
				results.add(string);
			}
		}
		return results;
	}
	
}
/*
output:

go
me
goal
*/

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

public static void main(String[] args) {
		System.out.println("Valid Words:" + printAllValidWords(new Character[]{'e','o','b','a','m','g','l'}, new HashSet<String>(){{
			 addAll( Arrays.asList( "go","goa","bat","me","eat","goal","boy","run"));
		 }}));
	}
	
	private static List<String> printAllValidWords( Character [] cArray, Set<String> dictionary ){
		 Set<Character> charSet = new HashSet<Character>(Arrays.asList( cArray ));
		 Map<Character, List<String>> charMapping = getWordsStartingFromChar( dictionary );
		 List<String> validWords = new ArrayList<String>();
		 for( Character ch: charSet ){
			 if( charMapping.containsKey( ch )){
				 List<String> chWords = charMapping.get(ch);
				 for( String word: chWords ){
					 char [] wordChar = word.toCharArray();
					 StringBuffer buffer = new StringBuffer();
					 for( char c: wordChar ){
						 if( charSet.contains( c )){
							 buffer.append( c );
						 }else {
							 break;
						 }
					 }
					 if( buffer.toString().equals( word )){
						 validWords.add( word );
					 }
				 }
			 }
		 }
		 return validWords;
				
	}
	
	private static Map<Character, List<String>> getWordsStartingFromChar(Set<String> validWords){
		Map<Character, List<String>> charToWord = new HashMap<Character, List<String>>();
		for( String word: validWords ){
			if( !charToWord.containsKey( word.charAt(0))){
				charToWord.put( word.charAt(0), new ArrayList<String>());
			}
			charToWord.get( word.charAt(0)).add( word );
		}
		return charToWord;
	}

- puttappa.raghavendra December 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class StringMatch {

String[] dict = {"go","bat","me","eat","goal", "boy", "run"};
char[] arr = {'e','o','b', 'a','m','g', 'l'};

boolean isPresent(String str) {
//We can implement HashMap as well for this operation
for (String x:dict) {
if(x.equals(str)){
return true;
}
}
return false;
}

void printAllStrings(String larr, String rstr) {
if(larr.length()>0) {
for(int i=0; i<larr.length(); i++) {
String myStr = rstr + larr.charAt(i);
if(this.isPresent(myStr)) {
System.out.println(myStr);
}
printAllStrings(larr.substring(0,i)+larr.substring(i+1,larr.length()),myStr);
}
}
}

public static void main(String[] args) {
StringMatch sm = new StringMatch();
sm.printAllStrings(String.valueOf(sm.arr), "");
}
}

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

I think the best solution is to load dictionary words in a Trie and iterate through characters and check if any words start with this character and so on. the Time complexity would be O(NS), N being length of char array and S being average length of a string

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

def init

@char_list = ['e','o','b','a','m','g','l']
@string_list = ["go","bat","me","eat","goal","boy","run"]
@char_hash = {}

end


def string_exist(char_hash,string_list,string_sent)

flag = true
string_list.each do |each_string_char|

if char_hash.key?each_string_char then
else

flag = false
print "String is not part of chars : ",string_sent,"\n"
break

end

end

if flag == true then

print "Belong to the list : ",string_sent,"\n"

end

end

def store_chars(char_list,char_hash)

char_list.each do |each_char|

char_hash[each_char] = nil

end


end

init()
store_chars(@char_list,@char_hash)
@string_list.each do |each_string|

string_exist(@char_hash,each_string.split(""),each_string)

end

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

def init

@char_list = ['e','o','b','a','m','g','l']
@string_list = ["go","bat","me","eat","goal","boy","run"]
@char_hash = {}

end


def string_exist(char_hash,string_list,string_sent)

flag = true
string_list.each do |each_string_char|

if char_hash.key?each_string_char then
else

flag = false
print "String is not part of chars : ",string_sent,"\n"
break

end

end

if flag == true then

print "Belong to the list : ",string_sent,"\n"

end

end

def store_chars(char_list,char_hash)

char_list.each do |each_char|

char_hash[each_char] = nil

end


end

init()
store_chars(@char_list,@char_hash)
@string_list.each do |each_string|

string_exist(@char_hash,each_string.split(""),each_string)

end

- Dharmu Using hash you can solve it better December 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<?php
function findw($str, $arr){
	$tmp = "";
	for($j=0; $j < strlen($str); $j++){
		for($k=0; $k < sizeof($arr); $k++){
			if($str[$j] == $arr[$k]){
				$tmp .= $arr[$k];
			}else{
				continue;
			}
		}
	}
	
	if($tmp === $str){
		return $tmp;
	}else{
		return null;
	}
}

function init(){
	$arr = ['e','o','b', 'a','m','g', 'l'];
    $dic = ["go","bat","me","eat","goal", "boy", "run"];
	
	for($i=0; $i < sizeof($dic); $i++){
		if(findw($dic[$i], $arr)){
			echo findw($dic[$i], $arr)."</br >";
		}
	}
}

init();

?>

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

function findw($str, $arr){
	$tmp = "";
	for($j=0; $j < strlen($str); $j++){
		for($k=0; $k < sizeof($arr); $k++){
			if($str[$j] == $arr[$k]){
				$tmp .= $arr[$k];
			}else{
				continue;
			}
		}
	}
	
	if($tmp === $str){
		return $tmp;
	}else{
		return null;
	}
}

function init(){
	$arr = ['e','o','b', 'a','m','g', 'l'];
    $dic = ["go","bat","me","eat","goal", "boy", "run"];
	
	for($i=0; $i < sizeof($dic); $i++){
		if(findw($dic[$i], $arr)){
			echo findw($dic[$i], $arr)."</br >";
		}
	}
}

init();

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

function findw($str, $arr){
	$tmp = "";
	for($j=0; $j < strlen($str); $j++){
		for($k=0; $k < sizeof($arr); $k++){
			if($str[$j] == $arr[$k]){
				$tmp .= $arr[$k];
			}else{
				continue;
			}
		}
	}
	
	if($tmp === $str){
		return $tmp;
	}else{
		return null;
	}
}

function init(){
	$arr = ['e','o','b', 'a','m','g', 'l'];
    $dic = ["go","bat","me","eat","goal", "boy", "run"];
	
	for($i=0; $i < sizeof($dic); $i++){
		if(findw($dic[$i], $arr)){
			echo findw($dic[$i], $arr)."</br >";
		}
	}
}

init();

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

$str = "sdas";

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

asdasd

$str = nul

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

<?php


function findw($str, $arr){
$tmp = "";
for($j=0; $j < strlen($str); $j++){
for($k=0; $k < sizeof($arr); $k++){
if($str[$j] == $arr[$k]){
$tmp .= $arr[$k];
}else{
continue;
}
}
}

if($tmp === $str){
return $tmp;
}else{
return null;
}
}

function init(){
$arr = ['e','o','b', 'a','m','g', 'l'];
$dic = ["go","bat","me","eat","goal", "boy", "run"];

for($i=0; $i < sizeof($dic); $i++){
if(findw($dic[$i], $arr)){
echo findw($dic[$i], $arr)."</br >";
}
}
}

init();

?>

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

<?php

function findw($str, $arr){

$tmp = "";
for($j=0; $j < strlen($str); $j++){
for($k=0; $k < sizeof($arr); $k++){
if($str[$j] == $arr[$k]){
$tmp .= $arr[$k];
}else{
continue;
}
}
}

if($tmp === $str){
return $tmp;
}else{
return null;
}
}

function init(){
$arr = ['e','o','b', 'a','m','g', 'l'];
$dic = ["go","bat","me","eat","goal", "boy", "run"];

for($i=0; $i < sizeof($dic); $i++){
if(findw($dic[$i], $arr)){
echo findw($dic[$i], $arr)."</br >";
}
}
}

init();

?>

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

import java.util.Scanner;
class dictionary{
public static void main(String[]args){
Scanner scan=new Scanner(System.in);
String[] temp=new String[10];
char[] arr={'e','o', 'b', 'a', 'm', 'g', 'l'};
String[] Dict={"go","bat","me","eat","goal","boy","run"};
int val=0,k=0,len=0;
for(int i=0;i<7;i++)
{
val=0;
for(int j=0;j<7;j++)
{
len=Dict[i].length();
if(Dict[i].contains((arr[j]+"")))
{
val++;
}
}
if(val==len)
{
temp[k]=Dict[i];
len=0;
k++;
}
}
for(int i=0;i<k;i++)
{
System.out.println(temp[i]);
}
}
}

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

Why don't we iterate over all the dictionary words and check if every character in it is there within the character list ?

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

class Program
    {
        static void Main(string[] args)
        {
            string[] dic = {"go", "bat", "me", "eat", "goal", "boy", "run"};
            char[] arr = { 'e', 'o', 'b', 'm', 'a', 'g', 'l' };

            foreach(var item in dic)
            {
                bool print = true;
                foreach(var c in item)
                {
                    if(!arr.Contains(c))
                    {
                        print = false;
                    }
                }

                if(print)
                Console.WriteLine(item);
            }

            Console.ReadLine();
        }

}

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

Please suggest changes if any :

import java.util.*;

public class Dictionary {
	static Map<String, String> test = new TreeMap<>();
	public static void main(String[] args) {
		long startTime = new Date().getTime();
		char []arr = {'e','o','b','a','m','g','l'};
		int min_length, max_length = 4;
		List<String> dict = new ArrayList<>();
		dict.add("go");
		dict.add("bat");
		dict.add("me");
		dict.add("eat");
		dict.add("goal");
		dict.add("boy");
		dict.add("run");
		List<String> output = new ArrayList<>();
		for(min_length=2;min_length<=max_length;min_length++){
			 possibleStrings(min_length, arr,"");
		}
		for(String dictionaryWord : dict){
			if(test.containsKey(dictionaryWord)) 
				output.add(dictionaryWord);			
		}
		for(int i=0;i<output.size();i++){
			System.out.print(output.get(i)+" ");
		}
		long endTime = new Date().getTime();
		System.out.println();
		System.out.println("Time taken : "+(endTime-startTime));
	}

	public static void possibleStrings(int maxLength, char[] alphabet, String curr) {

		// If the current string has reached it's maximum length
		if (curr.length() == maxLength) {
			test.put(curr, curr);

			// Else add each letter from the alphabet to new strings and process
			// these new strings again
		} else {
			for (int i = 0; i < alphabet.length; i++) {
				String oldCurr = curr;
				curr += alphabet[i];
				possibleStrings(maxLength, alphabet, curr);
				curr = oldCurr;
			}
		}
	}
}

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

List<String> formValidWords(List<String> dict, char[] givenChar)
	{	int[] avail = new int[26];  			//assuming givenChar contains only alphabets a-z
		for(char c:givenChar)
			avail[c-'a']++;
		List<String> result = new ArrayList<String>();
		for(String word: dict)
		{	int[] count = new int[26];
			boolean flag = true;
			for(char c: word.toCharArray)
			{	count[c-'a']++;
				if(count[c-'a'] > avail[c-'a'])
				{	flag = false;
					break;
			}	}
			if(flag)	result.add(word);
		}
		return result;	
	}

- Ezhilarasi Swaminathan February 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The best way to create an efficient solution would be to create a binary search tree kind of data structure from all words in the dictionary. After that just search the data structure for each character as we come by them in our character array.

- Anonymous February 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class S1 {

public static void main(String[] args) {

char a[] = {'e' ,'b' ,'o','a','m','g','l'};
String[] a1 ={"go","bat","me","eat","goal","boy","run"};
for (int i = 0; i < a1.length; i++) {
int count =0;
String s1= a1[i] ;
for (int j = 0; j < s1.length(); j++) {
for (int j2 = 0; j2 < a.length; j2++) {
if (s1.charAt(j) == a[j2]) {
count++;
if(count == s1.length()){
System.out.println(s1);

}
}
}
}
}

}

}

- Sandeep kumar March 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class S1 {

public static void main(String[] args) {

char a[] = {'e' ,'b' ,'o','a','m','g','l'};
String[] a1 ={"go","bat","me","eat","goal","boy","run"};
for (int i = 0; i < a1.length; i++) {
int count =0;
String s1= a1[i] ;
for (int j = 0; j < s1.length(); j++) {
for (int j2 = 0; j2 < a.length; j2++) {
if (s1.charAt(j) == a[j2]) {
count++;
if(count == s1.length()){
System.out.println(s1);

}
}
}
}
}
}
}

- Sandeep kumar March 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

An easier approach is to precompute a map of sorted characters for each word in the dictionary. Also, sort the char array. This would allow us to find solution linearly.

private static List<String> possibleWords(char[] chars, String[] wordDict) {
        List<String> possibleWords = new LinkedList<>();
        Arrays.sort(chars);
        Map<String, char[]> wordToSortedCharMap = getWordToSortedCharsMap(wordDict);
        for(Map.Entry<String, char[]> entry: wordToSortedCharMap.entrySet()){
            char[] wordChars = entry.getValue();
            for(int i=0, j=0; i<chars.length && j<wordChars.length;){
                if(chars[i]==wordChars[j]){
                    j++;
                    //i++;//if no repetition allowed
                } else {
                    i++;
                }

                if(j == wordChars.length){//i.e. all chars matched
                    possibleWords.add(entry.getKey());
                }
            }
        }
        return possibleWords;
    }

    private static Map<String, char[]> getWordToSortedCharsMap(String[] list){
        Map<String, char[]> map = new HashMap<>();
        for(String word: list){
            char[] chars = word.toCharArray();
            Arrays.sort(chars);
            map.put(word, chars);
        }
        return map;
    }

    public static void main(String[] args){
        char[] chars = {'e','o','b', 'a','m','g', 'l'};
        String[] dict = {"go","bat","me","eat","goal", "boy", "run"};
        System.out.println(possibleWords(chars, dict));
    }

- sn March 30, 2017 | 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