Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
First thing I feel might work... do two sorts... careful that second is stable:
1) Sort the array using string comparison
THEN
2) Stable sort the array using string length
Then pairs are:
first element with last
second element with second last
... etc...
Above works for your case (sort of increasing characters)
This would work better for general case:
Sort the array by size.
One of the first two elements is a prefix of one of the last two elements.
Let "s" be the one from the first two elements that is the prefix in above test.
Now walk down array checking pairs(a[0],a[1]) , (a[2],a[3]) ,...
One element of each pair has "s" as a prefix, just adjust each pair so the one with "s" as prefix comes in each pair.
Now you your final result is:
(first element of a, last element of a)
(second element of a, second last element of a)
... etc...
* One element of each pair has "s" as a prefix, just adjust each pair so the one with "s" as prefix comes _first_ in each pair.
To make it (more) failsafe.
Assume "t" was one of the first two elemetns that was a suffix of one of the last two.
When you rearrange each pair, make sure s is prefix of first one and t is suffix of last one.
And there might be more cases that squeek by, but you should be able to add it to the "rerrange pairs" linear scan.
I think we can youse graph algrithm approach to this problem. It's quite common in genome assbmling problem to build de Bruijn graph and find out Euler cycle on it. So let'sbuild graph, where strings are vertexes, and edge from u to v means that string corresponds to u contain suffix that also is preffix of string v. So the solution of this problem is to find Euler cycle on this graph.
One more idea to build suffix trie on this array. We have to concat all strings like s1$1s2$2..sn$n and insert specific delimeters, that will be unique in all string. Than we find lowest vertex, that contains under itself all strings. It's also popular problem how to find leats string, that contains another.
"common combinations" ? Ambiguous.
I think you just mean a string that contains all other strings as a permuted subsequence. Or put it another way, a string that is a superset of all characters appearing amoungst all the characters appearing in a.
Your examples are very unclear or basic. Example makes it seems like the strings come in pairs, and we have to add each pair (this would be easy also, a variant of below).
If you mean what I said at the very top, then simply count the occurences of letters as you check every string. So for example, if your encoding is ascii you can declare a 256 boolean/bit array, "seen", then:
For each string in a:
For every valid letter c in the string:
set seen[(int)c]=true;
For i=0 to 255:
if seen[i]==true:
print char(i); // or add char(i) to output result
The question to be exact is find all pairs of strings in an array that when concatenated gives the same string. Condition is there are N elements(N is even) and there are definitely N/2 pairs. We need to find all the pairs and all pairs when concatenated with each other will give the same string.
- ur2cdanger September 20, 2013For example : Array a = { "abc","efgh","abcde","fgh","abcd","defgh"};
Expected output : ("abc","defgh") , ("abcde","fgh") , ( "abcd","efgh")