Lakshmi Narain College of Technology & Science (LNCTS) 2024
My Stats
EXP gained
4326
Level
5 (Champion)
Community stats
Discussions
0
0
Know more
84
Total problems solved
35
Easy
42
Moderate
7
Hard
0
Ninja

Current streak:

0 days

Longest streak:

4 days

Less

More

Achievements
3
Ronin
Topics
Binary Search Trees
Arrays
+ 1 more
Discussions
Using Trie Method Explained By Striver using C++
Interview problems
``````class Node{
public:
Node* list[26];

Node(){
for(int i=0; i<26; i++){
list[i] = NULL;
}
}

bool containsKey(char c){
return list[c - 'a'] != NULL;
}

Node* get(char c){
return list[c - 'a'];
}

void put(char c, Node* node){
list[c - 'a'] = node;
}
};

int countDistinctSubstrings(string &s)
{
int cnt = 0;
Node* root = new Node;

for(int i=0; i<s.size(); i++){
Node* node = root;
for(int j=i; j<s.size(); j++){
if(!node->containsKey(s[j])){
cnt++;
node->put(s[j],new Node);
}
node = node->get(s[j]);
}
}

return cnt + 1;
}``````
Chirag Dhunna
Published On 11-Oct-2023
136 views
0 replies
Answer Explained same as the Love Babbar Explained
Interview problems
``````#include <bits/stdc++.h>
using namespace std;

void topoSort(int node, unordered_map<int,bool> &isVisited, stack<int> &s, unordered_map<int,list<pair<int,int>>> &adj){

isVisited[node] = true;

if(!isVisited[neighbours.first]){
}
}

s.push(node);
return;
}

vector<int> shortestPathInDAG(int n, int m, vector<vector<int>> &edges)
{

// Step 1 -> Create Topological Order Stack

//Step (a) -> Mapping of adj

for(int i=0; i<m; i++){
int x = edges[i][0];
int y = edges[i][1];
int dist = edges[i][2];

}

//Step (b) -> Creating isVisited

unordered_map<int,bool> isVisited;

//Step (c) -> Creating Stack

stack<int> s;

//Step (d) -> Calling DFS method function to fill the stack

for(int i=0; i<n; i++){
if(!isVisited[i]){
}
}

// Step 2 -> Creating result answer vector

// Declaring the src node
int src = 0;

// Declaring the dist vector
vector<int> dis(n,INT_MAX);

// Setting the values in dis vector
dis[src] = 0;
while(!s.empty()){
int top = s.top();
s.pop();

if(dis[top]!=INT_MAX){
if(dis[top] + i.second < dis[i.first]){
dis[i.first] = dis[top] + i.second;
}
}
}
}

for(int i=0; i<n; i++){
if(dis[i]==INT_MAX){
dis[i] = -1;
}
}

return dis;
}
``````
Chirag Dhunna
Published On 30-Sep-2023
125 views
0 replies
Simple iterative method using c++. Steps described too..
Interview problems
``````vector<int> bfsTraversal(int n, vector<vector<int>> &adj){

vector<int> res;

// n is number of nodes

// Steps

// Step 1 -> create a map for knowing if a node is visited or not
unordered_map<int,bool> isVisited;

for(int i=0; i<n; i++){
isVisited[i] = false;
}

// Step 2 -> create a queue

queue<int> q;
q.push(0);

// Step 3 -> while poping out of the queue we run the while loop
while(!q.empty()){
int frontNode = q.front();
q.pop();

if(!isVisited[frontNode]){
isVisited[frontNode] = true;
res.push_back(frontNode);