Google Interview Question Software Engineers
Country: United States
The brute force solution (option 1) can be done in O(n^2 * m), rather than stated O(n^2 * m ^ 2) -
when checking if two words (of length m) share any characters, we can count-sort and check duplicates in O(m)
Thank you, I like idea with bit set.
I would suggest some improvements that can improve performance.
steps of algorithm:
1) Build bit set for every word as you did before (O(N*maxlength) which is linear in terms of characters).
2) Build Trie using bitset:
iterate through all bit masks and on every step:
a) traverse trie in a way that you visit only nodes that evaluate as 0 with current i;
if current bit is 0 then go both children 0 and 1
if current bit is 1 then go 0 only
for every leaf node check if you just found new maximum and update it (store length information in leafs)
b) insert current mask into tree
c) store index and max length of original strings in leafs
In the worst case this algo has the same complexity(but with lower constant factor) but it is much better in average and best case. Because you will traverse only nodes where characters are not shared. So complexity will be O(K) where K is max(N,Number of all possible pairs of words without shared characters) so worst case when you have all N(N-1)/2 pairs and non of them shares character with another. But on practice this is possible only when words are short, because with 26 letters alphabet it is hard to get a lot of words without sharing any character :)))
Best and Average case will have linear time performance.
Thank you, I like idea with bit set.
I would suggest some improvements that can improve performance.
steps of algorithm:
1) Build bit set for every word as you did before (O(N*maxlength) which is linear in terms of characters).
2) Build Trie using bitset:
iterate through all bit masks and on every step:
a) traverse trie in a way that you visit only nodes that evaluate as 0 with current i;
if current bit is 0 then go both children 0 and 1
if current bit is 1 then go 0 only
for every leaf node check if you just found new maximum and update it (store length information in leafs)
b) insert current mask into tree
c) store index and max length of original strings in leafs
In the worst case this algo has the same complexity(but with lower constant factor) but it is much better in average and best case. Because you will traverse only nodes where characters are not shared. So complexity will be O(K) where K is max(N,Number of all possible pairs of words without shared characters) so worst case when you have all N(N-1)/2 pairs and non of them shares character with another. But on practice this is possible only when words are short, because with 26 letters alphabet it is hard to get a lot of words without sharing any character :)))
Best and Average case will have linear time performance.
I'm very sorry for two previous posts. It is an accident. Admins could you Please delete them as they were posted anonymously and I cannot delete them :(
Thank you, I like idea with bit set.
I would suggest some improvements that can improve performance.
steps of algorithm:
1) Build bit set for every word as you did before (O(N*maxlength) which is linear in terms of characters).
2) Build Trie using bitset:
iterate through all bit masks and on every step:
a) traverse trie in a way that you visit only nodes that evaluate as 0 with current i;
if current bit is 0 then go both children 0 and 1
if current bit is 1 then go 0 only
for every leaf node check if you just found new maximum and update it (store length information in leafs)
b) insert current mask into tree
c) store index and max length of original strings in leafs
In the worst case this algo has the same complexity(but with lower constant factor) but it is much better in average and best case. Because you will traverse only nodes where characters are not shared. So complexity will be O(K) where K is max(N,Number of all possible pairs of words without shared characters) so worst case when you have all N(N-1)/2 pairs and non of them shares character with another. But on practice this is possible only when words are short, because with 26 letters alphabet it is hard to get a lot of words without sharing any character :)))
Best and Average case will have linear time performance.
c#.
Brute force.
static private int Get( string[] arr ) {
int greatest = 0;
var list = new List<Tuple<int, HashSet<char>>>();
foreach ( var word in arr ) {
list.Add( new Tuple<int, HashSet<char>>( word.Length, new HashSet<char>( word ) ) );
}
for ( int i = 0; i < list.Count - 1; i++ ) {
for ( int j = i + 1; j < list.Count; j++ ) {
if ( list[ i ].Item2.Overlaps( list[ j ].Item2) ) {
continue;
}
var res = list[ i ].Item1 * list[ j ].Item1;
if ( res > greatest ) {
greatest = res;
}
}
}
return greatest;
}
at least O(n^2), depending how efficient the hashset.Overlaps() operation is. Of it is O(1), then total complexity is O(n^2).
memoreku makes a great observation that the set for a basic character string can just be an array of bool that fits in a 32-bit integer (or 64-bit if you want mixed case). I decided to stick with the more conservative standard library data structure, mostly for expository purposes.
This algorithm solves the problem in amortized worst-case O(n lg n) by sorting the list of words in decreasing order of size first. This allows you to test the best possible answers in decreasing order by traversing the words appropriately.
It is also worth noting that you only need to store the set of one word at a time and only calculate the set of each word once.
There are trade-offs to be made depending on the average word length M.
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <string>
#include <iostream>
#include <unordered_set>
using namespace std;
using word_hash = unordered_set<char>;
// let m = average length of a word
// let w = length of a specific word
// let n = number of words
// amortized worst-case time complexity: O(w)
bool disjoint(string const &word_a, word_hash const &word_b)
{
auto const in_b = [&](char const c){ return word_b.find(c) != end(word_b); };
return find_if(begin(word_a), end(word_a), in_b) == end(word_a);
}
int main(int argc, char **argv)
{
// argc == n + 1; we require at least two words.
if (argc < 3)
exit(1);
vector<string> words(argv + 1, argv + argc);
auto greater_size = [](string const &a, string const &b){ return a.size() > b.size(); };
sort(begin(words), end(words), greater_size); // O(n lg n)
size_t a = 0, b = 1; // invariant: a < b
word_hash b_word(begin(words[b]), end(words[b])); // Only need to hash one word at a time.
while (b < words.size() && !disjoint(words[a], b_word)) // amortized O(nm)
{
if (a == b - 1)
{
b++;
a = 0;
b_word.clear();
b_word.insert(begin(words[b]), end(words[b]));
}
else
a++;
}
// Success?
if (b < words.size())
{
auto const answer = words[a].size() * words[b].size();
cout << words[a] << " * " << words[b] << " = " << answer << "\n";
}
else
exit(2);
}
I believe you are confusing amortized analysis with average case analysis. The difference is average case analysis relies on probabilistic assumptions about the shape of your input data, while amortized analysis considers the total performance of a sequence of operations.
Your analysis of
in_b
relies on the fact that the characters of the input words are uniformly distributed over the 26 characters of the alphabet.
// ZoomBA : Not optimal this. But shows the power of expression
words = ["ABCW", "BAZ", "FOO", "BAR", "XTFN", "ABCDEF" ]
max_tuple = [ num("-inf") , null, null ]
r = [ 0 : #|words| ]
join( r , r ) :: {
continue ( $.o.0 >= $.o.1 )
left = words[ $.o.0 ] ; right = words[ $.o.1 ]
continue ( !empty( left.value & right.value ) )
val = #|left| * #|right|
continue ( max_tuple.0 >= val )
max_tuple.0 = val ; max_tuple.1 = left ; max_tuple.2 = right
false
}
println( max_tuple )
C# implementation
public int MultiplyTwoWords(string[] words)
{
var arr = new HashSet<char>[words.Length];
for (int i = 0; i < words.Length; i++)
arr[i] = new HashSet<char>(words[i]);
int max = 0;
for (int i=0; i < arr.Length - 1; i++)
for (int j=i+1; j < arr.Length; j++)
if (!arr[i].Overlaps(arr[j]))
{
int value = arr[i].Count * arr[j].Count;
if (value > max)
max = value;
}
return max;
}
C# implementation
public int MultiplyTwoWords(string[] words)
{
var arr = new HashSet<char>[words.Length];
for (int i = 0; i < words.Length; i++)
arr[i] = new HashSet<char>(words[i]);
int max = 0;
for (int i=0; i < arr.Length - 1; i++)
for (int j=i+1; j < arr.Length; j++)
if (!arr[i].Overlaps(arr[j]))
{
int value = arr[i].Count * arr[j].Count;
if (value > max)
max = value;
}
return max;
}
public int getMaxLengthProduct(String[] arr)throws NullPointerException
{
if(arr==null)
{
throw new NullPointerException();
}
if(arr.length==0)
{
return -1;
}
Array.sort(a);
return findMaxLength(arr);
}
private int findMaxLength(String[] arr)
{
for(int i=0;i<arr.length;i++)
{
boolean[] b=setValues(arr[i]);
for(int j=i+1;j<arr.length;j++)
{
boolean hasMatches=(b,arr[j]);
if(!hasMatches)
{
return (arr[i].length() * arr[j].length());
}
}
}
return -1;
}
private boolean[] setValues(String s)
{
boolean[] b=new boolean[27];
for(int i=0;i<b.length;i++)
{
b[i]=false;
}
for(int i=0;i<s.length();i++)
{
b[s.charAt(i)-'A']=true;
}
return b;
}
private boolean hasMatches(boolean[] b, String s)
{
for(int i=0;i<s.length();i++)
{
if(b[s.charAt(i)-'a'])
{
return true;
}
}
return false;
}
//Running time complexity (O((n^2m^2)), Space is O(1)
//My earlier solution stops as soon as it finds two strings with mismatching characters, even if these two strings aren't necessarily the ones which yield the max product of their lengths.
Here is my updated solution.
public int getMaxLengthProduct(String[] arr)throws NullPointerException
{
if(arr==null)
{
throw new NullPointerException();
}
if(arr.length==0)
{
return -1;
}
Array.sort(a);
return findMaxLength(arr);
}
private int findMaxLength(String[] arr)
{
int maxMatch=-1;
for(int i=0;i<arr.length;i++)
{
boolean[] b=setValues(arr[i]);
for(int j=i+1;j<arr.length;j++)
{
boolean hasMatches=(b,arr[j]);
if(!hasMatches)
{
maxMatch=Math.max(maxMatch,arr[i].length()*arr[j].length())
}
}
}
return maxMatch;
}
private boolean[] setValues(String s)
{
boolean[] b=new boolean[27];
for(int i=0;i<b.length;i++)
{
b[i]=false;
}
for(int i=0;i<s.length();i++)
{
b[s.charAt(i)-'A']=true;
}
return b;
}
private boolean hasMatches(boolean[] b, String s)
{
for(int i=0;i<s.length();i++)
{
if(b[s.charAt(i)-'A'])
{
return true;
}
}
return false;
}
//Running time complexity (O((n^2m^2))
// give input as string seperated with " " ie. "abc dof boo" to method getData
import java.util.ArrayList;
import java.util.HashMap;
import java.util.ListIterator;
import java.util.Map;
public class ClashOfWords {
Map<Integer,ArrayList> map = new HashMap<Integer,ArrayList>();
int max = 0;
int maxResult = 0;
private String mainString="";
public void getData(String s){
int l;
String[] array = s.split(" ");
for(int i=0;i<array.length;i++){
l = array[i].length();
if(l>max) max=l;
if(map.containsKey(l)){
ArrayList list = map.get(l);
list.add(array[i]);
}
else{
ArrayList<String> list = new ArrayList<String>();
list.add(array[i]);
map.put(l, list);
}
}
showData();
System.out.println(mainString);
getResult();
System.out.println(maxResult);
}
public void showData(){
for(int i = max;i>0;i--){
ArrayList l = map.get(i);
if(l != null){
printAll(l);
}
}
}
private void printAll(ArrayList l) {
// TODO Auto-generated method stub
ListIterator iterator = l.listIterator();
while(iterator.hasNext()){
mainString = mainString + iterator.next() +" " ;
}
}
public void getResult(){
//select next word
String[] strings = mainString.split(" ");
for(int i=0;i<strings.length-1;i++){
for(int j=i+1;j<strings.length;j++){
if(!hascommon(strings[i],strings[j])){
int prod = strings[i].length()*strings[j].length();
if(prod>maxResult)maxResult=prod;
}
}
}
}
private boolean hascommon(String string, String string2) {
// TODO Auto-generated method stub
for(int i=0;i<string.length();i++){
if(string2.contains(string.charAt(i)+""))
return true;
}
return false;
}
}
arr = ['ABCW','BAZ', 'FOO', 'BAR', 'XTFN', 'ABCDEF']
res = []
mx = 0
def chk(s,t):
for x in s:
if x in t:
return False
return True
for s in range(len(arr)-1):
for t in range(1,len(arr)):
if mx<len(arr[t])*len(arr[s]):
if chk(arr[s],arr[t]):
print arr[s],arr[t],len(arr[t])*len(arr[s])
mx = len(arr[t])*len(arr[s])
print mx
#include<stdio.h>
#include<string.h>
int main()
{
char str[6][9]={"ABCW", "BAZ", "FOO", "BAR", "XTFN", "ABCDEF"};
int i,j,l,m,count,max,max1,firstlength,secondlength;
count=0;
max=0;
max1=0;
char *firstptr,*secondptr;
for(i=0;i<5;i++)
{
for(j=i+1;j<6;j++)
{
firstptr=&str[i];
secondptr=&str[j];
firstlength=strlen(firstptr);
secondlength=strlen(secondptr);
count=0;
for(l=0;l<firstlength;l++)
{
for(m=0;m<secondlength;m++)
{
if(firstptr[l]!=secondptr[m])
continue;
else
{
count++;
break;
}
}
if(count==1)
break;
}
if(count==0)
{
max=firstlength*secondlength;
if(max>max1)
max1=max;
}
}
}
printf("MAXIMUM VALUE OF length(s) * length(t) :=> %d",max1);
return 0;
}
please pardon the duplicates, posted them before signing in so I can't delete them.
public static Integer findLongestExclusiveMultiple(String[] array) {
if (array == null) {
return null;
}
if (array.length <= 1) {
return 0;
}
Map<String, Set<Character>> words = new HashMap<>();
for (String word : array) {
if (word == null) continue;
words.put(word, new HashSet<>());
for (char c : word.toCharArray()) {
words.get(word).add(c);
}
}
int greatest = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] == null) continue;
for (int j = i + 1; j < array.length; j++) {
if (array[j] == null) continue;
Set<Character> left = words.get(array[i]);
Set<Character> right = words.get(array[j]);
int multiple = array[i].length() * array[j].length();
if (greatest >= multiple) {
continue;
}
if (!Sets.intersection(left, right).isEmpty()) {
continue;
}
greatest = multiple;
}
}
return greatest;
}
We observe that a simple brute force solution to test all possible combination results in n^2 pairs, with testing for similarity causing another M^2. Giving us worst case O((NM)^2).
Further, we observe that the alphabet set for strings is limited by the choice of alphabets. Therefore we consider it a constant. 26 for single case english/roman alphabets for example. The time complexity now comes to O(MN) to fill the bitvec for N strings, and O(N^2) for comparison.
Another way to solve is :
We could have also arranged references of string in a set wise manner such that all strings containing an alphabet x are in set(x). etc. This way, if we compare against one string, we know we don't need to compare against other strings in that same set.
Using this technique, we could have reduced the runtime complexity to O(N) assuming that N is very large (as given in definition). There are NM total alphabets. But, there are only 27 unique alphabets. Even if it were all unique strings, every 28th string will collide.There are M such alphabets where it can collide, so, collusion space is directly proportional to MN, and therefore, number of entries in a set alphabet x is also directly proportional to MN.
So total time complexity O(N*N*M*M/MN) = O(NM).
We observe that a simple brute force solution to test all possible combination results in n^2 pairs, with testing for similarity causing another M^2. Giving us worst case O((NM)^2).
Further, we observe that the alphabet set for strings is limited by the choice of alphabets. Therefore we consider it a constant. 26 for single case english/roman alphabets for example. The time complexity now comes to O(MN) to fill the bitvec for N strings, and O(N^2) for comparison.
Another way to solve is :
We could have also arranged references of string in a set wise manner such that all strings containing an alphabet x are in set(x). etc. This way, if we compare against one string, we know we don't need to compare against other strings in that same set.
Using this technique, we could have reduced the runtime complexity to O(N) assuming that N is very large (as given in definition). There are NM total alphabets. But, there are only 27 unique alphabets. Even if it were all unique strings, every 28th string will collide.There are M such alphabets where it can collide, so, collusion space is directly proportional to MN, and therefore, number of entries in a set alphabet x is also directly proportional to MN.
So total time complexity O(N*N*M*M/MN) = O(NM).
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <math.h>
using namespace std;
bool testIntersect(string x,string y){
cout<<"Testing: "<<x<<" "<<y;
vector<char> res;
set<char> a(x.begin(),x.end());
set<char> b(y.begin(),y.end());
set_intersection(a.begin(),a.end(),b.begin(),b.end(),back_inserter(res));
cout<<" InterSect Length:"<<res.size()<<endl;
return res.size()>0;
}
int getMax(vector<string> words){
if(words.size()<=1)
return 0;
int maxLen=0;
for(int i=0;i<words.size()-1;++i){
for(int j=i+1;j<words.size();++j){
if (!testIntersect(words[i],words[j])){
maxLen = max(maxLen,(int)words[i].length()*(int)words[j].length());
cout<<"max:"<<maxLen<<endl;
}
}
}
return maxLen;
}
int main(){
vector<string> words{"ABCW","BAZ","FOO","DOE","BAR","XTFN","ABCDEF"};
cout<<getMax(words)<<endl;
}
Forewarning: I have not taken advantage of error handling for this. I'd leave this to be some extra work for whoever wants to try this.
Assumptions:
Words will never contain anything other than ASCII letters.
Lower case and upper case are considered equal characters
public static int getMaxProduct( String[] strs )
{
int[] maskMap = new int[strs.length];
int max = -1;
for( int i=0; i < strs.length; i++ )
{
maskMap[i] = getMask( strs[i] );
}
for( int i = 0; i < strs.length; i++ )
{
for( int j = i+1; j < strs.length; j++ )
{
if( uniqueChars( maskMap[i], maskMap[j] ) )
{
int prod = strs[i].length() * strs[j].length();
if( max < prod )
max = prod;
}
}
}
return max;
}
public static int getMask( String str )
{
int mask = 0;
for( int i=0; i < str.length(); i++ )
{
int repType = getCharIntRep( str.charAt(i) );
if( repType != -1 )
mask |= 1 << repType;
}
return mask;
}
public static int getCharIntRep( char c )
{
int charInt = (int)Character.toLowerCase(c) - 97;
if( charInt >= 0 && charInt <= 25 )
{
return charInt;
}
else
{
return -1;
}
}
public static boolean uniqueChars( int lhs, int rhs )
{
return ( lhs & rhs ) == 0;
}
#include <iostream>
#include <iterator>
#include <set>
#include <string>
struct Compare{
bool operator()(std::string string1, std::string string2) const {
if (string1.compare(string2) == 0) {
return false;
} else {
return string1.length() >= string2.length();
}
}
};
void findMaximunLength(std::string * strings, int lengthOfStrings) {
bool sameCharacter;
std::set<std::string, Compare> * stringSet;
std::set<std::string>::iterator firstIterator, secondIterator;
sameCharacter = false;
stringSet = new std::set<std::string, Compare>(strings, strings + lengthOfStrings);
std::cout << "Containing: ";
for (std::string string : *stringSet) {
std::cout << string << ' ';
}
std::endl(std::cout);
for (firstIterator = stringSet->begin(); firstIterator != stringSet->end(); firstIterator++) {
sameCharacter = false;
for (secondIterator = std::next(firstIterator, 1); secondIterator != stringSet->end(); secondIterator++) {
sameCharacter = false;
for (int i = 0; i < (*firstIterator).length(); i++) {
if ((*secondIterator).find((*firstIterator).at(i)) != std::string::npos) {
sameCharacter = true;
break;
}
}
if (sameCharacter == false) {
break;
}
}
if (sameCharacter == false) {
break;
}
}
if (sameCharacter == true) {
std::cout << "Can't find any match." << std::endl;
} else {
std::cout << "The words are " << (*firstIterator) << " and " << (*secondIterator) << " and maximun length will be " << (*firstIterator).length() * (*secondIterator).length() << std::endl;
}
delete stringSet;
}
int main(int argc, const char * argv[]) {
std::string strings[] = {"ABCW", "BAZ", "FOO", "BAR", "XTFN", "ABCDEF"};
findMaximunLength(strings, sizeof(strings) / sizeof(std::string));
return 0;
}
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>
#include <set>
#include <string>
bool compare(std::string string1, std::string string2) {
if (string1.compare(string2) == 0) {
return false;
} else {
return string1.length() >= string2.length();
}
}
void createRandomStrings(std::string *& strings, int & lengthOfStrings) {
int lengthOfCharacters;
std::srand((double)std::time(nullptr));
lengthOfCharacters = 0;
lengthOfStrings = std::rand() % 10 + 1;
strings = new std::string[lengthOfStrings];
for (int i = 0; i < lengthOfStrings; i++) {
lengthOfCharacters = std::rand() % 10 + 1;
for (int j = 0; j < lengthOfCharacters; j++) {
strings[i] += char(std::rand() % 26 + 65);
}
}
std::cout << "Before ordering: ";
for (int i = 0; i < lengthOfStrings; i++) {
std::cout << strings[i] << ' ';
}
std::cout << std::string(80, '=') << std::endl;
}
void findMaximunLength(std::string * strings, int lengthOfStrings) {
bool sameCharacter;
bool (*functionPointerToCompare)(std::string, std::string);
std::set<std::string, bool(*)(std::string, std::string)> * stringSet;
std::set<std::string>::iterator firstIterator, secondIterator;
sameCharacter = true;
functionPointerToCompare = compare;
stringSet = new std::set<std::string, bool(*)(std::string, std::string)>(strings, strings + lengthOfStrings, functionPointerToCompare);
std::cout << "After ordering: ";
for (std::string string : *stringSet) {
std::cout << string << ' ';
}
std::cout << std::string(80, '=') << std::endl;
for (firstIterator = stringSet->begin(); firstIterator != stringSet->end(); firstIterator++) {
for (secondIterator = std::next(firstIterator, 1); secondIterator != stringSet->end(); secondIterator++) {
sameCharacter = false;
for (int i = 0; i < (*firstIterator).length(); i++) {
if ((*secondIterator).find((*firstIterator).at(i)) != std::string::npos) {
sameCharacter = true;
break;
}
}
if (sameCharacter == false) {
break;
}
}
if (sameCharacter == false) {
break;
}
}
if (sameCharacter == true) {
std::cout << "Can't find any match." << std::endl;
} else {
std::cout << "The words are " << (*firstIterator) << " and " << (*secondIterator) << " and maximun length will be " << (*firstIterator).length() * (*secondIterator).length() << std::endl;
}
delete stringSet;
}
int main(int argc, const char * argv[]) {
int lengthOfStrings;
std::string * strings;
createRandomStrings(strings, lengthOfStrings);
findMaximunLength(strings, lengthOfStrings);
delete [] strings;
return 0;
}
import java.util.Arrays;
import java.util.Comparator;
public class Question
{
public class MyComparator implements Comparator<String>
{
public int compare (String a, String b)
{
if (a.length()>b.length())
return -1;
else if (b.length() > a.length())
return 1;
else
return 0;
}
}
private boolean haveCommonChars(String a, String b)
{
String one = (a.length()>=b.length())?b:a;
String two = (a.length()<b.length())?b:a;
for(int i=0; i<one.length(); i++)
{
if (two.indexOf(one.charAt(i)+"")>=0)
return true;
}
return false;
}
public int maxLength(String[] arr)
{
int maxVal = 0;
Arrays.sort(arr, new MyComparator());
for(int i=0; i<arr.length-1; i++)
{
for (int j=i+1; j<arr.length; j++)
{
if (!haveCommonChars(arr[i],arr[j]))
{
int newMaxVal=arr[i].length()*arr[j].length();
if (newMaxVal>maxVal)
{
maxVal=newMaxVal;
break;
}
}
}
}
return maxVal;
}
public static void main(String[] args)
{
System.out.println(new Question().maxLength(new String[]{"ABCW","BAZ","FOO","BAR","XTFN","ABCDEF"}));
}
}
import java.util.Arrays;
import java.util.Comparator;
public class Question
{
public class MyComparator implements Comparator<String>
{
public int compare (String a, String b)
{
if (a.length()>b.length())
return -1;
else if (b.length() > a.length())
return 1;
else
return 0;
}
}
private boolean haveCommonChars(String a, String b)
{
String one = (a.length()>=b.length())?b:a;
String two = (a.length()<b.length())?b:a;
for(int i=0; i<one.length(); i++)
{
if (two.indexOf(one.charAt(i)+"")>=0)
return true;
}
return false;
}
public int maxLength(String[] arr)
{
int maxVal = 0;
Arrays.sort(arr, new MyComparator());
for(int i=0; i<arr.length-1; i++)
{
for (int j=i+1; j<arr.length; j++)
{
if (!haveCommonChars(arr[i],arr[j]))
{
int newMaxVal=arr[i].length()*arr[j].length();
if (newMaxVal>maxVal)
{
maxVal=newMaxVal;
break;
}
}
}
}
return maxVal;
}
public static void main(String[] args)
{
System.out.println(new Question().maxLength(new String[]{"ABCW","BAZ","FOO","BAR","XTFN","ABCDEF"}));
}
}
Here's my implementation in Python, almost brute force but improving slightly from most people's runtime, in O(n^2 * m) by a space tradeoff in overlap function.
def max_mutliple_length(l):
max_len = float("-inf")
for i in range(len(l)):
for j in range(i+1,len(l)):
if not overlap(l[i], l[j]):
mult = len(l[i]) * len(l[j])
max_len = max(mult, max_len)
return max_len
def overlap(word1, word2):
letter_set = set(word1)
for c in word2:
if c in letter_set:
return True
return False
if __name__ == '__main__':
l = ["ABCW", "BAZ", "FOO", "BAR", "XTFN", "ABCDEF"]
print max_mutliple_length(l)
def max_mutliple_length(l):
max_len = float("-inf")
for i in range(len(l)):
for j in range(i+1,len(l)):
if not overlap(l[i], l[j]):
mult = len(l[i]) * len(l[j])
max_len = max(mult, max_len)
return max_len
def overlap(word1, word2):
letter_set = set(word1)
for c in word2:
if c in letter_set:
return True
return False
if __name__ == '__main__':
l = ["ABCW", "BAZ", "FOO", "BAR", "XTFN", "ABCDEF"]
print max_mutliple_length(l)
def max_mutliple_length(l):
max_len = float("-inf")
for i in range(len(l)):
for j in range(i+1,len(l)):
if not overlap(l[i], l[j]):
mult = len(l[i]) * len(l[j])
max_len = max(mult, max_len)
return max_len
def overlap(word1, word2):
letter_set = set(word1)
for c in word2:
if c in letter_set:
return True
return False
if __name__ == '__main__':
l = ["ABCW", "BAZ", "FOO", "BAR", "XTFN", "ABCDEF"]
print max_mutliple_length(l)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
public class FindMaxLength
{
public static void main (String[] args)
{
String[] words = {"ABCW","BAZ","FOO","DOE","BAR","XTFN","ABCDEF"};
HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
int total = 0;
int count = 0;
for (String word : words)
{
map.put(word, new ArrayList<String>(Arrays.asList(word.split("(?<=\\G.{1})"))));
}
for (String key1 : map.keySet())
{
for (String key2 : map.keySet())
{
if(!key1.equals(key2))
{
ArrayList<String> temp = new ArrayList<String>();
temp = (ArrayList<String>) map.get(key2).clone();
map.get(key2).removeAll(map.get(key1));
map.get(key1).removeAll(temp);
}
}
}
for (String key : map.keySet())
{
if (String.join("", map.get(key)).equals(key))
{
System.out.println(key + " " + map.get(key));
count++;
total = count > 1 ? total * map.get(key).size() : map.get(key).size();
}
}
System.out.println("Total: " + total);
}
}
I think it can be done in O(NlogN) time.
First you sort the array based on the length of each element in non increasing order,which costs O(nlogn).
Then you keep two pointers from begin move forward one of them based on product of length next elements and length current elements.
Check if they have no duplicates,which can be done in O(n) if we assume all chars are in ASCii table(use an array of length 256, two traverse). If no duplicates exists, return the product.
I think it can be done in O(NlogN) time.
First you sort the array based on the length of each element in non increasing order,which costs O(nlogn).
Then you keep two pointers from begin move forward one of them based on product of length next elements and length current elements.
Check if they have no duplicates,which can be done in O(n) if we assume all chars are in ASCii table(use an array of length 256, two traverse). If no duplicates exists, return the product.
/*
* @author shivam.maharshi
*/
public class DiffCharArrMaxLenProduct {
public static int max(String[] a) {
Arrays.sort(a, new LengthComprarator());
int max = 0;
boolean[] flag = new boolean[26];
for (int i = 0; i < a.length; i++) {
if (a[i].length() * a[i].length() <= max)
break; // Optimization.
for (char c : a[i].toCharArray()) {
flag[(int) c - 65] = true;
}
for (int j = i = 1; j < a.length; j++) {
if (a[i].length() * a[j].length() <= max) {
break; // Optimization.
} else if (!hasSimilarCharacters(a[j], flag)) {
max = a[i].length() * a[j].length();
break;
}
}
Arrays.fill(flag, false);
}
System.out.println(max);
return max;
}
private static boolean hasSimilarCharacters(String s, boolean[] flag) {
for (char c : s.toCharArray()) {
if (flag[c - 65])
return true;
}
return false;
}
This code has: O(nlog(n) + n*n*26 + n*m) worst case complexity. But two major optimizations:
1. When the length of the outer loop string is less than the sqrt of the maximum product reached, no further computations are required.
2. When the product of the length of the inner loop string and the outer loop string is less than the maximum product reached, no further inner loop computations are required.
A simple version is:
def doesNotOverlap(x, y):
# x and y are sets
if x.intersection(y):
return False
else:
return True
def findMax(aList):
wordDict = dict()
maxLen = 0
for i,a in enumerate(aList):
al = len(a)
b = set(list(a))
for j in wordDict.keys():
tj = wordDict[j]
if doesNotOverlap(tj[1], b):
x = tj[0] * al
if maxLen < x: maxLen = x
wordDict[i] = (al, b)
print(wordDict)
print(maxLen)
def testRun():
X = ['apple', 'bow', 'butterfly', 'cute']
findMax(X)
X.append('cattle')
findMax(X)
testRun()
#include <iostream>
#include <stdio.h>
using namespace std;
int multiply( const char* array [], int size)
{
int maxMul = 0;
for( int n = 0; n < size; n++ )
{
for(int m = 0; m < size; m++)
{
if( string(array[n]).find_first_of(array[m] ) == string::npos )
{
int mul = string(array[n]).size() * string(array[m]).size();
if( mul > maxMul )
maxMul = mul;
}
}
}
return maxMul;
}
int main()
{
const char* array [] = {"abc", "devxx", "acf", "zxd"};
int max = multiply(array, 4);
cout << max;
}
Use C++ find_first_of. It looks for the *any* occurance of a character in another.
#include <iostream>
#include <stdio.h>
using namespace std;
int multiply( const char* array [], int size)
{
int maxMul = 0;
for( int n = 0; n < size; n++ )
{
for(int m = 0; m < size; m++)
{
if( string(array[n]).find_first_of(array[m] ) == string::npos )
{
int mul = string(array[n]).size() * string(array[m]).size();
if( mul > maxMul )
maxMul = mul;
}
}
}
return maxMul;
}
int main()
{
const char* array [] = {"abc", "devxx", "acf", "zxd"};
int max = multiply(array, 4);
cout << max;
}
#include <iostream>
#include <stdio.h>
using namespace std;
int multiply( const char* array [], int size)
{
int maxMul = 0;
for( int n = 0; n < size; n++ )
{
for(int m = 0; m < size; m++)
{
if( string(array[n]).find_first_of(array[m] ) == string::npos )
{
int mul = string(array[n]).size() * string(array[m]).size();
if( mul > maxMul )
maxMul = mul;
}
}
}
return maxMul;
}
int main()
{
const char* array [] = {"abc", "devxx", "acf", "zxd"};
int max = multiply(array, 4);
cout << max;
}
#include <iostream>
#include <stdio.h>
using namespace std;
int multiply( const char* array [], int size)
{
int maxMul = 0;
for( int n = 0; n < size; n++ )
{
for(int m = 0; m < size; m++)
{
if( string(array[n]).find_first_of(array[m] ) == string::npos )
{
int mul = string(array[n]).size() * string(array[m]).size();
if( mul > maxMul )
maxMul = mul;
}
}
}
return maxMul;
}
int main()
{
const char* array [] = {"abc", "devxx", "acf", "zxd"};
int max = multiply(array, 4);
cout << max;
}
public static void main(String args[]) throws NumberFormatException, IOException{
DataInputStream in = new DataInputStream(System.in);
System.out.println("Enter size of array");
int n = Integer.parseInt(in.readLine());
String a[] = new String[n];
for(int i=0;i<n;i++){
a[i]=in.readLine();
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n-1;j++){
if(a[i].compareTo(a[j])<0){
System.out.println(a[i]+"*"+a[j]+"="+a[i].length()*a[j].length());
System.out.println();
}
}
}
}
OUTPUT:
nter size of array
6
abcw
baz
foo
bar
xtfn
abcdef
abcw*baz=12
abcw*foo=12
abcw*bar=12
abcw*xtfn=16
baz*foo=9
baz*xtfn=12
foo*xtfn=12
bar*xtfn=12
Complexity is still O(n^2)
Is it correct? Anyone who has better than n square?
public static Integer findLongestExclusiveMultiple(String[] array) {
if (array == null) {
return null;
}
if (array.length <= 1) {
return 0;
}
Map<String, Set<Character>> words = new HashMap<>();
for (String word : array) {
if (word == null) continue;
words.put(word, new HashSet<>());
for (char c : word.toCharArray()) {
words.get(word).add(c);
}
}
int greatest = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] == null) continue;
for (int j = i + 1; j < array.length; j++) {
if (array[j] == null) continue;
Set<Character> left = words.get(array[i]);
Set<Character> right = words.get(array[j]);
int multiple = array[i].length() * array[j].length();
if (greatest >= multiple) {
continue;
}
if (!Sets.intersection(left, right).isEmpty()) {
continue;
}
greatest = multiple;
}
}
return greatest;
}
public static Integer findLongestExclusiveMultiple(String[] array) {
if (array == null) {
return null;
}
if (array.length <= 1) {
return 0;
}
Map<String, Set<Character>> words = new HashMap<>();
for (String word : array) {
if (word == null) continue;
words.put(word, new HashSet<>());
for (char c : word.toCharArray()) {
words.get(word).add(c);
}
}
int greatest = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] == null) continue;
for (int j = i + 1; j < array.length; j++) {
if (array[j] == null) continue;
Set<Character> left = words.get(array[i]);
Set<Character> right = words.get(array[j]);
int multiple = array[i].length() * array[j].length();
if (greatest >= multiple) {
continue;
}
if (!Sets.intersection(left, right).isEmpty()) {
continue;
}
greatest = multiple;
}
}
return greatest;
}
The answer given in the question is wrong. It should be "ABCDEF" (6) * "XTFN" (4) = 24.
long MaxLengths(vector<string>& data)
{
sort(data.begin(), data.end(), [&](string a, string b) {return a.size() > b.size(); });
map<long, vector<string>&> lengths;
for (vector<string>::const_iterator it = data.begin(); it != data.end(); it++)
for (vector<string>::const_iterator it1 = it + 1; it1 != data.end(); it1++) {
size_t i = 0;
for (; i < it1->size(); i++)
if (it->find(it1[i]) != string::npos)
break;
if (i != it1->size() - 1)
return it->size() * it1->size();
}
return 0;
}
To prove intersection between we can:
1. each time do lookup of characters of s1 in s2. It will give us O(n^2 * maxlength^2)
2. for each word mark used letters by using bool[]. Assuming that words are made of 'a'-'z'('A'-'Z' can be lowered to 'a'-'z') letter we get O(n*maxlength + 27*n^2) complexity
3. 2nd one is good, but it can be improved: instead of allocation of bool[] we can simply use int32_t value and mark there all used letters and check intersection by bit-and operation:
static int32_t hash_chars(const std::string &s) { int32_t ret = 0; for (char c : s) { ret |= (1 << (c - 'a')); } return ret; } int32_t main(int32_t argc, char **argv) { using StringCharsT = std::pair<std::string, int32_t>; std::vector<StringCharsT> vs; std::string s; const int32_t n = argc > 1 ? atoi(argv[1]) : 6; for (int32_t i = 0; i < n; ++i) { std::string s; std::cin >> s; std::transform(s.begin(), s.end(), s.begin(), ::tolower); vs.push_back({s, hash_chars(s)}); } int32_t ret = 0; for (int32_t i = 0; i < vs.size(); ++i) { for (int32_t j = i+1; j < vs.size(); ++j) { if ((vs[i].second & vs[j].second) == 0) { int32_t ml = vs[i].first.length()*vs[j].first.length(); ret = std::max(ret, ml); } } } std::cout << ret << "\n";It has O(n*maxlength + n^2) complexity.
- memoreku December 14, 2015