Register for our webinar

How to Nail your next Technical Interview

1 hour
Loading...
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
By sharing your contact details, you agree to our privacy policy.
Step 1
Step 2
Congratulations!
You have registered for our webinar
check-mark
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
check-mark
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.
close-icon
Iks white logo

You may be missing out on a 66.5% salary hike*

Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Iks white logo
Help us know you better!

How many years of coding experience do you have?

Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
Iks white logo

FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Thank you! Please check your inbox for the course details.
Oops! Something went wrong while submitting the form.
closeAbout usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career
close

Zombie Clusters Problem

There are zombies in Seattle. Some of them know each other directly. Others might know each other transitively, through others. For example, if zombies A<->B and B<->C know each other directly, then A and C know each other indirectly and all three belong to one cluster.

Knowing which zombies know each other directly, find the number of the zombie clusters.

Input is a square matrix where each cell, zombies[A][B], indicates whether zombie A knows zombie B directly.

Example One

Input:

[“1100”,

 “1110”,

 “0110”,

 “0001”]

Output: 2

There are four zombies: z0, z1, z2 and z3.

Each zombie knows oneself, thus the matrix diagonal has all 1s.

Other than that, the green matrix cells indicate that z0<->z1 and z1<->z2 know each other directly.

Because of the transitive property, zombies z0, z1 and z2 form one cluster.

The remaining zombie, z3, doesn't know others and forms their own separate cluster.

This gives us a total of 2 zombie clusters.

Example Two

Input:

[“10000”,

 “01000”,

 “00100”,

 “00010”,

 “00001”]


Output: 5

Each zombie forms their own cluster: {z0}, {z1}, {z2}, {z3}, and {z4}. The total number of clusters is 5.

Notes

Input Parameters: The function has one argument, an array of n strings. Each string has n characters, each character is either ‘0’ or ‘1’.

Output: Return an integer, the number of zombie clusters.

Constraints:

●      1 <= number of zombies <= 1000

Solutions

We provided one efficient solution, it uses depth first traversal (DFS) to locate the clusters (connected components) in the graph of zombies. We think of “zombie A knows zombie B” as an undirected graph edge. The given list of strings (essentially a two-dimensional boolean array) is an adjacency matrix for our graph of connected zombies.

Please note that solutions that use Union Find algorithm with Path Compression (refer to IK class covering that) might pass all tests but will be suboptimal; time complexity of such solutions would be O(n^2 * log(n)) versus O(n^2) for the DFS solution we discuss here.

dfs_solution.java

  • Iterating over zombies from 0 to n-1 (the DFS outer loop), we perform DFS traversal on the current node if it isn’t yet visited.
  • DFS marks graph nodes it visits so that they aren’t visited again. It doesn’t need to do anything else because all we need is to count the connected components (nothing more specific than that like remembering which nodes belong to which component).
  • Every time the DFS outer loop encounters an unvisited node, we know that we have found another connected component, so we increment the counter. The DFS function call then takes care of marking all the nodes in that component visited.
  • By the time the DFS outer loop is done, we have the number of zombie clusters in the counter variable.

Let us see how this algorithm works on this example input:

1 1 0

1 1 0

0 0 1

The outer loop first tries zombie0. It is unvisited, so we increment the counter and call function dfs() on zombie0. That call ends up visiting zombie0 and zombie1.

The outer loop then tries zombie1. It is already visited by then so the counter isn’t incremented and dfs() isn’t called.

The outer loop then tries zombie2. It is unvisited, so we increment the counter and call function dfs() on zombie2. That call ends up visiting zombie2.

The outer loop is now done. We return the value of the counter; that’s 2.

Time Complexity:

O(n^2) for the number of zombies.

Function dfs() is called exactly once (either from the DFS outer loop or from the dfs() function itself) on every graph none, so a total of n times.

Once called on a node, dfs() takes O(n) time because it needs to check if that node is connected to any other node, one by one.

n * O(n) = O(n^2) is the total time complexity.

Auxiliary Space Used:

O(n) for the number of zombies.

“Visited” array takes O(n) space.

Recursive function dfs() will make O(n) nested calls of itself in the worst case, so up to O(n) space can be allocated in the call stack at any time.

Space Complexity:

O(n^2) because of the input size.


 // -------- START --------
    static int zombieCluster(List zombies) {
        int clusters = 0, n = zombies.size();
        boolean[] visited = new boolean[n];

        // Call dfs on any zombie that has not been visited yet.
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                // Any unvisited zombie is a part of a cluster we have not seen until now.
                clusters++;
                // dfs() call will visit *all* zombies in that cluster.
                dfs(i, n, zombies, visited);
            }
        }
        return clusters;
    }

    // Traverse depth first starting from node x, mark all visited nodes visited.
    static void dfs(int x, int n, List zombies, boolean[] visited) {
        visited[x] = true;
        for(int i = 0; i < n; i++) {
            if(zombies.get(x).charAt(i) == '1' && !visited[i]) {
                dfs(i, n, zombies, visited);
            }
        }
    }
}
// -------- END --------


