Skip to content

Instantly share code, notes, and snippets.

View rupalbarman's full-sized avatar

Rupal Barman rupalbarman

View GitHub Profile
@rupalbarman
rupalbarman / trie_filesystem.py
Created January 16, 2019 17:59
Print filesystem directory structure using trie datastructure
'''
Coding Problem Statement
Given a list of file paths (e.g. as output by grep), pretty print all the paths in a tree-like format.
Write your code as the prettyPrint function (do not assume the input is sorted):
String[] prettyPrint(String[] files);
Example Input:
/a/b/c/d
/b/b/f
@rupalbarman
rupalbarman / trie.py
Created December 3, 2018 15:49
Trie implementation basic
class Trie(object):
def __init__(self):
self.data = [None for _ in range(26)]
self.count = 0
self.is_end = False
def __repr__(self):
node_data = (lambda x : (1, x.count, x.is_end) if x is not None else 0)
return str([node_data(x) for x in self.data])
@rupalbarman
rupalbarman / dfs_maze.py
Created June 9, 2017 05:31
maze traversal using dfs
def pretty(maze):
for i in maze:
print(*i)
print()
def trace_ways(maze, i, j, ex, ey, visited):
maze[i][j] = '+'
visited[i][j] = True
if i == ex and j == ey:
@rupalbarman
rupalbarman / permutations_prime.py
Created June 8, 2017 10:50
permutations of a number ( digits in it) to print the biggest prime number formed with it
d = []
def isprime(n):
if n<=1: return False
if n<=3: return True
if n%2 == 0 or n%3 == 0: return False
i = 5
while i*i <= n:
if n % i ==0 or n%(i+2) == 0: return False
i+=1
@rupalbarman
rupalbarman / next_great_permutation.cpp
Created June 7, 2017 15:13
Next greatest permutation of a number, without using inbuilt function
/*
Following is the algorithm for finding the next greater number.
I) Traverse the given number from rightmost digit, keep traversing till you find a digit which is smaller than the previously traversed digit. For example, if the input number is “53(4)976”, we stop at 4 because 4 is smaller than next digit 9. If we do not find such a digit, then output is “Not Possible”.
II) Now search the right side of above found digit ‘d’ for the smallest digit greater than ‘d’. For “534976″, the right side of 4 contains “97(6)”. The smallest digit greater than 4 is 6.
III) Swap the above found two digits, we get 536974 in above example.
IV) Now sort all digits from position next to ‘d’ to the end of number. The number that we get after sorting is the output. For above example, we sort digits in 536(974). We get “536479” which is the next greater number for input 534976.
*/
@rupalbarman
rupalbarman / advanced_sort.py
Last active June 5, 2017 15:20
multiple attribute based sorting in python (object based and list based)
# sort dates using Objects, and also by lists
# first year wise, then month and finally day wise
class Date:
def __init__(self, d, m, y):
self.d = d;
self.m = m;
self.y = y;
def __repr__(self):
@rupalbarman
rupalbarman / trie2.py
Created June 3, 2017 08:42
trie using dict in python
N = int(input())
d = {}
for _ in range(N):
cmd = input().strip().split()
if cmd[0] == 'add':
s = cmd[1]
for i in range(len(s)):
prefix = s[:i+1]
d[prefix] = d.get(prefix, 0) + 1
elif cmd[0] == 'find':
@rupalbarman
rupalbarman / bsearchqsort.cpp
Last active June 1, 2017 15:56
binary search and qsort in c++ (bsearch, qsort)
#include <iostream>
#include <string.h>
using namespace std;
int compare(const void *a, const void *b){
return (*(int *)a- *(int*)b);
}
int str_compare(const void *a, const void *b) {
@rupalbarman
rupalbarman / mergeunique.cpp
Created June 1, 2017 10:07
Merge two arrays (sorted) with no repetitions of values
#include <iostream>
using namespace std;
void merge_em_all(int *a, int *b, int *c, int x, int y, int z) {
int i=0, j=0, k= 0;
for(i=0, j=0; i<x && j<y; ) {
if(a[i]< b[j]){
@rupalbarman
rupalbarman / mat_layer_rot.py
Created May 30, 2017 05:18
matrix rotation (layer wise) anti clockwise by 90 degrees
a= [
[1,2,3,4],
[5,6,7,8],
[9,10,11,12],
[13,14,15,16]
]
for _ in a:
print(*_)
print()
ab= [x[::-1] for x in zip(*a)]