Skip to content

Instantly share code, notes, and snippets.

View beingmartinbmc's full-sized avatar
🏠
Working from home

Ankit Sharma beingmartinbmc

🏠
Working from home
  • Games24x7
  • Bengaluru
  • 17:42 (UTC -12:00)
View GitHub Profile
@beingmartinbmc
beingmartinbmc / DisjointSet.java
Created April 6, 2019 17:54
Disjoint Sets implementation of makeSet, findSet, and union.
import java.util.*;
class Node{
int data;
Node parent;
int rank;
}
public class DisjointSet{
private Map<Integer, Node> map;
@beingmartinbmc
beingmartinbmc / Trie.java
Created March 16, 2019 18:30
Implementation of a Trie that supports insertion, deletion, updation, and querying the count.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
class TrieNode{
private Map<Character, TrieNode> children;
private boolean wordBreak;
private int count;
@beingmartinbmc
beingmartinbmc / Jobs Sequencing.py
Created March 12, 2019 17:17
Clean and concise code for the job sequencing problem. Using greedy approach.
def print_jobs(jobs):
slots = [False] * len(jobs)
result = [9] * len(jobs)
jobs.sort(reverse=True, key=lambda x: x[2])
d_max = max(jobs, key=lambda x: x[1])[1]
count = 0
for i in range(len(jobs)):
k = min(d_max, jobs[i][1])
while k >= 1:
if not slots[k]:
@beingmartinbmc
beingmartinbmc / CoinChange.py
Created March 12, 2019 15:32
Includes the memoised version of the coin change problem
def coin_change(coins, amount, items, lookup):
key = str(amount) + '->' + str(items)
if key in lookup:
return lookup[key]
else:
if amount == 0:
lookup[key] = 1
return 1
if amount < 0 or items < 0:
lookup[key] = 0
@beingmartinbmc
beingmartinbmc / Knapsack.java
Created February 23, 2019 11:42
0/1 Knapsack using Memoization
import java.util.HashMap;
public class Knapsack {
private static HashMap<String, Integer> map = new HashMap<>();
private static int ks(int i, int w, int[] weight, int[] profit){
if(i < 0 || w == 0)
return 0;
String key = i + " -> " + w;
if(map.containsKey(key))
return map.get(key);
@beingmartinbmc
beingmartinbmc / PrintBrackets.java
Created February 19, 2019 16:35
Printing the bracket number of each bracket.
public class PrintBrackets{
private static void printBrackets(String w){
Stack<Integer> stack = new Stack<>();
int count = 1;
for(char c : w.toCharArray()){
if(isOpeningSymbol(c)) {
System.out.print(count+" ");
stack.add(count++);
}
if(isClosingSymbol(c)) {
@beingmartinbmc
beingmartinbmc / MazeSolver.java
Created January 12, 2019 12:51
Solves a grid(maze) using breadth first search
import java.util.LinkedList;
import java.util.Queue;
class Point{
int x;
int y;
int distance;
Point(int x, int y, int distance){
this.x = x;
@beingmartinbmc
beingmartinbmc / NQueen.py
Last active December 14, 2018 10:58
N-Queen problem implementation based on @Tushar_Roy video
n = (int(input('Enter number of queens\n')))
board = [[0] * n for i in range(n)]
def is_safe(row, col):
for i in range(n):
if board[row][i] == 1 or board[i][col] == 1:
return False
for i in range(n):
for j in range(n):
@beingmartinbmc
beingmartinbmc / Stack.py
Created December 11, 2018 04:53
Implementation of stack in Python
__author__ = 'Ankit Sharma'
class Stack:
""" This is an easy implementation of a stack """
def __init__(self):
self.stack = []
def push(self, some_value):
@beingmartinbmc
beingmartinbmc / BST.c
Created November 24, 2018 19:41
Binary search tree implementation
#include "stdio.h"
#include "stdlib.h"
#define pf printf
#define sf scanf
typedef struct tree
{
int data;
struct tree *left,*right;
}node,*nodeptr;
nodeptr tree=NULL;