## Apple Interview Question for Software Engineer in Tests

Country: United States
Interview Type: Phone Interview

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

If the number of alphabets possible is less, this will work
1) Assign each alphabet in the character array a unique prime number and have this char to number mapping in a hash map.
HashChars[] = [ "a->2" , "n->3" , "c->5" , "b->7"]
2) Multiply each prime number corresponding to the chars in chars[] array.
[ "a" , "a" , "n" , "c" , "b"]
2 * 2 * 3 * 5 * 7 = 420
3) Use the same prime number mapping and find the product of each string in the words array, Ignore the string who does not have a char prime no mapping from step (1), in this step find the length of each string as well
abc = 2*7*5 = 70 ( 3 - length )
baa = 7*2*2 = 28 ( 3 - length )
caan = 5*2*2*3 = 60 ( 4- length )
banc = 7*2*3*5 = 210( 4-length )
4) Divide the number from step (2) with number for each word calculated from step (3) and return the words which are divisible and have the longest string length.

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

Not feasible for the production produced in step 2 can be a huge number? For example, when the chars[] contains 20 characters? The production will be no smaller than 2^20.

Comment hidden because of low score. Click to expand.
0

This is completely feasible in real life as words are rarely that long in english dictionary! Use a long for storing product values. Also: calculate product just once for dictionary words and use them for subsequent searches.

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

Convert the character array to a string and sort that string .
ex if char[] a={ a,c,d,e,f}
String b="acdef"
now sort b
Hence b=acdef;

Now itterate through the array of words
1)Check if word[i].length >=largestword lenght
if no ignore word and move on to the next word.
if yes get the signature of the word(ie sorted word ) and check if it is a substring of the sorted string of characters if yes and its lenght is greater than the longest word length save it and set it to the new longest word .

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

Substring will not work since aacn (Sorted word) is not a substring of aabcn (Sorted characters).

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

``````//
//  main.m
//  CommondLineProject
//
//  Created by Dun Liu on 6/23/14.
//

#import <Foundation/Foundation.h>

/*
given 2 arrays wrds[] , chars[] as an input to a function such that
wrds[] = [ "abc" , "baa" , "caan" , "an" , "banc" ]
chars[] = [ "a" , "a" , "n" , "c" , "b"]
Function should return the longest word from words[] which can be constructed from the chars in chars[] array.
for above example - "caan" , "banc" should be returned

Note: Once a character in chars[] array is used, it cant be used again.
eg: words[] = [ "aat" ]
characters[] = [ "a" , "t" ]
then word "aat" can't be constructed, since we've only 1 "a" in chars[].
*/

@interface Handler : NSObject
+ (NSArray *)longestWords:(NSArray *)words useChars:(NSArray *)chars;
@end

@implementation Handler

+ (NSArray *)longestWords:(NSArray *)words useChars:(NSArray *)chars {
NSMutableArray *result = [NSMutableArray new];
NSUInteger longest = 0;
NSArray *sortedChars= [ chars sortedArrayUsingSelector:@selector(compare:)];
for (NSString *word in words) {
NSMutableArray *wordChars = [NSMutableArray new];
for (int i=0; i<word.length; i++) {
}
[wordChars sortUsingSelector:@selector(compare:)];
if ([self array:wordChars isSubArrayOf:sortedChars]) {
if (wordChars.count > longest ) {
[result removeAllObjects];
longest = wordChars.count;
}
if (wordChars.count == longest ) {
}
}
}
return result;
}

+ (BOOL)array:(NSArray *)a1 isSubArrayOf:(NSArray *)a2 {
NSUInteger i1=0, i2=0;
while(i1<a1.count && i2<a2.count) {
if ([a1[i1] isEqualToString:a2[i2]]) {
i1++;
i2++;
} else {
i2++;
}
}
return i1==a1.count;
}

@end

