Author Archives: vishpat

Building an interpreter in RUST

Just finished going through “Writing An Interpreter In Go“. However instead of implementing the interpreter in Go, I decided to implement it in RUST. This was one of the most satisfying software projects that I worked on in a while. I must say that I just love RUST as a systems programming language.

The important RUST features that I used to get this project done are

  • Enums as data types
  • Box
  • Rc
  • RefCell
  • Lots of recursion

RUST enables you to write the code in a declarative manner which makes the code really compact and easy to understand

OpenDNS

Cisco has a great product called OpenDNS that enables you to control the websites that can be reached from home your network. If you have Google wifi at home, you can use OpenDNS to block gaming websites like Roblox.

Wireless issues on Lenovo Flex running FC 33

I purchased a Lenovo Flex couple of months ago and installed Fedora 33 on it. Was really frustrated with the wifi on the laptop. The realtek wireless drivers merged in the official kernel suck big time.

Trying out a solution, hope will work (and it did not)

sudo nmcli con reload wlp2s0

The above command to restart the wireless seems to have helped. Also following are the wireless kernel modules that are currently loaded

lsmod | grep rt
rtl88x2ce            3018752  0
rtw_8822ce             16384  0
rtw_8822c             471040  1 rtw_8822ce
rtw_pci                28672  1 rtw_8822ce
rtw_core              212992  2 rtw_8822c,rtw_pci
mac80211             1081344  2 rtw_core,rtw_pci

Shifted binary search

 
public static int shiftedBinarySearch(int[] array, int target) {
    return shiftedSearch(array, 0, array.length - 1, target);
}

public static int binarySearch(int[] array, int startIdx, int endIdx, int target) {
        int midIdx = (startIdx + endIdx) / 2;

        if (startIdx > endIdx || endIdx >= array.length) {
            return -1;
        }

        if (startIdx == endIdx) {
            if (array[midIdx] == target) {
                return midIdx;
            } else {
                return -1;
            }
        }

        int result = -1;
        if (target <= array[midIdx]) {
            result = binarySearch(array, startIdx, midIdx, target);
        } else {
            result = binarySearch(array, midIdx + 1, endIdx, target);
        }

        return result;
    }

    public static int shiftedSearch(int[] array, int startIdx, int endIdx, int target) {

        if (startIdx > endIdx || endIdx >= array.length) {
            return -1;
        }

        if (array[startIdx] == target) {
            return startIdx;
        }

        if (array[endIdx] == target) {
            return endIdx;
        }

        int result = -1;
        int midIdx = (startIdx + endIdx) / 2;


        if (array[startIdx] > array[midIdx]) {
            result = shiftedSearch(array, startIdx, midIdx, target);
            if (result != -1) {
                return result;
            }
        }

        if (array[midIdx + 1] < array[endIdx]) {
            result = binarySearch(array, midIdx + 1, endIdx, target);
            if (result != -1) {
                return result;
            }
        }


        if (array[startIdx] < array[midIdx]) {
            result = binarySearch(array, startIdx, midIdx, target);
            if (result != -1) {
                return result;
            }
        }


        if (array[endIdx] < array[midIdx + 1]) {
            result = shiftedSearch(array, midIdx + 1, endIdx, target);
            if (result != -1) {
                return result;
            }
        }
        return result;
    }

Lowest Common Manager

#!/bin/python3

class OrgChart:

    def __init__(self, name, manager):
        self.name = name
        self.manager = manager
        self.directReports = []

    def __repr__(self):
        return f'{self.name}'


def getLowestCommonManager(topManager, reportOne, reportTwo):
    report_one_manager = reportOne.manager
    report_one_chain = list()
    while report_one_manager:
        report_one_chain.append(report_one_manager)
        report_one_manager = report_one_manager.manager

    report_two_manager = reportTwo.manager
    report_two_chain = list()
    while report_two_manager:
        report_two_chain.append(report_two_manager)
        report_two_manager = report_two_manager.manager

    report_one_chain.reverse()
    report_two_chain.reverse()
    common_manager = None
    for a, b in zip(report_one_chain, report_two_chain):
        if a == b:
            common_manager = a
        else:
            break

    return common_manager


if __name__ == '__main__':
    org = [
        {"directReports": ["B", "C"], "id": "A", "name": "A"},
        {"directReports": ["D", "E"], "id": "B", "name": "B"},
        {"directReports": ["F", "G"], "id": "C", "name": "C"},
        {"directReports": ["H", "I"], "id": "D", "name": "D"},
        {"directReports": [], "id": "E", "name": "E"},
        {"directReports": [], "id": "F", "name": "F"},
        {"directReports": [], "id": "G", "name": "G"},
        {"directReports": [], "id": "H", "name": "H"},
        {"directReports": [], "id": "I", "name": "I"}
    ]

    top_manager = None
    members = {}
    for member in org:
        name = member['name']
        if name not in members:
            member_obj = OrgChart(name, None)
            top_manager = member_obj
            members[name] = member_obj

        member_obj = members[name]

        for direct_report in member['directReports']:

            if not direct_report in members:
                direct_report_obj = OrgChart(direct_report, member_obj)
                direct_report_obj.name = direct_report
                members[direct_report] = direct_report_obj
            else:
                direct_report_obj = members[direct_report]

            member_obj.directReports.append(direct_report_obj)

    print(getLowestCommonManager(top_manager, members['F'], members['H']))

Longest Peak

package com.vishpat.practice.ds.array;

enum States {
    UNKNOWN,
    ASCENDING,
    DESCENDING
}

