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

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

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
development

Union-Find Problem

The problem is to find if a given edge (a, b) is connected in a graph with vertices {a, b, c, …}. Naive Solution – O(n^2) Maintain a parent array of size (len of vertex array) Update an edge (a, b) with the index a & b in the vertex array ParentArray[a] = b ParentArray[b] […]

Read more
development

Check Two Strings are Anagrams?

class Solution(object): def isAnagram(self, s, t): “”” :type s: str :type t: str :rtype: bool “”” # Keep a frequency array frequency = {} for c in s: if c not in frequency: frequency[c] = 1 else: frequency[c] += 1 # Go over the other string for d in t: if d in frequency: frequency[d] […]

Read more