Spectral
BAN USER- 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
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 July 18, 2016