# Tries as data structure

Tries is a data structure which is usually neglected by programmers while designing solutions. Tries are very useful in cases where strings are involved with a good amount of duplication of their prefixes. What are tries? Trie is a data structure which stores information, referred to as key, in such a manner that the common information is stored only once. Usually keys are strings. No node in trie stores the whole key, but the position of the node gives us information that which key it is part of. All the descendant node in trie have the same prefix, hence trie is also know as prefix trees.Word trie is taken from retrieval word.

Another property of trie is that every node of trie has multiple children. In case of string (assuming lower case), there will be 26 children of each node. Take an example: We have the following strings: “House”, “Home”, “Tree” I need to store this information, Trie for the above words would look like:

## Insertion in trie

Before insertion, we need to understand that how can we represent a node of a trie. Since intermediate nodes of a key do not store any information at them, we need to distinguish between the leaf node and the intermediate node. For that we can store a field called as the value inside each node, If the value is zero, it’s an intermediate node, if non-zero, it’s a leaf node.
In our case, we are assuming MAX_SIZE of 26.
Basic initialization

#define MAX_SIZE 26

#define GET_CHAR_INDEX(ch)\
((int) ch - (int)'a' )

#define LEAF_NODE  1
#define true 1
#define false 0

typedef struct trie_node_t {
int value;
struct trie_node_t * children[MAX_SIZE];
}Node;

typedef struct trie{
int count ;
Node *root;
}trie;

void initialize(trie *t){
t->root = (Node *)malloc(sizeof(Node));
t->count =0;
}

Now we can go and see insertion part.
Scan through the string character one by one. For each character, check if it has child nodes. The character acts as an index in children array. If the node at the char index has a child node, move to the child node and take the next character of the string. Repeat step 2 and 3 If the node at the char index doesn’t have a child node, create a child node and add it to trie. Move the character in the string and move down to a newly created child. Go to step 2.

void insert(trie *t, char key[]){

int len = strlen(key);
int i;

if(t->root == NULL){
printf("\n Trie is not initialized\n");
}

Node * current = t->root;
for(i=0; i<len; i++){

/* Get the index of char in children array */
int index  =  GET_CHAR_INDEX(key[i]);

/* If the children array does not contain the pointer
at index pointed by char, allocate new node */

if(current->children[index] == NULL){
current->children[index] = (Node *)malloc(sizeof(Node));
}
/* Else traverse down the trie. */
current = current->children[GET_CHAR_INDEX(key[i])];
}

/* To mark it as leaf */
current->value = LEAF_NODE;
}

Search in trie
The best part of the trie is its search. It is done in O(M) where M is the length of the input string.
Start from the root. and take the first character of the string. If the array index pointed by the character is NULL, return false. Else move to the child node and next character. Repeat step 2 and 3 till the end to the input string. If we reach till the end of the string and the current node is a leaf node (identified using value), then return true.

int search(trie *t, char key[]){
int len = strlen(key);
int i;
if(t->root == NULL){
printf("\n Trie is not initialized\n");
}

Node * current = t->root;
for(i=0; i<len; i++){
int index  =  GET_CHAR_INDEX(key[i]);

/* If characters are left in key and we have
reached at NULL, there is no key present */
if(current->children[index] == NULL) return false;

/* Else traverse down the trie */
current = current->children[index];
}

/* If we have reached the lead=f node, key is present */
if(current && current->value == LEAF_NODE )
return true;

return false;
}

The only drawback with tries is that it takes a lot more space (K *  MAX_SIZE * N) as compared to the binary search tree. It is evident from the fact that every node in trie has to have a place for all the possible characters. In time complexity terms, insertion and search both are O(M) where M is length of string being entered. In this post we saw insertion and search operation in tries. We will use these operations in the future post and solve some real problems.

# Word break problem

This problem is commonly asked in the Google and Amazon interview. We all know that if you typed string in Google search box does not make sense, Google breaks that into meaningful words and asks us back if we meant those words instead of a single word. This post discusses how can we find if the given string can be broken into meaningful dictionary words. For example, if I typed algorithmsandme and given dictionary is [“algorithms”, “and”, “me”], this string is breakable in meaningful words. but if the string is algorithmsorme this is not breakable into meaningful words. You can find this problem for practice at leetcode.

## Word break problem : thoughts

We start with the first character of the string, check if the character itself is a word in the dictionary? If yes, then our problem reduces to the smaller problem, that is to check if substring from index 1 to s.length is breakable or not.
If not, then we check two characters and then three characters and so on till we can check the whole string. As with every character inclusion, the problem reduces in size but remains the same, so ideal case for recursive implementation.

package AlgorithmsAndMe;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class WordBreak {

public boolean wordBreak(String s, List<String> wordDict) {
return wordBreakUtil(s, wordDict, 0, table);
}

private boolean wordBreakUtil(String s,
List<String> wordDict,
int index) {

if (index == s.length()) return true;

boolean isBreakable = false;
for(int i=index; i<s.length(); i++) {
isBreakable = isBreakable
|| wordDict.contains(s.substring(index, i+1))
&& wordBreakUtil(s, wordDict, i + 1);
}

return isBreakable;
}
}

If you notice we are solving the same problems again and again in recursive function wordBreakUtil, how can we save that repeated calculations? Best way to save the already solve problems in a cache, that way we can refer to the cache if the problem is already solved or not. If yes, do not solve it again and use the cached value. This approach is called a Top Down approach and uses memoization to avoid repeated subproblems.

