Hashmap
# HASH MAP implementation in python
class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.next = None
class HashMap:
def __init__(self):
self.store = [None for _ in range(16)]
def get(self, key):
index = hash(key) & 15
if self.store[index] is None:
return None
n = self.store[index]
while True:
if n.key == key:
return n.value
else:
if n.next:
n = n.next
else:
return None
def put(self, key, value):
nd = Node(key, value)
index = hash(key) & 15
n = self.store[index]
if n is None:
self.store[index] = nd
else:
if n.key == key:
n.value = value
else:
while n.next:
if n.key == key:
n.value = value
return
else:
n = n.next
n.next = nd
hm = HashMap()
hm.put("1", "sachin") |
Stack, queue, dequeue
#Queue #addition at the rear end and removal at the frond end FIFO
#Deque #items can be added or removed from the either end of the queue. so its like stack and queue together
# (front) 1 2 3 4 5 (rear)
class Queue(object):
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def size(self):
return len(self.items)
def enqueue(self,item):
self.items.insert(0,item)
def dequeue(self):
self.items.pop()
def printQueue(self):
for item in self.items:
print item
class Deque(object):
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def size(self):
return len(self.items)
def addFront(self,item):
self.append()
def addRear(self):
self.items.insert(0,item)
def removeFront(self,item):
self.items.pop()
def removeRear(self):
self.items.pop(0)
def printQueue(self):
for item in self.items:
print item
class stack(object):
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def size(self):
return len(self.items)
def push(self, item):
self.items.append(item)
def pop(self):
self.items.pop()
def peek(self, item):
#returns last pusehd item
return self.items[len(items)-1]
def printStack(self):
for item in self.items:
print item
s = stack()
print s.isEmpty()
s.push(6)
print s.isEmpty()
s.push(8)
s.push(9)
s.size()
s.pop()
s.printStack()
#s.pop()
print "stack done"
q = Queue()
q.isEmpty()
q.enqueue(6)
q.enqueue(8)
q.enqueue(9)
#q.printQueue()
q.dequeue()
q.printQueue() |
LinkedList
Singly linked list cycle check
class Node:
def __init__(self, val):
self.val = val
self.next = None
head = n = Node(3)
m = Node(4)
o = Node(5)
n.next = m
m.next = o
o.next = None
def insert(head, valuetoinsert):
current = head
while current != None:
if current.next == None:
current.next = Node(valuetoinsert)
current.next.next = None
print "return", head
return head
current = current.next
return head
def delete(head, valuetobedeleted):
current = head
prev = None
while current != None:
if current.val == valuetobedeleted:
if prev == None:
return current.next
prev.next = current.next
return head
prev = current
current = current.next
return head #did not find
def traverse(head):
current = head
while current != None:
print current.val
current = current.next
#head = insert(head, 6)
#head = insert(head, 8)
#head = delete(head, 6)
#head = insert(head, 10)
#traverse(head)
###################
def hasCycle(head):
if head == None or head.next == None:
return False
slow = head
fast = head
while fast != None and fast.next != None:
print "slow - ", slow.val
print "fast - ", fast.val
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
#traverse(head)
#print "CYCLE TEST "
#print hasCycle(head) |
Reversing a linked list
class Node:
def __init__(self, val):
self.next = None
self.val = val
def reverse_linked_list(head):
print ("reverse")
prev = None
cur = head
nex = None
while cur != None:
nex = cur.next
cur.next = prev
prev = cur
cur = nex
return prev
def traverse(head):
while head != None:
print (head.val)
head = head.next
a = Node(5)
b = Node(6)
c = Node(8)
a.next = b
b.next = c
traverse(a)
n = reverse_linked_list(a)
traverse(n)
|
Reverse doubly linked list
class Node:
def __init__(self, val):
self.next = None
self.prev = None
self.val = val
def reverse_doubly_linked_list(head):
print ("reverse")
temp = None
cur = head
new_head = None
while cur != None:
# swap prev and next pointers
temp = cur.next
cur.next = cur.prev
cur.prev = temp
if temp is None:
new_head = cur
cur = cur.prev
return new_head
def traverse(head):
while head != None:
print (head.val)
head = head.next
a = Node(5)
b = Node(6)
c = Node(8)
a.next = b
b.next = c
b.prev = a
c.prev = b
traverse(a)
n = reverse_doubly_linked_list(a)
traverse(n)
|
Print Nth to last node
def nthtoLastNode(head, n):
right = head
left = head
if head == None:
return None #
for i in xrange(n-1):
if right.next == None:
return None #error #number greater then elements in the list
right = right.next
while right != None:
left = left.next
right = right.next
return left.val
traverse(head)
print nthtoLastNode(head, 1) |
Search
Binary search
def binary_search(arr, ele):
if len(arr) == 0:
return False
if ele is None:
return False
first = 0
last = len(arr) - 1
while first <= last:
mid = (first + last) / 2
print "mid = ", mid
print "array ", arr
if arr[mid] == ele:
return True
else:
if ele < arr[mid]:
last = mid - 1
else:
first = mid + 1
return False
def rec_binary_search(arr, ele):
if len(arr) == 0:
return False
else:
mid = len(arr) / 2
print "mid =", mid
if arr[mid] == ele:
return True
else:
if ele < arr[mid]:
print "array", arr[:mid]
return rec_binary_search(arr[:mid], ele)
else:
print "array 11", arr[mid+1:]
return rec_binary_search(arr[mid+1:], ele)
arr = [3, 6, 8, 9, 10, 45, 78, 90, 100]
#arr = [10]
ele = 0
print binary_search(arr, ele)
#print rec_binary_search(arr, ele) |
Sequential search
def seq_search(arr, element):
for item in arr:
if item == element:
return True
return False
def seq_search_ordered(arr, element):
for item in arr:
print item
if item == element:
return True
else:
if item > element:
return False
return False
arr = [1, 7, 4, 12, 0, 3]
ele = 2
print seq_search(arr, ele)
arr.sort()
print seq_search_ordered(arr, ele)
|
Sort
Insertion sort
arr = [2,5,1,6,3]
for i in range(1, len(arr)):
key = arr[i]
# Move elements of arr[0..i-1], that are
# greater than key, to one position ahead
# of their current position
j = i-1
while j >= 0 and key < arr[j] :
print "j", arr[j]
print "j+1", arr[j+1]
arr[j + 1] = arr[j]
print arr
j -= 1
print "key", key
print "-----"
arr[j + 1] = key
print arr
print "----"
print arr |
Merge sort
def mergesort(arr):
print "ENTER"
if len(arr) > 1:
mid = len(arr)/2
left = arr[:mid]
#print "left", left
right = arr[mid:]
#print "right", right
#print "==========="
print "calling merge sort on left", left
mergesort(left)
print "calling merge sort of right", right
mergesort(right)
i=j=k=0
while i < len(left) and j < len(right):
if left[i] < right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1
while i < len(left):
arr[k] = left[i]
i += 1
k += 1
while j < len(right):
arr[k] = right[j]
j += 1
k += 1
print "end of while loops", arr
print "exit if", arr
arr = [4,2,45,23]
mergesort(arr) |
Selection sort
def selection_sort(arr):
for n in range(len(arr)-1,0,-1):
max = 0
for k in range(1, n+1):
if arr[k] > arr[max]:
max = k
temp = arr[n]
arr[n] = arr[max]
arr[max] = temp
arr=[1,66,22,4,2,55]
print selection_sort(arr)
print arr |
Backtracking
#Given two integers n and k, return all possible combinations of k numbers out of 1 ... n. #Input: n = 4, k = 2 #Ouput: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]] def combine(n, k):
def backtrack(first = 1, curr = []):
# if the combination is done
print ("backtrack ++ i, curr",first, curr)
if len(curr) == k:
output.append(curr[:])
print ("output", output)
print ("backtrack return")
return
for i in range(first, n + 1):
# add i into the current combination
curr.append(i)
#print ("after append i, curr", i, curr)
# use next integers to complete the combination
backtrack(i + 1, curr)
# backtrack
print("pop",curr.pop())
print ("backtrack --")
output = []
backtrack()
return output
print (combine(4, 2)) |
Palindrome partitioning
def partition(self, s):
res = []
self.dfs(s, [], res)
return res
def dfs(self, s, path, res):
if not s:
res.append(path)
return
for i in range(1, len(s)+1):
if self.isPal(s[:i]):
self.dfs(s[i:], path+[s[:i]], res)
def isPal(self, s):
return s == s[::-1] |
Amazon card from leetcode
Two sum problem
nums = [2, 1, 11, 15, 5, 4]
sum = 9
d = {}
for i in range(0, len(nums)):
c = sum - nums[i]
if c in d:
print ("output is ", c, nums[i])
print ("index", i, d[c])
d[nums[i]] = i
print (d) |
Longest substring without repeating chars
# Brute force
def is_all_unique(str):
s = set(str)
if len(s) != len(str):
return False
else:
return True
def longest_substring(str):
sub_len = 0
sub = ""
maxx = 0
for i in range(0, len(str)):
for j in range(i+1, len(str)+1):
if is_all_unique(str[i:j]):
sub_len = j - i
if sub_len > maxx:
maxx = sub_len
sub = str[i:j]
print (maxx)
print (sub)
return sub_len
print("#==========")
str = "abb"
longest_substring(str)
# sliding subset
def sliding_set(str):
i = j = 0
n = len(str)
s = set()
ans = 0
sub = ""
while (i < n and j < n):
if str[j] in s:
s.remove(str[i])
i = i + 1
else:
s.add(str[j])
j = j + 1
if (j-i) > ans:
ans = j - i
sub = str[i:j]
print (sub)
return ans
print (sliding_set(str))
print("#==========") |
Implement atoi which converts a string to an integer.
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned.
Note:
Only the space character ' ' is considered as whitespace character.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.
def my_atoi(str):
INT_MIN = -2 ** 31
INT_MAX = 2 ** 31 - 1
str = str.strip()
if str == "":
return 0
if str[0].isalpha():
return 0
sign = 0
start = 0
if str[0] == '-':
sign = 1
start = start + 1
res = 0
for i in range(start, len(str)):
if str[i].isdigit():
n = ord(str[i]) - ord('0')
res = res * 10 + n
else:
break
if sign == 1:
res = -res
if res < INT_MIN:
res = INT_MIN
if res > INT_MAX:
res = INT_MAX
return res
str = "42"
str1 = "-42"
str2 = "ambika 456"
str3 = "456 ambika"
str4 = "4147483648"
str5 = "-91283472332"
str6 = " -456 ambika"
print(str, my_atoi(str))
print(str1, my_atoi(str1))
print(str2, my_atoi(str2))
print(str3, my_atoi(str3))
print(str4, my_atoi(str4))
print(str5, my_atoi(str5))
print(str6, my_atoi(str6)) |
Container with most water
Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.
def max_area(height):
max_ = 0
for i in range(0, len(height)):
for j in range(i+1, len(height)):
h = min(height[i], height[j])
w = j - i
max_ = max(max_, (h*w))
return max_
h = [1,8,6,2,5,4,8,3,7]
print (max_area(h))
def max_area_opt(height):
max_ = 0
l = 0
r = len(height) - 1
while (l < r):
h = min(height[l], height[r])
w = r - l
max_ = max(max_, (h*w))
if height[l] < height[r]:
l = l + 1
else:
r = r - 1
return max_
h = [1,8,6,2,5,4,8,3,7]
print (max_area_opt(h)) |
Integer to roman
def intToRoman(num: int) -> str:
mapping = {
1: "I",
4: "IV",
5: "V",
9: "IX",
10: "X",
40: "XL",
50: "L",
90: "XC",
100: "C",
400: "CD",
500: "D",
900: "CM",
1000: "M",
}
arr = sorted(mapping.keys(),reverse=True)
result = ""
for a in arr:
while num >= a:
print (num,a)
num = num - a
result = result + mapping[a]
return result
print(intToRoman(30)) |
Using quotient method
for a in arr:
while num >= a: q = num // a
num = num % a
result = result + mapping[a] * q
return result
print(intToRoman(1994)) |
|
Roman to integer
def romanToInt(s):
sym={"I":1,"IV":4,"V":5,"IX":9,"X":10,"XL":40,"L":50,"XC":90,"C":100,"CD":400,"D":500,"CM":900,"M":1000}
if s in sym.keys():
return(sym[s])
else:
res = 0
for i in range(len(s)-1):
if sym[s[i]] >= sym[s[i+1]]:#If element at curr loc is larg than elem at next loc
res += sym[s[i]]#String concat
else:
res -= sym[s[i]]
res += sym[s[-1]]#for last element concat
return res
print(romanToInt("XC")) |
Three sum closest
def threeSumClosest(num, target):
num.sort()
result = num[0] + num[1] + num[2]
for i in range(len(num) - 2):
j = i+1
k = len(num) - 1
while j < k:
sum = num[i] + num[j] + num[k]
if sum == target:
return sum
if abs(sum - target) < abs(result - target):
result = sum
if sum < target:
j += 1
elif sum > target:
k -= 1
return result
nums = [-1, 2, 1, -4]
t = 1
print(threeSumClosest(nums, t)) |
Needle in haystack
h = "l lheljkll"
n = "ll"
h = h.replace(" ", "")
l = len(h) - len(n) + 1
for i in range(0, l):
if h[i:i+len(n)] == n:
print (h[i:i+len(n)], i)
print ("not found") |
Rotate matrix by 90degree anti clockwise
Find the transpose and reverse columns of the transpose
for i in range(N):
for j in range(i, N):
a[j][i], a[i][j] = a[i][j], a[j][i]
for i in range(N):
j = 0
k = N-1
while j < k:
a[j][i],a[k][i] = a[k][i],a[j][i]
j += 1
k -= 1 |
Rotate matrix by 90degree clockwise
The obvious idea would be to transpose the matrix first and then reverse each row. This simple approach already demonstrates the best possible time complexity o (n square) space - O(1)
class Solution:
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
n = len(matrix[0])
# transpose matrix
for i in range(n):
for j in range(i, n):
matrix[j][i], matrix[i][j] = matrix[i][j], matrix[j][i]
# reverse each row
for i in range(n):
matrix[i].reverse()
|
Group anagram
Given an array of strings, group anagrams together.
Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
Note:
import collections
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
ans = collections.defaultdict(list)
print (ans)
for s in strs:
t = tuple(sorted(s))
ans[t].append(s)
# If you want a list
l = []
for key in ans:
l.append(ans[key])
print (l) |
# Time Complexity: O(NK \log K), where N is the length of strs, and K is the maximum length of a string in strs.
# The outer loop has complexity O(N) as we iterate through each string. Then, we sort each string in O(KlogK) time.
# Space Complexity: O(NK), the total information content stored in ans.
import collections
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
ans = collections.defaultdict(list)
for s in strs:
count = [0] * 26
print ("c1",count)
for c in s:
count[ord(c) - ord('a')] += 1
print ("c2",count)
print ("tuple",tuple(count))
ans[tuple(count)].append(s)
print(ans.keys())
print(ans.values())
Time - O(NK) and Space - O(NK)
Most common word
Given a paragraph and a list of banned words, return the most frequent word that is not in the list of banned words. It is guaranteed there is at least one word that isn't banned, and that the answer is unique.
Words in the list of banned words are given in lowercase, and free of punctuation. Words in the paragraph are not case sensitive. The answer is in lowercase.
Input:
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]
Output: "ball"
Explanation:
"hit" occurs 3 times, but it is a banned word.
"ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph.
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as "ball,"),
and that "hit" isn't the answer even though it occurs more because it is banned.
class Solution(object):
def mostCommonWord(self, paragraph, banned):
banset = set(banned)
for c in "!?',;.":
paragraph = paragraph.replace(c, " ")
count = collections.Counter(
word for word in paragraph.lower().split())
ans, best = '', 0
for word in count:
if count[word] > best and word not in banset:
ans, best = word, count[word]
return ans |
Time - O(P+B) P is the size of the paragraph and B is the size of banned
Space - O(P+B)
Merge two sorted linked list
class Solution:
def mergeTwoLists(self, l1, l2):
# maintain an unchanging reference to node ahead of the return node.
prehead = ListNode(-1)
prev = prehead
while l1 and l2:
if l1.val <= l2.val:
prev.next = l1
l1 = l1.next
else:
prev.next = l2
l2 = l2.next
prev = prev.next
# exactly one of l1 and l2 can be non-null at this point, so connect
# the non-null list to the end of the merged list.
prev.next = l1 if l1 is not None else l2
return prehead.next |
Time complexity : O(n+m) Because exactly one of l1 and l2 is incremented on each loop iteration, the while loop runs for a number of iterations equal to the sum of the lengths of the two lists. All other work is constant, so the overall complexity is linear.
Space complexity : O(1)
The iterative approach only allocates a few pointers, so it has a constant overall memory footprint.
Comments
Post a Comment