int main(int argc, const char * argv[])
{

@autoreleasepool {
NSArray *words = @[ @"abc" , @"baa" , @"caan" , @"an" , @"banc" ];
NSArray *chars = @[ @"a" , @"a" , @"n" , @"c" , @"b"];
NSLog(@"%@", [Handler longestWords:words useChars:chars]);

}
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

you mean subsequence not substring

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

How about using a map for chars[] and store the number of occurrences as value.

While iterating words[], check if the character is present in the above map and reduce the value every time it is used.

Comment hidden because of low score. Click to expand.
0

``````int returnlongestword ( string wrds[],int lenw, char chars[], int lenc) {
int dict[256] = {0}, mydict[256] = {0};
int i, j, index;
int maxlen = 0;
for (i = 0; i < lenc; i++ )
dict[chars[i]]++;

for (i=0; i < lenw; i++) {
memcpy(mydict,dict,256);
string str = wrds[i];
int curlen;
int len = str.length;
for (j=0;j<len;j++) {
if (!mydict[str[j]]) {
break;
} else {
mydict[str[j]]--;
curlen++;
}
}
if (curlen > maxlen) {
maxlen = curlen;
index = i;
}
}
return index;
}``````

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

Build a complete graph of the letters from chars[] array. Use DFS to navigate the complete graph, each time checking for the existence of the word based on the sequence of letters seen so far.

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

Sort the strings by string length in decreasing order , create a hash map of the char array

return the first string with all chars in the hash map , but don't stop check if next string is of a smaller length and if so continue till the string length reduces

Comment hidden because of low score. Click to expand.
0

Does sorting give any improvement in performance. We anyway have to access all words in word array for sorting. So why not do the second task for all elements in word array.

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

Python solution:

``````def hash_it(chars):
d = dict()
for c in chars:
if c not in d:
d[c] = 1
else:
d[c] += 1
return d

max_len = 0
l = []
d = hash_it(chars)

#print d
for word in wrds:
hashed = hash_it(word)
if len(hashed) > len(d) or len(word) < max_len:
continue
good = True
for k, v in hashed.iteritems():
if k not in d or v > d[k]:
good = False
break

if not good:
continue

if max_len < len(word):
max_len = len(word)
l = []
l.append(word)

print l``````

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

/*
chars[] = [ "a" , "a" , "n" , "c" , "b"]
bit[] = [ ]//0 or 1

callling this function is pretty expensive
*/
bool IsThisWordGood(wrd, chars[])
{
bool res = false;
char charWord;
bit bitSet[length(chars[])]
ResetZeroBit(bitSetOff);
for (int x = 0;x<length(wrd);x++)
{
res = false;
charWord = wrd[x];
for (int i = 0;i<length(chars[]) && res == false; i++)
{
if (chars[i] == charWord && bitSet[i]==0)
{
bitSet[i]=1;
result = true;
}
}
}

return res;
}

/*
The worst case is:
wrds[] has all the words with the same length and in the chars[]
/*
word* function (wrds[] , chars[])
{
word longestWord[];//the worst case longestWord[] = wrds[]
int longestLengthOfWord = 0
int i =0, j =0;

if(IsEmpty(wrds[]) || IsEmpty(wrds[chars]))
{
return null;
}

SortDecreasingOrder(wrds[]);
longestLengthOfWord = GetNumberOfChar(wrds[0])
for(i =0; i<length(wrds[]) && (j == 0 || longestLengthOfWord == GetNumberOfChar(wrds[i]));i++)
{
if(IsThisWordGood(wrds[i], chars[]) == true)
{
longestLengthOfWord = GetNumberOfChar(wrds[i]);
longestWord[j] = wrds[i];
j++;
}
}

return longestWord;
}

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

To be precise, the range of possible values for chars[] of length 20 is [2^20, 101^20]. 101 is the 26th prime numbers.

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

``````public static void Function(string[] str, char[] ch)
{

//Create hashtable with char and it's count
var hashtable1 = new Hashtable();
foreach (var a in ch)
{
if (!hashtable1.Contains(a))
{
hashtable1[a] = 1;
}
else
hashtable1[a] = Convert.ToInt32(hashtable1[a]) + 1;
}

//Sort array of strings in descending order so that you dont have to check for any string which is less than current max
IEnumerable<string> str2 = from n in str orderby n.Length descending select n;

string maxStr="";
int count = 0;
int count1 = 0;

foreach (var word in str2)
{
var hashtable = new Hashtable(hashtable1);
//the word has to be less than ch array length and greater or equal to max string
if (word.Length <= ch.Length && word.Length >= maxStr.Length)
{
for (int i = 0; i < word.Length; i++)
{
//Take the count of char
count1 = Convert.ToInt32(hashtable[word[i]]);
//If the hashtable doesnt contains key OR count of that key is less than 1, then break;
if (!hashtable.Contains(word[i]) || count1 < 1)
{
count = 0;
break;
}
count++;
count1--;
hashtable[word[i]] = count1;
}
if (count == word.Length)
{
maxStr = word;
count = 0;
Console.WriteLine(maxStr);

}
}
//If the word is <= char array length OR >= to max string, then no point looking into smaller string
else
break;

}
}``````

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

Can this be done using trie's data structure in any case?

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

private Map<Character, Integer> copyCount(char[] chars) {
Map<Character, Integer> charCounts = new HashMap<Character, Integer>(chars.length);
for (char c : chars) {
int value = 0;
if (charCounts.containsKey(c)) {
value = charCounts.get(c);
charCounts.put(c, ++value);
} else {
charCounts.put(c, 1);
}
}
return charCounts;
}

public boolean isContained(Map<Character, Integer> toBeCompared, Map<Character, Integer> toCompare) {

for(Character c: toBeCompared.keySet()){
if(!toBeCompared.containsKey(c) || !toCompare.containsKey(c)) {
return false;
}
if (toBeCompared.get(c) > toCompare.get(c)){
return false;
}
}
return true;
}

public PriorityQueue<String> longestWords() {
String[] words = {"abc", "baa", "caan", "an", "banc", "tolosa"};
char[] chars = {'a', 'a', 'n', 'c', 'b'};

PriorityQueue<String> values = new PriorityQueue<String>(words.length, new Comparator<String>() {

@Override
public int compare(String o1, String o2) {
if (o1.length() > o2.length()) {
return 1;
}else if (o1.length() == o2.length()) {
return 0;
}
return -1;
}});
Map<Character, Integer> toCompare = copyCount(chars);
for (String word: words) {
Map<Character, Integer> toBeCompare = copyCount(word.toCharArray());
if(isContained(toBeCompare, toCompare)) {
}

}
return values;
}

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

private Map<Character, Integer> copyCount(char[] chars) {
Map<Character, Integer> charCounts = new HashMap<Character, Integer>(chars.length);
for (char c : chars) {
int value = 0;
if (charCounts.containsKey(c)) {
value = charCounts.get(c);
charCounts.put(c, ++value);
} else {
charCounts.put(c, 1);
}
}
return charCounts;
}

public boolean isContained(Map<Character, Integer> toBeCompared, Map<Character, Integer> toCompare) {

for(Character c: toBeCompared.keySet()){
if(!toBeCompared.containsKey(c) || !toCompare.containsKey(c)) {
return false;
}
if (toBeCompared.get(c) > toCompare.get(c)){
return false;
}
}
return true;
}

public PriorityQueue<String> longestWords() {
String[] words = {"abc", "baa", "caan", "an", "banc", "tolosa"};
char[] chars = {'a', 'a', 'n', 'c', 'b'};

PriorityQueue<String> values = new PriorityQueue<String>(words.length, new Comparator<String>() {

@Override
public int compare(String o1, String o2) {
if (o1.length() > o2.length()) {
return 1;
}else if (o1.length() == o2.length()) {
return 0;
}
return -1;
}});
Map<Character, Integer> toCompare = copyCount(chars);
for (String word: words) {
Map<Character, Integer> toBeCompare = copyCount(word.toCharArray());
if(isContained(toBeCompare, toCompare)) {
}

}
return values;
}

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

``````-(NSSet *)largestWordsForWords:(NSArray *)words chars:(NSArray *)chars
{

//check for valid input
if(!words || !chars)
return nil;

//check for valid chars
for(NSString *s in chars)
if(s.length > 1)return nil;

//create our result
NSMutableSet *results = [[NSMutableSet alloc]init];

//create a counted set of the chars
NSCountedSet *cSet = [[NSCountedSet alloc]initWithArray:chars];

//save our current longest result
int longestResult = 0;

//test every string
for(NSString *s in words)
{
//if our current string is less than the max, no need to process it
if(s.length < longestResult)
{
continue;
}

//make a copy of the counted set
NSCountedSet *tempSet = [cSet copy];

for(int i = 0; i < s.length; i++)
{
//the the current character
NSString *tempChar = [NSString stringWithFormat:@"%c",[s characterAtIndex:i]];
//do we have enough of this char left?
if([tempSet countForObject:tempChar] <= 0)
{
break;
}
//update the count for the current char
[tempSet removeObject:tempChar];
}
//is this result longer than the previous results?
if(s.length > longestResult)
{
longestResult = (int)s.length;
[results removeAllObjects];
}

//we have found a valid string
}

return results;
}``````

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

``````public static int getLength(String word, char [] chs){
int [] map = new int [26];
int count = 0;
char [] chars = word.toCharArray() ;
for (int i = 0  ; i < chars.length ; ++i){
map[chars[i] - 'a']++;
}

for (char c: chs){
if (map[c - 'a'] != 0){
map[c - 'a'] -- ;
count++ ;
}
}

return count ;``````

}

use the above method to get length for all words ,then sorted or using a binary heap

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

{{
wrds = [ "abc" , "baa" , "caan" , "an" , "banc" , "bank"]
chars= [ "a" , "a" , "n" , "c" , "b"]

matching_words = []
max_len = 0

for i in wrds:
chars_copy = list(str(i) for i in chars)
for j in i:
if j not in chars_copy:
break
else:
chars_copy.remove(j)
else:
if len(i) > max_len:
max_len = len(i)
matching_words = [i]
elif len(i) == max_len:
matching_words.append(i)

print matching_words
}}

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

A python solution:

``````wrds = [ "abc" , "baa" , "caan" , "an" , "banc" , "bank"]
chars= [ "a" , "a" , "n" , "c" , "b"]

matching_words = []
max_len = 0

for i in wrds:
chars_copy = chars[:] # create a shallow copy
for j in i:
if j not in chars_copy:
break
else:
chars_copy.remove(j)
else:
if len(i) > max_len:
max_len = len(i)
matching_words = [i]
elif len(i) == max_len:
matching_words.append(i)

print matching_words``````

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

#!/usr/bin/python
from itertools import permutations
char=['a','a','n','c','b']
word= [ "abc" , "baa" , "caan" , "an" , "banc" ]
for i in char :
if char.count(i) > 1:
char.remove(i)

s="".join(char)
s1=[''.join(p) for p in permutations(s)]

for x in s1:
for y in word:
if x==y:
print(x)

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

Don't see any note about extra collection so it is reasonable to use map. Key search is amortised O(1). Also it reasonable to use custom counter class to prevent active memory allocations and reset it after any word we test.

``````using System.Collections.Generic;

namespace Appl{
internal class Counter {
int _base = 0;
int _current;

_base++;
_current = _base;
}

public bool Use() {
return (--_current) >= 0;
}

public void Reset(){
_current = _base;
}
}

class WordRutine{
static string GetBiggestWord(string[] words, char[] chars){
var map = new Dictionary<char,Counter> (chars.Length);

foreach (var c in chars) {
if (!map.ContainsKey (c))

}

int largestIndex = -1;
int largestLength = 0;

for (int i = 0; i < words.Length; i++) {
var word = words[i];

if (word.Length < largestLength)
continue;

if (word.Length > chars.Length)
continue;

if (CanBeCreated (map, word)) {
largestIndex = i;
largestLength = word.Length;
}

foreach (var pair in map) {
pair.Value.Reset ();
}
}

if (largestIndex > 0)
return words [largestIndex];

return null;
}

static bool CanBeCreated(Dictionary<char,Counter> map, string word){
foreach(var c in word){
if(!map[c].Use()) return false;
}

return true;
}
}
}``````

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

``````package com.knowledgebase.company.apple;

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

/**
* given 2 arrays wrds[] , chars[] as an input to a function such that wrds[] =
* [ "abc" , "baa" , "caan" , "an" , "banc" ] chars[] = [ "a" , "a" , "n" , "c"
* , "b"] Function should return the longest word from words[] which can be
* constructed from the chars in chars[] array. for above example - "caan" ,
* "banc" should be returned
*
* Note: Once a character in chars[] array is used, it cant be used again. eg:
* words[] = [ "aat" ] characters[] = [ "a" , "t" ] then word "aat" can't be
* constructed, since we've only 1 "a" in chars[].
*
* @author rachana
*
*/
public class WordGame {

public static void main(String... strings) {
List<String> list = Arrays.asList("abc", "baa", "caan", "an", "banc");
List<String> chars = Arrays.asList("a", "a","n", "c", "b");
List<String> required = new ArrayList<String>();

int max = 0;
for (String word : list) {
if (max < word.length()) {
max = word.length();
}
}
System.out.println(Arrays.toString(required.toArray()));
HashMap<String, Integer> map = new HashMap<String, Integer>();
for (String c : chars) {
if (map.containsKey(c)) {
map.put(c, map.get(c) + 1);
} else {
map.put(c, 1);
}
}

HashMap<String, Integer> map1 = new HashMap<String, Integer>();
for (String word : list) {
if (word.length() == max) {
String[] letOfWords = word.split("");
boolean isGood = false;
map1.putAll(map);
for (String c : letOfWords) {
if (map1.containsKey(c) && map1.get(c) > 0) {
isGood = true;
map1.put(c, map1.get(c) - 1);
} else {
isGood = false;
}
}
if(isGood) {
System.out.println(Arrays.toString(letOfWords));
}
}
}
}
}``````

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

Java Solution, returns maximum length and prints the strings that are possible to construct a long the way.

``````int CanWeMakeIt()
{
String[] wrds ={ "abc" , "baa" , "caanb" , "an" , "banc" };
char[] chars = { 'a' , 'a' , 'n' , 'c' , 'b'};
int maxLength=0;
boolean constructable=false;
for(String s: wrds)
{
char[] charCopy=chars;

for(char c: s.toCharArray())
{
if(charCopy.length>0)
{
charCopy= this.remove(charCopy, c);
constructable=true;
}
}

if(charCopy.length>=0)
{
if(s.length()>=maxLength)
{
maxLength=s.length();
System.out.println(s);
}
}
}
return maxLength;
}

public char[] remove(char[] symbols, char c)
{
for (int i = 0; i < symbols.length; i++)
{
if (symbols[i] == c)
{
char[] copy = new char[symbols.length-1];
System.arraycopy(symbols, 0, copy, 0, i);
System.arraycopy(symbols, i+1, copy, i, symbols.length-i-1);
return copy;
}
}
return symbols;
}``````

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

brute force

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

We can do this using 1 hash only.

``````#python code
import sys

def test():
wrds = [ "abc" , "baa" , "caan" , "banca", "an" , "anp", "banc"]
chars = [ "a" , "a" , "n" , "c" , "b"]

dict = {}
for c in chars:
if c not in dict:
dict[c] = 1
else:
dict[c] += 1

#print (dict)
var = 0
for word in wrds:
for c in word:
if c in dict and dict[c]>0:
count = dict[c]
count -= 1
else:
print("Word", word, "not possible as", c, "does not exist in dict")
break

l = len(word)
if l>var:
var=l
#list comprehension technique
op = [ w   for w in wrds  if len(w)==var]
print (op)

#boiler plate for main
if __name__ == '__main__':
test()``````

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

``````public List<String> findLongestWord (String [] wrds  , char [] chars ){
int maxLen = 0 ;
HashMap <Character, Integer> dict = new HashMap<> ();
HashMap <Integer, List<String> > rst  = new HashMap<> ();
for (char ch : chars) {
int c = dict.containsKey(ch) ? dict.get(ch) + 1 : 1 ;
dict.put(ch, c) ;
}
HashMap <Character, Integer> runtime = new HashMap<> ();
for (String w : wrds) {
int count = 0 ;
for (char c : w.toCharArray()) {
if (!dict.containsKey(c)) break ;
int curr = runtime.containsKey(c) ? runtime.get(c) + 1 : 1 ;
if (curr > dict.get(c)) break ;
count++;
if (count == w.length()) {
maxLen = Math.max(maxLen, count) ;
if (!rst.containsKey(count)) {
List<String> list = new ArrayList<> ();
rst.put(count, list) ;
} else{
}
}
runtime.put(c, curr) ;
}
runtime.clear();
}
return maxLen == 0 ? new ArrayList<String>() : rst.get(maxLen) ;
}``````

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

``````public List<String> findLongestWord (String [] wrds  , char [] chars ){
int maxLen = 0 ;
HashMap <Character, Integer> dict = new HashMap<> ();
HashMap <Integer, List<String> > rst  = new HashMap<> ();
for (char ch : chars) {
int c = dict.containsKey(ch) ? dict.get(ch) + 1 : 1 ;
dict.put(ch, c) ;
}
HashMap <Character, Integer> runtime = new HashMap<> ();
for (String w : wrds) {
int count = 0 ;
for (char c : w.toCharArray()) {
if (!dict.containsKey(c)) break ;
int curr = runtime.containsKey(c) ? runtime.get(c) + 1 : 1 ;
if (curr > dict.get(c)) break ;
count++;
if (count == w.length()) {
maxLen = Math.max(maxLen, count) ;
if (!rst.containsKey(count)) {
List<String> list = new ArrayList<> ();
rst.put(count, list) ;
} else{
}
}
runtime.put(c, curr) ;
}
runtime.clear();
}
return maxLen == 0 ? new ArrayList<String>() : rst.get(maxLen) ;``````

}

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

``````-(void)longestWordsFromArray:(NSArray*)words andLetters:(NSArray*)letters {
if (!words || !letters || words.count == 0 || letters.count == 0) {
return;
}

NSMutableDictionary *letterHash = [[NSMutableDictionary alloc] init];
NSMutableArray *results = [[NSMutableArray alloc] init];
NSUInteger maxSize = 0;
// Traverse words array

for (NSString* word in words) {
// Create hash
for (NSString* letter in letters) {
NSInteger previousNumber = [[letterHash objectForKey:letter] integerValue];
previousNumber = previousNumber < 0 ? 0 : ++previousNumber;
[letterHash setObject:[NSNumber numberWithInteger:previousNumber] forKey:letter];
}

NSUInteger size = word.length;

BOOL isWordPresent = YES;

for (int i=0; i < size; i++) {
NSString* str = [NSString stringWithFormat:@"%C",[word characterAtIndex:i]];
NSNumber *value = [letterHash objectForKey:str];
if ([value integerValue] <= 0) {
isWordPresent = NO;
break;
}
else {
value = [NSNumber numberWithInteger:([value integerValue]-1)];
}
}

if (!isWordPresent) {
break;
}
else {
if (maxSize < size) {
maxSize = size;
[results removeAllObjects];
}
else if (maxSize == size) {
}
}
}

NSLog(@"Result %@", results);
}``````

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

``````-(void)longestWordsFromArray:(NSArray*)words andLetters:(NSArray*)letters {
if (!words || !letters || words.count == 0 || letters.count == 0) {
return;
}

NSMutableDictionary *letterHash = [[NSMutableDictionary alloc] init];
NSMutableArray *results = [[NSMutableArray alloc] init];
NSUInteger maxSize = 0;
// Traverse words array

for (NSString* word in words) {
// Create hash
for (NSString* letter in letters) {
NSInteger previousNumber = [[letterHash objectForKey:letter] integerValue];
previousNumber = previousNumber < 0 ? 0 : ++previousNumber;
[letterHash setObject:[NSNumber numberWithInteger:previousNumber] forKey:letter];
}

NSUInteger size = word.length;

BOOL isWordPresent = YES;

for (int i=0; i < size; i++) {
NSString* str = [NSString stringWithFormat:@"%C",[word characterAtIndex:i]];
NSNumber *value = [letterHash objectForKey:str];
if ([value integerValue] <= 0) {
isWordPresent = NO;
break;
}
else {
value = [NSNumber numberWithInteger:([value integerValue]-1)];
}
}

if (!isWordPresent) {
break;
}
else {
if (maxSize < size) {
maxSize = size;
[results removeAllObjects];
}
else if (maxSize == size) {
}
}
}

NSLog(@"Result %@", results);``````

}

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

Python solution:

words = ["baa", "caan", "cann", "ba", "cab", "noob"]
chars = ["b", "a", "c", "n"]

for word in words:
temp = list(chars)
if len(word) > len(chars):
continue
for char in word:
if char not in temp:
break
else:
temp.remove(char)
if len(chars) - len(word) == len(temp):
print word

C++ solution:
int main() {
string words[] = {"baa", "caan", "cann", "ba", "cab", "noob"};
char chars[] = {'b', 'a', 'c', 'n', 'a'};
multiset<char> vchar;
for(char x : chars)
vchar.insert(x);

for(string word : words){
multiset<char> temp(vchar);
if(word.size() > temp.size()){
continue;
}
for(char c : word){
if(temp.find(c) == temp.end())
break;
else
temp.erase(temp.find(c));
}
if(vchar.size() - word.size() == temp.size())
cout<<word<<endl;
}
return 0;
}

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

Python

``````words = ["baa", "caan", "cann", "ba", "cab", "noob"]
chars = ["b", "a", "c", "n"]

for word in words:
temp = list(chars)
if len(word) > len(chars):
continue
for char in word:
if char not in temp:
break
else:
temp.remove(char)
if len(chars) - len(word) == len(temp):
print word``````

c++ Solution

``````int main() {
string words[] = {"baa", "caan", "cann", "ba", "cab", "noob"};
char chars[] = {'b', 'a', 'c', 'n', 'a'};
multiset<char> vchar;
for(char x : chars)
vchar.insert(x);

for(string word : words){
multiset<char> temp(vchar);
if(word.size() > temp.size()){
continue;
}
for(char c : word){
if(temp.find(c) == temp.end())
break;
else
temp.erase(temp.find(c));
}
if(vchar.size() - word.size() == temp.size())
cout<<word<<endl;
}
return 0;
}``````

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

``````public static String longest(String [] strings, char[] chars){
Map<Character, AtomicInteger> charSet = new HashMap<>();
for(char c: chars){
charSet.computeIfAbsent(c, key-> new AtomicInteger(0)).incrementAndGet();
}
String longest = "";

for(String s : strings){
if(s.length() > chars.length || s.length() < longest.length()){
continue;
}
Map<Character, AtomicInteger> m = new HashMap<>();
for (char c: s.toCharArray()) {
if(!charSet.containsKey(c)){
break;
}
if(m.containsKey(c)){
if(charSet.get(c).intValue() <= m.get(c).intValue()){
break;
}else{
m.get(c).incrementAndGet();
}
}else{
m.put(c, new AtomicInteger(1));
}
}
longest = s;
}
return longest;
}``````

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

How about the below, written in scala.

``````def main(args: Array[String]): Unit = {
val words = Array("abc", "baa", "caan", "an", "banc")
val chars = Array("a", "a", "n", "c", "b")

//breaking each word in words into a pair of it's chars and their existence (initially zero).
val wordMapList = words.sortWith(_ > _).map(_.map(_.toString -> 0))
//iterating on chars array and marking current chars existence in the previous list if string is present and the char is not already used.
val r = chars.foldLeft(wordMapList)((b, a) => b.map(w => if (w.exists(e => e._1 == a && e._2 == 0)) w.map(x => if (x._1 == a) (x._1, x._2 + 1) else x) else w))
println(r.find(_.forall(_._2 == 1)).map(_.foldLeft("")((b, a) => s"\$b\${a._1}")).getOrElse("NotFound"))
}``````

Comment hidden because of low score. Click to expand.
0

Hi @careercup, could you please format my code? I followed your suggestion and wrapped the code part with

``and``

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.

### 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.