## Amazon Interview Question for SDE-2s

• 2

Country: United States
Interview Type: In-Person

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

``````public static List<List<Integer>> arraySplit(int[] arr, int k){
List<List<Integer>> res = new ArrayList<>();
int i = 0;
for(i=arr.length-1; i>=(arr.length - k); i--){
List<Integer> temp = new ArrayList<>();
}
//int c = 0;
while(i>=0){
int c = getListIndexWithMinSum(res);
i--;
}
return res;
}

private static int getListIndexWithMinSum(List<List<Integer>> arr){
int minIndex = 0;
int minSum = Integer.MAX_VALUE;
int i = 0;
for(List<Integer> l:arr ){
int currSum = sum(l);
if(minSum > currSum){
minSum = currSum;
minIndex = i;
}
i++;
}
return minIndex;
}

private static int sum(List<Integer> arr){
int sum = 0;
for(int n: arr){
sum += n;
}
return sum;
}
public static void main(String[] args){
int[] arr = {1, 3, 6, 9, 10};
List<List<Integer>> res = arraySplit(arr, 2);
for(List<Integer> l: res){
System.out.println(l);
}``````

}

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

It's just a K way partition problem, where you don't have to sort the array in reverse order, since the problem states, that the array is already sorted.

A greedy algorithm, works just fine.

``````public static List<List<Integer>> arraySplit(int[] arr, int k){
List<List<Integer>> res = new ArrayList<>();
int i = 0;
for(i=arr.length-1; i>=(arr.length - k); i--){
List<Integer> temp = new ArrayList<>();
}
//int c = 0;
while(i>=0){
int c = getListIndexWithMinSum(res);
i--;
}
return res;
}

private static int getListIndexWithMinSum(List<List<Integer>> arr){
int minIndex = 0;
int minSum = Integer.MAX_VALUE;
int i = 0;
for(List<Integer> l:arr ){
int currSum = sum(l);
if(minSum > currSum){
minSum = currSum;
minIndex = i;
}
i++;
}
return minIndex;
}

private static int sum(List<Integer> arr){
int sum = 0;
for(int n: arr){
sum += n;
}
return sum;
}
public static void main(String[] args){
int[] arr = {1, 3, 6, 9, 10};
List<List<Integer>> res = arraySplit(arr, 2);
for(List<Integer> l: res){
System.out.println(l);
}``````

}

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

Time complexity can be improved, by using a hash-map to store the the running sum of each sub list. That we we don't have to calculate the sum, every time a new element is inserted into one of the sub-lists.

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

Using a Heap to keep track of the bucket with minimal weight, a greedy algorithm yields an O(n*logn) solution.

``````class HeapNode {
public:
int weight;
int bucket_index;
HeapNode() {};
HeapNode(int w, int b) : weight(w), bucket_index(b) {};
friend bool operator<(const HeapNode& h1, const HeapNode& h2) {
return h1.weight < h2.weight;
}
friend bool operator>(const HeapNode& h1, const HeapNode& h2) {
return h1.weight > h2.weight;
}
};

typedef priority_queue<HeapNode, vector<HeapNode>, std::greater<HeapNode>> min_queue;

void findBestDistribution(vector<vector<int>>& buckets, const vector<int>& a, min_queue& q) {
for (int i = a.size()-1; i >= 0; i--) {
//find bucket with minimal weight using our heap:
HeapNode h = q.top();
q.pop();
int bucket_index = h.bucket_index;
buckets[bucket_index].push_back(a[i]);
q.push(HeapNode(h.weight + a[i], bucket_index));
}
}

int main() {
int N,K;
cin >> N >> K;

vector<int> a(N);
for (int i = 0; i < N; i++) {
cin >> a[i];
}

vector<vector<int>> buckets(K, vector<int>());

min_queue q;
for (int i = 0; i < K; i++) {
q.push(HeapNode(0, i));
}

findBestDistribution(buckets, a, q);
for (int i = 0; i < K; i++) {
vector<int> bucket = buckets[i];
for (int j = 0; j < bucket.size(); j++) {
cout << bucket[j] << " ";
}
cout << endl;
}
}``````

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

1. Create K sub-arrays, based on the sorted array.
2. Compute, the sum of the K sub-arrays.
3. Swap the largest element of the smallest weight, with the smallest sub-array of the largest weight.

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

This problem is imprecise. Observe this:

``````a = [ 0 , 1000, 10000] // k = 1
a = [ 0 , 1000, 10000] // k = 3``````

Thus, the problem needs to be precisely stated.
The proper formulation will entail :
Given there is an array of sorted values, and a parameter k, group the values into k buckets (bucket_i s) such that :

``M = sum ( abs( sum(bucket_i) - sum(bucket_j)  ) )``

