Question

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

Answer 1

In an auditorium, the lighting system of N bulbs is placed in a row. Due to some technical fault in the power supply, only some of the bulbs remain ON and the rest of them go OFF. Due to this flaw in the network, the bulbs which are OFF are unable to work. So till the technical team finds the actual cause of the fault, the technical head Akshay makes some temporary arrangements for the OFF bulbs at a minimum cost. Akshay decides to connect all the OFF bulbs to the nearby ON bulbs so that the length of the cable used to connect them is minimum. He calculates the distance of the systems from the first system.

 

Write an algorithm to help Akshay find the minimum length of the cable used to turn all the bulbs ON.

 

Input

 

The first line of the input consists of an integral num, representing the number of bulbs (N).
The second line consists of N space-separated integers representing the initial state of each bulb, ON(1) or OFF(0)
The last line consists of N space-separated integers representing the distance of the bulbs from the first bulb.
Output

 

Print an integer representing the minimum length of the cable used to turn all the bulbs ON.
Example

 

Input:
3
1 0 0
1 5 6
Output:
5
Explanation:

 

Length of the cable required to connect the 2nd bulb to the 1st bulb =4
Length of the cable required to connect the 3rd bulb to the 2nd bulb =1
The total length of the cable = 5(4+1)
So, the output is 5.

Answer 2

Minimum Spanning Tree [Union Find]

We are asked to construct a minimum spanning tree, so we use a union find.

1. Every OFF bulbs have 2 edges connecting the 2 closest bulbs.
2. Every ON bulbs is connected with the supernode BRIGHT which is denoted as node N.

    private static int solve(int[] bulbs, int[] dist){ // Java
        int N = bulbs.length;
        UF uf = new UF(N+1);
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < N; i++){
            if (bulbs[i] == 1){
                uf.union(i, N);
            }else{
                if (i > 0){
                    edges.add(new int[]{dist[i]-dist[i-1], i, i-1});
                }else if (i < N-1){
                    edges.add(new int[]{dist[i+1]-dist[i], i, i+1});
                }
            }
        }
        if (uf.size() == N+1){
            return -1; // IMPOSSIBLE
        }
        int ans = 0;
        edges.sort(Comparator.comparingInt(o -> o[0]));
        for (int[] e : edges){
            int cost = e[0], v = e[1], u = e[2];
            if (uf.union(v, u)){
                ans += cost;
            }
        }
        return ans;
    }