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