## Bloomberg LP Interview Question for SDETs

Country: United States

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

We can build a min_heap of string pointers (using array heap implementation). Complexity of this is O(number of strings). Then use the min_heap to extract the smallest 2 strings in content time (constant time) and add the resulting string to heap back (log n time). This must be the best solution to this problem. Please respond if you think otherwise.

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

I have exactly the similar idea and before posting it wanted to search if it exists here:), cool, it is there.

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

Here is a solution I propose. Not sure if it is the fastest, I'd like to see others thoughts on it.
Start by concatenating the smallest strings and concatenate with a bigger string and so on.
Say we have three strings A, B & C with lengths L1 > L2 > L3.
If we concatenate largest to smallest (A with B and then with C),
# of operations = (L1 + L2)(For A&B) + (L1+L2 + L3 (For A&B with C)= 2L1 + 2L2 + L3
If however, we concatenate smallest to largest (C & B and then with A)
# of operations = L1 + 2L2 + 2L3 which would be less than the above case.

So, first sort the strings according to increasing length and then use concatenate function on them, from smallest to largest.

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

This should not deserve a down vote. You were almost there. One correction is that you have to kind of "re-sort" the new list of array after each calculation. But maybe not necessarily a full sort or an insertion, but use an extra queue to store the temporary result and only need to check the first in the queue.
That way you may have a O(n*logn) solution.

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

This implementation illustrate what I said above:

``````public int concatMinCost(String[] arr){
if (arr==null || arr.length<= 1)
return -1;
if (arr.length == 2) return arr[0].length() + arr[1].length();
Arrays.sort(arr, new Comparator<String>(){
public int compare(String s1, String s2){
return s1.length() - s2.length();
}
});

int cost = 0;
int id = 2;
cost += queue.getLast().length();

while (id<arr.length || queue.size()>1){
String[] s = new String[2]; int c = 0;
while (c<2){
if (!queue.isEmpty()){
if (id < arr.length && queue.getFirst().length() > arr[id].length()){
s[c++] = arr[id++];
}
else
s[c++] = queue.pollFirst();
}
else {
s[c++] = arr[id++];
}
}
System.out.println(s[0].length()+" + " + s[1].length());
cost += queue.getLast().length();
}
return cost;
}``````

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

Thank you! If there is one thing I hate with a passion, its people hiding behind anonymity. I mean, if you're down-voting it, give me a reason, say something, don't just hide behind your computer.
That being said, I'm pretty sure someone will be down-voting this comment too :-)

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

Coming back to the discussion, I'm not sure if sorting the string after concatenation will be all that useful?
Consider 4 strings A < B < C < D (in that sorted order)
# of operations to concatenate without sorting:
A,B,C,D join A&B -> A+B,C,D join A&B with C -> 2A+2B+C,D
join A&B&C with D -> 3A+3B+2C+D
# of operations to concat with sorting:
A,B,C,D join A&B -> A+B,C,D sort -> C,D,A+B -> join C+D -> C+D, A+B
sort -> A+B, C+D join the two -> 2A+2B+2C+2D
Without sorting might be faster?

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

maybe I'm mistaking but isn't that a simply greedy algo ?
i.e., on every step merge 2 strings (any) which have total least length

the point is, if the order of string merges would matter (like you need to merge in that exact order: A + B + C and not A + C + B), then this would be the same as DP chain matrix multiplication problem. But here the order does not matter => hence this is a dumb greedy algo

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

Construct a huffman tree, using priority queue. Then traverse the tree and sum up the values of all non-leaf nodes. Time complexity is nlog(n). Even better, no need to traverse --- calc the sum when constructing the tree.

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

I used recursion. Running time is horrendous though (n^n)

``````void findMin(vector<string> strings, vector<int> vals, string concat_str, int & min, vector<string> orderOfConcat, vector<string> * ptr_to_min){
if(strings.empty()){
int sum =0;
for(int i=1;i<vals.size();i++){
sum += vals[i];
}
if(sum<min){
min = sum;
ptr_to_min = &orderOfConcat;
}
return;
}
for(int i=0;i<strings.size();i++){
vector<string> newStrings(strings.size());
vector<int> newVals (vals.size());
vector<string> newOrder(orderOfConcat.size());
string newConcat_str(concat_str);
int val;
copy(strings.begin(), strings.end(), newStrings.begin());
newStrings.erase(newStrings.begin()+i);
copy(vals.begin(), vals.end(), newVals.begin());
val = concat(newConcat_str, strings[i]);

newVals.push_back(val);
copy(orderOfConcat.begin(), orderOfConcat.end(), newOrder.begin());
newOrder.push_back(strings[i]);
findMin(newStrings, newVals, newConcat_str, min, newOrder, ptr_to_min);
}

}``````

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

