Indian Institute of Technology, Delhi 2024
My Stats
EXP gained
4317
Level
5 (Champion)
Community stats
Discussions
0
3
Know more
113
Total problems solved
45
Easy
58
Moderate
8
Hard
2
Ninja

Current streak:

0 days

Longest streak:

4 days

Less

More

Achievements
4
Ronin
Topics
Backtracking
Tries
Strings
+ 1 more
1
Samurai
Topics
Arrays
Discussions
c++ solution
Interview problems
``````#include <bits/stdc++.h>
using namespace std;

bool dfs(vector<unordered_set<int>>& adj, vector<int>& vis, vector<int>& par, int a, int b) {
if (a == b) return true;
vis[a] = 1;
for (auto it : adj[a]) {
if (!vis[it]) {
par[it] = a;
if (dfs(adj, vis, par, it, b)) return true;
}
}
return false;
}

int getMinDistance(int v, int e, vector<int>& v1, vector<int>& v2, int a, int b) {
for (int i = 0; i < e; i++) {
}

vector<int> par(v, -1);
vector<int> vis(v, 0);
bool pathExists = dfs(adj, vis, par, a, b);

if (!pathExists) {
return -1; // No path exists between 'a' and 'b'
}

vector<int> path;
for (int i = b; par[i] != -1; i = par[i]) {
path.push_back(i);
}
path.push_back(a); // Include 'a' in the path
reverse(path.begin(),path.end());
int ans = 0;
for (int i = 1; i < path.size(); i++) {
int prev = path[i - 1];
vector<int> vis(v, 0);
if (!dfs(adj, vis, par, prev, b)) {
ans++;
}
}

return ans;
}``````
Published On 08-Sep-2023
29 views
0 replies
easy c++ solution
Interview problems
``````#include <bits/stdc++.h>
vector<int> solve(int n, vector<int> &arr, int qs, vector<vector<int>> &q)
{
unordered_set<int> o2e, e2o;
vector<int> ans;
vector<int> arr_e(n),arr_o(n);
if(n==0) return ans;
arr_e[0]=(arr[0]%2? 0:1); arr_o[0]=(arr[0]%2 ? 1:0);
for(int i=1;i<n;i++){
arr_e[i]=arr_e[i-1]+(arr[i]%2? 0:1);
arr_o[i]=arr_o[i-1]+(arr[i]%2? 1:0);
}
for(int i=0;i<qs;i++){
vector<int> v=q[i];
if(v[0]==0){
if(v[2]%2==0 && arr[v[1]]%2!=0){
o2e.insert(v[1]);
}else if(v[2]%2!=0 && arr[v[1]]%2==0) e2o.insert(v[1]);
arr[v[1]]=v[2];
}else if(v[0]==1){
int even=0;
for(auto& it: o2e){
if(it>=v[1] && it<=v[2]) even++;
}for(auto& it: e2o) if(it>=v[1] && it<=v[2]) even--;
even+=(arr_e[v[2]]-(v[1]==0 ? 0: arr_e[v[1]-1]));
ans.push_back(even);
}else{
int odd=0;
for(auto& it: o2e){
if(it>=v[1] && it<=v[2]) odd--;
}for(auto& it: e2o) if(it>=v[1] && it<=v[2]) odd++;
odd+=(arr_o[v[2]]-(v[1]==0 ? 0: arr_o[v[1]-1]));
ans.push_back(odd);

}
}
return ans;
}``````
Published On 09-Sep-2023
44 views
0 replies
easy c++ DP solution
Interview problems
``````#include <bits/stdc++.h>
using namespace std;

int minimumHp(int n,int m,vector<vector<int>>& board) {

vector<vector<int>> dp(n, vector<int>(m));
// The value at bottom-right should be 1 or more
dp[n-1][m-1] = max(1, 1 - board[n-1][m-1]);

// Initialize the last row
for (int j = m-2; j >= 0; j--) {
dp[n-1][j] = max(1, dp[n-1][j+1] - board[n-1][j]);
}

// Initialize the last column
for (int i = n-2; i >= 0; i--) {
dp[i][m-1] = max(1, dp[i+1][m-1] - board[i][m-1]);
}

// Fill up the DP table
for (int i = n-2; i >= 0; i--) {
for (int j = m-2; j >= 0; j--) {
int minOnExit = min(dp[i+1][j], dp[i][j+1]);
dp[i][j] = max(1, minOnExit - board[i][j]);
}
}

return dp[0][0];
}

``````