MVC Explained

MVC is an architecture to separate an application in three cohesive, loosely coupled verticals.

  1. Model: The data of your application and methods to access it.
  2. View: The final output/expected result.
  3. Controller: The interface that handles requests from the model

I’m trying to map it to a Linux Filesystem (e.g. ext2).

Model: The file system block manager and allocator for the storage device.
View: read()/write() methods.
Controller: Maps a file descriptor to file system blocks.

Guidelines for a System Architect

The system architect is key personnel to enable the success of an organization. From the book, Building Microservices, I learned the following worth highlighting nuggets:

An architect defines the technical vision of an organization. This vision is compatible with the strategic goals (e.g. expanding markets, market segments, etc) of the company. Taking an example of a town planner, an architect defines the zone in a town but not what goes in a zone. However, the architect defines how interaction happens among zones.

The technical vision is implemented by developers and the architect needs to ensure that vision is standard and adaptable too. It allows ease of development and a long-tern lower cost for the company.

The architect also needs to ensure that vision is translated sincerely in the product aka governance. The technical vision constantly evolves so an architect needs to stay top of the latest technical developments and have an open approach to refine and redefine the current vision.

What does an Architect Do?

Find Number with More Than 25 Percent Frequency In Sorted Array

Leetcode

  1. 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
        
        for n in counter:
            if counter[n] > targetPercent:
                return n
            
    def getMostFrequentNumberOptimized(self, arr):
        numsCount = len(arr)
        p1 = (numsCount // 4) - 1
        p2 = (numsCount // 2) - 1
        p3 = ((numsCount * 3) // 4) - 1
        
        print("len=", numsCount, "p1=", p1, "p2=", p2, "p3=", p3)
        print(arr[0], arr[p1], arr[p2], arr[p3], arr[-1])
        
        if arr[0] == arr[p1]:
            return arr[0]
        
        if arr[p1] == arr[p2]:
            return arr[p1]
        
        if arr[p2] == arr[p3]:
            return arr[p2]
        
        if arr[p3] == arr[-1]:
            return arr[p3]

The above optimized approach has a flaw. The offsets are fixed and the 25% spread can be across two quartets.

num = [1,2,2,2,3,4,4,5,6,6,7,7]

We need to use a sliding window of quarters.

def getMostFrequentNumberOptimized(self, arr):
        n = len(arr)
        offset = n/4
        
        for i in range(n - offset):
            if arr[i] == arr[i + offset]:
                return arr[i]

Reference

K Weakest Rows in a Matrix

Problem

  1. 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.
from heapq import heappushpop, heappush, heappop

class Solution(object):
    def countOne(self, row):
        ans = 0
        for n in row:
            if n == 0:
                break
            ans += 1
        return ans
    
    def countOneBS(self, row, start, end):
        if row[start] == 0:
            return 0
        
        if row[end] == 1:
            return end - start + 1
        
        mid = start + (end - start) // 2
        
        # print("mid=", mid, "start=", start, "end=", end)
        return self.countOneBS(row, start, mid) + \
               self.countOneBS(row, mid + 1, end)
    
    
    def kWeakestRows(self, mat, k):
        """
        :type mat: List[List[int]]
        :type k: int
        :rtype: List[int]
        """
        # max heap
        heap = []
        weakestRows = []
        
        for index, row in enumerate(mat):
            c = self.countOneBS(row, 0, len(row) - 1)
            
            if len(heap) == k:
                heappushpop(heap, (-c, -index))
            else:
                heappush(heap,(-c, -index))
                
        while heap:
            weakestRows.append(-heappop(heap)[1])
            
        return weakestRows[::-1]

Reference

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=", start, "end=", end)
        return countOneBS(row, start, mid) + countOneBS(row, mid + 1, end)
    
l = [1,1,1,0,0,0]

print(countOneBS(l, 0, len(l) - 1))

Reference

Why Use Python Ordered Dictionary?

An ordered dictionary offers same time complexity as the standard dict.

The implementation is simple:

  • Keep two dictionaries and a doubly-linked list of keys.
  • The DLL maintains order.
  • One dict maps key => DLL node
  • Other dict maps key => value

Implementation details

https://github.com/python/cpython/blob/3.7/Lib/collections/init.py#L129

Example

Problem: Find the first non-repeating char in a string.

def firstUniqChar(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) == 0:
            return -1

        d = collections.OrderedDict()
        
        for index, c in enumerate(s):
            if c in d:
                d[c][0] += 1
            else:
                d[c] = [1, index]
        
        for k in d:
            if d[k][0] == 1:
                return d[k][1]
        
        return -1

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 low, int high)
{
    int pivot = arr[low];
    int i = low;
    int j = high + 1;

    do {
        do {
            i++;
        } while (arr[i] < pivot && i <= high);

        do {
            j--;
        } while(arr[j] > pivot);

        if (i < j)
            swap(arr[i], arr[j]);

    } while (i < j);
    swap(arr[low], arr[j]);
    return j;
}
int main()
{
    int arr[] = {11,2,100,1,2,31};

    size_t size = sizeof(arr)/sizeof(arr[0]);
    qsort(arr, 0, size - 1);

    for (int i = 0; i < size; i++)
        cout << arr[i] << endl;
}                                     

Reference

Distributed Systems Consensus: Raft Protocol

Raft

A consensus protocol in a distributed system

Raft Applications

  • Consul
  • etcd
  • InfluxDB

A naive explanation of Raft is as follows:

Fundamental Idea

  • Replicated logs
  • Leader
  • Follwers
  • Candidates

Leader

The leader serves writes and the client gets an ack after reliably storing the write with followers.
Each follower expects a heartbeat from the leader. If no heartbeat, a follower chooses to be a leader and ask for majority votes.

Log Replication

Each change to the system goes through the leader. There are three phases of a commit:

  1. The leader appends the change in its log. A log entry has a term number & an index.
  2. It then sends the change to followers.
  3. A follower applies the change(not commit) in its log and ack the leader.
  4. If the leader gets acknowledgment from the majority of the followers, leader commits the change and acknowledges the client.
  5. In the next heartbeat, the leader notifies followers.
  6. Followers apply the change.

Leader Election

  1. Each leader gets a term. The term remains a unique, non-decreasing number in the cluster. The term number increases with each successful leader election.
  2. A node can vote for only one candidate node in a term.
  3. A node votes for a candidate whose log is at least the same index.
  4. The candidate with maximum vote wins.

Network Partition

The leader with a higher term always wins. If there was a leader in a partition, the leader steps down and sync its log with the winner leader.

References

%d bloggers like this: