Bloomberg LP Interview Question for SDETs


Country: United States




Comment hidden because of low score. Click to expand.
4
of 4 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.

- vinodnalla October 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- venkatesh.duggirala December 21, 2015 | Flag
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.

- puneet.sohi July 07, 2015 | Flag Reply
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.

- hieu.pham July 11, 2015 | Flag
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();
		}
	});
	
	LinkedList<String> queue = new LinkedList();
	int cost = 0;
	int id = 2;
	queue.addLast(arr[0] + arr[1]);
	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());
		queue.addLast(s[0]+s[1]);
		cost += queue.getLast().length();
	}
	return cost;
}

- hieu.pham July 11, 2015 | Flag
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 :-)

- puneet.sohi July 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- puneet.sohi July 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous October 03, 2015 | Flag
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.

- putin July 07, 2015 | Flag Reply
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);
    }

}

- Anonymous July 10, 2015 | Flag Reply
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);
    }

}

- Ali July 10, 2015 | Flag Reply
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

- Anonymous July 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

public class strAdd {

public static void main(String []args)
{
strAdd o = new strAdd();
String arr[]={"avd","qwsasa","sdsda","aq"};
System.out.println(o.getAdd(arr));
}

int getAdd(String a[])
{
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;
}
}

- Suyash R September 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

public class strAdd {

public static void main(String []args)
{
strAdd o = new strAdd();
String arr[]={"avd","qwsasa","sdsda","aq"};
System.out.println(o.getAdd(arr));
}

int getAdd(String a[])
{
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;
}
}

- suyash.m.rathi September 10, 2015 | Flag Reply
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 ?

- anonymous September 29, 2015 | Flag Reply
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>();
        s.add("abcd");
        s.add("def");
        s.add("gh");
        s.add("jh");
        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
            s.add(tmp); // Add the concatenated string to the list
            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;

        }
    }

}

- Prabhat Nayak October 17, 2015 | Flag Reply
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>();
s.add("abcd");
s.add("def");
s.add("gh");
s.add("jh");
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
s.add(tmp); // Add the concatenated string to the list
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;

}
}

}

- Anonymous October 17, 2015 | Flag Reply
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.

- Maverick55 December 25, 2015 | Flag Reply
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;
}
};

- jianhe25 December 30, 2015 | Flag Reply
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

- enigma2006.kishore February 22, 2016 | Flag Reply
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;
	}
}

- Preeti April 22, 2016 | Flag Reply
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) {
            minPQ.add(s.length());
        }
        
        int sum = 0;
        while (minPQ.size() > 1) { // remove smallest, add back sum
            int toAdd = minPQ.poll() + minPQ.poll();
            sum += toAdd;
            // log(n)
            minPQ.add(toAdd);
        }

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

- sbiyyala July 07, 2016 | Flag Reply
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);
}

- tionogu February 14, 2017 | Flag Reply
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.

- DR A.D.M July 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- zahl July 08, 2015 | Flag
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 ;		  
		}					
	}

- Scott July 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More