development

Time Complexity of a Memoized Algorithm

The memoization eliminated duplicate calls to a function. A memoized implementation of Fibonacci code is as follows: package complexity import “fmt” var mem map[int]int func fibo(count int) int { if count == 0 || count == 1 { return count } if mem[count] != -1 { return mem[count] } s := fibo(count-1) + fibo(count-2) mem[count] […]

Read more
development

K-Messed Array Sort: Python Solution

K-Messed Array Sort Given an array of integers arr where each element is at most k places away from its sorted position Solution from Queue import PriorityQueue def sort_k_messed_array(arr, k): kheap = PriorityQueue() result = [] for num in arr: kheap.put(num, ‘num’) if kheap.qsize() == (k + 1): item = kheap.get() result.append(item) while not kheap.empty(): […]

Read more
development

Find Number with More Than 25 Percent Frequency In Sorted Array

Leetcode Element Appearing More Than 25% In Sorted Array class Solution(object): def findSpecialInteger(self, arr): “”” :type arr: List[int] :rtype: int “”” if len(arr) > 8: return self.getMostFrequentNumberOptimized(arr) return self.getMostFrequentNumber(arr) def getMostFrequentNumber(self, arr): counter = {} for n in arr: if n in counter: counter[n] += 1 else: counter[n] = 1 targetPercent = (len(arr) * 25)//100 […]

Read more
development

K Weakest Rows in a Matrix

Problem The K Weakest Rows in a Matrix Solution Uses Binary search to count 1s Uses heap to keep k weakest rows It naturally satisfies the condition for weak rows with the same number of soldiers. The smaller index row is processed first and hence any next row would not get pushed to the heap. […]

Read more
development

Number of 1s in a sorted array

Problem Count number of 1s in a sorted array. e.g. [1,1,1,1,0,0,0,0,0,0] Code def countOneBS(row, start, end): if row[start] == 0: return 0 if row[end] == 1: return end – start + 1 # The mid is dependent on the index of start mid = start + (end – start) // 2 # print(“mid=”, mid, “start=”, […]

Read more
development

Quicksort in C++

// cat quicksort.cc #include <bits/stdc++.h> #include <algorithm> // std::swap using namespace std; int partition(int arr[], int low, int high); void qsort(int arr[], int start, int end) { int p; if (start < end) { p = partition(arr, start, end); qsort(arr, start, p – 1); qsort(arr, p + 1, end); } } int partition(int arr[], int […]

Read more
development

Find a Fibonacci Number with Matrix Exponentiation

Core Concepts We can represent any number with a power of (2 or 3 or anything). Evidence? The binary system 🙂 So we can represent any number with log n bits and using 2 as the exponent. f(n) = f(n-1) + f(n-2) => f(n) = 1*f(n-1) + 1*f(n-2) [f(n)] = |1 1| * |f(n-1)| |f(n-2)| […]

Read more
development

Another Solution: Longest Palindrome Substring

class Solution(object): def __init__(self): self.lookup = {“test”} def isPalindrome(self, s, i, k): j = i + k – 1 if s[i] == s[j]: key = self.createKey(i + 1, j – 1) if key in self.lookup: #self.lookup.remove(key) return True return False def createKey(self, i, j): #return “{}:{}”.format(i,j) #return (i, j) #key = bin(i) + bin(j) #return […]

Read more
development

Longest Palindrome Substring in a String

DP based solution class Solution(object): def __init__(self): self.lookup = {} def isPalindrome(self, s, dp, i, k): j = i + k – 1 if s[i] == s[j] and dp[i + 1][j – 1]: return True return False def longestPalindrome(self, s): “”” :type s: str :rtype: str “”” size = len(s) if size < 2: return […]

Read more