mazharmik/interview_ds_algo

Super Repository for Coding Interview Preperation

Hello world 👋 🌍

Thank you for helping my channel reach 34K+ Subscribers.

Here are few things about me:

• 🧑‍💻 Cracked interviews of ⤵️
     🏆 _Mentor Graphics/Siemens EDA (Joined 💻)
     🏆 Microsoft
     🏆 Tokopedia (Joined 💻)
     🏆 Tower Research
     🏆 ThoughtWorks
     🏆 Expedia (Joined 💻)
• Support my Youtube Channel : codestorywithMIK (Subscribers : 34K+ ♥️)
• My YouTube Videos List in Doc Sheet - codestorywithMIK - YouTube Treasure
• DSA Sheet For Masters - DSA SHEET-1 (codestorywithMIK)
• You can book one to one sessions with me on : topmate.io (CURRENTLY PAUSED IT DUE TO TIGHT SCHEDULE)
• Official Whatsapp Page - codestorywithMIK-Whatsapp
• Official Facebook Page - codestorywithMIK-Facebook
• Official Instagram Page - codestorywithMIK-Instagram
• Official Twitter Page - codestorywithMIK-Twitter
• 🔭 I’m currently working on creating a DS & Algo Package for Interview ➡️ (838 ⭐, 427 🍴) (Only 89🍴 left to make it :500: 😱)
• 🔭 Check this out Crash Course for C++ OOPs Interview ➡️ (48 ⭐, 16 🍴)
• 🔭 Learn how to use awesome C++ STLs while problem solving, Check out my treasure Cpp-STL-Quick-Help ➡️ (37 ⭐, 19 🍴)
• 🌱 I’m currently learning "System Design", getting hands dirty on "Golang":green_book: and going through "Elastic Stack" :monocle_face:
• 📫 How to reach me on LinkedIn: LinkedIn Profile
• 📧 [email protected]
• ⚡ Fun fact: coding is fun 😉
• Want to see my Linktree - CLICK HERE ➡️

---

Profile on Coding Platforms:

Leetcode🏆       Hackerrank🏆       InterViewBit🏆       Hackerearth🏆

---

                                                    🏆 My Github Stats 🏆

Show ❤️ by starring and forking repositories you find good!

Quotes

✍🏻 Start Your Day With Inspiring Quotes:

My YouTube Channel Name - codestorywithMIK

interview_ds_algo's Issues

Java code Issue

Problem link : https://leetcode.com/problems/cheapest-flights-within-k-stops/

This is the exact replica code in Java and some test case is failing(Leetcode 47/53)
n = 4
[[0,1,1],[0,2,5],[1,2,1],[2,3,1]]
src = 0
dest = 3
k = 1

Expected output : 6
Actual output: 3

Was struggling to solve this problem from 5-6 hours then came to your video and explanation was wow but in java it's not passing all test case, Please help out with this

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        List<ArrayList<Pair>> adj = new ArrayList<>();
        for(int i=0; i<n; i++) adj.add(new ArrayList<>());
        for(int i=0; i<flights.length; i++) adj.get(flights[i][0]).add(new Pair(flights[i][2], flights[i][1]));
        // for(ArrayList<Pair> al:adj) System.out.println(al);

        int[] dis = new int[n];
        Arrays.fill(dis, (int)1e8);
        dis[src] = 0;

        Queue<Pair> pq = new LinkedList<>();

        pq.add(new Pair(0, src));
        int stop = 0;

        while(!pq.isEmpty() && stop<=k){
            int size = pq.size();

            while(size-->0){
                Pair p = pq.poll();
                int cost = p.cost;
                int node = p.node;

                for(Pair al : adj.get(node)){
                    int adjNode = al.node;
                    int wt = al.cost;

                    if(dis[adjNode] > dis[node]+wt){
                        dis[adjNode] = dis[node]+wt;
                        pq.add(new Pair(dis[adjNode], adjNode));
                    }
                }
            }

            stop++;
        }
        if(dis[dst] != (int)1e8) return dis[dst];
        return -1;
    }
}

class Pair{
    int cost;
    int node;

    Pair(int cost, int node){
        this.cost = cost;
        this.node = node;
    }
}

Please cover this question in one of your videos https://leetcode.com/problems/maximize-the-profit-as-the-salesman/

The recursive code I wrote obviously gave TLE but worked

class Solution 
{
    
    int[] dp;
    
    public int solve(List<List<Integer>> arr, int prev_start, int prev_end, int i)
    {
        if(i == arr.size())
            return 0;
        
        
        List<Integer> cur = arr.get(i);
        int start = cur.get(0);
        int end = cur.get(1);
        int taken = 0;
        
        if(start > prev_end)
            taken = cur.get(2) + solve(arr, start, end, i+1);
        int not_taken = solve(arr, prev_start, prev_end, i+1);
        
        return Math.max(taken, not_taken);
            
    }
    
    public int maximizeTheProfit(int n, List<List<Integer>> arr) 
    {
        Collections.sort(arr, (a, b) -> a.get(1) - b.get(1));    
        dp = new int[n];
        Arrays.fill(dp, -1);
        return solve(arr, -1, -1, 0);
    }
}

The dp I tried to make from this did not work, if you could help me figure out why, I'll be grateful :)

class Solution 
{
    
    int[] dp;
    
    public int solve(List<List<Integer>> arr, int prev_start, int prev_end, int i)
    {
        if(i == arr.size())
            return 0;
        
        
        List<Integer> cur = arr.get(i);
        int start = cur.get(0);
        int end = cur.get(1);
        int taken = 0;
         
        if(cur.get(2) < dp[end])
        {
            return dp[end];
        }
            
        
        if(start > prev_end)
            taken = cur.get(2) + solve(arr, start, end, i+1);
        int not_taken = solve(arr, prev_start, prev_end, i+1);
        
        return dp[end] = Math.max(taken, not_taken);
            
    }
    
    public int maximizeTheProfit(int n, List<List<Integer>> arr) 
    {
        Collections.sort(arr, (a, b) -> a.get(1) - b.get(1));    
        dp = new int[n];
        Arrays.fill(dp, -1);
        return solve(arr, 0, 0, 0);
    }
}

Other Progamming language solutions.

Hey @MAZHARMIK, I would love to contribute JS solutions to the problems. I propose to restructure the directory like below:
topic->language->allProblemSolutions
example: array->javascript->problems && graphs->javascript->problems
of course, we'll have other programming languages too in place of JavaScript.