package AlgorithmsAndMe;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class WordBreak {

public boolean wordBreak(String s, List<String> wordDict) {
int [] table =  new int[s.length()];
for(int i=0; i<s.length(); i++){
table[i] = -1;
}
return wordBreakUtilTopDown(s, wordDict, 0, table);
}

private boolean wordBreakUtilTopDown(String s,
List<String> wordDict,
int index,
int[] table) {

if (index == s.length()) return true;

if(table[index] < 0) {
boolean isBreakable = false;
for (int i = index; i < s.length(); i++) {
isBreakable = isBreakable
|| wordDict.contains(s.substring(index, i + 1))
&& wordBreakUtilTopDown(s, wordDict, i + 1);
}
table[index] = isBreakable ? 1 : 0;
}
return table[index] == 1 ? true : false;
}
}

If you run the first solution, it will exceed the time limit on leetcode, however, the second implementation should be accepted with 4ms as the time to run. Now you can appreciate the efficiency by memoization.

### Word break problem using dynamic programming

In the last two implementations, two things are evident: first, the optimal solution of a subproblem leads to the optimal solution of the original problem. Second, there are overlapping subproblems. These are two must have conditions for applying dynamic programming. We already saw the memoization and top-down approach of DP to avoid repeated solving of subproblems. How can we do it bottom up?

What if store an information if the string till index i is breakable? What will be the base case? The string before index 0 is alway breakable as empty string. So table[0] can be always true. To check if string till index i is breakable or not, we check from index 0 to index i-1 if there is any index j till which string is breakable. If yes, then we just check if substring from index j to i, that will make table[i] as true.

package AlgorithmsAndMe;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class WordBreak {

public boolean wordBreak(String s, List<String> wordDict) {
return wordBreakBottomUp(s, wordDict, 0, table);
}

private boolean wordBreakUtilBottomUp(String s, List<String> wordDict){

if(s == null || s.length() == 0) return false;

boolean[] table  = new boolean[s.length()+1];

table[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = i - 1; j >= 0; j--) {
if (table[j] && wordDict.contains(s.substring(j, i))) {
table[i] = true;
}
}
}
}
return table[s.length()];
}
}

The time complexity of the above implementation of the word break problem is O(n2)

If you want to store all the strings which can be generated by breaking a particular word, below is the code.

package AlgorithmsAndMe;

import java.util.*;

public class WordBreak2 {

public List<String> wordBreak(String s, List<String> wordDict) {
Map<String, List<String>> map = new HashMap<>();
return wordBreakUtil2(s, wordDict, map);
}

private List<String> wordBreakUtil2(String s,
List<String> wordDict,
Map<String, List<String>> map) {

if(map.containsKey(s)){
return map.get(s);
}

List<String> result = new ArrayList<String>();
if (wordDict.contains(s)){
}

for(int i=1; i<=s.length(); i++) {
String prefix = s.substring(0, i);
if(wordDict.contains(prefix)){
List<String> returnStringsList = wordBreakUtil2(s.substring(i), wordDict, map);

for(String returnString :returnStringsList ){
result.add(prefix + " " + returnString);
}
}
}
map.put(s,result);

return result;
}
}

Please share if there is something is wrong or missing. If you are preparing for an interview and need any help with preparation, please reach out to us or book a free session.

## Anatomy of a Process

A process is a program in execution, with it associated are process context and executable instruction.
A process has its own data, code, stack, register and memory space. Every process has its own virtual memory address range, I/O resources, opened files etc.

We can check what all processes running in system (Linux) using ps command.

## Process states

It is not that process is always running once we execute the program. There is scheduling involved which depends on the priority of the process. Following are the states a process can be in :

1. RUNNING : Simple this is the state when process has got processor and it is being executed.

2. WAITING or UNINTERRUPTIBLE SLEEP  : When scheduler has moved process out of the processor while process is waiting for some input or action from I/O or any other resources.
3. INTERRUPTIBLE SLEEP : Process has gone to sleep while waiting on an event which will send signal or interrupt when that occurs.
4. TERMINATED : When process has completed its execution, process can terminated normally or abruptly due to some signal like SIGKILL, SIGSERV etc.
5. ZOMBIE : When process has completed execution but its return status is yet not collected by the parent process.

Following diagram shows transition between various states and events which trigger those transitions.

<!–[if gte vml 1]>

 R
 Z
 T
 S
 I/O operation
 Scheduled
 If exit status is not read
 Completes

<![endif]–>

 Process states and events

## Properties of a process

When a process is moved out of process and new process is bought in for the execution, process context switch happens. Process’s current state is saved before it moves out of the CPU and it is resumed from the point it left once it gets the hold of processor again. Process context switch is an expensive operation and algorithms are developed to minimize this. We will discuss them later.

Understand that in Linux every process except the INIT process has a parent, hence we can take all process in systems as nodes of a tree. INIT is root of that tree. Processes which are children of same parent are called as siblings. Also every process has associated process ID. Since it is 16 bit integer, maximum number of processes we can have in system at a time is around 32K.

At program level we can easily get the process ID and its parent ID using getpid() and getppid() APIs.

What else is associated with a process? Process has UID which is user ID which own this process; GID group ID which process is running on behalf of.

A process in memory looks like this:

 Process snapshot

## Creation of a process

How a process is created? Most widely used method to create a process is to use ‘fork’ and ‘exec’ system calls. As mentioned earlier, every process has parent, parent uses fork system call to create exactly same copy of itself. Once new process is scheduled, it can use exec system call to execute any program it wants to.

It is interesting to understand fork system call. It is a call where one process goes in and two come out. They both start there execution from the statement just after fork call (Remember new process is exact copy, hence its PC will be same). How to distinguish between parent and child process? fork comes to rescue there. Call to ‘fork’ return child process’s PID to parent process while zero to child process. By having check on return value of ‘fork’ system call we can figure out which process is parent and which is child.

Now, fork can be a very expensive call as OS has to duplicate whole lot of information, especially the virtually memory and pages currently used by the parent process. There is one concept which is called ‘Copy on Write’, so fork system call will not copy any of the pages till the time one of the process tries to modify the page. This arrangement makes fork system call fast.

