homebusinessblogart

Competitive Coding

Questions

Container with most water is a brilliant question with an elegant solution that feels like magic. Initial instinct would be to go through the array in O(n^2) time but turns out that it could be brought down to O(n) time and O(1) space complexity. I wish I could classify this problem but I haven't solved these kinda questions enough.
Reveal cards in increasing order is a very good question for testing your knowledge queue implementation.

Curated Questions

1. Uncrossed Lines
Approach 1 : Recursion

int retbest(int a,int b,vector A, vector B){
    if(a == A.size() || b==B.size()){
        return 0;
    }
    
    int best = 0;
    best = max(best,retbest(a+1,b,A,B));
    best = max(best,retbest(a,b+1,A,B));
    
    if (A[a]==B[b]){
        best = max(best,retbest(a+1,b+1,A,B)+1);
    }
    return best;
}
int maxUncrossedLines(vector& A, vector& B) {
    return retbest(0,0,A,B);
}

Approach 2: Memoization (arrays)

int memo[501][501]; // Storing in memory
bool calc[501][501]; // True if calculated
int retbest(int a,int b,vector A, vector B){
    if(a == A.size() || b==B.size()){
        return 0;
    }

    if(calc[a][b]==true){ 
        return memo[a][b]; // Return calculated 
    }

    int best = 0;
    best = max(best,retbest(a+1,b,A,B));
    best = max(best,retbest(a,b+1,A,B));
    
    if (A[a]==B[b]){
        best = max(best,retbest(a+1,b+1,A,B)+1);
    }
    
    memo[a][b] = best; // Store calculated value
    calc[a][b] = true; // Set as calculated
    return best;
}
int maxUncrossedLines(vector& A, vector& B) {
    return retbest(0,0,A,B);
}


2. Edit Distance
Approach : Memoization (vectors) 

int minDistance(string word1, string word2) {
    int n1 = word1.size();
    int n2 = word2.size();
    // For memoization.
    vector<vector<int>> dp(n1, vector(n2, -1));
    int result = cost(word1, word2, n1 - 1, n2 - 1, dp);
    return result;
}
int mini(int a, int b, int c) {
    return min(min(a, b), c);    
}
int cost(string &S, string &T, int i, int j, vector> &dp) {
    if (i < 0 || j < 0) {return abs(i - j);} // Insert leftovers
    if (dp[i][j] != -1) {return dp[i][j];} // Fetch cache
    if (S[i] == T[j]) { // Accept when equal
        return dp[i][j] = cost(S, T, i - 1, j - 1, dp); x
    }

    return dp[i][j] = mini( 1 + cost(S, T, i - 1, j - 1, dp),   // Replacement
                            1 + cost(S, T, i, j - 1, dp),       // Insertion
                            1 + cost(S, T, i - 1, j, dp));      // Deletion
}


Last Updated: 31 May 2020