Personal Page
https://medium.com/@rohitverma_87831/best-coding-interview-question-of-all-time-92f6cbdd656f [4,3,3,1,1,2]
We can use HashMap O(N) space and maintain count of each element of the array, as soon as we found an element whose count is more than 1 we found our answer. Or we can Sort array first O(NlogN) time . But there is solution without extra space:
- arr = [4, 1, 3, 2, 5, 4, 5, 5]
- take 4 and go to 4th index and make that number negative
- arr = [4, 1, 3, 2, -5, 4, 5,5]
- We also need to take absolute value.
- next process 1, arr = [4, -1, 3, 2, -5, 4, 5, 5]
- next process 3, arr = [4, -1, 3, -2, -5, 4, 5, 5]
- next process -2, arr = [4, -1, -3, -2, -5, 4, 5, 5]
- next process -5, arr = [4, -1, -3, -2, -5, -4, 5, 5]
- next process -4, arr = [4, -1, -3, -2, -5, -4, 5, 5] abs(-4) = 4
because 4th index is already negative it means that number 4 is encountered 2nd time So 4 is the answer.
int findAnyRepeatedNumber(int[] arr) {
for(int i = 0; i < arr.length; i++) {
int index = Math.abs(arr[i]);
if(arr[index] < 0) return index;
arr[index] = -arr[index];
}
throw new IllegalArgumentException("Invalid input array it should have elements in range [1, arr.length-1]");
}
In other words, one of the first string’s permutations is the substring of the second string.
# Examples:
# Input:s1 = "ab" s2 = "eidbaooo"
# Output:True
# Explanation: s2 contains one permutation of s1 ("ba")
# Input:s1= "ab" s2 = "eidboaoo"
# Output: False
def contains_permutation(s1: str, s2: str) -> bool:
from collections import Counter
len_s1, len_s2 = len(s1), len(s2)
if len_s1 > len_s2:
return False
s1_counter = Counter(s1)
window_counter = Counter(s2[:len_s1])
if s1_counter == window_counter:
return True
for i in range(len_s1, len_s2):
start_char = s2[i - len_s1]
end_char = s2[i]
window_counter[end_char] += 1
window_counter[start_char] -= 1
if window_counter[start_char] == 0:
del window_counter[start_char]
if window_counter == s1_counter:
return True
return False
https://stackoverflow.com/questions/20253580/hash-table-implementation-in-python
https://stackabuse.com/hash-tables-in-python/
class HashTable:
def __init__(self, size):
self.size = size
self.table = [[] for _ in range(size)]
def _hash(self, key):
return ord(key[0]) % self.size
def set(self, key, value):
hash_index = self._hash(key)
for kvp in self.table[hash_index]:
if kvp[0] == key:
kvp[1] = value
return
self.table[hash_index].append([key, value])
def get(self, key):
hash_index = self._hash(key)
for kvp in self.table[hash_index]:
if kvp[0] == key:
return kvp[1]
raise KeyError(f'Key {key} not found')
def remove(self, key):
hash_index = self._hash(key)
for i, kvp in enumerate(self.table[hash_index]):
if kvp[0] == key:
self.table[hash_index].pop(i)
return
raise KeyError(f'Key {key} not found')
https://habr.com/ru/articles/794556/
class HashTable:
def __init__(self):
self.hashTable = [[],] * 10
def checkPrime(self, n):
if n == 1 or n == 0:
return 0
for i in range(2, n//2):
if n % i == 0:
return 0
return 1
def getPrime(self, n):
if n % 2 == 0:
n = n + 1
while not self.checkPrime(n):
n += 2
return n
def hashFunction(self, key):
capacity = self.getPrime(10)
return key % capacity
def insertData(self, key, data):
index = self.hashFunction(key)
self.hashTable[index] = [key, data]
def removeData(self, key):
index = self.hashFunction(key)
self.hashTable[index] = 0
def __str__(self):
return str(self.hashTable)
hash_table = HashTable()
hash_table.insertData(123, "apple")
hash_table.insertData(432, "mango")
hash_table.insertData(213, "banana")
hash_table.insertData(654, "guava")
print(hash_table)
hash_table.removeData(123)
print(hash_table)
# [[], [], [123, 'apple'], [432, 'mango'], [213, 'banana'], [654, 'guava'], [], [], [], []]
# [[], [], 0, [432, 'mango'], [213, 'banana'], [654, 'guava'], [], [], [], []]
https://www.educative.io/blog/apple-coding-interview-questions
def has_triplet_with_sum(arr, target):
arr.sort()
n = len(arr)
for i in range(n - 2):
left, right = i + 1, n - 1
while left < right:
current_sum = arr[i] + arr[left] + arr[right]
if current_sum == target:
return True
elif current_sum < target:
left += 1
else:
right -= 1
return False
For each letter in the input string, start expanding to the left and right
while checking for even and odd length palindromes.
Move to the next letter if we know a palindrome doesn’t exist there.
def all_palindrome_substrings(s):
n = len(s)
palindromes = set()
for center in range(n):
# Odd-length palindromes
l, r = center, center
while l >= 0 and r < n and s[l] == s[r]:
palindromes.add(s[l:r+1])
l -= 1
r += 1
# Even-length palindromes
l, r = center, center + 1
while l >= 0 and r < n and s[l] == s[r]:
palindromes.add(s[l:r+1])
l -= 1
r += 1
return list(palindromes)
def findPairs(arr1, arr2, n, m, x):
# Insert all elements of
# first array in a hash
s = set()
for i in range (0, n):
s.add(arr1[i])
# Subtract sum from second array elements one by one
# and check it's present in array first or not
for j in range(0, m):
if ((x - arr2[j]) in s):
print((x - arr2[j]), '', arr2[j])
# Driver code
arr1 = [1, 0, -4, 7, 6, 4]
arr2 = [0, 2, 4, -3, 2, 1]
x = 8
n = len(arr1)
m = len(arr2)
findPairs(arr1, arr2, n, m, x)
A function to randomly select a item from stream[0], stream[1], .. stream[i-1]
import random
res=0
# Count of numbers visited so far in stream
count=0
def selectRandom(x):
global res
global count
# increment count of numbers seen so far
count += 1;
# If this is the first element from stream, return it
if (count == 1):
res = x;
else:
# Generate a random number from 0 to count - 1
i = random.randrange(count);
# Replace the prev random number with new number with 1/count probability
if (i == count - 1):
res = x;
return res;
# Driver Code
stream = [1, 2, 3, 4];
n = len(stream);
# Use a different seed value
# for every run.
for i in range (n):
print("Random number from first",
(i + 1), "numbers is",
selectRandom(stream[i]));
If the data set has an odd number then the middle one will be consider as median.
If the data set has an even number then there is no distinct middle value and
the median will be the arithmetic mean of the two middle values.
We can use a max heap on the left side to represent elements that are less than effective median,
and a min-heap on the right side to represent elements that are greater than effective median.
After processing an incoming element, the number of elements in heaps differs atmost by 1 element.
When both heaps contain the same number of elements, we pick the average of heaps root data as effective median.
When the heaps are not balanced, we select effective median from the root of the heap containing more elements.
Time Complexity: O(n * log n),
All the operations within the loop (push, pop) take O(log n) time in the worst case for a heap of size N.
Auxiliary Space: O(n)
Function to find the median of stream of data
from heapq import heappush, heappop, heapify
import math
def streamMed(arr, N):
# Declaring two min heap
g = []
s = []
for i in range(len(arr)):
# Negation for treating it as max heap
heappush(s, -arr[i])
heappush(g, -heappop(s))
if len(g) > len(s):
heappush(s, -heappop(g))
if len(g) != len(s):
print(-s[0])
else:
print((g[0] - s[0])/2)
# Driver code
if __name__ == '__main__':
A = [5, 15, 1, 3, 2, 8, 7, 9, 10, 6, 11, 4]
N = len(A)
# Function call
streamMed(A, N)
Given k sorted arrays of possibly different sizes, find m-th smallest value in the merged array.
The time complexity of heap based solution is O(m Log k).
1. Create a min heap of size k and insert 1st element in all the arrays into the heap
2. Repeat following steps m times
…..a) Remove minimum element from heap (minimum is always at root) and store it in output array.
…..b) Insert next element from the array from which the element is extracted. If the array doesn’t have any more elements, then do nothing.
3. Print the last removed item.
This function takes an array of arrays as an argument and
all arrays are assumed to be sorted.
It returns m-th smallest element in the array obtained after merging the given arrays.
from heapq import *
def mThLargest(arr, m):
# Create a min heap. Every
# heap node has first element of an array
pq = []
for i in range(len(arr)):
heappush(pq, (arr[i][0], (i, 0)))
# Now one by one get the minimum element
# from min heap and replace it with next
# element of its array
count = 0
while count < m and pq:
curr = heappop(pq)
# i ==> Array Number
# j ==> Index in the array number
i = curr[1][0]
j = curr[1][1]
# The next element belongs to same array as current.
if j + 1 < len(arr[i]):
heappush(pq, (arr[i][j + 1], (i, j + 1)))
count += 1
return arr[i][j]
# Driver Code
arr = [[2, 6, 12], [1, 9], [23, 34, 90, 2000]]
m = 4
print(mThLargest(arr, m))
Create two variables, start=0, currentSum = arr[0]
Traverse the array from index 1 to end.
Update the variable currentSum by adding current element, currentSum = currentSum + arr[i]
If the currentSum is greater than the given sum, update the variable currentSum as currentSum = currentSum – arr[start],
and update start as, start++.
If the currentSum is equal to given sum, print the subarray and break the loop.
def subArraySum(arr, n, sum_):
# Initialize currentSum as value of first element and starting point as 0
currentSum = arr[0]
start = 0
# Add elements one by one to currentSum and if the currentSum exceeds
# the sum, then remove starting element
i = 1
while i <= n:
# If currentSum exceeds
# the sum, then remove
# the starting elements
while currentSum > sum_ and start < i-1:
currentSum = currentSum - arr[start]
start += 1
# If currentSum becomes
# equal to sum, then
# return true
if currentSum == sum_:
print("Sum found between indexes % d and % d" % (start, i-1))
return 1
# Add this element
# to currentSum
if i < n:
currentSum = currentSum + arr[i]
i += 1
# If we reach here, then no subarray
print("No subarray found")
return 0
# Driver program
if __name__ == '__main__':
arr = [15, 2, 4, 8, 9, 5, 10, 23]
n = len(arr)
sum_ = 23
subArraySum(arr, n, sum_)
def rotateMatrix(mat):
# reversing the matrix
for i in range(len(mat)):
mat[i].reverse()
# make transpose of the matrix
for i in range(len(mat)):
for j in range(i, len(mat)):
# swapping mat[i][j] and mat[j][i]
mat[i][j], mat[j][i] = mat[j][i], mat[i][j]
# Function to print the matrix
def displayMatrix(mat):
for i in range(0, len(mat)):
for j in range(0, len(mat)):
print(mat[i][j], end=' ')
print()
# Driver code
if __name__ == "__main__":
mat = [[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]]
# Function call
rotateMatrix(mat)
# Print rotated matrix
displayMatrix(mat)
1) Initialize count as 0
2) Sort all numbers in increasing order. O(nLogn) t
3) Remove duplicates from array.
4) Do following for each element arr[i]
a) Binary Search for arr[i] + k in subarray from i+1 to n-1.
b) If arr[i] + k found, increment count.
5) Return count.
def binarySearch(arr, low, high, x):
if (high >= low):
mid = low + (high - low)//2
if x == arr[mid]:
return (mid)
elif(x > arr[mid]):
return binarySearch(arr, (mid + 1), high, x)
else:
return binarySearch(arr, low, (mid - 1), x)
return -1
# Returns count of pairs with
# difference k in arr[] of size n.
def countPairsWithDiffK(arr, n, k):
count = 0
arr.sort() # Sort array elements
# code to remove duplicates from arr[] -
# TODO another approach to remove duplicated in arr and sort results : sorted(set(arr)) require extra space
# Pick a first element point
i = 0
while(i < n):
while(i - 1 >= 0 and arr[i] == arr[i - 1]):
i += 1
if (binarySearch(arr, i + 1, n - 1,
arr[i] + k) != -1):
count += 1
i += 1
return count
# Driver Code
arr = [1, 5, 3, 4, 2]
n = len(arr)
k = 3
print("Count of pairs with given diff is ",
countPairsWithDiffK(arr, n, k))
The maximum value on multiplying all values but the point is to handle the case of 0 and 1.
On multiplying with 0 and 1 we get the lower value as compared to on adding with 0 and 1
def calcMaxValue(str):
# Store first character as integer in result
res = ord(str[0]) - 48
# Start traversing the string
for i in range(1, len(str)):
# Check if any of the two numbers
# is 0 or 1, If yes then add current
# element
if(str[i] == '0' or
str[i] == '1' or res < 2):
res += ord(str[i]) - 48
else:
res *= ord(str[i]) - 48
return res
# Driver code
if __name__== "__main__":
str = "01891";
print(calcMaxValue(str));
Prints largest subset of an array whose all elements are fibonacci numbers
def findFibSubset(arr, n):
# Find maximum element in arr[]
m= max(arr)
# Generate all Fibonacci numbers till max and store them in hash.
a = 0
b = 1
hash = []
hash.append(a)
hash.append(b)
while (b < m):
c = a + b
a = b
b = c
hash.append(b)
# Npw iterate through all numbers andquickly check for Fibonacci using hash.
for i in range (n):
if arr[i] in hash :
print( arr[i],end=" ")
# Driver code
if __name__ == "__main__":
arr = [4, 2, 8, 5, 20, 1, 40, 13, 23]
n = len(arr)
findFibSubset(arr, n)
O(n) solution for finding smallest subarray with sum greater than x
# Returns length of smallest subarray with sum greater than x.
# If there is no subarray with given sum, then returns n + 1
def smallestSubWithSum(arr, n, x):
# Initialize current sum and minimum length
curr_sum = 0
min_len = n + 1
# Initialize starting and ending indexes
start = 0
end = 0
while (end < n):
# Keep adding array elements while current
# sum is smaller than or equal to x
while (curr_sum <= x and end < n):
curr_sum += arr[end]
end += 1
# If current sum becomes greater than x.
while (curr_sum > x and start < n):
# Update minimum length if needed
if (end - start < min_len):
min_len = end - start
# remove starting elements
curr_sum -= arr[start]
start += 1
return min_len
# Driver program
arr1 = [1, 4, 45, 6, 10, 19]
x = 51
n1 = len(arr1)
res1 = smallestSubWithSum(arr1, n1, x)
print("Not possible") if (res1 == n1 + 1) else print(res1)
arr2 = [1, 10, 5, 2, 7]
n2 = len(arr2)
x = 9
res2 = smallestSubWithSum(arr2, n2, x)
print("Not possible") if (res2 == n2 + 1) else print(res2)
arr3 = [1, 11, 100, 1, 0, 200, 3, 2, 1, 250]
n3 = len(arr3)
x = 280
res3 = smallestSubWithSum(arr3, n3, x)
print("Not possible") if (res3 == n3 + 1) else print(res3)
def findTriplets(arr, n):
found = False
# sort array elements
arr.sort()
for i in range(0, n-1):
# initialize left and right
l = i + 1
r = n - 1
x = arr[i]
while (l < r):
if (x + arr[l] + arr[r] == 0):
# print elements if it's sum is zero
print(x, arr[l], arr[r])
l += 1
r -= 1
found = True
# If sum of three elements is less
# than zero then increment in left
elif (x + arr[l] + arr[r] < 0):
l += 1
# if sum is greater than zero then
# decrement in right side
else:
r -= 1
if (found == False):
print(" No Triplet Found")
# Driven source
arr = [0, -1, 2, -3, 1]
n = len(arr)
findTriplets(arr, n)
def binary_search(arr, start, end, key):
# assuming all the keys are unique.
if (start > end):
return -1;
mid = int(start + (end - start) / 2)
if arr[mid] == key:
return mid
if arr[start] <= arr[mid] and key <= arr[mid] and key >= arr[start]:
return binary_search(arr, start, mid - 1, key)
elif arr[mid] <= arr[end] and key >= arr[mid] and key <= arr[end]:
return binary_search(arr, mid + 1, end, key)
elif arr[end] <= arr[mid]:
return binary_search(arr, mid + 1, end, key)
elif arr[start] >= arr[mid]:
return binary_search(arr, start, mid - 1, key)
return -1;
def binary_search_rotated(arr, key):
return binary_search(arr, 0, len(arr)-1, key)
v1 = [6, 7, 1, 2, 3, 4, 5];
print("Key(3) found at: " + str(binary_search_rotated(v1, 3)))
print("Key(6) found at: " + str(binary_search_rotated(v1, 6)))
v2 = [4, 5, 6, 1, 2, 3];
print("Key(3) found at: " + str(binary_search_rotated(v2, 3)))
print("Key(6) found at: " + str(binary_search_rotated(v2, 6)))
def find_low_index(arr, key):
low = 0
high = len(arr) - 1
mid = int(high / 2)
while low <= high:
mid_elem = arr[mid]
if mid_elem < key:
low = mid + 1
else:
high = mid - 1
mid = low + int((high - low) / 2)
if low < len(arr) and arr[low] == key:
return low
return -1
def find_high_index(arr, key):
low = 0
high = len(arr) - 1
mid = int(high / 2)
while low <= high:
mid_elem = arr[mid]
if mid_elem <= key:
low = mid + 1
else:
high = mid - 1
mid = low + int((high - low) / 2);
if high == -1:
return high
if high < len(arr) and arr[high] == key:
return high
return -1
array = [1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 6, 6]
key = 5
low = find_low_index(array, key)
high = find_high_index(array, key)
print("Low Index of " + str(key) + ": " + str(low))
print("High Index of " + str(key) + ": " + str(high))
key = -2
low = find_low_index(array, key)
high = find_high_index(array, key)
print("Low Index of " + str(key) + ": " + str(low))
print("High Index of " + str(key) + ": " + str(high))
n = size of given integer set
subsets_count = 2^n
for i = 0 to subsets_count
form a subset using the value of 'i' as following:
bits in number 'i' represent index of elements to choose from original set,
if a specific bit is 1 choose that number from original set and add it to current subset,
e.g. if i = 6 i.e 110 in binary means that 1st and 2nd elements in original array need to be picked.
add current subset to list of all subsets
def get_bit(num, bit):
temp = (1 << bit)
temp = temp & num
if temp == 0:
return 0
return 1
def get_all_subsets(v, sets):
subsets_count = 2 ** len(v)
for i in range(0, subsets_count):
st = set([])
for j in range(0, len(v)):
if get_bit(i, j) == 1:
st.add(v[j])
sets.append(st)
def main():
v = [8,13,3,22,17,39,87,45,36]
subsets = []
get_all_subsets(v, subsets);
print("****Total*****" + str(len(subsets)))
for i in range(0, len(subsets)):
print("{", end = "")
print(subsets[i], end = "")
print("}")
print("****Total*****" + str(len(subsets)))
main()
from directed_graph import *
def clone_rec(root, graph, nodes_completed):
# Base case when there is no node
if not root:
return None
# Creating new vertex/node
pNew = Node(root.data)
# Using hashmap to keep track of visited nodes
nodes_completed[root] = pNew
# Adding new vertex in the graph
graph.add_vertex_in_nodes(pNew)
# Iterate over each neighbor of the current vertex/node
for p in root.neighbors:
x = nodes_completed.get(p)
if not x:
# If node is not visited call recursive function to create vertex/node
pNew.neighbors.append(clone_rec(p, graph, nodes_completed))
else:
# If node is visited just add it to the neighbors of current vertex/node
pNew.neighbors.append(x)
return pNew
def clone(graph):
# Hashmap to keep record of visited nodes
nodes_completed = {}
# Creating new graph
clone_graph = DirectedGraph()
# clone_rec function call
# Passing first node as root node
if not graph.nodes:
return None
else:
clone_rec(graph.nodes[0], clone_graph, nodes_completed)
# Return deep copied graph
return clone_graph
def main():
# Main start from here
g1 = DirectedGraph()
print("------------ EXAMPLE # 1 -----------")
# Adding verteces/nodes
g1.add_vertex(0)
g1.add_vertex(1)
g1.add_vertex(2)
g1.add_vertex(3)
g1.add_vertex(4)
# Adding edges of vertex/node 0
g1.add_edge(0, 2)
g1.add_edge(0, 3)
g1.add_edge(0, 4)
# Adding edges of vertex/node 1
g1.add_edge(1, 2)
# Adding edges of vertex/node 2
g1.add_edge(2, 0)
# Adding edges of vertex/node 3
g1.add_edge(3, 2)
# Adding edges of vertex/node 4
g1.add_edge(4, 1)
g1.add_edge(4, 3)
g1.add_edge(4, 0)
# Printing graph
print("Original graph (before copy): ")
print(g1)
g1_copy = clone(g1)
print("Cloned graph (after copy):")
print(g1_copy)
print("\nOriginal graph (after deleting an edge [0->2]):")
g1.delete_edge(0, 2)
print(g1)
print("\nCloned graph (after deleting an edge [0->2] from original the graph): ")
print(g1_copy)
g2 = DirectedGraph()
# Adding verteces/nodes
print("\n\n------------ EXAMPLE # 2 -----------")
g2.add_vertex("v1")
g2.add_vertex("v2")
g2.add_vertex("v3")
g2.add_vertex("v4")
g2.add_vertex("v5")
g2.add_edge("v1", "v2")
g2.add_edge("v1", "v3")
g2.add_edge("v1", "v4")
g2.add_edge("v2", "v1")
g2.add_edge("v2", "v3")
g2.add_edge("v2", "v4")
g2.add_edge("v3", "v1")
g2.add_edge("v3", "v2")
g2.add_edge("v3", "v4")
g2.add_edge("v3", "v5")
g2.add_edge("v4", "v1")
g2.add_edge("v4", "v2")
g2.add_edge("v4", "v3")
g2.add_edge("v4", "v5")
g2.add_edge("v5", "v3")
print("Original graph (before copy):")
print(g2)
g2_copy = clone(g2)
print("\nCloned graph (after copy):")
print(g2_copy)
print("\nOriginal graph (after deleting an edge [v5->v3]):")
g2.delete_edge("v5", "v3")
print(g2)
print("\nCloned graph (after deleting an edge [v5->v3] from original the graph): ")
print(g2_copy)
if __name__ == '__main__':
main()
Given a dictionary of words and a large input string.
You have to find out whether the input string can be completely segmented
into the words of a given dictionary.
def can_segment_string(s, dictionary):
for i in range(1, len(s) + 1):
first = s[0:i]
if first in dictionary:
second = s[i:]
if not second or second in dictionary or can_segment_string(second, dictionary):
return True
return False
s = "hellonow";
dictionary= set(["hello","hell","on","now"])
if can_segment_string(s, dictionary):
print("String Can be Segmented")
else:
print("String Can NOT be Segmented")
Reverse the order of words in a given sentence (an array of characters).
def str_rev(str, start, end):
if str == None or len(str) < 2:
return
while start < end:
temp = str[start]
str[start] = str[end]
str[end] = temp
start += 1
end -= 1
def reverse_words(sentence):
# Here sentence is a null-terminated string ending with char '\0'.
if sentence == None or len(sentence) == 0:
return
# To reverse all words in the string, we will first reverse
# the string. Now all the words are in the desired location, but
# in reverse order: "Hello World" -> "dlroW olleH".
str_len = len(sentence)
str_rev(sentence, 0, str_len - 1)
# Now, let's iterate the sentence and reverse each word in place.
# "dlroW olleH" -> "World Hello"
start = 0
end = 0
while True:
# find the start index of a word while skipping spaces.
while start < len(sentence) and sentence[start] == ' ':
start += 1
if start == str_len:
break
# find the end index of the word.
end = start + 1
while end < str_len and sentence[end] != ' ':
end += 1
# let's reverse the word in-place.
str_rev(sentence, start, end - 1)
start = end
def get_array(t):
s = array('u', t)
return s
def print_array(s):
i = 0
while i != len(s):
stdout.write(s[i])
i += 1
print ()
s = get_array('Hello World!')
print_array(s)
reverse_words(s)
print_array(s)
https://www.educative.io/blog/cracking-top-facebook-coding-interview-questions
Keep two markers: read_index and write_index and point them to the end of the array.
While moving read_index towards the start of the array:
If read_index points to 0, skip.
If read_index points to a non-zero value, write the value at read_index to write_index and decrement write_index.
Assign zeros to all the values before the write_index and to the current position of write_index as well.
```python
def move_zeros_to_left(A):
if len(A) < 1:
return
lengthA = len(A)
write_index = lengthA - 1
read_index = lengthA - 1
while(read_index >= 0):
if A[read_index] != 0:
A[write_index] = A[read_index]
write_index -= 1
read_index -= 1
while(write_index >= 0):
A[write_index]=0;
write_index-=1
v = [1, 10, 20, 0, 59, 63, 0, 88, 0]
print("Original Array:", v)
move_zeros_to_left(v)
print("After Moving Zeroes to Left: ", v)
class Pair:
def __init__(self, first, second):
self.first = first
self.second = second
def merge_intervals(v):
if v == None or len(v) == 0 :
return None
result = []
result.append(Pair(v[0].first, v[0].second))
for i in range(1, len(v)):
x1 = v[i].first
y1 = v[i].second
x2 = result[len(result) - 1].first
y2 = result[len(result) - 1].second
if y2 >= x1:
result[len(result) - 1].second = max(y1, y2)
else:
result.append(Pair(x1, y1))
return result;
v = [Pair(1, 5), Pair(3, 1), Pair(4, 6),
Pair(6, 8), Pair(10, 12), Pair(11, 15)]
result = merge_intervals(v)
for i in range(len(result)):
print("[" + str(result[i].first) + ", " + str(result[i].second) + "]", end =" ")
https://towardsdatascience.com/4-types-of-tree-traversal-algorithms-d56328450846
We’ll use a pre-order traversal here.
We’ll also serialize some markers to represent a null pointer to help deserialize the tree.
from binary_tree import *
from binary_tree_node import *
# Initializing our marker as the max possible int value
MARKER = float('inf')
def serialize_rec(node, stream):
# Adding marker to stream if the node is None
if (node == None):
stream.append(MARKER)
return
# Adding node to stream
stream.append(node.data)
# Doing a pre-order tree traversal for serialization
serialize_rec(node.left, stream)
serialize_rec(node.right, stream)
# Function to serialize tree into list of integer.
def serialize(root):
stream = []
serialize_rec(root, stream)
return stream
# Function to deserialize integer list into a binary tree.
def deserialize(stream):
# dequeue first element form list
val = stream.pop(0)
# Return None when a marker is encountered
if (val == MARKER):
return None
# Creating new Binary Tree Node from current value from stream
node = BinaryTreeNode(val)
# Doing a pre-order tree traversal for serialization
node.left = deserialize(stream)
node.right = deserialize(stream)
# Return node if it exists
return node
def main():
input1 = [100, 50, 200, 25, 75, 350]
tree1 = BinaryTree(input1)
orgTree1 = tree1.get_tree_deep_copy()
tree2 = BinaryTree(100)
tree2.insert_bt(200)
tree2.insert_bt(75)
tree2.insert_bt(50)
tree2.insert_bt(25)
tree2.insert_bt(350)
orgTree2 = tree2.get_tree_deep_copy()
tree3 = BinaryTree(200)
tree3.insert_bt(350)
tree3.insert_bt(100)
tmp = tree3.find_in_BT(350)
tmp.right = BinaryTreeNode(75)
tmp.right.right = BinaryTreeNode(50)
tmp = tree3.find_in_BT(100)
tmp.left = BinaryTreeNode(25)
orgTree3 = tree3.get_tree_deep_copy()
input4 = [100, 50, 200, 25, 75, 350]
input4.sort()
tree4 = BinaryTree(input4)
orgTree4 = tree4.get_tree_deep_copy()
input5 = reversed(input4)
tree5 = BinaryTree(input5)
orgTree5 = tree5.get_tree_deep_copy()
tree6 = BinaryTree(100)
orgTree6 = tree6.get_tree_deep_copy()
# Defining test cases
inputs = [tree1.root, tree2.root, tree3.root,
tree4.root, tree5.root, tree6.root, None]
original_trees =[orgTree1, orgTree2, orgTree3, orgTree4, orgTree5, orgTree6, None]
for i in range(len(inputs)):
if (i > 0):
print("\n")
print(str(i + 1) + ".\tBinary tree:")
if (original_trees[i] == None):
display_tree(None)
else:
display_tree(original_trees[i].root)
print("\n\tMarker used for NULL nodes in serialization/deserialization: " + str(MARKER))
# Serialization
ostream = serialize(inputs[i])
print("\n\tSerialized integer list:")
print("\t" + str(ostream))
# Deserialization
deserialized_root = deserialize(ostream)
print("\n\tDeserialized binary tree:")
display_tree(deserialized_root)
print("----------------------------------------------------------------------------------------------------")
if __name__ == '__main__':
main()
traverse a string make first character as root and do following step recursively
If we see Symbol ‘?’ then we add next character as the left child of root.
If we see Symbol ‘:’ then we add it as the right child of current root.
class Node:
def __init__(self, key):
self.data = key
self.left = None
self.right = None
# Function to convert ternary
# expression to a Binary tree
# It returns the root node
# of the tree
def convert_expression(expression, i):
if i >= len(expression):
return None
# Create a new node object
# for the expression at
# ith index
root = Node(expression[i])
i += 1
# if current character of
# ternary expression is '?'
# then we add next character
# as a left child of
# current node
if (i < len(expression) and
expression[i] is "?"):
root.left = convert_expression(expression, i + 1)
# else we have to add it
# as a right child of
# current node expression[0] == ':'
elif i < len(expression):
root.right = convert_expression(expression, i + 1)
return root
# Function to print the tree
# in a pre-order traversal pattern
def print_tree(root):
if not root:
return
print(root.data, end=' ')
print_tree(root.left)
print_tree(root.right)
# Driver Code
if __name__ == "__main__":
string_expression = "a?b?c:d:e"
root_node = convert_expression(string_expression, 0)
print_tree(root_node)
from binary_tree import *
from binary_tree_node import *
# Initializing the first and the last nodes
first = None
last = None
def convert_to_linked_list_rec(curr_node):
global first
global last
# Return if the current node is None
if not curr_node:
return
else:
# Performing in-order tree traversal
convert_to_linked_list_rec(curr_node.left)
if last:
# Connecting the last and current nodes
last.right = curr_node
curr_node.left = last
else:
# Initializing the first node
first = curr_node
# Updating the current node
last = curr_node
convert_to_linked_list_rec(curr_node.right)
def convert_to_linked_list(root):
global first
global last
if not root:
# Return null if the root doesn't exist
return None
else:
first = None
last = None
convert_to_linked_list_rec(root)
# Closing the linked list
last.right = None
first.left = None
return first
def main():
input1 = [100, 50, 200, 25, 75, 125, 350]
tree1 = BinaryTree(input1)
tree2 = BinaryTree(100)
tree2.insert(50)
tree2.insert(200)
tree2.insert(25)
# Add a node at an incorrect position
tree2.insert_bt(110)
tree2.insert(125)
tree2.insert(350)
tree3 = BinaryTree(100)
tree3.insert(50)
tree3.insert(200)
tree3.insert(25)
tree3.insert(75)
# Add a node at an incorrect position
tree3.insert_bt(90)
tree3.insert(350)
input4 = [100, 50, 200, 25, 75, 125, 350]
input4.sort()
tree4 = BinaryTree(input4)
input5 = reversed(input4)
tree5 = BinaryTree(input5)
tree6 = BinaryTree(100)
# Defining test cases
test_case_roots = [tree1.root, tree2.root, tree3.root,
tree4.root, tree5.root, tree6.root, None]
for i in range(len(test_case_roots)):
if i > 0:
print()
print(str(i + 1) + ".\tBinary tree:")
display_tree(test_case_roots[i])
print("\n\tDoubly Linked List:")
get_dll_list(convert_to_linked_list(test_case_roots[i]))
print("----------------------------------------------------------------------------------------------------")
if __name__ == '__main__':
main()
###
Given the root of a binary tree, display the node values at each level.
Node values for all levels should be displayed on separate lines.
Here, you are using two queues: current_queue and next_queue.
You push the nodes in both queues alternately based on the current level number.
You’ll dequeue nodes from the current_queue, print the node’s data,
and enqueue the node’s children to the next_queue.
Once the current_queue becomes empty, you have processed all nodes for the current level_number. To indicate the new level, print a line break (\n), swap the two queues, and continue with the above-mentioned logic.
After printing the leaf nodes from the current_queue, swap current_queue and next_queue.
Since the current_queue would be empty, you can terminate the loop.
from collections import deque
from binary_tree import *
from binary_tree_node import *
# Using two queues
def level_order_traversal(root):
# We print None if the root is None
if not root:
print("None", end="")
else:
result = ""
# Declaring an array of two queues
queues = [deque(), deque()]
# Initializing the current and next queues
current_queue = queues[0]
next_queue = queues[1]
# Enqueuing the root node into the current queue and setting
# level to zero
current_queue.append(root)
level_number = 0
# Printing nodes in level-order until the current queue remains
# empty
while current_queue:
# Dequeuing and printing the first element of queue
temp = current_queue.popleft()
print(str(temp.data), end="")
result += str(temp.data) + ""
# Adding dequeued node's children to the next queue
if temp.left:
next_queue.append(temp.left)
if temp.right:
next_queue.append(temp.right)
# When the current queue is empty, we increase the level, print a new line
# and swap the current and next queues
if not current_queue:
level_number += 1
if next_queue:
print(" : ", end="")
current_queue = queues[level_number % 2]
next_queue = queues[(level_number + 1) % 2]
else:
print(", ", end="")
def main():
# Creating a binary tree
input1 = [100, 50, 200, 25, 75, 350]
tree1 = BinaryTree(input1)
# Creating a right degenerate binary tree
input2 = sorted(input1)
tree2 = BinaryTree(input2)
# Creating a left degenerate binary tree
input2.reverse()
tree3 = BinaryTree(input2)
# Creating a single node binary tree
tree4 = BinaryTree(100)
test_case_roots = [tree1.root, tree2.root, tree3.root, tree4.root, None]
test_case_statements = ["Level-Order Traversal of a normal binary search tree: ",
"Level-Order Traversal of a right degenerate binary search tree: ",
"Level-Order Traversal of a left degenerate binary search tree: ",
"Level-Order Traversal of a single node binary tree: ",
"Level-Order Traversal of a null tree: "]
for i in range(len(test_case_roots)):
if (i > 0):
print()
print(str(i + 1) + ". Binary Tree:")
display_tree(test_case_roots[i])
print("\n " + test_case_statements[i],end="\n ")
# Printing the in-order list using the method we just implemented
level_order_traversal(test_case_roots[i])
print("\n-------------------------------------------------------------------------------------------------------------------------------")
if __name__ == '__main__':
main()
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
from collections import deque
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
d = deque()
d.append(root)
res = []
while d:
level = []
for i in range(len(d)):
node = d.popleft()
level.append(node.val)
if node.left:
d.append(node.left)
if node.right:
d.append(node.right)
res.append(level)
return res
in-order: left subtree, current node, right subtree
(for Binary Search Tree it gives nodes in sorted manner)
pre-order: current node, left subtree, right subtree
post-order: left subtree, right subtree, current node
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if not p and not q:
return True
if not p or not q:
return False
if p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
class Node:
# Utility to create new node
def __init__(self , data):
self.data = data
self.left = None
self.right = None
def minDepth(root):
# Corner Case
if root is None:
return 0
# Create an empty queue for level order traversal
q = []
# Enqueue root and initialize depth as 1
q.append({'node': root , 'depth' : 1})
# Do level order traversal
while(len(q)>0):
# Remove the front queue item
queueItem = q.pop(0)
# Get details of the removed item
node = queueItem['node']
depth = queueItem['depth']
# If this is the first leaf node seen so far
# then return its depth as answer
if node.left is None and node.right is None:
return depth
# If left subtree is not None, add it to queue
if node.left is not None:
q.append({'node' : node.left , 'depth' : depth+1})
# if right subtree is not None, add it to queue
if node.right is not None:
q.append({'node': node.right , 'depth' : depth+1})
# Driver program to test above function
# Lets construct a binary tree shown in above diagram
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print (minDepth(root))
class Node:
def __init__(self , key):
self.data = key
self.left = None
self.right = None
def minDepth(root):
# Corner Case.Should never be hit unless the code is called on root = NULL
if root is None:
return 0
# Base Case : Leaf node.This accounts for height = 1
if root.left is None and root.right is None:
return 1
# If left subtree is Null, recur for right subtree
if root.left is None:
return minDepth(root.right)+1
# If right subtree is Null , recur for left subtree
if root.right is None:
return minDepth(root.left) +1
return min(minDepth(root.left), minDepth(root.right))+1
# Driver Program
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4
def maxDepth(root):
if not root return 0
return max(maxDepth(root.right), maxDepth(root.left)) + 1
https://www.youtube.com/watch?v=X7_5fYEVIIU&list=PLQZEzAa9dfpkv0kZkjomTj553gQyafNiB&index=16
https://www.youtube.com/watch?v=4kRn1xlDJlY&list=PLQZEzAa9dfpkv0kZkjomTj553gQyafNiB&index=11
def helper(root):
if not root: return None
helper(root.left)
helper(root.right)
# current node:
tmp = root.left
root.left = root.right
root.right = tmp
def invert(root):
helper(root)
return root
https://github.com/hotsno/blind-75/blob/main/solutions
class Solution:
res = float('-inf')
----------------------------
def maxPathSum(self, root: Optional[TreeNode]) -> int:
self.helper(root)
return self.res
---------------------
def helper(self, root):
if not root:
return 0
left, right = self.helper(root.left), self.helper(root.right)
path_max = max(root.val, root.val + left, root.val + right)
self.res = max(self.res, path_max, root.val + left + right)
return path_max
def isValid(self, s: str) -> bool:
stack = []
d = {")":"(", "}":"{", "]":"["}
for c in s:
if c in "([{":
stack.append(c)
if c in ")]}":
if len(stack) == 0:
return False
if d[c] != stack.pop():
return False
return len(stack) == 0
https://www.youtube.com/watch?v=PDO3vvly7eU
def min_removes(s):
incidesToRemove = set()
stack=list()
for i, c in enumerate(s):
if c == '(':
stack.append(c)
elif c == ')':
if stack: incidesToRemove.add(i)
else: stack.pop()
while stack:
incidesToRemove.add(stack.pop())
result = list()
for i in range(len(s)-1):
if i not in ncidesToRemove:
result.append(s[i])
return result
3sum a+b+c
all permutations of string without recursion
def find_buy_sell_stock_prices(array):
if array == None or len(array) < 2:
return None
current_buy = array[0]
global_sell = array[1]
global_profit = global_sell - current_buy
current_profit = float('-inf')
for i in range(1, len(array)):
current_profit = array[i] - current_buy
if current_profit > global_profit:
global_profit = current_profit
global_sell = array[i]
if current_buy > array[i]:
current_buy = array[i];
result = global_sell - global_profit, global_sell
return result
array = [1, 2, 3, 4, 3, 2, 1, 2, 5]
result = find_buy_sell_stock_prices(array)
print("Buy Price: " + str(result[0]) + ", Sell Price: " + str(result[1]))
array = [8, 6, 5, 4, 3, 2, 1]
result = find_buy_sell_stock_prices(array)
print("Buy Price: " + str(result[0]) + ", Sell Price: " + str(result[1]))
Yet another solution
def maxProfit(self, prices):
low = prices[0]
res = 0
for price in prices:
if price < low:
low = price
res = max(res, price - low)
return res
from collections import Counter
def topKFrequent(self, nums, k):
count = Counter(nums) # builds the dict: item: frequency
return [c[0] for c in count.most_common(k)]
from collections import Counter
def topKFrequent(self, nums, k):
count = Counter(nums)
heap = []
ans = []
for i in count:
heappush(heap, (-count[i], i))
while k:
ans.append(heappop(heap)[1])
k -= 1
return ans
https://github.com/david-legend/python-algorithms/
https://github.com/hotsno/blind-75/tree/main/solutions
https://github.com/abhimathore/Grind-75
https://github.com/redayzarra/leetcode
I bought it: https://www.udemy.com/course/blind-75-leetcode-questions-ace-algorithms-coding-interview/learn/lecture/37964360#overview
https://www.youtube.com/watch?v=em4EP-IiKac
https://www.youtube.com/watch?v=KLlXCFG5TnA&list=PLot-Xpze53ldVwtstag2TL4HQhAnC8ATf blind-75 solutions
https://medium.com/codex/leetcode-167-two-sum-ii-input-array-is-sorted-python-solution-daa49d13215f
https://www.youtube.com/playlist?list=PLQZEzAa9dfpkv0kZkjomTj553gQyafNiB Solving All 150 NeetCode Problems
https://www.youtube.com/watch?v=GcW4mgmgSbw Sliding windows
https://www.youtube.com/watch?v=EM8IgIIiOdY
https://www.youtube.com/watch?v=DDRo29ptFwE
https://www.youtube.com/watch?v=xF554Tlzo-c I solved 541 Leetcode problems. But you need only 150.
https://www.youtube.com/watch?v=kp3fCihUXEg
https://www.youtube.com/watch?v=SVvr3ZjtjI8&list=PLot-Xpze53leF0FeHz2X0aG3zd0mr1AW_
https://habr.com/ru/articles/764718/ leetcode
def rle_encode(data: str) -> str:
encoded = []
i = 0
while i <= len(data)-1:
count = 1
ch = data[i]
j = i
while j < len(data) - 1:
if data[j] == data[j+1]:
count = count+1
j = j + 1
else:
break
encoded.append(str(count) + ch)
i = j + 1
return "".join(encoded)
from itertools import groupby
def rle_encode(data: str) -> str:
return "".join(str(len(list(group_items))) + key
for key, group_items in groupby(data))