prat0318’s gists

prat0318 / lcs.py

Created November 17, 2013 04:12

sub optimal longest common substring

	def longest_common_prefix(str1, str2):
	result = ''
	for i in range(len(str1)):
	if(len(str2) > i and str1[i] == str2[i]):
	result = result + str1[i]
	else:
	break
	return result

	def longest_common_substring(str1, str2):

prat0318 / next.py

Last active December 28, 2015 13:39

next greater in array

	def next_greater(arr):
	while(not is_rev_sorted(arr)):
	for i in reversed(range(len(arr) - 1)):
	if arr[i] < arr[i+1]: break
	for j in reversed(range(len(arr))):
	if arr[i] < arr[j]: break
	swap(arr, i, j)
	yield reverse(arr, i+1)

	def swap(arr, i, j): arr[i], arr[j] = arr[j], arr[i]

prat0318 / minHops.py

Last active March 15, 2016 22:33

ArrayHopper You are given an array of integers with values greater than or equal to 0, for example: [5, 6, 0, 4, 2, 4, 1, 0, 0, 4] You will develop and implement an algorithm to traverse the array in the shortest number of “hops” starting at index 0, Start at the first (0th) index of the array, look at the array value there, and you can hop forw…

	import fileinput

	def find_min(a, x, length):
	if length == 0: return float('inf'), -1
	if len(a) == (x+1): return 1, 'out'
	h = reduce(lambda x, y: (a[y], y) if x[0] > a[y] else x, range(x+1, min(len(a), x+1+length)), (float('inf'), -1))
	return h[0]+1, h[1]

	def find_min_hops(a):
	length = len(a)

prat0318 / permutations.py

Created December 16, 2013 05:48

Find all permutations

	def print_permutations(str):
	if(len(str) == 1): return [str]
	perms = print_permutations(str[1:])
	return [x[0:i]+str[0]+x[i:] for x in perms for i in range(len(x)+1)]

	print print_permutations("abc")

prat0318 / MyArray.java

Created December 16, 2013 22:17

binary search without outer bound.

	class MyArray {
	// returns null, if out-of-bounds index, returns value otherwise
	public Integer get(Integer index);

	public Integer search(Integer value) {
	// if(get(0) == value)return 0;
	int base = 0;
	while(true) {
	int index_jump = 1;
	while(get(base+index_jump) != null && get(base+index_jump) <= value) {

prat0318 / copy_node.py

Created January 3, 2014 23:13

Imagine you are given a network of nodes. Node objects contain no extra data except a list of neighbor nodes to which they are connected. Your goal is to write a copy function that will duplicate the entire structure of a graph that has already been instantiated in memory. The function takes a single starting node as input and outputs a complete…

	class Node:
	def __init__(self, nbrs):
	self.nbrs = nbrs

	def add_nbr(self, node_nbr):
	self.nbrs.append(node_nbr)

	def copy(self):
	return self.copy_recurse({})

prat0318 / substr.py

Created January 3, 2014 23:15

/* return a pointer to the first occurrence of needle in haystack (if none, return NULL) */ char *strstr(char *haystack, char *needle); haystack - N needle - K

	def strstr(haystack, needle):
	for i in range(len(haystack) - len(needle) + 1):
	match = True
	for j in range(len(needle)):
	if haystack[i+j] != needle[j]:
	match = False
	break
	if match == True: return i
	return None

prat0318 / PROBTNPO.py

Last active January 3, 2016 17:29

SPOJ - http://www.spoj.com/problems/PROBTNPO/

	import sys
	cache = {}
	while True:
	c = sys.stdin.readline()
	if c == '': break
	a1, b1 = c.split()
	a = int(a1); b = int(b1)
	max_length = 0
	a, b = min(a,b), max(a,b)
	if a < b/2: a = b/2

prat0318 / OperatorDelete.cpp

Last active August 29, 2015 13:56

operator delete(ptr) doesn't work when the ptr has been initialised with new as operator syntax. WHY?

	#include <iostream>
	#include <cstdint>

	using namespace std;
	int main() {
	cout<<"Hello World! \n";
	//For invalid pointer, uncomment the below line...
	//string* s = new string[10];
	//And comment the following two lines...
	string* s = (string ) operator new(10 sizeof(string));

prat0318 / awesomeness.py

Created March 1, 2014 23:57

There are three singers Prateek, Akanksha and gurbinder. They are doing a concert to celebrate my awesomeness. I have asked them to sing X distinct number of songs. Though each one of them want to sing all X songs, but due to their limits, each one has to sing P, A and G songs. All songs can be sung by either 1, 2 or 3 of them. Each of the X son…

	f = lambda i,j: int("{0:b}".format(i+1).zfill(3)[j])

	def func(x, p, a, g):
	if(p == 0 and a == 0 and g == 0 and x == 0): return 1
	if(p < 0 or a < 0 or g < 0 or p+a+g < x or x==0): return 0
	l = lambda count, pos: count + func(x-1, p-f(pos,0), a - f(pos,1), g - f(pos,2))
	return reduce(l, range(7), 0)

	print func(3,1,1,3) #9
	print func(50,10,10,10) #0

Prateek Agarwal prat0318