Apple Interview Question Software Engineer in Tests
Country: United States
Interview Type: Phone Interview
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.
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 .
Substring will not work since aacn (Sorted word) is not a substring of aabcn (Sorted characters).
//
// main.m
// CommondLineProject
//
// Created by Dun Liu on 6/23/14.
// Copyright (c) 2014 Dun Liu. All rights reserved.
//
#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 addObject:[word substringWithRange:NSMakeRange(i,1)]];
}
[wordChars sortUsingSelector:@selector(compare:)];
if ([self array:wordChars isSubArrayOf:sortedChars]) {
if (wordChars.count > longest ) {
[result removeAllObjects];
longest = wordChars.count;
}
if (wordChars.count == longest ) {
[result addObject:word];
}
}
}
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;
}
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.
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;
}
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
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
/*
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;
}
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;
}
}
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)) {
values.add(word);
}
}
return values;
}
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)) {
values.add(word);
}
}
return values;
}
It's Apple right? How about an Objective-C answer?
-(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
[results addObject:s];
}
return results;
}
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
{{
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
}}
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
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;
public void Add(){
_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))
map.Add (c, new Counter ());
map[c].Add ();
}
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;
}
}
}
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();
required.add(word);
}
}
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));
}
}
}
}
}
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;
}
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()
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<> ();
list.add(w) ;
rst.put(count, list) ;
} else{
rst.get(count).add(w) ;
}
}
runtime.put(c, curr) ;
}
runtime.clear();
}
return maxLen == 0 ? new ArrayList<String>() : rst.get(maxLen) ;
}
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<> ();
list.add(w) ;
rst.put(count, list) ;
} else{
rst.get(count).add(w) ;
}
}
runtime.put(c, curr) ;
}
runtime.clear();
}
return maxLen == 0 ? new ArrayList<String>() : rst.get(maxLen) ;
}
-(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];
[results addObject:word];
}
else if (maxSize == size) {
[results addObject:word];
}
}
}
NSLog(@"Result %@", results);
}
-(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];
[results addObject:word];
}
else if (maxSize == size) {
[results addObject:word];
}
}
}
NSLog(@"Result %@", results);
}
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;
}
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;
}
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;
}
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"))
}
If the number of alphabets possible is less, this will work
- JP February 06, 20141) 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.