Amazon Interview Question SDE-2s
Country: United States
Interview Type: In-Person
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<>();
temp.add(arr[i]);
res.add(temp);
}
//int c = 0;
while(i>=0){
int c = getListIndexWithMinSum(res);
res.get(c).add(arr[i]);
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);
}
}
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;
}
}
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.
Sorting and everything is irrelevant here.
Read very carefully about the formulation : [ wikipedia.org/wiki/Partition_problem ]
========
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!
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
My solution with scala
class Splitter {
private[Splitter] class Bucket(var sum: Int = 0, values: ListBuffer[Int] = new ListBuffer[Int]) {
def addValue(value: 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
}
}
class Splitter {
private[Splitter] class Bucket(var sum: Int = 0, values: ListBuffer[Int] = new ListBuffer[Int]) {
def addValue(value: 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
}
}
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;
boolean addToLastBucketFirst = false;
while (i >= 0) {
if (!addToLastBucketFirst) {
// add elements in the bucket order
for (int j = 0; j < k; j++) {
buckets[j][counter] = array.get(i);
i--;
if (i < 0) {
break;
}
}
addToLastBucketFirst = true;
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;
}
}
addToLastBucketFirst = false;
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();
}
}
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)
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
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;
}
}
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;
}
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<>(); temp.add(arr[i]); res.add(temp); } //int c = 0; while(i>=0){ int c = getListIndexWithMinSum(res); res.get(c).add(arr[i]); 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); }}
- Anon April 03, 2017