Persistent Systems SDE-I interview

Introduction:

Persistent Systems Advanced coding round expects Candidate to know intermediate DSA (Tree, Graph, Trie, Dynamic Programming) concepts.
If you have solved standard Leetcode Medium DSA questions and able to solve them in 25 minutes window, you are pretty much good to go.

Assessment Constraints:

Question Count: 2
Time: 1 Hour

Question1:

200. Number of Islands (Leetcode):
This is a standard DFS(Can be solved using BFS too) problem where matrics can be considered as a undirected graph.

Approach:

created a visited matrix representing if the current cell is visited or not.

true - In any iteration the cell was visited previously.
false - The cell was never visited & is a candidate for a new iceland.

Create a vector<pair<int,int>> with 4 elements {0,1},{1,0},{0,-1},{-1,0} representing up, right, down & left movement for DFS.

Now iterate the matrix and whenever 1 is encountered (It's a part of an iceland) & not previously visited then increase iceland count by 1 and DFS from the point to {i,j+1},{i+1,j},{i,j-1},{i-1,j} and eventually one iceland section will be visited.

Repeat the iteration of matrics and when iterations will be completed return the final iceland count.

cpp

class Solution {
public:
    void markConnectedVisited(vector<vector<char>>& grid, int i, int j, int r, int c, vector<vector<bool>>& vis, vector<pair<int,int>>& direction)
    {
        if(i>=r || j>=c || i<0 || j<0 || grid[i][j]=='0' || vis[i][j])
            return;
        vis[i][j]=true;
        for(int x=0;x<4;x++)
            markConnectedVisited(grid,i+direction.at(x).first,j+direction.at(x).second,r,c,vis,direction);
    }
    int numIslands(vector<vector<char>>& grid) {
        int r=grid.size();
        int c=grid.at(0).size();
        vector<pair<int,int>> direction{{0,1},{1,0},{0,-1},{-1,0}};
        vector<vector<bool>> vis(r,vector<bool>(c,false));
        int count=0;
        for(int i=0;i<r;i++)
        {
            for(int j=0;j<c;j++)
            {
                if(grid[i][j]=='1' && !vis[i][j])
                {
                    count++;
                    markConnectedVisited(grid,i,j,r,c,vis,direction);
                }
            }
        }
        return count;
    }
};

This problem can also be solved using Disjoint Set Union:

cpp

class DSU {
    public:
        vector<int> parent;
        vector<int> rank;
        DSU(int v)
        {
            for(int i=0;i<=v;i++)
            {
                parent.push_back(i);
                rank.push_back(1);
            }
        }
        
        int find(int v)
        {
            if(v==parent[v])
                return v;
            int leader=find(parent[v]);
            parent[v]=leader;
            return leader;
        }
    
        void Union(int u, int v)
        {
            int lu=find(u);
            int lv=find(v);
            if(lu!=lv)
            {
                if(rank[lu]>rank[lv])
                    parent[lv]=lu;
                else if(rank[lu]<rank[lv])
                    parent[lu]=lv;
                else
                {
                    parent[lv]=lu;
                    rank[lu]++;
                }
            }
        }    
};
class Solution {
public:
    
    int getUnique(int i,int j,int numCol)
    {
        return i*numCol+j;
    }
    
    int numIslands(vector<vector<char>>& grid) {
        int r=grid.size();
        int c=grid.at(0).size();
        int count=0;
        DSU* dsu=new DSU(r*c);
        unordered_set<int> included;
        for(int i=0;i<r;i++)
        {
            for(int j=0;j<c;j++)
            {
                if(grid[i][j]=='1')
                {
                    int smallestIsland=true;
                    if(i+1<r && grid[i+1][j]=='1')
                    {
                        dsu->Union(getUnique(i,j,c),getUnique(i+1,j,c));
                        included.insert(getUnique(i,j,c));
                        included.insert(getUnique(i+1,j,c));
                        smallestIsland=false;
                    }
                    if(j+1<c && grid[i][j+1]=='1')
                    {
                        dsu->Union(getUnique(i,j,c),getUnique(i,j+1,c));
                        included.insert(getUnique(i,j,c));
                        included.insert(getUnique(i,j+1,c));
                        smallestIsland=false;
                    }
                    if(smallestIsland=true)
                        included.insert(getUnique(i,j,c));
                }
            }
        }
        for(auto x: included)
            if(dsu->parent[x]==x)
                count++;
        return count;
    }
};

Question 2:

322. Coin Change(Leetcode):
This is a standard 1D Dynamic Programming Problem where there are two scenarios:

Take the coin and stay at the same index(as we can include the coin multiple times) to calculate minimum number of coins needed for target from [index, arr.length).
Not take the coin and move to index + 1 to calculate minimum number of coins needed for target from [index + 1, arr.length).(As the coin is discarded).

If you draw the recursion tree you will understand there will be overlapping subproblems so it is a standard DP problem where dp[index] represents minimum number of coins to reach target using [inxex, arr.length) sub array.

Memoization Solution:

cpp

class Solution {
public:
    int minimumCoins(int amount, vector<int>& coins, vector<int>& dp) {
        if(amount==0)
            return 0;
        if(dp[amount]!=-1)
            return dp[amount];
        int ans=10001;
        for(int i=0;i<coins.size();i++) {
            if(amount-coins[i]>=0) {
                ans=min(ans,minimumCoins(amount-coins[i],coins,dp)+1);
            }
        }
        return dp[amount]=ans;
    }
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,-1);
        int answer=minimumCoins(amount, coins, dp);
        return answer==10001?-1:answer;
    }
};