public class LongestPeak {
    public static int longestPeak(int[] array) {
        States currentState = States.UNKNOWN;
        States prevState = States.UNKNOWN;
        int longestSize = 0;
        int ascendingStartIdx = -1;
        int descendingEndIdx = -1;

        if (array.length < 3) {
            return 0;
        }

        for (int i = 0; i < array.length - 1; i++) {
            prevState = currentState;

            if (array[i + 1] > array[i]) {
                switch (prevState) {
                    case UNKNOWN:
                        currentState = States.ASCENDING;
                        ascendingStartIdx = i;
                        break;
                    case ASCENDING:
                        currentState = States.ASCENDING;
                        break;
                    case DESCENDING:
                        currentState = States.ASCENDING;
                        ascendingStartIdx = i;
                        break;
                }
            }

            if (array[i + 1] < array[i]) {
                switch (prevState) {
                    case UNKNOWN:
                        currentState = States.DESCENDING;
                        break;
                    case ASCENDING:
                        currentState = States.DESCENDING;
                        descendingEndIdx = i + 1;
                        break;
                    case DESCENDING:
                        currentState = States.DESCENDING;
                        descendingEndIdx = i + 1;
                        break;
                }
            }

            if (ascendingStartIdx >= 0 && descendingEndIdx >= 0 &&
                ascendingStartIdx < descendingEndIdx) {
                int size = descendingEndIdx - ascendingStartIdx + 1;
                if (size > longestSize && size > 2) {
                    longestSize = size;
                }
            }
        }
        return longestSize;
    }
}

Max 2 integers from an array

def sol2(data):
    max_idx1 = 0
    max_idx2 = 1
    max_sum = data[0] + data[1]

    for next_idx in range(2, len(data)):
        
        if data[max_idx1] + data[next_idx] > max_sum and max_idx1 != next_idx:
            max_sum = data[max_idx1] + data[next_idx]
            max_idx2 = next_idx

        if data[max_idx2] + data[next_idx] > max_sum and max_idx2 != next_idx:
            max_sum = data[max_idx2] + data[next_idx]
            max_idx1 = next_idx

    print(max_idx1, max_idx2)


if __name__ == "__main__":
    data = [1, 5, 3, 2, 4]
    sol2(data)

Simple in-memory file system

class Dir:

    def __init__(self, parent, name):
        self.parent = parent
        self.name = name
        self.children = dict()

    def mkdir_path(self, path):
        sub_dirs = path.split('/')
        current_dir = self
        for child_dir_name in sub_dirs:
            current_dir = current_dir.mkdir(child_dir_name)

    def mkdir(self, name):
        dir = Dir(self, name)
        self.children[name] = dir
        return dir

    def get_child_dir(self, name):
        return self.children[name]

    def get_child_dir_path(self, path):
        sub_dirs = path.split('/')
        current_dir = self
        for sub_dir in sub_dirs:
            current_dir = current_dir.children[sub_dir]
        return current_dir

    def write_file(self, name, contents):
        self.children[name] = contents

    def write_file_path(self, path, contents):
        sub_dirs = path.split('/')
        file_name = sub_dirs[-1]
        current_dir = self
        for sub_dir in sub_dirs[:-1]:
            current_dir = current_dir.children[sub_dir]
        current_dir.write_file(file_name, contents)

    def read_file(self, name):
        return self.children[name]

    def read_file_path(self, path):
        sub_dirs = path.split('/')
        file_name = sub_dirs[-1]
        current_dir = self
        for sub_dir in sub_dirs[:-1]:
            current_dir = current_dir.children[sub_dir]
        return current_dir.read_file(file_name)

    def __repr__(self):
        return f'{self.name} {self.children}'


if __name__ == "__main__":
    fs = Dir(None, '/')
    fs.mkdir('tmp').mkdir('1')
    fs.get_child_dir('tmp').get_child_dir('1').write_file('test', 'data')
    contents = fs.get_child_dir('tmp').get_child_dir('1').read_file('test')
    assert contents == 'data', "contents of the file don't match"

    fs.mkdir_path('tmp/1/2/3/4')
    fs.write_file_path('tmp/1/2/3/4/4.dat', '4')
    contents = fs.read_file_path('tmp/1/2/3/4/4.dat')
    assert contents == '4', 'Correct content not found'

Check if concatenation of any permutation of given list of arrays generates the given array

Solution for geeksforgeeks problem

def solve(arr, sub_arrs):

    sub_arr_membership = {}
    curr_indx = [-1 for i in range(0, len(sub_arrs))]
    for idx, sub_arr in enumerate(sub_arrs):
        for sub_arr_idx, element in enumerate(sub_arr):
            sub_arr_membership[element] = (idx, sub_arr_idx)

    for element in arr:
        idx, sub_arr_idx = sub_arr_membership[element]
        if curr_indx[idx] > sub_arr_idx:
            print(f'False')
            return
        else:
            curr_indx[idx] = sub_arr_idx

    print(f'True')

Custom kubernetes ingress authentication using Hashicorp Vault

This article explains how to implement an ngnix ingress authentication (basic http auth) mechanism for securing your kubernetes (k8s) application endpoints using the credentials stored in hashicorp vault. This can be achieved easily by writing a simple http auth (python-flask) app that talks with the vault. The workflow for custom authentication is explained well in this article.

The basic idea to is modify the opensource httpbin app by adding a new endpoint such as vault-auth. The code this endpoint is going to basic-auth except the http auth credentials will be validate against hashicorp vault instead of the passed parameters. The modified code can then be deployed as a container and as an auth service in your kubernetes cluster.

All the applications whose ingress endpoints need to be secured have to add the following line to their ingress deployment yaml

nginx.ingress.kubernetes.io/auth-url: http://auth.default.svc.cluster.local/vault-auth/x/y

Where auth.default.svc.cluster.local is the service that is running the modified httpbin app