Other system call is exec(). It is used to start a new program, it will replace contents of process with of program binary. There are many versions of the same system call used for varying purposes.

1. The calls with v in the name take an array parameter to specify the argv[] array of the new program.
2. The calls with l in the name take the arguments of the new program as a variable-length argument list to the function itself.
3. The calls with e in the name take an extra argument to provide the environment of the new program; otherwise, the program inherits the current process’s environment.
4. The calls with p in the name search the PATH environment variable to find the program if it doesn’t have a directory in it (i.e. it doesn’t contain a / character). Otherwise, the program name is always treated as a path to the executable

When a process creates a child process, it may or may not wait for return status of the child process.
To wait for the return status, parent process uses wait() system call. It blocks the parent process till the time one of its child returns status. Usually return status of child process is used to check if the child process terminated normally or abnormally. Child process can inform their exit status using SIGCHILD signal.
There are variants of wait() like wait3() and wait4() which are non blocking call on parent process.

## Difference between zombie and orphan process

When a child process exits and if parent process is not waiting to receive exit status of it, the child process is termed as Zombie process. This process continues to exist in process table, its PID is not freed even though it has terminated.

If parent process exits before child process, the child process is called as orphan process. This process is put directly under the INIT process and its parent process ID becomes 1. There is slight difference between zombie and orphan that is zombie process’s parent may not have exited while orphan process’s parent has terminated.

In next post we would closely on linux code for process implementation.

## LRU cache implementation

This is commonly asked question in interview, especially Microsoft and Amazon interviews. Problem statement is very simple

Implement LRU cache or Least Recently Used cache

Before going further into solution, first let’s understand what is cache?  In computer architectural terms, a cache is small buffer of pages OS maintains in-order to avoid more expensive main memory accesses.

Usually cache accesses are faster than main memory access, improving overall performance. Whenever a process needs to access content from a specific memory location, it tries to search that page in the cache first. If it finds a page in the cache, it uses it and does not access memory. It’s called cache hit.

However, caches are very small in size as compared to main memory, there is a probability that page requested by the process is not present in the cache. In that case, the new page is moved into the cache and one of the existing pages is swapped out. When this happens, it is called cache miss.

Caching also happens at application layer too, for example, caching visited pages on a browser, caching frequently accessed data from DB to in-memory caches like Redis.

Based on how cache miss is handled in cache, there different type of caches like first in first out cache, least recently use cache, least frequently use cached.

In first in first out cache, in the event of a cache miss, an entity which came first into the cache is evicted first; whereas in least recently used cache, the page which was used least recently gets evicted. In the same vein, least frequently used cache is where page which is least frequently used among all the pages in cache.

## LRU cache implementation

Consider that you have a cache with space for an additional page. If cache miss happens, we bring a page from memory and put it in the cache for future access.

Now, if the cache is full, and cache miss happens, we have to bring in a new page and evict a page from cache. In LRU cache, this page will  be the page which accessed the longest time ago.

What if a page was accessed at the start, and then accessed just before the cache miss? Is it the least recently used page? On the contrary, it is the most recently used page and hence should be last to evict. The question now is which page should we evict? In this case, page which came after the first page goes out.

If page is brought into cache first, it is first candidate for eviction, if it is not accessed again before cache miss happens.

Why queue?

In principle, LRU cache is first in first out cache with a special case, that if a page is accessed again, it goes to end of the eviction order. Which data structure is best to implement FIFO pattern? Of course, it’s a queue. So our LRU cache will be a queue where each node will store a page. This queue will have a specific size as cache as a limited size. Whenever a new page is brought in, it is added at the rear of the queue. When eviction happens, it happens from the front of cache.

Why hash?

There is one requirement of LRU cache which does not map directly to queue data structure, which is to move a node corresponding recently accessed page to end of the queue. This poses two problems: First, how to find the node in the queue corresponding to page id being accessed? Second, how to move it to end as efficiently possible? Both problems are very similar to what we solved in first nonrepeated character in stream.

We will use hash which will store the node address in the queue corresponding to page id. This will give us immediate access to the node to be reshuffled.

Still the problem remains to move nodes around with moving all elements of the queue. Which data structure removes an element in O(1), given the element? Doubly linked list it is. If we implement queue as a doubly linked list, removing and adding pages from the queue will be O(1) operation.

### LRU cache algorithm

• Cache miss happens :
• If cache has free entry, enqueue page to queue.
• If cache is full,  remove the page from from of queue and add new page at the end of queue.
• Cache hit happens :
• delete node from current location in queue.
• Enqueue page at the end of queue.
• If page is present in hash, it’s a cache hit, if page is not present in hash map, it’s a cache miss.

Queue interface

package com.company;

/**
* Created by sangar on 8.10.18.
*/
public interface Queue<E> {
public ListNode<E> peek();
public ListNode<E> remove();
public ListNode<E> enqueue(E data);
public ListNode<E> deleteNode(ListNode<E> node);
public boolean isEmpty();
public int size();
}

Queue implementation

package com.company;

/**
* Created by sangar on 8.10.18.
*/
public class QueueImplementation<E> implements Queue<E>{
ListNode<E> tail;
int size;

public QueueImplementation(){
tail = null;
this.size = 0;
}

@Override
public ListNode<E> deleteNode(ListNode<E> node){
if(this.isEmpty()) {
return null;
}

this.size--;
return node;
}

if(this.tail == node){
if(this.tail.getPrev() != null) this.tail.getPrev().setNext(null);
this.tail = this.tail.getPrev();
this.size--;
return node;
}
/*
We are deleting node in between. So following things happen
1. If node has prev, set node.prev.next = node.next.
2. If node has next, set node.next.prev = node.prev
*/
if(node.getPrev() != null) node.getPrev().setNext(node.getNext());
if(node.getNext() != null) node.getNext().setPrev(node.getPrev());

this.size--;
return node;
}

