# 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; // Storing in memorybool calc; // True if calculatedint 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