Spectral
BAN USER
Questions (1)
Comments (5)
Reputation 70
 2of 2 votes
AnswersThere's a function that concatenates two strings and returns the length of the resultant string. When called upon a series of strings how do we minimize the cost of using this function. Let's say we have 3 strings, A= "abc", B="def", C = "gh".
 Spectral in United States
Now cost of merging AB = 6 and cost of merging the resultant string with C is 8. Thus the total cost is 6 + 8 = 14. However, if we merge A and C, then the cost is 5 and then merge B with this, the cost is 8, so the total cost is 13.
Find an algorithm that minimizes the cost of adding such a series of strings. Report Duplicate  Flag  PURGE
Bloomberg LP SDET Algorithm
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
My solution in O(n^2), easy to understand.
public static int goldCoins(int cells, int released, int[] cellNum){
boolean[] check = new boolean[cells+1];
int count = 0;
for (int i = 0; i <released ; i++) {
check[cellNum[i]] = true;
int lower = 1;
int upper = check.length 1;
//go left
for (int j = cellNum[i]; j > 0; j) {
if(check[j]) lower = j;
}
//go right
for(int j = cellNum[i]; j < check.length; j++){
if(check[j]) upper = j;
}
int addendum = upper  lower 1;
count+= addendum;
}
return count;
}

Spectral
May 13, 2016 Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Open Chat in New Window
Open Chat in New Window
 Spectral July 18, 2016