@Override
public ListNode peek() {
if(this.isEmpty()) {
return null;
}
}

@Override
public ListNode remove() {
if(this.isEmpty()) {
return null;
}
/*
We are deleting node at head. So following things happen
1. Set temporary node point to head.
2. Move head to next of node.
3. Set prev of new head to NULL.
4. Free the temp node.
*/

this.size--;
return tempNode;
}

@Override
public ListNode enqueue(E data) {
if(this.isEmpty()) {
this.size++;
}
ListNode<E> newNode = new ListNode<E>(data,null, this.tail);
this.tail.setNext(newNode);
this.tail = newNode;

this.size++;
return newNode;
}

@Override
public boolean isEmpty() {
}

@Override
public int size() {
return this.size;
}
}

LRU cache implementation in java

package com.company;

import java.util.ArrayList;
import java.util.HashMap;

/**
* Created by sangar on 9.10.18.
*/
public class LRUCache {
private Queue<Integer> queue;
private HashMap<Integer, ListNode> pages;
private int cacheSize;

public LRUCache(int cacheSize){
this.cacheSize = cacheSize;
queue = new QueueImplementation<>();
pages = new HashMap<>();
}

/* This function implements the LRU cache */

/*Cache Miss and we can add the page in the cache */
if (!pages.containsKey(pageId) && queue.size() < cacheSize) {
pages.put(pageId, queue.enqueue(pageId));
return;
}

/* Cache Miss and we cannot add new page to cache,
remove the LRU page */
if (!pages.containsKey(pageId) && queue.size() >= cacheSize) {
//First remove it from the queue.
ListNode evictedPage = queue.remove();
//Remove node from hash table
pages.remove(evictedPage.getData());
//Enqueue new node and add it at tail
pages.put(pageId, queue.enqueue(pageId));
return;
}

/* Cache is Hit */
if (pages.containsKey(pageId)) {
updateCache(pageId);
}

return;
}

/* This function modifies queue when there is cache hit */
public void updateCache(int pageId){

/* Case where queue may be empty - defensive programing*/
if(queue.isEmpty() && queue.size() < cacheSize){
pages.put(pageId,queue.enqueue(pageId));
}
/* Update the pointers of neighbor nodes and tail in dummy node */
else{
ListNode node = queue.deleteNode(pages.get(pageId));
if(node != null){
queue.enqueue((Integer)node.getData());
}
}
}

public ArrayList<Integer> cacheState(){
ListNode current = queue.peek();
ArrayList<Integer> cacheState = new ArrayList<>();
while(current != null){
current = current.getNext();
}
return cacheState;
}
}

#### Test case for LRU cache implementation

package test;

import com.company.LRUCache;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
* Created by sangar on 23.9.18.
*/
public class LRUCacheTest {

LRUCache tester = new LRUCache(5);

@Test
public void testCacheInsertion() {

ArrayList<Integer> cacheState = new ArrayList<>(Arrays.asList(1,2,3,4,5));

assertEquals(cacheState, tester.cacheState());
}

@Test
public void testCacheHit() {

ArrayList<Integer> cacheState = new ArrayList<>(Arrays.asList(1,4,5,2,3));

assertEquals(cacheState, tester.cacheState());
}

@Test
public void testCacheMiss() {

ArrayList<Integer> cacheState = new ArrayList<>(Arrays.asList(2,3,4,5,6));

assertEquals(cacheState, tester.cacheState());
}

@Test
public void testEvictionAndInsertion() {

ArrayList<Integer> cacheState = new ArrayList<>(Arrays.asList(3,4,5,6,1));

assertEquals(cacheState, tester.cacheState());
}

@Test
public void testEmptyCache() {
ArrayList<Integer> cacheState = new ArrayList<>();

assertEquals(cacheState, tester.cacheState());
}
}

Let’s take an example and see how whole thing works. Let’s say we have cache of size 5, which is empty to start with. Application accesses page id 1,2,3,4 and 5. As they are all cache miss to start with and there is space in cache, all these pages are brought into cache.

Now, the application accesses page 6. We have a cache miss. What happens? As the cache is full, we evict the page which is at the front and add page 6 to it.

Application accesses page 2 again, which is already present in the cache, it’s a cache hit. As page 2 is the most recently used page, it has to go to the end of the queue.

Let’s say next page accessed is page 7, it is a cache miss. Evict a page from the cache, which is the first node in the queue (3).

Insertion and removal from queue is O(1) complexity.

## Process

In simple terms, any program in execution is called as process. Every process has a process state associated with it like memory, resources, code, data etc. In operating system, process has unique process identifier and associated process controller block (PCB). We will see in detail what PCB contains in later posts.

 Process execution

Thread is an abstract entity which executes a sequence of instructions. Threads are light weight as compared to process, their creation is efficient and inter thread communication is fast as they use memory to communicate with each other instead of IPC. Process context switch is rather very expensive operation as compared to thread switches. Every program has at least one thread of execution.  A thread cannot live on its own, it has to be within some process. A process can have multiple threads.

From the definition we came across some differences. Let’s tabulate them.

 Process Threads Can live on its own Always runs in a process All process have separate address space and stacks Threads of a process share address space with each other. Threads have separate stack and registers as process has. Inter process communication is done using IPC Inter thread communication is done through shared memory. Heavy weight in terms of IPC, context switch and creation Light weight in terms of IPC, context switch and creation. Process has data segment and heap of its own Thread does not have them

There are two types of threads :

Both have their own use and use case for using in a particular context.
User space threads are very fast in terms of create and switch. But they are not suitable when we need to do blocking I/O calls. Language level threads are best example of this kind of threads.

Kernel space threads are inefficient in terms of creation and switch but they do not block on system calls. These threads are scheduled using system scheduler as any normal process. Programmer does not have any direct controller over these threads.

