Amazon Interview Question for SDE-2s


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<>();
			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 | Flag Reply
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<>();
			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 | Flag Reply
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.

- Anon April 03, 2017 | Flag Reply
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;
	}
}

- trevorvanloon April 07, 2017 | Flag Reply
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.

- Anonymous April 03, 2017 | Flag Reply
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.

- NoOne April 03, 2017 | Flag Reply
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;

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

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

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!

- NoOne April 03, 2017 | Flag Reply
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

- steephen April 05, 2017 | Flag Reply
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]) {
    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
  }
}

- marco.fago April 14, 2017 | Flag Reply
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]) {
    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
  }
}

- marco.fago April 14, 2017 | Flag Reply
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;
        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();
        }

    }

- Eddy May 02, 2017 | Flag Reply
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)

- sumitgaur.iiita May 11, 2017 | Flag Reply
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

- lalat.nayak July 05, 2017 | Flag Reply
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;
	}

}

- Sudip April 02, 2017 | Flag Reply
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;
	}

- Sudip April 02, 2017 | 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