Tabulation Solution:

cpp

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,-1);
        dp[0]=0;
        for(int i=1;i<=amount;i++) {
            int ans=10001;
            for(int j=0;j<coins.size();j++) {
                if(i-coins[j]>=0) {
                    ans=min(ans,dp[i-coins[j]]+1);
                }
            }
            dp[i]=ans;
        }
        return dp[amount]==10001?-1:dp[amount];
    }
};

Introduction:

Assessment Constraints:

Question Count: 2
Time: 1 Hour

Question1:

200. Number of Islands (Leetcode):
This is a standard DFS(Can be solved using BFS too) problem where matrics can be considered as a undirected graph.

Approach:

created a visited matrix representing if the current cell is visited or not.

true - In any iteration the cell was visited previously.
false - The cell was never visited & is a candidate for a new iceland.

Create a vector<pair<int,int>> with 4 elements {0,1},{1,0},{0,-1},{-1,0} representing up, right, down & left movement for DFS.

Repeat the iteration of matrics and when iterations will be completed return the final iceland count.

cpp

class Solution {
public:
    void markConnectedVisited(vector<vector<char>>& grid, int i, int j, int r, int c, vector<vector<bool>>& vis, vector<pair<int,int>>& direction)
    {
        if(i>=r || j>=c || i<0 || j<0 || grid[i][j]=='0' || vis[i][j])
            return;
        vis[i][j]=true;
        for(int x=0;x<4;x++)
            markConnectedVisited(grid,i+direction.at(x).first,j+direction.at(x).second,r,c,vis,direction);
    }
    int numIslands(vector<vector<char>>& grid) {
        int r=grid.size();
        int c=grid.at(0).size();
        vector<pair<int,int>> direction{{0,1},{1,0},{0,-1},{-1,0}};
        vector<vector<bool>> vis(r,vector<bool>(c,false));
        int count=0;
        for(int i=0;i<r;i++)
        {
            for(int j=0;j<c;j++)
            {
                if(grid[i][j]=='1' && !vis[i][j])
                {
                    count++;
                    markConnectedVisited(grid,i,j,r,c,vis,direction);
                }
            }
        }
        return count;
    }
};