There are models where one user thread maps to one kernel thread and one user thread maps to multiple kernel space threads or multiple user threads maps to one kernel space threads. These are termed as
1: 1 Model
M: N Model
M : 1 Model

These models are realized using virtual processor (VP).  For first model, all user threads run in one VP.  In second model, user threads run in pool of VPs. This is default model.  While in third model, multiple user threads run in single VP.

In next post we would discuss POSIX library APIs for thread creation, execution and termination along with detailed look at process life cycle and structures used.

This post highlights key points of difference between process and threads, in future posts, we will understand more on these two concepts.

# Linked list-based implementation of queue

A Queue is an abstract data structure which follows the First In First Out FIFO principle. It means the element which came into the queue first will leave the queue first. This ordering is very helpful in a lot of solutions. Two things are important for a queue: front and rear or tail.

A new element is added into the queue at the rear or at the tail, which is called enqueue operation.

The front is the point from where an element of a queue is taken out. This operation is called dequeue operation.

Interface for a queue would be as shown below. This interface can be implemented in multiple ways. There are different ways in which an abstract data structure can be implemented using concrete data structures, for example, a queue can be implemented using arrays or linked lists. Limitation in array-based implementation is that we have to allocate array size beforehand which restricts the number of elements that can be accommodated. Another issue is to correctly tell if the queue is empty or full. We have to maintain an extra counter for that purpose.

package com.company;

/**
* Created by sangar on 8.10.18.
*/
public interface Queue<E> {
public ListNode<E> peek();
public ListNode<E> remove();
public ListNode<E> enqueue(E data);
public boolean isEmpty();
public int size();
}

Let’s discuss how to implement a queue using linked lists.

## Single linked list based implementation of queue

A linked list a collection of nodes where each node has two components, first component store the data for the node and second component points to the next node in the linked list. In the last node, the second component points to NULL, which signifies the end of the linked list.

If we use a linked list, we solve the first problem of statically allocating memory beforehand for the queue. The linked list is a dynamic data structure, we can allocate memory at the runtime based on our requirements. Also, to find if a queue is empty, check if linked list empty, which is a simple operation to check if the head of linked list NULL.

The time complexity to remove an element out to the singly linked list based queue is O(1), remove the head and make the next node of the head new head. However, to add an element into the singly linked list, we have to go the end of the lists which has a time complexity of O(n).

This problem can be easily be solved by keeping a tail pointer, which points to the last node of the linked list. When we have to enqueue an element in the queue, we update the next of tail to point to the new node and make new node has the tail of the queue. The complexity of enqueue operation is also O(1).

The singly linked list seems to be working for the queue implementation, with dynamic size, dequeue and enqueue operation with O(1) complexity.

One more operation performed on queues to solve certain problems like LRU Cache, non repeated characters in a stream etc. This operation is to delete a random node in queue. Given a random node in the queue, remove that node from the queue.

This problem is tricky in a singly linked list. Brute force solution is to traverse the linked list, go till the previous node and the do the pointer rearrangement and then free the memory of the given node. This operation in the worst case requires O(n) operations. There is a trick method, which is to copy the data of the next node of the given node to the given node and then delete the next node. Caveat to this trick, which I have discussed in delete a node from linked list.

To delete a node from a linked list, two pointers are required: the previous node of the node and the next node of the node. All we do is to make the next pointer of the previous node point to the next node of the given node and free the given node.

## Doubly linked list based implementation of queues

From the above discussion, it is easy to guess which type of linked list implementation will give us previous and next node of a given node without traversing the list. It is doubly linked list.

All the operations remain the same, with same time complexity. With the doubly linked list, delete operation also becomes O(1). So, whenever you have a use case where you may have to delete a random node from the queue, always go for the doubly linked list based implementation. The only overhead is that we have to store double the number of pointers than a singly linked list.

package com.company;

/**
* Created by sangar on 8.10.18.
*/
public interface Queue<E> {
public ListNode<E> peek();
public ListNode<E> remove();
public ListNode<E> enqueue(E data);
public ListNode<E> deleteNode(ListNode<E> node);
public boolean isEmpty();
public int size();
}
package com.company;

/**
* Created by sangar on 8.10.18.
*/
public class QueueImplementation<E> implements Queue<E>{
ListNode<E> tail;
int size;

public QueueImplementation(){
tail = null;
this.size = 0;
}

@Override
public ListNode<E> deleteNode(ListNode<E> node){
if(this.isEmpty()) {
return null;
}

this.size--;
return node;
}

if(this.tail == node){
if(this.tail.getPrev() != null)
this.tail.getPrev().setNext(null);
this.tail = this.tail.getPrev();
this.size--;
return node;
}
/*
We are deleting node in between. So following things happen
1. If node has prev, set node.prev.next = node.next.
2. If node has next, set node.next.prev = node.prev
*/
if(node.getPrev() != null) node.getPrev().setNext(node.getNext());
if(node.getNext() != null) node.getNext().setPrev(node.getPrev());

this.size--;
return node;
}

@Override
public ListNode peek() {
if(this.isEmpty()) {
return null;
}
}

@Override
public ListNode remove() {
if(this.isEmpty()) {
return null;
}
/*
We are deleting node at head. So following things happen
1. Set temporary node point to head.
2. Move head to next of node.
3. Set prev of new head to NULL.
4. Free the temp node.
*/

this.size--;
return tempNode;
}

@Override
public ListNode enqueue(E data) {
if(this.isEmpty()) {
this.size++;
}
ListNode<E> newNode = new ListNode<E>(data,null, this.tail);
this.tail.setNext(newNode);
this.tail = newNode;

this.size++;
return newNode;
}

@Override
public boolean isEmpty() {
}

@Override
public int size() {
return this.size;
}
}

### Circular linked list base implementation of queue

