Amazon Interview Question SDE-2s
Country: United States
Interview Type: In-Person
package com.problems;
import java.util.Arrays;
import java.util.Comparator;
public class Solution {
public static void main(String[] args) {
// TODO Auto-generated method stub
int minCost = calculateMinimumConcatCost(args);
System.out.println(minCost);
}
private static int calculateMinimumConcatCost(String [] arr){
Arrays.sort(arr, new StringLengthComparator());
int cost = 0;
int totalCumulativeCost = 0;
StringBuilder sb = new StringBuilder(arr[0]);
for(int i = 1;i < arr.length;++i){
sb.append(arr[i]);
cost = sb.length();
totalCumulativeCost = totalCumulativeCost + cost;
}
return totalCumulativeCost;
}
private static class StringLengthComparator implements Comparator<String>{
@Override
public int compare(String o1, String o2) {
// TODO Auto-generated method stub
return o1.length() - o2.length();
}
}
}
I was thinking about the same approach at first but consider when strings can be of the same length. Assume the following string lengths in a sorted array.
1 1 1 1 2 3
Concatenating these string sequentially results in cost
2 + 3 + 4 + 6 + 9 = 24
vs
1 + 1 = 2
2 + 1 = 3
1 + 2 = 3
3 + 3 = 6
6 + 3 = 9
Total cost = 23 for this one.
package com.problems;
import java.util.Arrays;
import java.util.Comparator;
public class Solution {
public static void main(String[] args) {
// TODO Auto-generated method stub
int minCost = calculateMinimumConcatCost(args);
System.out.println(minCost);
}
private static int calculateMinimumConcatCost(String [] arr){
Arrays.sort(arr, new StringLengthComparator());
int cost = 0;
int totalCumulativeCost = 0;
StringBuilder sb = new StringBuilder(arr[0]);
for(int i = 1;i < arr.length;++i){
sb.append(arr[i]);
cost = sb.length();
totalCumulativeCost = totalCumulativeCost + cost;
}
return totalCumulativeCost;
}
private static class StringLengthComparator implements Comparator<String>{
@Override
public int compare(String o1, String o2) {
// TODO Auto-generated method stub
return o1.length() - o2.length();
}
}
}
I tried to write a code and the approach was to sort the Strings and just add the cost.
package com.problems;
import java.util.Arrays;
import java.util.Comparator;
public class Solution {
public static void main(String[] args) {
// TODO Auto-generated method stub
int minCost = calculateMinimumConcatCost(args);
System.out.println(minCost);
}
private static int calculateMinimumConcatCost(String [] arr){
Arrays.sort(arr, new StringLengthComparator());
int cost = 0;
int totalCumulativeCost = 0;
StringBuilder sb = new StringBuilder(arr[0]);
for(int i = 1;i < arr.length;++i){
sb.append(arr[i]);
cost = sb.length();
totalCumulativeCost = totalCumulativeCost + cost;
}
return totalCumulativeCost;
}
private static class StringLengthComparator implements Comparator<String>{
@Override
public int compare(String o1, String o2) {
// TODO Auto-generated method stub
return o1.length() - o2.length();
}
}
}
def strcat(a,b) { a+b }
def cost(ss) {
def c = 0;
println "${ss.size()} $c $ss"
while (ss.size() > 1) {
ss.sort{ it.size() }
def a = ss.remove(0)
def b = ss.remove(0)
c += a.size() + b.size()
ss += strcat(a,b)
println "${ss.size()} $c $ss"
}
c
}
def ss = ['a', 'bb', 'mmmmmm', 'ddd', 'sssssssss', 'ggggg', 'z']
cost(ss)
7 0 [a, bb, mmmmmm, ddd, sssssssss, ggggg, z]
6 2 [bb, ddd, ggggg, mmmmmm, sssssssss, az]
5 6 [ddd, ggggg, mmmmmm, sssssssss, bbaz]
4 13 [ggggg, mmmmmm, sssssssss, dddbbaz]
3 24 [dddbbaz, sssssssss, gggggmmmmmm]
2 40 [gggggmmmmmm, dddbbazsssssssss]
1 67 [gggggmmmmmmdddbbazsssssssss]
Result: 67
void strCatMinCost(char strData[m][n])
{
char resultArr[n]={0};
char temp[n] = {0};
int costStrCat =0;
for(int j=0;j<m;j++)
{
for(int i=j+1;i<m;i++)
{
if(strlen(strData[j])> strlen(strData[i]))
{
strcpy(temp,strData[j]);
strcpy(strData[j],strData[i]);
strcpy(strData[i] ,temp);
}
}
if(strcmp(resultArr,"")==0)
strcpy(resultArr,strData[j]);
else
{
strcat(resultArr,strData[j]);
costStrCat = costStrCat+ strlen(resultArr);
}
}
}
void strCatMinCost(char strData[m][n])
{
char resultArr[n]={0};
char temp[n] = {0};
int costStrCat =0;
for(int j=0;j<m;j++)
{
for(int i=j+1;i<m;i++)
{
if(strlen(strData[j])> strlen(strData[i]))
{
strcpy(temp,strData[j]);
strcpy(strData[j],strData[i]);
strcpy(strData[i] ,temp);
}
}
if(strcmp(resultArr,"")==0)
strcpy(resultArr,strData[j]);
else
{
strcat(resultArr,strData[j]);
costStrCat = costStrCat+ strlen(resultArr);
}
}
}
public int min(List<Integer> list, int cost) {
if (list.size() == 2) return list.get(0) + list.get(1) + cost;
int min = Integer.MAX_VALUE;
for (int i=0; i<list.size()-1; i++) {
for (int j=i+1; j<list.size(); j++) {
List<Integer> temp = new ArrayList<Integer>(list);
Integer a = temp.remove(j);
Integer b = temp.remove(i);
temp.add(a+b);
min = Math.min(min, min(temp, cost+a+b));
}
}
return min;
}
package amazon;
import java.util.ArrayList;
import java.util.List;
/**
* It is equivalent to huffman coding algorithm. Step 1, pick the two strings with smallest length and concatenate them.
* Step 2, put it back to the string pool. Redo step 1 & 2, until only one string is left.
*/
public class MinimumCostStringConcatination {
public static void main(String[] args) {
String[] strArray = {
"abc", "wxyz", "a"
};
List<String> strList = new ArrayList<String>();
for(String s:strArray) {
strList.add(s);
}
int cost = 0;
cost = getMinimumCostOfConcatenation(cost, strList);
System.out.println("Cost :" + cost + " String " + strList.get(0));
}
private static int getMinimumCostOfConcatenation(Integer cost, List<String> strList) {
if (strList.size() == 1) {
return cost;
} else {
// find two smallest string and concatenate them
String s1 = getSmallestString(strList);
String s2 = getSmallestString(strList);
String s3 = s1 + s2;
strList.add(s3);
cost = cost + s3.length();
return getMinimumCostOfConcatenation(cost, strList);
}
}
private static String getSmallestString(List<String> strList) {
int minLength = strList.get(0).length();
int index = 0;
for (int ind = 1; ind < strList.size(); ind++) {
if (strList.get(ind).length() < minLength) {
minLength = strList.get(ind).length();
index = ind;
}
}
String s = strList.remove(index);
return s;
}
}
public MainWindow()
{
InitializeComponent();
List<string> toJoin = new List<string>();
toJoin.Add("122222222222222222");
toJoin.Add("1");
toJoin.Add("1");
toJoin.Add("1");
CheapJoin(toJoin);
MessageBox.Show(score.ToString());
}
int score = 0;
private string CheapJoin(List<string> l)
{
if(l.Count==1)
{
return l[0];
}
int index_a = 0;
int length_a=l[0].Length;
int index_b = 1;
int length_b=l[1].Length;
for (int i = 0; i < l.Count;i++ )
{
if (l[i].Length < length_a)
{
length_a = l[i].Length;
index_a = i;
}
else
{
if(l[i].Length<= length_b)
{
length_b = l[i].Length;
index_b = i;
}
}
}
score += length_b + length_a;
l[index_a] += l[index_b];
l.RemoveAt(index_b);
return CheapJoin(l);
}
public MainWindow()
{
InitializeComponent();
List<string> toJoin = new List<string>();
toJoin.Add("122222222222222222");
toJoin.Add("1");
toJoin.Add("1");
toJoin.Add("1");
CheapJoin(toJoin);
MessageBox.Show(score.ToString());
}
int score = 0;
private string CheapJoin(List<string> l)
{
if (l.Count == 1)
{
return l[0];
}
int index_a = 0;
int length_a = l[0].Length;
int index_b = 1;
int length_b = l[1].Length;
for (int i = 0; i < l.Count; i++)
{
if (l[i].Length < length_a)
{
length_a = l[i].Length;
index_a = i;
}
else
{
if (l[i].Length <= length_b)
{
length_b = l[i].Length;
index_b = i;
}
}
}
score += length_b + length_a;
l[index_a] += l[index_b];
l.RemoveAt(index_b);
return CheapJoin(l);
}
public MainWindow()
{
InitializeComponent();
List<string> toJoin = new List<string>();
toJoin.Add("122222222222222222");
toJoin.Add("1");
toJoin.Add("1");
toJoin.Add("1");
CheapJoin(toJoin);
MessageBox.Show(score.ToString());
}
int score = 0;
private string CheapJoin(List<string> l)
{
if (l.Count == 1)
{
return l[0];
}
int index_a = 0;
int length_a = l[0].Length;
int index_b = 1;
int length_b = l[1].Length;
for (int i = 0; i < l.Count; i++)
{
if (l[i].Length < length_a)
{
length_a = l[i].Length;
index_a = i;
}
else
{
if (l[i].Length <= length_b)
{
length_b = l[i].Length;
index_b = i;
}
}
}
score += length_b + length_a;
l[index_a] += l[index_b];
l.RemoveAt(index_b);
return CheapJoin(l);
}
public MainWindow()
{
InitializeComponent();
List<string> toJoin = new List<string>();
toJoin.Add("122222222222222222");
toJoin.Add("1");
toJoin.Add("1");
toJoin.Add("1");
CheapJoin(toJoin);
MessageBox.Show(score.ToString());
}
int score = 0;
private string CheapJoin(List<string> l)
{
if (l.Count == 1)
{
return l[0];
}
int index_a = 0;
int length_a = l[0].Length;
int index_b = 1;
int length_b = l[1].Length;
for (int i = 0; i < l.Count; i++)
{
if (l[i].Length < length_a)
{
length_a = l[i].Length;
index_a = i;
}
else
{
if (l[i].Length <= length_b)
{
length_b = l[i].Length;
index_b = i;
}
}
}
score += length_b + length_a;
l[index_a] += l[index_b];
l.RemoveAt(index_b);
return CheapJoin(l);
}
Add two smallest strings and put result back in PriorityQueue and repeat the process.
package carrercup;
import java.util.Comparator;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
public class StringCatMinCost {
public void buildTree(String[] arr){
int n = arr.length;
Comparator<String> com = new MyComparator();
PriorityQueue<String> q = new PriorityQueue<String>(n,com);
for (int i = 0; i < arr.length; i++) {
q.add(arr[i]);
}
try {
while(q.size()>=2){
// System.out.println(q.remove());
//String s = q.remove();
//System.out.println(s);
StringBuffer sb = new StringBuffer("");
if(q.peek()!=null) sb.append(q.remove());
if(q.peek()!=null) sb.append(q.remove());
q.add(sb.toString());
}
}
catch(NoSuchElementException e){
e.printStackTrace();
}
System.out.println(q.remove());
}
public static void main(String[] args) {
StringCatMinCost obj = new StringCatMinCost();
String[] arr = {"abc","wxyz","a","xxx","dgjndfk"};
obj.buildTree(arr);
}
}
class MyComparator implements Comparator<String>{
public int compare(String arg0, String arg1) {
// TODO Auto-generated method stub
if(arg0.length()>arg1.length()) return 1;
if(arg0.length()<arg1.length()) return -1;
return 0;
}
}
private int calculateMinCost(String[] arr) {
Queue<String> minHeap = new PriorityQueue<>(arr.length, new IntegerComparator());
for (int i = 0; i < arr.length; i++) {
minHeap.add(arr[i]);
}
int cost = 0;
while(!minHeap.isEmpty()) {
StringBuilder sb = new StringBuilder(minHeap.remove());
if (!minHeap.isEmpty()) {
sb.append(minHeap.remove());
cost = cost + sb.length();
minHeap.add(sb.toString());
}
}
return cost;
}
private class IntegerComparator implements Comparator<String> {
@Override
public int compare(String o1, String o2) {
return o1.length() - o2.length();
}
}
To solve this problem, first we have to sort all the strings based on their length and then we can concatenate all the string in linera order.
It is equivalent to huffman coding algorithm. Step 1, pick the two strings with smallest length and concatenate them. Step 2, put it back to the string pool. Redo step 1 & 2, until only one string is left.
- iamsqq March 23, 2015