I used recursion in C++. the running time is horrendous though (n^n)

``````void findMin(vector<string> strings, vector<int> vals, string concat_str, int & min, vector<string> orderOfConcat, vector<string> * ptr_to_min){
if(strings.empty()){
int sum =0;
for(int i=1;i<vals.size();i++){
sum += vals[i];
}
if(sum<min){
min = sum;
ptr_to_min = &orderOfConcat;
}
return;
}
for(int i=0;i<strings.size();i++){
vector<string> newStrings(strings.size());
vector<int> newVals (vals.size());
vector<string> newOrder(orderOfConcat.size());
string newConcat_str(concat_str);
int val;
copy(strings.begin(), strings.end(), newStrings.begin());
newStrings.erase(newStrings.begin()+i);
copy(vals.begin(), vals.end(), newVals.begin());
val = concat(newConcat_str, strings[i]);

newVals.push_back(val);
copy(orderOfConcat.begin(), orderOfConcat.end(), newOrder.begin());
newOrder.push_back(strings[i]);
findMin(newStrings, newVals, newConcat_str, min, newOrder, ptr_to_min);
}

}``````

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

popalgo dot blogspot dot com/2015/07/minimize-cost-of-string-concatenation.html

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

import java.util.Arrays;
import java.util.Comparator;

public static void main(String []args)
{
String arr[]={"avd","qwsasa","sdsda","aq"};
}

{
int sum=0,i=0,l=0;
Arrays.sort(a,new Comparator<String>(){ public int compare(String a,String b){return (a.length() - b.length());}});
l=a.length;
while(i<l-1)
{
a=this.Update(a);
l=a.length;
a[l-1]=a[i]+a[i+1];
sum+=a[l-1].length();
Arrays.sort(a,new Comparator<String>(){ public int compare(String a,String b){return (a.length() - b.length());}});
i+=2;
}
return sum;
}

String[] Update(String []a)
{
String b[]=new String[a.length+1];
int i=0;
for(String x:a)
b[i++]=x;
return b;
}
}

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

import java.util.Arrays;
import java.util.Comparator;

public static void main(String []args)
{
String arr[]={"avd","qwsasa","sdsda","aq"};
}

{
int sum=0,i=0,l=0;
Arrays.sort(a,new Comparator<String>(){ public int compare(String a,String b){return (a.length() - b.length());}});
l=a.length;
while(i<l-1)
{
a=this.Update(a);
l=a.length;
a[l-1]=a[i]+a[i+1];
sum+=a[l-1].length();
Arrays.sort(a,new Comparator<String>(){ public int compare(String a,String b){return (a.length() - b.length());}});
i+=2;
}
return sum;
}

String[] Update(String []a)
{
String b[]=new String[a.length+1];
int i=0;
for(String x:a)
b[i++]=x;
return b;
}
}

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

would sorting help here?
e,g "qwer","gab" , "dee" , "yzxv"
if we sort to 3,3,4,4 then its 6 + 10 +14
if we have 4,3,3,4 then its 7 + 10 +14
if we have 4,4,3,3 then its 8 + 11 + 14
wouldnt sort by lowest solve this ?

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

``````public class MinimumCost {
public static void main(String[] args) {
ArrayList<String> s = new ArrayList<String>();
System.out.println(getCost(s)); //Prints 22 for the above list
}
public static int getCost(ArrayList<String> s){
int cost = 0;
Collections.sort(s, new MySort()); //Sort the list according to length of the string
while (s.size() != 1){ //Repeat until the list got one final string out of all the strings
cost = cost + s.get(0).length() + s.get(1).length();
String tmp = s.get(0) + s.get(1);
s.remove(0);
s.remove(0); // Remove the top 2 strings as they are concatenated now
Collections.sort(s, new MySort()); //Sort the list again after concatenation
}
return cost;
}
static class MySort implements Comparator<String> {
@Override
public int compare(String s1, String s2) {
if (s1.length() < s2.length())
return -1;
if (s1.length() > s2.length())
return 1;
return 0;

}
}

}``````

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

public class MinimumCost {
public static void main(String[] args) {
ArrayList<String> s = new ArrayList<String>();
System.out.println(getCost(s)); //Prints 22 for the above list
}
public static int getCost(ArrayList<String> s){
int cost = 0;
Collections.sort(s, new MySort()); //Sort the list according to length of the string
while (s.size() != 1){ //Repeat until the list got one final string out of all the strings
cost = cost + s.get(0).length() + s.get(1).length();
String tmp = s.get(0) + s.get(1);
s.remove(0);
s.remove(0); // Remove the top 2 strings as they are concatenated now
Collections.sort(s, new MySort()); //Sort the list again after concatenation
}
return cost;
}
static class MySort implements Comparator<String> {
@Override
public int compare(String s1, String s2) {
if (s1.length() < s2.length())
return -1;
if (s1.length() > s2.length())
return 1;
return 0;

}
}

}

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