gets minimized.

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

Sudip, I thought of upvoting you - and then I found this :

``````int[] arr = new int[]{-1, 1, 1, 1, 10, 8 };
int K = 2;``````

=====
8 1 1 1
10 -1
=====
Actual solution :
=====
8 1 1 :: 10
10 -1 1 :: 10
=====
Think more about a precise formulation.

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

Sorting and everything is irrelevant here.
========
The algorithm can be extended to the k-way multi-partitioning problem, but then takes O(n(k − 1)mk − 1) memory where m is the largest number in the input, making it impractical even for k = 3 unless the inputs are very small numbers.
=========

``````k = 2
M = [ -1,1,1,1,8,10 ]
N = size(M)
last = k ** N // the largest one k to the power N
min = num('inf') // well, infinity
min_p = null // nothing
// now we iterate - recursion only cool for divine
for ( n : [0:last] ){
s = str(n,k) // representing number n in base k
// reject when all the k digits do not exist in base k rep
continue( size(set(s.value) ) != k )
// left pad with zeros thus making the string N size
s = '0' ** ( N - size(s)) + s
// collect into k partitions ( change the char into int as key )
p = mset( M ) as def(inx){ int(s[inx]) }
// now generate total - calculating all pairs between 0,k-1
tot = sum ( comb( [0:k] , 2 ) ) as def(inx, pair){
// size(x) is abs(x)
size( sum(p[pair[0]]) - sum(p[pair[1]]))
}
// search for min m
if ( tot < min ){
min = tot
min_p = p
}
}
// well...
println(min)
println(min_p)
// and Finally, Galaxy has peace!``````

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

``````std::vector<std::vector<int> > kmeans(std::vector<int> & vec, int k)
{
std::vector<std::vector<int> > result (k, std::vector<int> () );
if(k == 1)
{
result.push_back(vec);
return result;
}
int target = std::ceil(std::accumulate(vec.begin(), vec.end(), 0.0) / k );
std::vector<bool> taken(vec.size(), false);

for(int i = 0; i < k ; ++i)
{
for( size_t j = 0; j < vec.size() ; ++j)
{
if( !taken[j] )
{
result[i].push_back(vec[j]);

if(std::accumulate(result[i].begin(), result[i].end(), 0)  > target)
{
result[i].pop_back();
break;
}
taken[j] = true;
}
}
}

for(auto& x: result)
{
for(auto& y : x)
{
std::cout << y;
}
std::cout << "\n";
}
return result;
}

int main()
{
std::vector<int> vec = {1,3,6,9,10};
kmeans(vec, 3);
vec = {-1,1,1,1,8,10};
kmeans(vec, 2);
}

Result :

136
9
10
-11118
10``````

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

My solution with scala

``````class Splitter {
private[Splitter] class Bucket(var sum: Int = 0, values: ListBuffer[Int] = new ListBuffer[Int]) {
sum += value
values += value
}
override def toString = "Sum=" + sum + " count=" + values.length + " values=" + values
}

def makeBuckets(sequence: Array[Int], numberOfBuckets: Int): Array[Bucket] = {
val buckets: Array[Bucket] = Array.fill(numberOfBuckets)(new Bucket);
sequence filter (_ >= 0) sortWith (_ > _) foreach (buckets.zipWithIndex.minBy(_._1.sum)._1.addValue(_))
sequence filter (_ <  0) sortWith (_ < _) foreach (buckets.zipWithIndex.maxBy(_._1.sum)._1.addValue(_))
buckets
}
}``````

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

``````class Splitter {
private[Splitter] class Bucket(var sum: Int = 0, values: ListBuffer[Int] = new ListBuffer[Int]) {
sum += value
values += value
}
override def toString = "Sum=" + sum + " count=" + values.length + " values=" + values
}

def makeBuckets(sequence: Array[Int], numberOfBuckets: Int): Array[Bucket] = {
val buckets: Array[Bucket] = Array.fill(numberOfBuckets)(new Bucket);
sequence filter (_ >= 0) sortWith (_ > _) foreach (buckets.zipWithIndex.minBy(_._1.sum)._1.addValue(_))
sequence filter (_ <  0) sortWith (_ < _) foreach (buckets.zipWithIndex.maxBy(_._1.sum)._1.addValue(_))
buckets
}
}``````

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

Actually there is a much more simple solution to this problem: all you need to do is to take the array elements from the end and add them to each bucket, then after you finished adding an element to each bucket you continue but reverse the bucket order, so now you will add to the last bucket you added, repeat until you reach the end of the array. Tested on multiple inputs including: [-1, 1, 1, 1, 10, 8 ], K = 2 and [1,3,6,9,10], k= 3 java code is bellow, sorry for variable naming and any language mistakes,time complexity O(n), space: O(n) (for storing the buckets)

