## Google Interview Question for Software Engineers

• 0

Country: United States

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

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) : 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.

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

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)

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

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.

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

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.

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

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.

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

We can sort the array of string with their lengths decreasing. For each string, we will have to find out the next string for which letters are different. This optimization should reduce some extra comparisons.

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

result is 4 * 4 = "16". Please, correct.

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

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;
}``````

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

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

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

msdn says "The HashSet<T> class provides high-performance set operations similar to accessing the keys of the Dictionary<TKey, TValue> or Hashtable collections".
So, depending on complexity of Overlaps, total complexity is from at least O(n^2) to at most O(n^2*m^2)

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

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);
}``````

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

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.

``in_b``

relies on the fact that the characters of the input words are uniformly distributed over the 26 characters of the alphabet.

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

``````// 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 )``````

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

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;

}``````

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

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;

}``````

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

``````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;
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)``````

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

``````//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;
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))``````

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

// 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);
}
else{
ArrayList<String> list = new ArrayList<String>();
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;
}
}

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

``````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``````

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

``print test``

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

@supatroopa Can we assume english letters only and case insensitive?

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

#include<stdio.h>
#include<string.h>

int main()
{

char str={"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;
}

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

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()) {
}
}

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;
}``````

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

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

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

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

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

``````#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;
}``````

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

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 max = -1;

for( int i=0; i < strs.length; i++ )
{
}

for( int i = 0; i < strs.length; i++ )
{
for( int j = i+1; j < strs.length; j++ )
{
{
int prod = strs[i].length() * strs[j].length();
if( max < prod )
max = prod;
}
}
}

return max;
}

public static int getMask( String str )
{

for( int i=0; i < str.length(); i++ )
{
int repType = getCharIntRep( str.charAt(i) );
if( repType != -1 )
}

}

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;
}``````

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

``````#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;
}``````

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

``````#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;
}``````

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

``````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"}));

}
}``````

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

``````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"}));

}
}``````

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

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)``````

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

``````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)``````

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

``````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)``````

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

``````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);
}
}``````

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

Why isn't the answer XTFN * ABCDEF = 24?

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

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.

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

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.

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

``````/*
* @author shivam.maharshi
*/
public class DiffCharArrMaxLenProduct {

public static int max(String[] a) {
Arrays.sort(a, new LengthComprarator());
int max = 0;
boolean[] flag = new boolean;
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;
}``````

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

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.

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

I would first do the multiplication of all length with all other length - O(n^2). Then starting from the max n check if there common letters. Stop when no common chars found. Using bit mask to find the intersection is great (memoreku).

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

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, b):
x = tj * 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()``````

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

Use bit AND to find intersacton. This lead O(n^2)

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

#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;
}

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

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;
}``````

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

``````#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;
}``````

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

``````#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;``````

}

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

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

public static void main(String args[]) throws NumberFormatException, IOException{
DataInputStream in = new DataInputStream(System.in);
System.out.println("Enter size of array");
String a[] = new String[n];
for(int i=0;i<n;i++){
}
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?

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

``````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()) {
}
}

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;
}``````

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

``````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()) {
}
}

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;
}``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

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;
}``````

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

no, "ABCDEF" and "XTFN" share common letter "F".

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.