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