Skip to content

Instantly share code, notes, and snippets.

View santhalakshminarayana's full-sized avatar

Santha Lakshmi Narayana santhalakshminarayana

View GitHub Profile
@santhalakshminarayana
santhalakshminarayana / Daily_coding_Problem_11.py
Created September 6, 2019 11:52
Implement an autocomplete system. That is, given a query string s and a set of all possible query strings, return all strings in the set that have s as a prefix.
'''
For example, given the query string 'de' and
the set of strings [dog, deer, deal],
return [deer, deal].
'''
class TrieNode:
def __init__(self):
self.next_chars=[None for i in range(26)]
self.is_end=False
@santhalakshminarayana
santhalakshminarayana / Daily_coding_Problem_12.py
Last active September 6, 2019 12:16
There exists a staircase with N steps, and you can climb up either 1 or 2 steps at a time. Given N, write a function that returns the number of unique ways you can climb the staircase. The order of the steps matters.
'''
For example, if N is 4, then there are 5 unique ways:
1, 1, 1, 1
2, 1, 1
1, 2, 1
1, 1, 2
2, 2
'''
@santhalakshminarayana
santhalakshminarayana / Daily_coding_Problem_13.py
Created September 15, 2019 17:50
Given an integer k and a string s, find the length of the longest substring that contains at most k distinct characters.
'''
For example, given s = "abcba" and k = 2, the longest substring with k distinct characters is "bcb".
'''
def long_substr(s,k):
long_st=0
has_found=0
dq=[]
mapp=dict()
for i,ch in enumerate(s):
@santhalakshminarayana
santhalakshminarayana / Daily_coding_Problem_14.py
Created September 15, 2019 18:18
The area of a circle is defined as πr^2. Estimate π to 3 decimal places using a Monte Carlo method.
import numpy as np
def dst_to_origin(x,y):
return np.sqrt(x*x + y*y)
def monte_carlo_pi():
'''
sq_area=(2*r)**2
cir_area=pi*(r**2)
@santhalakshminarayana
santhalakshminarayana / Daily_coding_Problem_15.py
Created September 15, 2019 18:53
Given a stream of elements too large to store in memory, pick a random element from the stream with uniform probability.
import random
def pick_random(l):
'''
l(list) : imagine stream is passed as list
in loop
'''
count=1
x=l[0]
print(x)
for i in l[1:]:
@santhalakshminarayana
santhalakshminarayana / Daily_coding_Problem_16.py
Last active September 15, 2019 19:10
You run an e-commerce website and want to record the last N order ids in a log. Implement a data structure to accomplish this, with the following API: ::) record(order_id): adds the order_id to the log ::) get_last(i) : gets the ith last element from the log. i is guaranteed to be smaller than or equal to N.
class Record_Last_N:
def __init__(self,last_n):
self.ord_list=[]
self.last_n=last_n
def record(self,order_id):
self.ord_list.append(r_id)
if len(self.ord_list) > self.last_n:
self.ord_list.pop(0)
def get_last(self,i):
@santhalakshminarayana
santhalakshminarayana / Daily_coding_Problem_17.py
Created September 15, 2019 20:23
Given a string representing the file system, return the length of the longest absolute path to a file in the abstracted file system.
'''
Suppose we represent our file system by a string in the following manner:
The string "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" represents:
dir
subdir1
subdir2
file.ext
The directory dir contains an empty sub-directory subdir1 and a sub-directory subdir2 containing a file file.ext.
@santhalakshminarayana
santhalakshminarayana / Daily_coding_Problem_18.py
Last active September 15, 2019 20:45
Given an array of integers and a number k, where 1 <= k <= length of the array, compute the maximum values of each subarray of length k.
'''
For example, given array = [10, 5, 2, 7, 8, 7] and k = 3, we should get: [10, 7, 8, 8], since:
10 = max(10, 5, 2)
7 = max(5, 2, 7)
8 = max(2, 7, 8)
8 = max(7, 8, 7)
'''
from collections import deque
def largest_subarray(arr,n,k):
'''
@santhalakshminarayana
santhalakshminarayana / imagetopdf_base.py
Created September 27, 2019 14:21
Convert Image documents to scanned PDF document in Python using OpenCv, PIL, Scikit-Image.
import numpy as np
import matplotlib.pyplot as plt
import cv2
from PIL import Image
from skimage.filters import threshold_local
import os
def plot_img(img,is_gray=True):
fig=plt.figure(figsize=(10,15))
ax=fig.add_subplot(111)
@santhalakshminarayana
santhalakshminarayana / imagetopdf_imports.py
Created September 27, 2019 14:27
Medium: Imagetopdf imports
import numpy as np
import matplotlib.pyplot as plt
import cv2
from PIL import Image
from skimage.filters import threshold_local
import os