Blog

What is RCU? Read-Copy-Update(RCU) is way of implementing wait-free synchronization between multiple processes/threads (alternative to lock mechanism). It works well in multiple reader and writer scenarios (especially ready heavy scenario). The key idea in RCU is doing a write/update operation in 2 steps namely ‘removal’ and ‘reclaim’.In step 1 (removal step), we have to remove references to […]

Given problem: A list of n strings each of length n is sorted into lexicographic order using the merge sort algorithm. Solution: Comparing two strings require O(n) comparisons, hence each merge will take O(n2) time. So, the recurrence equation will be: T(n) = 2 T(n/2) + O(n2) The n in the equation represents no.of elements […]

Let us start with the heapsort algorithm: The build_maxheap() funnction has a standard implementation of O(n). The important part of the sorting is the for loop, which executes for n times. Inside that we have a swap method call and heapify method call. The heapify method is a standard walk through of complete binary tree. […]

Problem statment Given two queues with their standard operations (enqueue, dequeue, isempty, size), implement a stack with its standard operations (pop, push, isempty, size). Solution There can be two ways you can solve the above problem. Option A: The stack – efficient when pushing an item Option B: The stack – efficient when popping an item In this post lets us discuss the an implementation […]

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It works best on a nearly sorted list. It has the following characteristics Stable; i.e., does not change the relative order of elements with equal keys In-place; i.e., only requires a constant amount O(1) of […]

What is multiple-column index? MySQL or many RDBMS supports multiple-column indexes. i.e. The index key will be more than 1 column in the table. For example, consider a table consolidated CREATE TABLE `consolidated` ( `consolidated_id` int(11) NOT NULL AUTO_INCREMENT, `pub_id` int(11) DEFAULT NULL, `cp_id` int(11) DEFAULT NULL, `ro_id` int(11) DEFAULT NULL, `country_id` int(11) DEFAULT NULL, […]

Coin Exchange Problem: Coin exchange problem is nothing but finding the minimum number of coins (of certain denominations) that add up to a given amount of money. It is a knapsack type problem. The interesting fact is that it has 2 variations: 1. Greedy Algorithm: For some type of coin system (canonical coin systems — […]

Everyone of us are familiar with RAM (Random Access Memory), this post is an attempt to explore the different types of RAM and how they store the data. We typically have 2 types of RAM SRAM (Static RAM) DRAM (Dynamic RAM) SDRAM (Synchronous DRAM) — is simply DRAM, which is synchronized with System Bus (newer […]

OOPS — Abstraction One of the core concept in object oriented paradigm is ‘Abstraction’. As most of us know Abstraction is nothing but hiding complete technical details (how its implemented or working) from the user (client code using the system/object/module) and exposing only necessary details for interacting with system/object/module. Static Function & Variables I guess […]

Let us try to create a toy system call to do add operation, which takes 2 arguments and return their added value. Following are the steps in adding a new system call to Linux Kernel: Step 1: Unzip and untar the latest Linux kernel source (https://www.kernel.org currently 3.14 is the stable version) into /usr/src/ directory. Step […]