``````public static void solve(ArrayList<Integer> array, int k) {

int maxBucketSize = (int) Math.ceil((double) array.size() / k);
int[][] buckets = new int[k][maxBucketSize];
int i = array.size() - 1;
int counter = 0;

while (i >= 0) {
// add elements in the bucket order
for (int j = 0; j < k; j++) {
buckets[j][counter] = array.get(i);
i--;
if (i < 0) {
break;
}
}
counter++;
} else {
// add elements in reverse bucket order
for (int j = k - 1; j >= 0; j--) {
buckets[j][counter] = array.get(i);
i--;
if (i < 0) {
break;
}
}
counter++;
}
}

// Print buckets
for (i = 0; i < k; i++) {
for (int j = 0; j < buckets[i].length; j++) {
System.out.print(buckets[i][j] + " ");
}
System.out.println();
}

}``````

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

``````def array_split(arr, k):
res = [[] for _ in range(k)]
i = len(arr) - 1
for l in xrange(k):
res[l].append(arr[i])
i -= 1

while i >= 0:
min_list = get_list_with_min_sum(res)
min_list.append(arr[i])
i -= 1
return res

def get_list_with_min_sum(res):
min_list = None
for l in res:
if min_list == None or sum(l) < sum(min_list):
min_list = l
return min_list

print array_split([1, 3, 6, 9, 10], 3)``````

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

``````def partition_array(arr, k):
if not arr:
return None
avg = sum(arr)//k
results = []
left = 0
right = len(arr) - 1
while left < right:
result = []
if arr[right] <= avg:
s = arr[right]
while s < avg and left < right:
result.append(arr[left])
s += arr[left]
left += 1
result.append(arr[right])
results.append(result[:])
right -= 1
return results``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````public class DivideSortedArrayInNearlyWeightedKBuckets {

public static void main(String[] args) {
int[] arr = new int[]{1,3,6,9,10};
int K = 3;

int[][] res = divide(arr, K);

for (int i = 0; i < res.length; i++) {
for (int j = 0; j < res[i].length; j++) {
System.out.print(res[i][j] + " ");
}
System.out.println();
}
}

static int[][] divide(int[] arr, int K){
int[][] dBuc = new int[K][1];

for (int i = arr.length-1, c = 0; i >= arr.length-K; i--,c++) {
int[] a = new int[1];
a[0] = arr[i];
dBuc[c] = a;
}
return divide(arr, dBuc, arr.length - K -1);
}

static int[][] divide(int[] arr, int[][] dBuc, int i){
if(i < 0) return dBuc;

int minSumIndex = -1;
int minSum = Integer.MAX_VALUE;
for (int j = 0; j < dBuc.length; j++) {
int s = 0;
for (int k = 0; k < dBuc[j].length; k++) {
s += dBuc[j][k];
}
if(s < minSum)
minSumIndex = j;
}

int[] v = dBuc[minSumIndex];
int[] res = new int[v.length +1];
res = Arrays.copyOf(v, res.length);
res[res.length-1] = arr[i];
dBuc[minSumIndex] = res;

dBuc = divide(arr, dBuc, i-1);
return dBuc;
}

}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````public class DivideSortedArrayInNearlyWeightedKBuckets {

public static void main(String[] args) {
int[] arr = new int[]{1,3,6,9,10};
int K = 2;

int[][] res = divide(arr, K);

for (int i = 0; i < res.length; i++) {
for (int j = 0; j < res[i].length; j++) {
System.out.print(res[i][j] + " ");
}
System.out.println();
}
}

static int[][] divide(int[] arr, int K){
int[][] dBuc = new int[K][1];

for (int i = arr.length-1, c = 0; i >= arr.length-K; i--,c++) {
int[] a = new int[1];
a[0] = arr[i];
dBuc[c] = a;
}
return divide(arr, dBuc, arr.length - K -1);
}

static int[][] divide(int[] arr, int[][] dBuc, int i){
if(i < 0) return dBuc;

int minSumIndex = -1;
int minSum = Integer.MAX_VALUE;
for (int j = 0; j < dBuc.length; j++) {
int s = 0;
for (int k = 0; k < dBuc[j].length; k++) {
s += dBuc[j][k];
}
if(s < minSum){
minSum = s;
minSumIndex = j;
}
}

int[] v = dBuc[minSumIndex];
int[] res = new int[v.length +1];
res = Arrays.copyOf(v, res.length);
res[res.length-1] = arr[i];
dBuc[minSumIndex] = res;

dBuc = divide(arr, dBuc, i-1);
return dBuc;
}``````

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.

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