Salesforce | MTS | OA

Round 1

Questions: Implement a prototype service for malware spread control in a network.

There are g_nodes servers in a network and g_edges connections between its nodes. The ith bidirectional connection connects g_from[i] and g_to[i]. Some of the nodes are infected with malware. They are listed in the array malware, where if malware[i] = 1 node i is infected, and if malware[i] = 0, node i is not infected.

Any infected node infects other non-infected nodes, which are directly connected. This process goes on until no new infected nodes are possible. Exactly 1 node can be removed from the network. Return the index of the node to remove such that the total infected nodes in the remaining network are minimized. If multiple nodes lead to the same minimum result, then return the one with the lowest index.

Example
Suppose g_nodes = 9, g_edges = 5, g_from[] - [1, 2, 4, 6, 7], g_to[] - [2, 3, 5, 7, 8], malware[] = [0, 0, 1, 0, 1, 0, 0, 0, 0]

Initially, nodes [3, 5] are infected. At the end, nodes [1, 2, 3, 4, 5] will be infected. If node 3 is removed, only nodes 4 and 5 are infected, which is the minimum possible. Return 3, the node to remove.

Function Description
Complete the function getNodeToRemove in the editor below.

getNodeToRemove has the following parameter(s):

• int g_nodes: the number of nodes
• int g_from[m]: one end of the connections
• int g_to[m]: another end of the connections
• int malware[n]: the affected nodes

Returns:
int: the optimal node to remove

Constraints

• 1 ≤ g_nodes ≤ 10^3
• 0 ≤ g_edges ≤ min(g_nodes×(g_nodes-1)/2, 10^3)
• 1 ≤ g_from[i], g_to[i] ≤ n
• malware[i] = 0 or 1.

Sample Case 0
Sample Input for Custom Testing

STDIN             FUNCTION
------            ----------
5 4        →      g_nodes = 5, g_edges = 4
1 2        →      g_from[] = [1, 2, 3, 4], g_to[] = [2, 3, 4, 5]
2 3
3 4
4 5
5          →      malware[] size g_nodes = 5
1          →      malware[] = [1, 1, 1, 1, 1]
1
1
1
1

Sample Output

1

Explanation

Working Solution (6/15 test cases passing)

import java.util.*;

class MainClass {
    public static void main(String[] args) {
        int g_nodes = 5;
        int g_edges = 4;
        int[] g_from = {1, 2, 3, 4};
        int[] g_to = {2, 3, 4, 5};
        int[] malware = {1, 1, 1, 1, 1};
    
        System.out.println(getNodeToRemove(g_nodes, g_edges, g_from, g_to, malware));
    }
    
    public static int getNodeToRemove(int g_nodes, int g_edges, int[] g_from, int[] g_to, int[] malware) {
        // Convert input to adjacency list
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < g_nodes; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < g_edges; i++) {
            int u = g_from[i] - 1; // Convert to 0-based index
            int v = g_to[i] - 1; // Convert to 0-based index
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        
        List<Integer> initial = new ArrayList<>();
        for (int i = 0; i < g_nodes; i++) {
            if (malware[i] == 1) {
                initial.add(i);
            }
        }
        
        // Call the function to find the node to remove
        return minMalwareSpread(graph, initial.stream().mapToInt(Integer::intValue).toArray()) + 1; // Convert to 1-based index
    }
    
    // Function to find the node to remove
    private static int minMalwareSpread(List<List<Integer>> graph, int[] initial) {
        int n = graph.size();
        
        // Initialize Union-Find
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int neighbor : graph.get(i)) {
                if (i < neighbor) { // Ensure each edge is processed only once
                    uf.union(i, neighbor);
                }
            }
        }
        
        int[] parent = uf.getParent();
        int[] size = uf.getSize();
        
        int[] idToMalwareCount = new int[n];
        for (int i : initial) {
            idToMalwareCount[uf.find(i)]++;
        }
        
        Arrays.sort(initial);
        
        int maxSize = 0, malwareInMaxSize = initial[0];
        for (int i : initial) {
            int rootI = uf.find(i);
            int malwareCount = idToMalwareCount[rootI];
            if (malwareCount == 1) {
                int sz = size[rootI];
                if (sz > maxSize) {
                    maxSize = sz;
                    malwareInMaxSize = i;
                }
            }
        }
        return malwareInMaxSize;
    }
}

class UnionFind {
    private int[] parent;
    private int[] size;

    public UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX != rootY) {
            parent[rootX] = rootY;
            size[rootY] += size[rootX];
        }
    }

    public int find(int x) {
        if (parent[x] == x)
            return x;
        return parent[x] = find(parent[x]);
    }

    public int[] getParent() {
        return parent;
    }

    public int[] getSize() {
        return size;
    }
}

Candidate's Approach

No approach provided.

Interviewer's Feedback

No feedback provided.

---