Sometimes, the interviewer asks to you solve a trick question like this: Implement queue using only one pointer, either front or rear

The correct answer to it is to use a circular linked list, where the last pointer points back to the head or front pointer. In that case, we will use only the rear pointer.

Enqueue operation:
We create a new node, point the next of new node to the next of tail node, make it next of the tail node and new node becomes the tail node. This whole operation is in constant time, hence the complexity of this operation is O(1).

newNode.next=tail.next;
tail.next=newNode;
tail=newNode;

Dequeue operation:

node = tail.next //node to be removed
tail.next =  node.next // point to the next of front node.

We learned different ways to implement a queue using linked lists. Based on the requirements and constraints of the problem we choose one of the give implementations. To understand more how queues are implemented in Java, please read Queue Implementations

Please share if there is something wrong or missing. If you are preparing for an interview and need personalized coaching to help you with preparation, please book a free session with us.

## Queue Abstract Data Type

Queue in computer programming has same properties which a queue in real life has. First there is only one end where one can enter in queue from and other where one can exit from.  Second, the person who entered first will exit first.

The end where person enters from is usually called as rear of queue and where person goes out is called as front of queue. The principle in which person who entered first leaves first is called as First In First Out (FIFO). It is exactly opposite of stack which is a LIFO data structure.
Queue abstract data structure has following basic operations:
1. Enqueue() : This operation adds new element at the rear of queue.
2. Dequeue() : This removes element from front of queue.
3. Is_empty() : Checks if there are some elements present in queue at given point of time.
4. Queue() : This initializes the queue.

Let us first consider different underlying data structures to implement queue.

## Array based implementation

Ideally a queue should not have any limit on number of elements that can be added to it. But an array would inherently have limit on size. Let’s first see the simple implementation where we say queue as full if we reach at the end of array.

## Code

This implementation has limitation that is queue drifts towards end of the array as enqueue() and dequeue() operations are performed. We might end up saying queue full when there is only one element present in queue.

We can fix it by making rear pointing to first element once all slots in array are filled, that is wrapping around. We need to now come up with the full and empty condition of such a queue.

We can easily wrap around as rear = rear +1 % MAX_SIZE.
Queue is full when rear +1 = front but we see closely, same condition is true in case queue is empty.

So, initialize back and front appropriately. We start with front as 0 and rear as MAX_SIZE -1.Also, keep a counter in order to check if the queue is full or not.

Application of Queues are plenty. Like OS uses queues at multiple places like scheduler, waiting queues on semaphore, sending data from one process to another etc.
In next few posts we would problems which can be solved efficiently using queue ADT. Before that we would like to see linked list base implementation of queue in next post.

# Constant time max operation on stack

We understood stack data structure, operations on it and some examples problems which can be solved using stack. Let’s take problem which is actually based on stack and with the help of other data structures, how can make it more efficient for certain function. Today’s problem is to implement constant time max operation on stack.

To elaborate, you have been given a stack, where elements are pushed and popped randomly. At any given point of time, you have to tell max of all the elements present in stack.
For example : we have stack, we push 5,3,1, current max in stack is 5; we push 6 next, current max is 6 now. How about we pop 6 back. Current max goes back to 5 again.

## Constant time max operation: Line of thoughts

Push and pop operation in a stack are already constant time operations. Let’s concentrate on max operation.
If always just pushed on to stack, it would have been easy to just keep track of ma of all the elements we pushed on to stack. However if we are popping out from stack, this may not be as easy. Max will change if the element just popped from stack was current max. What can we do? We keep track of previous max just before the current max. What if next operation is again pop and it pops out the new current max. Again, we have to keep track of previous to previous max.
Are you getting some hint here? We have to keep track of all the max we ever saw while operating on stack in reverse order. That means the max we saw the last, goes out first. LIFO pattern and what better data structure than stack to implement that.

Idea is to have an auxiliary stack which stores all the max seen till a given point of time. Top of this auxiliary stack would be current max. What happens when pop happens on original array? We check if popped element is equal to top element of auxiliary array, that means popped element was current max. So we pop that from auxiliary stack too.

Let’s take an example and see if it works? To start with, both stacks are empty. Now, you add 2 as first element on to stack. Since auxiliary stack is empty, we add 2 on to that stack too.

Push 3 on to stack. Push operation so check if current top of aux stack is less than new element pushed. If yes, push new element to aux stack too.

Push 5 on to stack. Again, push operation and new push element is greater than top of aux stack, we push 5 there too.

Now, push 1. Tricky case. Push 1 on to original stack, but since new element is less than current top of aux stack, nothing gets pushed on aux stack.

Pop from stack now. 1 is popped, it is not equal to current top on aux stack, nothing happens.

Pop from stack again, this time popped element is equal to current max, so we have pop from aux stack too. If we are asked max at this point of time, answer would be 3.

### Constant time max operation on stack : Implementation

package com.company;

import java.util.Stack;

/**
* Created by sangar on 22.9.18.
*/
public class MaxStack {
Stack<Integer> stack;
Stack<Integer> auxStack;

public MaxStack() {
stack = new Stack();
auxStack = new Stack();
}

public void push(int x) {
int max = auxStack.isEmpty() ? x : auxStack.peek();
//Push on max stack only if max value is being changed.
if (max <= x) auxStack.push(x);
stack.push(x);
}

public int pop() {
int returnValue = stack.pop();
//Pop from aux stack only if ax value is being popped out.
if(auxStack.peek() == returnValue) {
auxStack.pop();
}
return returnValue;
}

public int top() {
return stack.peek();
}

public int peekMax() {
return auxStack.peek();
}

public int popMax() {
int max = peekMax();
Stack<Integer> buffer = new Stack();
while (top() != max) buffer.push(pop());
pop();
while (!buffer.isEmpty()) push(buffer.pop());
return max;
}
}

