Scribbling

To design a hashmap, we need 1) hashing function -- will use hash() method 2) an array for the hash table 3) Linkedlist for hash collision class Node: def __init__(self, key, val, nxt=None): self.key = key self.val = val self.nxt = nxt class LinkedList: def __init__(self): self.head = Node(0, 0) def append(self, key, val) -> None: prv, cur = self.head, self.head.nxt while cur is not None: if cur..

https://leetcode.com/problems/binary-search-tree-iterator/description/?envType=study-plan-v2&envId=top-interview-150 LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Python Code with yield # Definition for a binary tree node..

276. Paint Fence https://leetcode.com/problems/paint-fence/ Paint Fence - LeetCode Can you solve this real interview question? Paint Fence - Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com let dp[i] be # of all ways painting i-th fence: then, dp[i] = num_same(i) + num_diff(i) holds. (where ..

How does one can find the number of pairs in an array that satisfies the below condition? : lower

A dynamic programming approach: Let dp[i, j] be the total number of cases of target[i] corresponding to jth position dp[i, j] = dp[i][j-1] + dp[i-1][j-1] * counter[j, target[i]] 1) Bottom-up import string from functools import lru_cache class Solution: def numWays(self, words: List[str], target: str) -> int: N = len(words[0]) freqs = [{c: 0 for c in string.ascii_lowercase} for _ in range(N)] for..

Greedy solution with heap & deque - append character with 'max frequency' currently - put the appended character to a deque for cool-down from collections import Counter, deque import heapq class Solution: def rearrangeString(self, s: str, k: int) -> str: if k = k: freq, char = q.popleft() if freq >= 1: heapq.heappush(h, (-freq, char)) return ''.join(ret) if len(ret) == len(s) else ""

Fenwick Tree (or Binary Indexed Tree) is very efficient in dealing with range queries, especially when elements get updated occasionally. For how it works, refer to the below video. He elaborates on the principle of the tree in a very clean way. https://www.youtube.com/watch?v=CWDQJGaN1gY&t=160s&ab_channel=TusharRoy-CodingMadeSimple Below is the python implementation of it. class Fenwick: """ Py..

First thing first: To implement an expression tree with "Postfix", we can easily do so with a stack. For the evaluation part: "ABC" might be a bit unfamiliar, but all you need to know about it here is that you cannot initiate an instance with the ABC class (in this case Node class). In addition, an abstract method must be implemented in the child class. import abc from abc import ABC, abstractme..

Video I recommend: https://www.youtube.com/watch?v=SToUyjAsaFk In this post, I will cover "Recursive Descent Parsing". Details about it are well elaborated in the above video. This post is to summarize core concepts and implement the algorithm with an actual code. Goal: Implement a parser that parse an arithmetic experssion. - ( 3 + 5) * -2 Elements: Numbers Infix Operators (+, -, *, /) Prefix O..

Rabin-Karp Algorithm is an efficient algorithm to search a string pattern in a given sentence. The core of the idea is to use hash function to compare strings. Time complexity is O(n), where n is length of the string. However, this is true only when there is no hash collision. Time complexity is O(n * m) if hash function is poorly selected (producing many hash collisions), where m is length of t..