I think this problem is very similar to the Matrix Chain Multiplication problem and hence we can use dynamic programming with memoization to find an optimal solution.

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

class Solution {
public:
int minCostMerge(vector<string> words) {
priority_queue<int, vector<int>, greater<int>> heap;
for (int i = 0; i < words.size(); ++i) {
heap.push(words[i].size());
}

int cost = 0;
while (heap.size() >= 2) {
int len1 = heap.top();
heap.pop();
int len2 = heap.top();
heap.pop();
cost += len1 + len2;
heap.push(len1 + len2);
}
return cost;
}
};

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

My solution:

Sort the lengths (O(nlogn))
tot_sum = 0
do
{
n = Merge the least ones (Greedy approach)
Remove the least ones
tot_sum += n
Add the element n to the sorted list using binary Search (O(logn)) //Removes sorting again
}untill alist length == 1
print tot_sum;

Analysis: O(2nlogn)

Please correct me if I am wrong

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

``````int hashFns(string str)
{
int len = str.length();
return len%n;
}

int main()
{
cout<<"Enter number of strings: ";
cin>>n;
int modVal = n;

map< int,vector<string> > m;
vector<string> v;
map< int,vector<string> >::iterator it;

string str;
int key;
for(int i=0;i<n;i++)
{
cout<<"Enter string "<< i+1 <<": ";
cin>>str;
cout<<"Call hash function...."<<endl;
key = hashFns(str);
cout<<"Key: "<<key<<endl;
it = m.find(key);

if(it == m.end())
{
v.clear();
v.push_back(str);
m.insert(make_pair(key, v ));
}
else
{
v = it->second;
v.push_back(str); //update vector
it->second = v;
}
}

long int cost = 0;
for(it=m.begin(); it !=m.end();it++)
{
v = it->second;
for(int i =0; i<v.size();i++)
cost += v[i].length();
cout<<"Cost: "<<cost<<endl;
}
}``````

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

``````import java.util.PriorityQueue;

public class MinimizeStringCost {
public static void main(String[] args) {

PriorityQueue<Integer> minPQ = new PriorityQueue<Integer> ((i1, i2) -> i1 - i2);

// nlog(n)
for (String s : args) {
}

int sum = 0;
while (minPQ.size() > 1) { // remove smallest, add back sum
int toAdd = minPQ.poll() + minPQ.poll();
// log(n)
}

//Overall: nlog(n)
System.out.println(sum);
}
}``````

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

Here is a simple C++11 STL-ish solution.
Space: Constant O(1);
Complexity: (N log (N)): where N is the number of strings

``````int Minimize(const std::vector<std::string>& vec){
std::vector<int> vInt;
std::transform(vec.begin(), vec.end(), std::back_inserter(vInt), [](const auto& x){ return x.size(); });
std::sort(vInt.begin(), vInt.end());
std::transform(vInt.begin() + 1, vInt.end(), vInt.begin(), vInt.begin() + 1, [](int p, int n){ return p + n; });
return std::accumulate(vInt.begin() + 1, vInt.end(), 0);
}``````

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

Sounds like the classic string merging sequencing dynamic programming problem. It is very similar to the rod cutting or matrix multiplication sequencing problem.

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

No, that would be if there was an order and you could only merge contiguous elements..In here (given the example above) you can merge any two strings at a given time so you can use a greedy algorithm.. a la Huffman

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

my brutal force solution the time complexity is O(n!)

``````int min = Integer.MAX_VALUE ;
public int findMin (String [] a){
if (a == null || a.length == 0 || a.length == 1) {
return 0 ;
}
if (a.length == 2) {
return a[0].length() + a[1].length() ;
}
Arrays.sort(a);
boolean [] used = new boolean [a.length] ;
permutate (a, 0 , "", 0, used);
return min ;
}

public void permutate (String [] a , int pre ,String preWord , int index, boolean [] used){
if (index >= a.length) {
min = Math.min(2 * pre - preWord.length(), min) ;
return  ;
}
for (int i = 0 ; i < a.length ;++i) {
if (i != 0 && a[i].length() == a[i - 1].length() && !used[i -1]) {
continue ;
}
if (used[i]) {
continue ;
}
used[i] = true ;
permutate (a, pre + a[i].length() , a[i] , index + 1 , used) ;
used[i] = false ;
}
}``````

Comment hidden because of low score. Click to expand.

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.