Skip to content

Instantly share code, notes, and snippets.

View sauravgpt's full-sized avatar
💻
Building Tasker Platform

Saurav Kumar Gupta sauravgpt

💻
Building Tasker Platform
View GitHub Profile
@sauravgpt
sauravgpt / trie_impl.cpp
Created May 21, 2021 09:04
Trie Implementation from Scratch
#include<bits/stdc++.h>
using namespace std;
// Considering only small alphabets
class TrieNode {
public:
TrieNode* children[26];
bool endOfWord;
int count;
@sauravgpt
sauravgpt / word_break_trie.cpp
Created May 21, 2021 09:49
Word Break Problem Trie Implementation
/* * *
Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words. See following examples for more details.
* * */
#include<bits/stdc++.h>
using namespace std;
class TrieNode {
public:
bool endOfWord;
@sauravgpt
sauravgpt / activity_selection_problem.cpp
Created May 24, 2021 02:45
Activity Selection Problem (N meetings in one room)
int maxMeetings(int start[], int end[], int n) {
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) -> bool {
return end[a] < end[b];
});
pair<int, int> last = {start[order[0]], end[order[0]]};
vector<int> JobScheduling(Job arr[], int n) {
vector<int> slots(n, -1);
sort(arr, arr+n, [&](const Job &a, const Job &b) -> bool {
return a.profit > b.profit;
});
for(int i=0; i<n; i++) {
int index = min(arr[i].dead, n)-1;
@sauravgpt
sauravgpt / constructBSTFromPreorder.cpp
Created May 27, 2021 03:28
Contruct BST from Preorder Traversal O(n^2)
int findIndex(vector<int>& pre, int l, int r, int v) {
while (l <= r) {
if (pre[l] > v) return l;
l++;
}
return -1;
}
@sauravgpt
sauravgpt / minTimeDAG.cpp
Last active May 30, 2021 07:33
Minimum time taken by each job to be completed given by a Directed Acyclic Graph
/*
Author: Saurav Kumar Gupta
Problem: Minimum time taken by each job to be completed given by a Directed Acyclic Graph
Data Structures: Queue, Array
*/
#include "./../my_lib.h"
vector<int> adj[100005];
void findMinTime(int V) {
@sauravgpt
sauravgpt / primsAlgoBruteForce.cpp
Created May 30, 2021 09:43
Implementing Prim's Brute Force Code
#include "./../my_lib.h"
vector<pair<int, int>> adj[100005];
void primsBrute(int V) {
vector<int> key(V, INT_MAX);
vector<int> parent(V, -1);
vector<bool> MST(V, false);
key[0] = 0;
parent[0] = -1;
@sauravgpt
sauravgpt / primsAlgoEfficient.cpp
Created May 30, 2021 10:00
Minimum Spanning Tree ( Prim's Algo)
#include "./../my_lib.h"
vector<pair<int, int>> adj[100005];
void primsBrute(int V) {
vector<int> key(V, INT_MAX);
vector<int> parent(V, -1);
vector<bool> MST(V, false);
key[0] = 0;
parent[0] = -1;
@sauravgpt
sauravgpt / kruskalsAlgo.cpp
Created May 31, 2021 06:10
Kruskal's Algorithm
class Solution
{
public:
//Function to find sum of weights of edges of the Minimum Spanning Tree.
class Node {
public:
int wt, u, v;
Node() {}
Node(int wt, int u, int v) {
@sauravgpt
sauravgpt / flatten_linkedList
Created June 10, 2021 12:22
Flattening a Linked List
/*
https://practice.geeksforgeeks.org/problems/flattening-a-linked-list/1#
struct Node{
int data;
struct Node * next;
struct Node * bottom;
Node(int x){
data = x;