This problem can also be solved using Disjoint Set Union:

cpp

class DSU {
    public:
        vector<int> parent;
        vector<int> rank;
        DSU(int v)
        {
            for(int i=0;i<=v;i++)
            {
                parent.push_back(i);
                rank.push_back(1);
            }
        }
        
        int find(int v)
        {
            if(v==parent[v])
                return v;
            int leader=find(parent[v]);
            parent[v]=leader;
            return leader;
        }
    
        void Union(int u, int v)
        {
            int lu=find(u);
            int lv=find(v);
            if(lu!=lv)
            {
                if(rank[lu]>rank[lv])
                    parent[lv]=lu;
                else if(rank[lu]<rank[lv])
                    parent[lu]=lv;
                else
                {
                    parent[lv]=lu;
                    rank[lu]++;
                }
            }
        }    
};
class Solution {
public:
    
    int getUnique(int i,int j,int numCol)
    {
        return i*numCol+j;
    }
    
    int numIslands(vector<vector<char>>& grid) {
        int r=grid.size();
        int c=grid.at(0).size();
        int count=0;
        DSU* dsu=new DSU(r*c);
        unordered_set<int> included;
        for(int i=0;i<r;i++)
        {
            for(int j=0;j<c;j++)
            {
                if(grid[i][j]=='1')
                {
                    int smallestIsland=true;
                    if(i+1<r && grid[i+1][j]=='1')
                    {
                        dsu->Union(getUnique(i,j,c),getUnique(i+1,j,c));
                        included.insert(getUnique(i,j,c));
                        included.insert(getUnique(i+1,j,c));
                        smallestIsland=false;
                    }
                    if(j+1<c && grid[i][j+1]=='1')
                    {
                        dsu->Union(getUnique(i,j,c),getUnique(i,j+1,c));
                        included.insert(getUnique(i,j,c));
                        included.insert(getUnique(i,j+1,c));
                        smallestIsland=false;
                    }
                    if(smallestIsland=true)
                        included.insert(getUnique(i,j,c));
                }
            }
        }
        for(auto x: included)
            if(dsu->parent[x]==x)
                count++;
        return count;
    }
};

Question 2:

322. Coin Change(Leetcode):
This is a standard 1D Dynamic Programming Problem where there are two scenarios:

Take the coin and stay at the same index(as we can include the coin multiple times) to calculate minimum number of coins needed for target from [index, arr.length).
Not take the coin and move to index + 1 to calculate minimum number of coins needed for target from [index + 1, arr.length).(As the coin is discarded).

Memoization Solution:

cpp

class Solution {
public:
    int minimumCoins(int amount, vector<int>& coins, vector<int>& dp) {
        if(amount==0)
            return 0;
        if(dp[amount]!=-1)
            return dp[amount];
        int ans=10001;
        for(int i=0;i<coins.size();i++) {
            if(amount-coins[i]>=0) {
                ans=min(ans,minimumCoins(amount-coins[i],coins,dp)+1);
            }
        }
        return dp[amount]=ans;
    }
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,-1);
        int answer=minimumCoins(amount, coins, dp);
        return answer==10001?-1:answer;
    }
};

Tabulation Solution:

cpp

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,-1);
        dp[0]=0;
        for(int i=1;i<=amount;i++) {
            int ans=10001;
            for(int j=0;j<coins.size();j++) {
                if(i-coins[j]>=0) {
                    ans=min(ans,dp[i-coins[j]]+1);
                }
            }
            dp[i]=ans;
        }
        return dp[amount]==10001?-1:dp[amount];
    }
};

Advanced Coding Round Questions with Solution for Persistent Systems.

Introduction:

Assessment Constraints:

Question1:

Approach:

Question 2:

Comments

Advanced Coding Round Questions with Solution for Persistent Systems.

Introduction:

Assessment Constraints:

Question1:

Approach:

Question 2:

Comments