Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
11
of 11 vote

Make a min heap out of the elements given.
Pop the smallest and the second smallest, add them and again insert that back to the heap.
Finally you will get the minimum cost

- Anonymous December 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

well bro i think you are right is the ,, !

- probby December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this is correct, but a proof of correctness would be nice.

- eugene.yarovoi December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- We Pin January 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 January 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- Kahn March 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi July 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The proof is the same one for Huffman encoding. It's not that trivial. Search it up on google.

- tkrsn August 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

sort by length...add first two string if sum > sum of next two no sum next two no..repeat likewise

- Anonymous January 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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)

- qtpie January 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If the order was to be maintained then where is the question of optimizing the cost? It would be fixed!

- Kahn March 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
        }

- Vj December 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i think the sum of first two string length is crucial... minimize the first sum and then proceeding in any order will work

- anon January 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

#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.

- muthukumarsp January 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

should you add the longest string with the shortest??? the longest will be s1 and you move through the shortest and attach it to the longest..

In this sense you would move through only the shortest possible length and avoid the longer ones..

- deepakguns February 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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];

- Naresh April 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Typedef struct strconcatter {
char *current;
struct strconcatter *next;
} strconcatter;

Just setup this like a linked list. isn't link list the usual way to add data?

- abhityagi85 July 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think order is to be maintained and for that matrix chain multiplication like approach will work perfectly..

- Code_Freak December 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));

    }

- rishi t September 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Sort the given lengths in ascending order and start adding from left to right

- Adarsh Ranjan December 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- manjunath426jc December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Apoorv December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- loveCoding December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

nothing is said about the order of concatenation, so you do not need to assume it.

- stanimir December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

wont this always be same ,, cuz ... a+b = b + a ?

- Anonymous December 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

no, b/c you're adding the 1st length n-1 times, hence you want the 1st string to be the shortest. Draw further conclusions.

- stanimir December 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)

- stanimir December 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Well, that's not the question. Also, Ranjan's answer isn't correct.

- eugene.yarovoi December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- stanimir December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)

- Vj December 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

your solution is not optimal

- Anonymous December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

the optimal cost for this set is 51. You might have to check your algo.

- manjunath426jc December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

-1: Yep, this is incorrect.

- eugene.yarovoi December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I think string buffer is a better solution

- sweet.prash December 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

True, but that's not the question.

- eugene.yarovoi December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Dude..
String Concat(String s1,String s2){
StringBuffer sb = new StringBuffer(s1);
StringBuffer sb1 = new StringBuffer(s2);
sb.concat(sb1);
String s3 = sb.toString();
return s3;
}

- sweet.prash December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I believe if S1,S2,S3,S4 are 4 strings that needs be concatenated,
S1="Hello"
S2="How"
S3="Are"
S4="You"

then we can have a string S5 of length = sum of lengths of s1, s2, s3, s4
and then we can construct S5 by simply concatinating s1..s4
Am I missing something here?

- abhityagi85 December 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

should you add the longest and the shortest strings???

- deepakguns February 19, 2012 | Flag Reply


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