Complexity of implementation of constant time max operation stack is O(n) in terms of space, with O(1) time complexity for push, pop and max operation.

Wait, interviewer is not satisfied with this only. What we solve is just reporting the max element in stack at a given point of time. What if we were asked to implement pop max element from stack? Well, first of all finding the max element works as it is. However, popping max element requires popping out all element before max, popping out max and then pushing back all other elements again. Quite a lot of work, even when max operation is O(1).

Which data structure allows us to remove an element in constant time? It’s doubly link list. Once you know which node is to be removed, all we have to do is link previous node to next node. If we implement our original stack as doubly linked list, popping max from stack is O(1) operation without moving any other element on stack.

However finding the node in doubly linked list itself is O(n) operation. Back to square one. What would be helpful is that instead of just storing the max element, we store node address of max in doubly linked list. So in our aux stack, we do not store primitive data type, but a pointer to node which is current max.

Let’s see how it works? We follow the same process of finding the max as explained in earlier solution. It starts with pushing element 2 on to stack. This creates the first node on DLL and stores the pointer on stack.

Now, we push 3 on to stack. Since this is greater than current max being pointed to by top of aux stack, we push that to DLL and store the pointer as max pointer on aux stack.

As for 3, same thing happens when 5 is pushed on to stack.

Since new element pushed is less than current max, it’s pointer is not pushed on to aux stack.

After pushing 1, we want to pop max. Step 1 would be to fetch the node pointer for current max. Go to that node in doubly linked list. Remove that node from DLL and then remove the pointer from top of stack.

Make a note that whenever, new pushed element is equal to current max, push that on aux stack too. Why?

Let’s see the implementation of this method using doubly linked list.

package com.company;

import java.util.Stack;

/**
* Created by sangar on 22.9.18.
*/
public class MaxStackDLL {
private Stack<ListNode<Integer>> auxStack;

public MaxStackDLL() {
auxStack = new Stack();
}

public void push(int x) {
int max = auxStack.isEmpty() ? x : auxStack.peek().getData();
//Push on max stack only if max value is being changed.
if (max <= x) auxStack.push(newNode);
}

public int pop() {

//Pop from aux stack only if ax value is being popped out.
if(auxStack.peek() == returnValue) {
auxStack.pop();
}
return returnValue.getData();
}

public int peekMax() {
return !auxStack.isEmpty() ? auxStack.peek().getData() : -1;
}

public int popMax() {
return auxStack.isEmpty() ? -1 : dll.deleteNode(auxStack.pop()).getData();
}
}

Doubly linked list class is as follows

package com.company;

/**
* Created by sangar on 22.9.18.
*/

}

public boolean isEmpty(){
}

if(this.isEmpty()) {
}
/*
We are inserting node at head. So following things happen
1. Create a new node.
2. Set next of new pointer to current head.
3. Set prev of head to new node
*/
//First two steps are done here
ListNode<Integer> newNode = new ListNode<Integer>(data,this.head, null);
//Step 3.
//Step 4.

}

if(this.isEmpty()) {
return null;
}
/*
We are deleting node at head. So following things happen
1. Set temporary node point to head.
2. Move head to next of node.
3. Set prev of new head to NULL.
4. Free the temp node.
*/

return tempNode;
}

public ListNode<Integer> deleteNode(ListNode<Integer> node){
if(this.isEmpty()) {
return null;
}
/*
We are deleting node in between. So following things happen
1. If node has prev, set node.prev.next = node.next.
2. If node has next, set node.next.prev = node.prev
*/
if(node.getPrev() != null) node.getPrev().setNext(node.getNext());
if(node.getNext() != null) node.getNext().setPrev(node.getPrev());

return node;
}
}

ListNode class is as follows

package com.company;

/**
* Created by sangar on 22.9.18.
*/
public class ListNode<T> {
private T data;

private ListNode<T> next;
private ListNode<T> prev;

public ListNode(T data){
this.data = data;
next = null;
prev = null;
}

public ListNode(T data, ListNode<T> next, ListNode<T> prev){
this.data = data;
this.next = next;
this.prev = prev;
}

public ListNode<T> getNext(){
return this.next;
}

public ListNode<T> getPrev(){
return this.prev;
}

public void setPrev(ListNode<T> newNode){
this.prev = newNode;
}

public void setNext(ListNode<T> newNode){
this.next = newNode;
}

public T getData(){
return this.data;
}
}

Tester class is given below. Can you add more test cases to this?

package test;

import com.company.MaxStackDLL;
import org.junit.jupiter.api.Test;

import static org.junit.Assert.assertEquals;

/**
* Created by sangar on 22.9.18.
*/
public class MaxStackTest {

MaxStackDLL tester = new MaxStackDLL();
@Test
public void popMaxTest() {

tester.push(2);
tester.push(3);
tester.push(5);
tester.push(1);

assertEquals(5, tester.popMax());
assertEquals(3, tester.popMax());
}
}

Time complexity of push, pop and popMax is O(1). There is additional space requirement which is O(n).

Please share if there is something wrong or missing. If you are interested in taking personalized coaching by our experienced coaches, please reach out to us at [email protected]

## Kernel APIs for semaphore

In last post we discussed difference between mutex and semaphore. In this post we will discuss various flavors and APIs used for semaphore usage.

Any locking mechanism has to deal with interrupts. Semaphore too has to deal with it. Since interrupts can call down (we will see it later) and up, any semaphore locking implementation should disable interrupts. At the same time, interrupt may use down when it is sure that it will get the lock, such cases we need to use another variant of down namely down_interruptable() and down_killable.

There are two basic operations which are done on semaphore, namely decrease the counter while acquiring the resource and increase the counter while releasing resource. There are two APIs:

For decreasing the counter :
void down(struct semaphore *sem)

For increasing the counter :

void up(struct semaphore *sem)

