Google Interview Question Software Engineers
Country: India
Interview Type: In-Person
public class Solution {
public static Optional<String> getMinimumLengthWord(List<String> dictionary, Set<Character> characterSet) {
int minLength = 0;
String result = null;
for (String str : dictionary) {
if (isIncludeAllChars(str, characterSet)) {
if (str.length() < minLength) {
minLength = str.length();
result = str;
}
}
}
return Optional.ofNullable(result).filter(s -> !s.isEmpty());
}
public static boolean isIncludeAllChars(String word, Set<Character> characterSet) {
int [] array = new int[28];
word.chars().forEach(a -> array[a-'a']++);
return characterSet.stream()
.filter(i -> array[i - 'a'] == 0)
.collect(Collectors.toList())
.isEmpty();
}
}
let us have a string = "peace" I will convert into a char array and put them into hashset or treemap which has all unique values. The size of the map would be the minimum length of the word. As our condition is to have all the given chars, if we eliminate the duplicate values we need to have rest of them all and we can check whether a word is possible or not and not possible catch the exception.
{{
function minLengthWord(characters, dictionary) {
var found = null;
dictionary.forEach(function (_word) {
if (_word.length >= characters.length && (found === null || found.length > _word.length)) {
var include = true;
for (var i = 0; i < characters.length; i += 1) {
if (_word.indexOf(characters[i]) === -1) {
include = false;
break;
}
}
if (include) {
found = _word;
}
}
}, this);
return found !== false ? found.length : 0;
}
}}
function minLengthWord(characters, dictionary) {
var found = null;
dictionary.forEach(function (_word) {
if (_word.length >= characters.length && (found === null || found.length > _word.length)) {
var include = true;
for (var i = 0; i < characters.length; i += 1) {
if (_word.indexOf(characters[i]) === -1) {
include = false;
break;
}
}
if (include) {
found = _word;
}
}
}, this);
return found !== false ? found.length : 0;
}
Possible Approach I can think of is as follow.s
1>Let us say set of chars is of length 7{d,a,r,l,i,n,g}.
2.Start from point/index where dictinary starts with atleast 7 chars.
3.for all 7 digits in dictionary,we need to find sum of ascii values.and compare it with ascii sum of charcter string.and see if there is match.conitnue for rest of dictionary where length>7.
we can eliminate 19 chars check by using starts with()
Any one has better approach,please suggest.
Assuming the character array given is a set (no duplicates)
public class MinLengthWord {
public static void main(String args[]) {
String[] dic = { "addds", "asdfoisfiodijf" };
char[] c = { 'a', 's', 's' };
System.out.print(minLengthWord(c, dic));
}
public static String minLengthWord(char[] chars, String[] dic) {
int min = Integer.MAX_VALUE;
int minIndex = -1;
for (int i = 0; i < dic.length; i++) {
// Check if current word (dic[i]) is big enough to contain all characters and smaller than
// current smallest word
if (dic[i].length() >= chars.length && (dic[i].length() < min || min == Integer.MAX_VALUE)) {
// Check if current word contains all characters in chars
if (containsAll(dic[i], chars)) {
min = dic[i].length();
minIndex = i;
}
}
}
if (minIndex == -1) {
System.out.println("No words found that contain all characters.");
return null;
} else {
return dic[minIndex];
}
}
public static boolean containsAll(String s, char[] chars) {
boolean[] c = new boolean[256];
for (int j = 0; j < s.length(); j++) {
c[(int) s.charAt(j)] = true;
}
for (int j = 0; j < chars.length; j++) {
if (!c[(int) chars[j]]) {
return false;
}
}
return true;
}
public void findIfWordContain(String[] dic, char[] chars){
String minLengthWord = null;
int minLength =0;
int currentLength =0;
for(String word: dic){
if(word.length() >= chars.length){
if(containsAllChar(word, chars)){
currentLength = word.length();
if(minLength>0 && currentLength<minLength){
minLengthWord = word;
minLength = currentLength;
}else if(minLength == 0){
minLength = currentLength;
minLengthWord = word;
}
}
}
}
if(minLengthWord == null){
System.out.println("No I dint find any word");
}else{
System.out.println(minLengthWord);
}
}
private boolean containsAllChar(String word, char[] chars) {
for(char c : chars){
if(!word.contains(String.valueOf(c))){
return false;
}
}
return true;
}
public void findIfWordContain(String[] dic, char[] chars){
String minLengthWord = null;
int minLength =0;
int currentLength =0;
for(String word: dic){
if(word.length() >= chars.length){
if(containsAllChar(word, chars)){
currentLength = word.length();
if(minLength>0 && currentLength<minLength){
minLengthWord = word;
minLength = currentLength;
}else if(minLength == 0){
minLength = currentLength;
minLengthWord = word;
}
}
}
}
if(minLengthWord == null){
System.out.println("No I dint find any word");
}else{
System.out.println(minLengthWord);
}
}
private boolean containsAllChar(String word, char[] chars) {
for(char c : chars){
if(!word.contains(String.valueOf(c))){
return false;
}
}
return true;
}
public void findIfWordContain(String[] dic, char[] chars){
String minLengthWord = null;
int minLength =0;
int currentLength =0;
for(String word: dic){
if(word.length() >= chars.length){
if(containsAllChar(word, chars)){
currentLength = word.length();
if(minLength>0 && currentLength<minLength){
minLengthWord = word;
minLength = currentLength;
}else if(minLength == 0){
minLength = currentLength;
minLengthWord = word;
}
}
}
}
if(minLengthWord == null){
System.out.println("No I dint find any word");
}else{
System.out.println(minLengthWord);
}
}
private boolean containsAllChar(String word, char[] chars) {
for(char c : chars){
if(!word.contains(String.valueOf(c))){
return false;
}
}
return true;
}
public void findIfWordContain(String[] dic, char[] chars){
String minLengthWord = null;
int minLength =0;
int currentLength =0;
for(String word: dic){
if(word.length() >= chars.length){
if(containsAllChar(word, chars)){
currentLength = word.length();
if(minLength>0 && currentLength<minLength){
minLengthWord = word;
minLength = currentLength;
}else if(minLength == 0){
minLength = currentLength;
minLengthWord = word;
}
}
}
}
if(minLengthWord == null){
System.out.println("No I dint find any word");
}else{
System.out.println(minLengthWord);
}
}
private boolean containsAllChar(String word, char[] chars) {
for(char c : chars){
if(!word.contains(String.valueOf(c))){
return false;
}
}
return true;
}
public void findIfWordContain(String[] dic, char[] chars){
String minLengthWord = null;
int minLength =0;
int currentLength =0;
for(String word: dic){
if(word.length() >= chars.length){
if(containsAllChar(word, chars)){
currentLength = word.length();
if(minLength>0 && currentLength<minLength){
minLengthWord = word;
minLength = currentLength;
}else if(minLength == 0){
minLength = currentLength;
minLengthWord = word;
}
}
}
}
if(minLengthWord == null){
System.out.println("No I dint find any word");
}else{
System.out.println(minLengthWord);
}
}
private boolean containsAllChar(String word, char[] chars) {
for(char c : chars){
if(!word.contains(String.valueOf(c))){
return false;
}
}
return true;
}
public static void main(String[] args) {
List<String> words = new ArrayList<>();
words.add("acb");
words.add("abc");
words.add("abcd");
words.add("abe");
words.add("ab");
words.add("aces");
words.add("ey");
Dictionary di = new Dictionary(words);
System.out.println(di.getMinSizeWordsContained(new char[]{'a','b','c'}));
}
// create class dictionary which contains a TreeMap with key = word.length and value= List<String> wordsWithTheSameSize
// it allows us to decrease scope of search (if we have 3 chars then we start search from words only with size 3 and unless we find them we take words with the following size)
public class Dictionary {
private TreeMap<Integer,List<String>> dictionary = new TreeMap<>();
public Dictionary(List<String> words) {
if (Helper.isEmpty(words)) {
throw new RuntimeException("Dictionary can not be empty");
}
for (String word : words) {
List<String> sameSizeWords = dictionary.get(word.length());
if (!Helper.isEmpty(sameSizeWords)) {
sameSizeWords.add(word);
} else {
sameSizeWords = new ArrayList();
sameSizeWords.add(word);
dictionary.put(word.length(), sameSizeWords);
}
}
}
public List<String> getMinSizeWordsContained(char[] chars) {
if (Helper.isEmpty(chars)) {
return null;
}
conditionValidation(chars);
for (int i = chars.length; i <= dictionary.lastKey(); i++) {
List<String> minWords = getListHits(chars, dictionary.get(i));
if (!Helper.isEmpty(minWords)) {
return minWords;
}
}
return null;
}
private List<String> getListHits(char[] chars, List<String> words) {
if (Helper.isEmpty(chars) || Helper.isEmpty(words)) {
return null;
}
List<String> hits = new ArrayList();
for (String word : words) {
if (isWordContainsChars(word, chars)) {
hits.add(word);
}
}
return hits;
}
private boolean isWordContainsChars(String word, char[] chars) {
for (char letter : chars) {
if(!word.contains(String.valueOf(letter))) {
return false;
}
}
return true;
}
private void conditionValidation(char[] chars) {
if (chars.length > dictionary.lastKey()) {
throw new RuntimeException("Count of chars is higher than the max word length in dictionary");
}
}
}
// just helper class
public class Helper {
public static boolean isEmpty(List<String> words){
if (words == null || words.isEmpty()) {
return true;
}
return false;
}
public static boolean isEmpty(char[] chars){
if (chars == null || chars.length() == 0) {
return true;
}
return false;
}
}
Just confirming do you mean "... find the minimum length word that contains all the CHARACTERS from the given word"?
- Anonymous June 19, 2016