Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
This is called Greedy Programming. you can refer to Algorithm books.
Problem is similar to find "Spanning tree" of a fully connected un directed graph. Kruskal's algorithm and Prim's algorithm do the same. They both use Greedy Programming.
This may be a greedy algorithm, but greedy algorithms are not correct for all problems. I was asking specifically for a proof that the greedy approach described is correct for this particular problem.
@eugene.yarovoi:
The proof seems trivial. Let's say that the successive costs obtained through this algorithm are C1, C2, ...,Ci,..., Cn. Now, each of the Ci's is the sum of smallest 'i' strings and hence each Ci is smaller than or equal to a corresponding Ci' obtained by any other approach. Consequently, C1+C2+...Ci+...Cn is smallest for the above-mentioned approach. Hence, greedy approach works in this case.
That doesn't seem like a very solid proof. After all, this algorithm will generate new strings (the results of the concatenation) that might not have been obtained with another approach in the first place.
It is not clear whether we have to maintain the order of the strings while concatenating.
If yes, I would suggest a dynamic programming approach like that used in matrix chain multiplication. (see Cormen)
I guess this code should work:
internal static int ConcateWithMinimumCost(Node input, int n)
{
cost = 0;
if (n == 0)
return -1;
if (n == 1)
{
// print message nothing to contatinate
Console.WriteLine("print message nothing to contatinate");
return input.Length;
}
Node start = input;
Node traverse = start;
Node first = traverse;
traverse = traverse.Next;
Node second = traverse;
traverse = traverse.Next;
int indexOfSmallestPair = 0;
int smallestPairLength = first.Length + second.Length;
int currentIndex = 2;
while (n >= 3)
{
Node temp = start;
while (temp != null)
{
Console.Write("{0}, ", temp.Length);
temp = temp.Next;
}
Console.WriteLine();
// if number of elements are 4 then we need to identify if
// we'll add them to in 2 pairs or add them in one pair at a time
if (n == 4)
{
if (first.Length + second.Length > traverse.Next.Length ||
first.Length < traverse.Length + traverse.Next.Length)
{
first.Length = add(first.Length, first.Next.Length);
n--;
first.Next.Length = add(traverse.Length, traverse.Next.Length);
first.Next.Next = null;
n--;
continue;
}
}
do
{
// Find smallest pair
if (smallestPairLength > second.Length + traverse.Length)
{
indexOfSmallestPair = currentIndex - 1;
smallestPairLength = traverse.Length + second.Length;
}
first = second;
second = traverse;
traverse = traverse.Next;
currentIndex++;
} while (traverse != null);
// Concatenate the smallest pair
first = start;
Console.WriteLine("indexOfSmallestPair={0}", indexOfSmallestPair);
for (int i = 0; i < indexOfSmallestPair; i++)
first = first.Next;
first.Length = add(first.Length, first.Next.Length);
first.Next = first.Next.Next;
n--;
// Reset values for next loop
traverse = start;
first = traverse;
traverse = traverse.Next;
second = traverse;
traverse = traverse.Next;
smallestPairLength = first.Length + second.Length;
currentIndex = 2;
}
return add(start.Length, start.Next.Length);
}
#include<stdio.h>
#include<string.h>
int main()
{
char s1[] = "I ";
char s2[] = "am";
char s3[] = "Muthu";
/* the length of the strings are given in the input,
but I am calcualting to avoid hard coding here */
int len1 = strlen(s1);
int len2 = strlen(s2);
int len3 = strlen(s3);
char *s = (char*)malloc( (len1+len2+len3+1)*sizeof(char));
s[0] ='\0';
strcat(s,s1);
strcat(&s[len1],s2);
strcat(&s[len1+len2],s3);
/* totally 9 copies are required instead of ( 4 + 9 ) */
printf(" %s\n",s);
}
This is the actual functionality of strcat in standard C. I have simply used it to optimise the solution.
char *strcat( char *s1, const char *s2)
appends the string s2 to the end of character array s1. The first character from s2 overwrites the '\0' of s1. The value of s1 is returned.
I think the order should be maintained.
If not the minheap solution looks fine.
otherwise use
for (i =1; i < strings.lenght; i++) {
for(j = 0; j < strings.length - i; j++) {
int gap = j + i;
for(k = j; k < gap; k++) {
int cost = Math.Min(cost[j][gap], cost[j][k] + cost[k][gap]);
if (cost < cost[j][gap]) cost[j][gap] = cost;
}
}
}
return cost[0][strings.length -1];
From what I understood, we need to add smallest string in successive order to find min cost
Please let me know if my understanding is incorrect of logic is flawed.
Steps:
Assuming n strings are passed in string array
Iterate in loop n times-for all strings
in each iteration, pick out smallest string and concatenate with output,calculate cost and make that string in array null;
return output
public static String concatString(String[] input) {
int size = input.length;
String output = "";
int cost = 0;
int outputcost = 0;
while (size > 0) {
int min = 0;
for (int i = 0; i < input.length; i++)
if (input[i] != "" && input[i].length() < input[min].length())
min = i;
cost = cost + output.length() + input[min].length();
output = output + input[min];
input[min] = "";
size--;
}
System.out.println(cost);
return output;
}
public static void main(String args[]) {
String[] input = { "Helloo ", "Hows ", "are ", "u " };
System.out.println(concatString(input));
}
I don't think that would help.
For ex: 1,2,3,4,5 (cost is mentioned in brackets)
3,3,4,5 (3)
6,4,5 (6)
10,5 (10)
15 (15)
Total cost=34
Optimum cost=33
After sorting first time, add first and second string. Then insert this string at correct place in the sorted order and recurse. In the above case 1,2,3,4,5-->3,3,4,5-->4,5,6-->6,9-->15. Total cost = 3 + 6 + 9 + 15 = 33
I thinks its wrong, we need to make sure strings are concatenated in correct order.
For e.g. if we are given stringlengths like 1-5- 2-3-4, we cannot combine 1 and 2 although we can combine 1and 5 or 5and 2
Ranjan's answer is the correct one although the only right way to concatenate is allocating he needed memory and then copying, anything else is just dumb (alternative allocating small and increasing the size by some factor like 2x)
then you are left w/ Hanoi tower algorithm that's:
a stack: if the stack is empty add the string,
if the current string length is less than the head of the stack push it. Otherwise pop the stack and concatenate w/ the current element. Repeat the operation w/ the next head of the stack.
If there are no more elements in the array pop the stack and consider it the current element (basically popping and concatenating till stack is empty).
When the stack has one element and no more elements in the source array of strings, it's done.
I suppose that was the question about, but it still sucks for concatenation.
We should add it in pairs like:
1 2 3 4 5 6
(1 2) (3 4) (5 6)
->3 7 11 (21)
(3 7) (11)
->10 11 (10)
(10 11)
->21 (21)
Total(52)
Make a min heap out of the elements given.
- Anonymous December 27, 2011Pop the smallest and the second smallest, add them and again insert that back to the heap.
Finally you will get the minimum cost