Processing in down() is as follows:
Check if the current counter is greater than 0.
If it is then decrease the counter  and take the resource.
If the counter is less than zero, put the process trying to acquire the lock in the semaphore queue.

In up() routine, process increments the counter value and wakes up next process from the queue. It is not necessary that up() is called by the same process which called down, Any process can call this function and wake up any process sleeping on this semaphore.

If we want process to wake up when any signal is received, we may use another variant of down that is down_interruptable(). Function is similar to simple down, only difference is if the process has gone n sleep state, signal can wake process up.

int down_interruptible(struct semaphore *sem)

This function return -EINTR if process woke up due to signal and 0 if it woke up after acquiring semaphore.

Another variant of down() is down_killable(). If we use this function, process waiting for semaphore can respond to FATAL signal.

int down_killable(struct semaphore *sem)

All above APIs are using a common structure
that is semaphore.
Definition of semaphore struct is :

struct semaphore {
spinlock_t lock;
unsigned int count;
};

spinlock  is used in all above function to protect critical section inside.

Reference
http://www.cs.fsu.edu/~baker/devices/lxr/http/source/linux/kernel/semaphore.c#L204

# Implement queue using stack

In last post, we learned about stack data structure, in this post, we will discuss another data structure called queue. However, problem at hand is to implement queue using stack. Implement following functions on queue using stack
1. push() : inserts element at the back of queue.
2. pop() : removes element from front of the queue.
3. peek() : return element at front of the queue.
4. empty() : returns true if there is no element in queue.

Keep in mind that you can only use standard stack operations : push(), pop(), peek() and empty()

Stack is data structure where the element which is entered at top is taken out from top. It’s called LIFO pattern. Oppose to that queue is a FIFO data structure, where elements are entered at the rear and taken out from front. So effectively, we have to implement a FIFO data structure using LIFO data structure.

## Implement queue using stack : Line of thoughts

To implement a FIFO using LIFO data structure, we need two stacks.

Push()
When element is inserted i.e push() operation, new element has to be pushed down the stack at bottom, as this should be the last element to be popped. So, to push an element in queue, we will take out all existing elements from stack s1 and put them into stack s2. Now, push the new element on to stack s1. At last, pop all elements from stack s2 back to stack s1. Below picture shows what happens when you we push 3 to queue and what happens behind the scene using stacks.

Complexity of push operation with this method is O(n). If there are n elements already inserted into queue, inserting a new element will require n pops from s1, n pushes to s2, then n pops from s2 and then again pushes to s1.

Pop()
If we follow the push operation described above, pop operation would be nothing but to return top of s1, which is constant operation with complexity of O(1).

Peek and empty functions also run always on stack s1. For peek, return s1.peek() and for empty return s1.empty()

### Queue with stack : Push O(n), pop O(1) implementation

package com.company;

import java.util.Stack;

/**
* Created by sangar on 23.9.18.
*/
public class QueueWithStack {
private Stack<Integer> s1;
private Stack<Integer> s2;

public QueueWithStack(){
s1 = new Stack<>();
s2 = new Stack<>();
}

public void push(int x){
if(s1.empty()) s1.push(x);
else{
while(!s1.empty()){
s2.push(s1.pop());
}
s2.push(x);
while(!s2.empty()){
s1.push(s2.pop());
}
}
}

public int pop(){
if(s1.empty()) return -1;
return s1.pop();
}

public boolean isEmpty(){
return s1.empty();
}

public int peek(){
return s1.peek();
}
}

Test class for above implementation would be:

package test;

import com.company.QueueWithStack;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
* Created by sangar on 23.9.18.
*/
public class QueueWithStackTest {

QueueWithStack tester = new QueueWithStack();
@Test
public void queueTest() {

tester.push(2);
tester.push(3);
tester.push(5);
tester.push(1);

assertEquals(2, tester.pop());
assertEquals(3, tester.pop());
assertEquals(5, tester.peek());
assertEquals(false, tester.isEmpty());
}
}

Can we do better than O(n) while pushing element in queue?

### Queue with stack : Push O(1), pop amortized complexity O(1) implementation

Push()
What if we push on s1 as it is. What does it change? It make push operation on queue O(1).

Pop()
How does it impacts pop operation? If we pop all element from s1 and push them onto s2, at the top of s2 is actually the element we need. Also, due to this pop and push operation, s2 now contains all the elements in correct pop order for queue.
So idea is to always push in s1 as it is, however when popping out, check if s2 is empty or not? If not, then pop from s2 and return, if it is empty, pop all elements from s1 and push them all on s2 and return the top.

How does it impact the performance? Well, it is true that if there is not element in s2, we have pop and push on s2, which has complexity of O(n). HOwever, all subsequent pop operations are O(1), this is called amortized complexity of O(1).

Empty()
Queue to be empty, there should not any element in either s1 or s2.

Peek()
If s2 is empty, then pop from s1 and push on to s2 and then return peek of s2.

package com.company;

import java.util.Stack;

/**
* Created by sangar on 23.9.18.
*/
public class QueueWithStackOptimized {
private Stack<Integer> s1;
private Stack<Integer> s2;
private int front;

public QueueWithStackOptimized(){
s1 = new Stack<>();
s2 = new Stack<>();
}

public void push(int x){
if(s1.empty()) front = x;
s1.push(x);
}

public int pop(){
if(!s2.empty()) return s2.pop();
if(!s1.empty()) return -1;

while(!s1.empty()){
s2.push(s1.pop());
}
return s2.pop();
}

public boolean isEmpty(){
return s1.empty() && s2.empty();
}

public int peek(){
if(!s2.empty()) return s2.peek();

return front;
}
}

Complexity of peek function is again amortized to O(1). Can you write test cases for implemented queue?

Reference : Leetcode

Please share if there is something wrong or missing. If you want to have personal coaching from our experienced coaches, please reach out to us at [email protected]