Skip to content

Instantly share code, notes, and snippets.

View rajatdiptabiswas's full-sized avatar
:octocat:
Octocat says Git Gud

rajat rajatdiptabiswas

:octocat:
Octocat says Git Gud
70 followers · 26 following
View GitHub Profile
@rajatdiptabiswas
rajatdiptabiswas / KMP.py
Created June 12, 2018 15:44
Finding a specific pattern in a text using the Knuth Morris Pratt pattern searching algorithm
def kmp(txt, pat):
# base conditions
if len(pat) == len(txt):
if pat == txt:
return 0
else:
return -1
if len(pat) > len(txt):
return -1
if len(pat) == 0 or len(txt) == 0:
@rajatdiptabiswas
rajatdiptabiswas / Dynamic Programming : Text Justification.py
Last active June 21, 2018 11:55
Find the position of line breaks in a given string such that the lines are printed neatly. The string and the number of characters that can be put in one line are given as inputs. (https://www.geeksforgeeks.org/dynamic-programming-set-18-word-wrap/) (https://www.youtube.com/watch?v=RORuwHiblPc)
#!/usr/bin/env python3
import math
def main():
# take inputs
string = input("Enter the text to be justified:\n").split()
width = int(input("Enter the width of the line: "))
@rajatdiptabiswas
rajatdiptabiswas / StreamMedian.java
Created July 27, 2018 03:37
Find the median in a stream of integers (running integers)
import java.io.*;
import java.math.*;
import java.util.*;
import java.lang.*;
public class StreamMedian {
public static void main(String[] args) {
@rajatdiptabiswas
rajatdiptabiswas / kSwapLargestPermutation.java
Created July 28, 2018 05:49
Given a permutation of first n natural numbers as array and an integer k. Print the lexicographically largest permutation after at most k swaps (https://www.geeksforgeeks.org/largest-permutation-k-swaps/)
import java.util.*;
import java.io.*;
import java.lang.*;
public class kSwapLargestPermutation {
public static void main(String[] args) {
Integer[] numberArray = new Integer[] {4, 5, 2, 1, 3};
@rajatdiptabiswas
rajatdiptabiswas / Count Islands (DFS).py
Created July 30, 2018 17:48
Finding the number of islands using DFS. A group of connected 1s form an island. (https://www.geeksforgeeks.org/find-number-of-islands/)
#!/usr/bin/env python3
def is_safe(x, y, matrix, visited):
col = len(visited[0])
row = len(visited)
if x >= 0 and y >= 0 and x < col and y < row and visited[y][x] == False and matrix[y][x] == 1:
return True
else:
@rajatdiptabiswas
rajatdiptabiswas / Sakamoto.java
Last active July 30, 2018 18:03
Finding the day from a given date using the Tomohiko Sakamoto Algorithm
import java.util.*;
import java.lang.*;
import java.io.*;
class Sakamoto {
static int sakamotoAlgorithm(int date, int month, int year) {
int[] dateDiff = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};
@rajatdiptabiswas
rajatdiptabiswas / nBitGrayCode.java
Created August 17, 2018 12:46
Generate n-bit gray codes. Given a number n, generate bit patterns from 0 to 2^n-1 such that successive patterns differ by one bit.
import java.io.*;
import java.lang.*;
import java.util.*;
class nBitGrayCode {
public static void main(String[] args) {
int n = 3;
@rajatdiptabiswas
rajatdiptabiswas / ShortestDistanceBetweenTwoCells.java
Created August 19, 2018 14:03
Given a matrix, find the shortest distance from a source cell to a destination cell, traversing through limited cells only. Can move only up, down, left and right. If found output the distance else -1.
import java.util.*;
import java.lang.*;
import java.io.*;
class ShortestDistanceBetweenTwoCells {
static class Cell {
int row;