Question

Microsoft | OA Coding Questions and Solutions | Set - 28 | 2022

Answer 1

Image of ques

 

 

Answer 2

I think this could work as O(n) solution. Why to keep track of min value in pq. We can do it by a variable for curr min.
{-49,-1,-1,-1,2,50} this test case should give 4. Thinking greedly would help here.

 

    public static void main(String... args){
        int[] arr = {-49,-1,-1,-1,2,50};
        int swap = 0;
        int currMin = Integer.MAX_VALUE;
        int sum = 0;

        for(int nx : arr){
            sum += nx;
            currMin = Math.min(nx,currMin);

            if(sum < 0){
                sum = sum - currMin;
                currMin = Integer.MAX_VALUE;
                swap++;
            }
        }

        System.out.println(swap);
    }

Answer 3

I think below solution works and it is O(n)
Idea:

 

1. First find the min element less than 0, by summing up all elements
2. Now count the negative elements from beginning to make min value to zero or greater

 

Solution:
def min_relocations(A):

 

prev = 0
min_ele = math.inf
for ele in A:
    prev = ele+prev
    min_ele = min(min_ele,prev)

if(min_ele>=0):
    return 0

count = 0
for ele in A:
    if(ele<0):
        min_ele = min_ele-ele
        count+=1
    if(min_ele>=0):
        return count

 

print(min_relocations([10,-10,-1,-1,10])) -- 1
print(min_relocations([-1,-1,-1,1,1,1,1])) -- 3
print(min_relocations([5,-2,-3,1])) -- 0

Answer 4

public static int revenue (int[] balance) {
		int sum = 0;
		int relocate = 0;
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		for(int i =0;i<balance.length;i++) {
			sum +=balance[i];
			if(balance[i]<0) 
				pq.add(balance[i]); 
			if(sum<0) {
				sum+=pq.poll()*-1; 
				relocate++;
			}
		}
		return relocate;
	}