Try yourself in the Editor

Note: Input and Output will already be taken care of.

Zombie Clusters Problem

There are zombies in Seattle. Some of them know each other directly. Others might know each other transitively, through others. For example, if zombies A<->B and B<->C know each other directly, then A and C know each other indirectly and all three belong to one cluster.

Knowing which zombies know each other directly, find the number of the zombie clusters.

Input is a square matrix where each cell, zombies[A][B], indicates whether zombie A knows zombie B directly.

Example One

Input:

[“1100”,

 “1110”,

 “0110”,

 “0001”]

Output: 2

There are four zombies: z0, z1, z2 and z3.

Each zombie knows oneself, thus the matrix diagonal has all 1s.

Other than that, the green matrix cells indicate that z0<->z1 and z1<->z2 know each other directly.

Because of the transitive property, zombies z0, z1 and z2 form one cluster.

The remaining zombie, z3, doesn't know others and forms their own separate cluster.

This gives us a total of 2 zombie clusters.

Example Two

Input:

[“10000”,

 “01000”,

 “00100”,

 “00010”,

 “00001”]


Output: 5

Each zombie forms their own cluster: {z0}, {z1}, {z2}, {z3}, and {z4}. The total number of clusters is 5.

Notes

Input Parameters: The function has one argument, an array of n strings. Each string has n characters, each character is either ‘0’ or ‘1’.

Output: Return an integer, the number of zombie clusters.

Constraints:

●      1 <= number of zombies <= 1000

Solutions

We provided one efficient solution, it uses depth first traversal (DFS) to locate the clusters (connected components) in the graph of zombies. We think of “zombie A knows zombie B” as an undirected graph edge. The given list of strings (essentially a two-dimensional boolean array) is an adjacency matrix for our graph of connected zombies.

Please note that solutions that use Union Find algorithm with Path Compression (refer to IK class covering that) might pass all tests but will be suboptimal; time complexity of such solutions would be O(n^2 * log(n)) versus O(n^2) for the DFS solution we discuss here.

dfs_solution.java

  • Iterating over zombies from 0 to n-1 (the DFS outer loop), we perform DFS traversal on the current node if it isn’t yet visited.
  • DFS marks graph nodes it visits so that they aren’t visited again. It doesn’t need to do anything else because all we need is to count the connected components (nothing more specific than that like remembering which nodes belong to which component).
  • Every time the DFS outer loop encounters an unvisited node, we know that we have found another connected component, so we increment the counter. The DFS function call then takes care of marking all the nodes in that component visited.
  • By the time the DFS outer loop is done, we have the number of zombie clusters in the counter variable.

Let us see how this algorithm works on this example input:

1 1 0

1 1 0

0 0 1

The outer loop first tries zombie0. It is unvisited, so we increment the counter and call function dfs() on zombie0. That call ends up visiting zombie0 and zombie1.

The outer loop then tries zombie1. It is already visited by then so the counter isn’t incremented and dfs() isn’t called.

The outer loop then tries zombie2. It is unvisited, so we increment the counter and call function dfs() on zombie2. That call ends up visiting zombie2.

The outer loop is now done. We return the value of the counter; that’s 2.

Time Complexity:

O(n^2) for the number of zombies.

Function dfs() is called exactly once (either from the DFS outer loop or from the dfs() function itself) on every graph none, so a total of n times.

Once called on a node, dfs() takes O(n) time because it needs to check if that node is connected to any other node, one by one.

n * O(n) = O(n^2) is the total time complexity.

Auxiliary Space Used:

O(n) for the number of zombies.

“Visited” array takes O(n) space.

Recursive function dfs() will make O(n) nested calls of itself in the worst case, so up to O(n) space can be allocated in the call stack at any time.

Space Complexity:

O(n^2) because of the input size.


 // -------- START --------
    static int zombieCluster(List zombies) {
        int clusters = 0, n = zombies.size();
        boolean[] visited = new boolean[n];

        // Call dfs on any zombie that has not been visited yet.
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                // Any unvisited zombie is a part of a cluster we have not seen until now.
                clusters++;
                // dfs() call will visit *all* zombies in that cluster.
                dfs(i, n, zombies, visited);
            }
        }
        return clusters;
    }

    // Traverse depth first starting from node x, mark all visited nodes visited.
    static void dfs(int x, int n, List zombies, boolean[] visited) {
        visited[x] = true;
        for(int i = 0; i < n; i++) {
            if(zombies.get(x).charAt(i) == '1' && !visited[i]) {
                dfs(i, n, zombies, visited);
            }
        }
    }
}
// -------- END --------


Worried About Failing Tech Interviews?

Attend our free webinar to amp up your career and get the salary you deserve.

Ryan-image
Hosted By
Ryan Valles
Founder, Interview Kickstart
blue tick
Accelerate your Interview prep with Tier-1 tech instructors
blue tick
360° courses that have helped 14,000+ tech professionals
blue tick
100% money-back guarantee*
Register for Webinar

Recommended Posts

All Posts