Bloomberg LP Interview Question SDETs
Country: United States
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.
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.
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;
}
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 :-)
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?
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
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);
}
}
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);
}
}
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;
}
}
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;
}
}
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;
}
}
}
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;
}
}
}
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;
}
};
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
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;
}
}
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);
}
}
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);
}
Sounds like the classic string merging sequencing dynamic programming problem. It is very similar to the rod cutting or matrix multiplication sequencing problem.
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 ;
}
}
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