Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
724 views
in Online Assessments by Expert (111,530 points) | 724 views

2 Answers

0 like 0 dislike
Best answer

Total time alloted was 60 mins.
This was an oncampus internship opportunity in India

 

image
image
image

oa2022uber

by Expert (111,530 points)
0 like 0 dislike

My take for Q1. Assuming 1 <= A[i] (cost) <= 2^30
It is always more optimal to delete the higher bit, so what I did is that I delete the edges from the highest bit to the lowest bit.
If deleting a bit and the graph is still connected, then we remove ALL (cuz it is OR) the edges containing that bit.
I run UF (path compression + union by rank) each time for each deletion, so the time complexity is about O(30N).

 

It is 3AM here and I had a really long day. Did not bother to stress test my code, but it passed the sample test case.
As for the cycle thing, I think it doesn't matter, but it is really late and I am exhausted, so I will just leave this here for now.

 

Java

    private static int solve(int N, int[][] edges){
        BitSet byebye = new BitSet();
        BitSet[] bit = new BitSet[31];
        Arrays.setAll(bit, o -> new BitSet());
        for (int i = 0; i < edges.length; i++){ // [from, to, cost]
            edges[i][0]--; edges[i][1]--; // one index is so evil.
            for (int cost = edges[i][2], pos = 0; cost > 0; cost>>=1, pos++){
                if ((cost&1)>0){ // let's get the position first.
                    bit[pos].set(i);
                }
            }
        }
        for (int i = 30; i >= 0; i--){ // run deletion from highest bit to the lowest
            BitSet ignore = (BitSet)byebye.clone();
            ignore.or(bit[i]); // delete these all 
            UF uf = new UF(N);
            for (int j = ignore.nextClearBit(0); j < N; j = ignore.nextClearBit(j+1)){
                uf.union(edges[j][0], edges[j][1]); // union the remaining edges
            }
            if (uf.sz == 1){ // if still all connected, then update byebye to ignore.
                byebye=ignore;
            }
        }
        int ans = 0;
        for (int i = byebye.nextClearBit(0); i < N; i = byebye.nextClearBit(i+1)){
            ans |= edges[i][2]; // whatever remains, OR that to answer
        }
        return ans;
    }
by Expert (111,530 points)