Min Stack

I recently started practicing on LeetCode to keep my coding skills sharp and also learn from submissions that other people make for same problem. 

Today I solved an easy category problem named "Min Stack". Problem statement was to design a stack data structure which has getMin() operation along with all regular stack operations like Push, Pop, Peek/Top. 

I used two stack approach, where one stack was for regular stack operations and other was to keep track of min values. At each push if pushed values is smaller or equal to the last smallest value then I push value in min values stack. You may take a look at my code here. Below is screenshot of the solution:

Next I started checking for solutions having better timing than my solutions. Sample solution present under best time category was created using Linked List where each item stores min value along with it. By using this approach it avoided multiple if checks as were present in my solution and made code look a lot more cleaner and run faster. This solution uses O(N) space in all cases while mine uses O(N) space in worst case but that is kind of tradeoff you make for speed.

Why I posted this as a blog, just so as at least a future me may read this again. Everyone else who reads this is a bonus ;)

Recursive CTE | Print total number of unique hackers who made at least one submission each day

	/*
	https://www.hackerrank.com/challenges/15-days-of-learning-sql/problem
	Query to print total number of unique hackers who made at least one submission each day (starting on the first day of the contest), and find the hacker_id and name of the hacker who made maximum number of submissions each day.
	Solution/Approach:
	This question comprises of two subproblems:
	1. Name and Id of hacker who did max number of submissions on given day
	2. Count of hackers who submitted on given day and all previous days
	To solve first problem, we can use ROW_NUMBER function of SQL Server. Using this function we can partition data by submission date and then order by count in descending and hackerId ascending orders. Ordering by hackerId is required because problem statement says if more than one such hacker has a maximum number of submissions, print the lowest hacker_id.
	To solve second problem, we can use recursive CTE. Here for each day we need to lookup data from all previous days. For day 1 it's count of all distinct hackers of that day, this will also be base case of our recursive CTE. Next we need to build on base case by joining next day data with previous day's. Limiting condition of our recursive query will be last day of our input data set.
	*/
	--Query
	--This temp table holds data that will help us solve problem 1
	SELECT s.submission_date, s.hacker_id, h.name, ROW_NUMBER() over (partition by submission_date ORDER BY COUNT(*) desc, s.hacker_id) rowNum
	INTO #tmpSubmissions
	FROM Submissions s
	JOIN Hackers h
	ON s.hacker_id = h.hacker_id
	GROUP BY s.submission_date, s.hacker_id, h.name
	ORDER BY s.submission_date, s.hacker_id
	DECLARE @startDate datetime = (SELECT min(submission_date) FROM #tmpSubmissions)
	DECLARE @endDate datetime = (SELECT DATEADD(day, 1, max(submission_date)) FROM #tmpSubmissions)
	--Recursive CTE
	;with cteResult AS (
	--Base CTE | Here we fetch data of day 1
	SELECT submission_date, t.hacker_id, name
	FROM #tmpSubmissions t
	where t.submission_date = @startDate
	UNION ALL
	--Here we are joining current day data with previous data data already present in CTE to find hackers from current day with that have submitted on previous day as well
	SELECT t.submission_date, t.hacker_id, t.name
	FROM #tmpSubmissions t
	JOIN cteResult c
	ON t.submission_date = DATEADD(day, 1, c.submission_date) and t.hacker_id = c.hacker_id
	--Limiting condition
	WHERE t.submission_date < @endDate
	)
	SELECT c.submission_date, count(*), t.hacker_id, t.name
	FROM cteResult c
	left JOIN (
	SELECT *
	FROM #tmpSubmissions
	where rowNum = 1
	) t
	ON c.submission_date = t.submission_date
	GROUP BY c.submission_date, t.hacker_id, t.name
	ORDER BY c.submission_date, t.hacker_id
	DROP TABLE #tmpSubmissions
	/*
	--Sample Data
	create table Hackers (hacker_id int, name varchar(100))
	create table Submissions (submission_date datetime, submission_id int, hacker_id int, score int)
	insert into Hackers values
	(15758, 'Rose'),
	(20703, 'Angela'),
	(36396, 'Frank'),
	(38289, 'Patrick'),
	(44065, 'Lisa'),
	(53473, 'Kimberly'),
	(62529, 'Bonnie'),
	(79722, 'Michael')
	insert into Submissions values
	('2016-03-01', 8494, 20703, 0),
	('2016-03-01', 22403, 53473, 15),
	('2016-03-01', 23965, 79722, 60),
	('2016-03-01', 30173, 36396, 70),
	('2016-03-02', 34928, 20703, 0),
	('2016-03-02', 38740, 15758, 60),
	('2016-03-02', 42769, 79722, 25),
	('2016-03-02', 44364, 79722, 60),
	('2016-03-03', 45440, 20703, 0),
	('2016-03-03', 49050, 36396, 70),
	('2016-03-03', 50273, 79722, 5)
	*/

view raw recursiveCTE.sql hosted with ❤ by GitHub

ASP.NET Core API - remove default logging providers to improve performance

So the basic point of this post is to tell you that ASP.NET Core applications have console logging on by default and you should disable that unless you really want that for some reason as it causes performance penalty. If you know how to do that then you may well skip reading this post beyond this point and check out my other posts, but if you didn't know this yet then read on.  

The ASP.NET Core provides four logging providers by default, namely Console, Debug, EventSource and TraceSource. You may or may not need these in your applications, so in case you just need to write logs to a file, database or something like that then better disable default ones. The next paragraph will show how doing that.

There are two ways to configure third-party logging provider in a .NET Core API application, Log4Net in my case. One way is to add the line "loggerFactory.AddLog4Net()" in your Startup.cs file as given in Log4Net plugin's github page and another is by using "ConfigureLogging" method in CreateHostBuilder method.  

Configure via Startup.cs file

Configure in Program.cs file

Now, as you can see in second screenshot clearing default providers is simple, you just need to call line logging.ClearProviders();

How much doing this helps?

To figure that out, I created, a default ASP.NET Core API project. Next I configured Log4Net using mechanisms, as shown in above two screenshots. Then I called both scenarios of API from a console application in a loop and recorded the time it took for 1000 executions. Below table shows how much difference in time was there between the two scenarios.

 Now if you measure "API hits per day", then this might not be of significance to you, but if it's "API hits per minute/second" then open your Visual Studio and remove unused providers ASAP. 

Happy Coding!!  

Web API complex input parameter is null

I do maintain a ASP.NET WebAPI 2.0 service that was running smoothly for quite some time on our production server, until one day an existing client of our service reported that they are getting "invalid request" response from our service and that behavior is random. So we checked our logs and found that request object we received from them were actually null and thus the error they got. Till this point our controller action looked like below: 

To diagnose this issue we added logs to check raw request received by us and that confirmed two things: 

1. First request received by was fine but every subsequent same request was landing in our action as null 

2. Raw request content and headers were similar for both successful and failed requests

Below is code that I used to log raw request content:

To sort out the issue we changed our action slightly. Now instead of letting framework to do model binding for us, we started doing it manually as shown in below snippet: 

Here we are reading request content as string and then converting it to our expected object using newtonsoft json converter. Hopefully this will help you to save some of your time.

Object Oriented Programming

There are loads of articles on this topic but still there are not many which give short answer to the question "what is OOPs" from an interview perspective (very much needed in these troubled times :). So I thought to come  up with one that does just that. If you have your interview tomorrow then you may want to skip to the end and just read the summary section. But if you have 5-10 minutes then I'll encourage you to go through this blog entry from start to end.

Below is basic known definition that majority of people will give if asked what is OOPs:
OOPS is a programming paradigm that keeps objects and methods together to create applications. In this paradigm we try to find entities that can store data, have some behavior and that can interact with one another. It involves several concepts and features like Inheritance, Polymorphism, Abstraction, and Encapsulation.

"this" pointer

Now consider green color highlighted first line of above definition and think what is that keeps objects(data) and methods(operations) together, it's "this" pointer. "this" pointer points to object(data) on which method(operation) is performed and that is fundamental thought of Object Oriented Programming. It enables us to avoid global variables and functions and ensures that operations become quality of data structure rather than a standalone operation. This in turn gives rise to approach mentioned in yellow highlighted second line of definition. You have to think about entities or actors in your project, data they are gonna hold, operations they can perform and relationship with other such entities.

Dynamic dispatch

"dynamic dispatch" is second foundation concept of OO. It is the process of selecting an implementation of a polymorphic operation(method or function) to call at run time. The purpose of dynamic dispatch is to defer the selection of an appropriate implementation until the run time type of a parameter is known (this line I took from Wikipedia article for dynamic dispatch). This process works by coordination of object, object's type and runtime environment. Here Object's duty is to carry data about it's type, Type's duty is to keep track of its virtual function table and runtime's duty is to find concrete function address.

Now coming to blue highlighted third line of our definition, we have OOPs principals, these are consequences of foundation. There are host of fabulous articles on OOPs principles, so I will not blabber around unnecessarily on those. For the sake of completeness of this article, below are short notes to get you going on these concepts:

Abstraction and Encapsulation
Abstraction and encapsulation are complementary concepts. Abstraction focuses on the observable behavior of an object while encapsulation focuses upon the implementation that gives rise to this behavior. Abstraction has to do with separating interface from implementation while encapsulation has to do with disallowing access to or knowledge of internal structures of an implementation.

e.g, You have to create a FlightBooking system with create and cancel operations. Now your Flight booking class shall expose two methods "Create" and "Cancel" for outside world via an interface or whatever but internally there will be multiple operations like communicate with airline, take money from bank, etc. Here abstraction is the interface that you created for world to coordinate with you and Encapsulation is mechanism like making methods for internal operations private. 

Inheritance
It is extending from something else, acquiring properties from a base class. E.g., a "Flight booking" extends from "Travel Booking" which in turn extends "Booking".

e.g, FlightBooking and HotelBooking classes extending from Booking class which has code for common operations like saving passenger details.

Polymorphism

It is the phenomenon wherein somewhat interchangeable objects each expose an operation of the same name but possibly differing in behavior. It allows the expression of some sort of contract, with potentially many types implementing that contract in different ways, each according to their own purpose. Both overloading(compile time polymorphism) and overriding(runtime polymorphism) are used to achieve this same concept.

e.g, FlightBooking having two methods for cancel operation, one taking no parameters and cancels whole booking while other taking passenger object so as to cancel for that passenger only. 

Summary
OOPs is programming paradigm that is based on two fundamental concepts:

• "this" pointer: It points to object on which function operates and results in two important properties of OOPs
• No more global functions
• Operations become quality of data structure
• "dynamic dispatch": It is the process of selecting which implementation of a polymorphic operation (method or function) to call at run time.
• Object’s duty
• To carry data about its type
• Type’s duty
• To keep track of its virtual function table
• To override some functions from its base type
• Runtime’s duty
• Find concrete function address

OOPs principals (Abstraction, Encapsulation, Inheritance and Polymorphism) are consequences of foundation concepts.

Using Non Clustered Indexes in SQL Server

In general most of us believe indexes improve performance of our select queries. But as with every other thing, this too doesn't holds true universally. They only help in their specific use cases.

Indexes are sure to take a toll on your insert, update and delete queries and may even negatively impact select queries if not created properly. To judiciously create indexes we need to understand when a particular index will be of help. Below are scenarios which may help you figure out the right kind of non clustered index for your particular use case.

To begin with, let us create a test table and populate it with some data.

Scenario 1: One non clustered index per column

Suppose we have below query on our table. To cater this query two separate indexes one each on columns "Name" and "VarField" are required. This is so because where clause in our query has two conditions joined with OR operator.

Note: If you have 10 fields in your where clause then this doesn't means you gotta create ten indexes. You should create and test and then decide on right balance. 

Create index script:

Scenario 2: Multiple key columns in single non clustered index (Composite Index)

Now suppose above query changes from OR condition to AND condition, in that case having one index comprising of both columns will be a better solution as we will get data from index in one go. If we had two different indexes one each for both fields then SQL engine would have used only one of those indexes and did a key lookup for second condition.

Create index script:

Scenario 3: Covering index

Now say we need to search on Name field and fetch value of VarField, in this case covering index comes to our rescue. Covering indexes should be created for hot columns or those fields that are accessed very frequently. If we have lot many columns and different queries fetching different set of columns then better will be to use index on where clause field only.

Create index script:

SQL Indexing is a very vast topic and I hope this will help you begin appreciating idea of making indexes judiciously and not on every other column blindly. 

Happy Coding!!

Generic MinHeap implementation

With things in complete lockdown due to coronavirus situation world over, I was getting bored this weekend. Also I hadn't added any new post here in this blog for quite some time. So thought to write a new post, kind of killing two birds with a stone :P

In today's post I am going to talk about MinHeap. 

A min-heap is a binary tree such that - the data contained in each node is less than (or equal to) the data in that node’s children. - the binary tree is complete. 

Heaps are useful when we need priority queue kind of structure. Here instead of adding a new item at the end of queue, it could be inserted further up the queue depending on their priority. This helps in a lot of scenario but lesser beings like me could tell you that I used it while solving merge n sorted array task at hacker rank but to see a real real world use case, you may check this Quora answer.

Below is my array based generic implementation of MinHeap in C#. Using array for heap makes it easy to access child/parent nodes, we can do so by using simple formulae:

    parentPosition => (currentChildPosition - 1) / 2

           leftChildPosition => 2 * currentChildPosition +1

rightChildPosition => 2 * currentChildPosition +2

	using System;
	namespace ConsoleAppVS2017
	{
	/// <summary>
	/// Array based implementation of Min Heap
	/// </summary>
	/// <typeparam name="T">T should be IComparable</typeparam>
	public class MinHeap<T> where T : IComparable<T>
	{
	//This will be used in case default contructor is called for initializing MinHeap
	private const int DefaultHeapSize = 10;
	/// <summary>
	/// Heap storage array
	/// </summary>
	private readonly T[] heap;
	/// <summary>
	/// lastItemIndex keeps track of position where new item needs be added
	/// </summary>
	private int lastItemIndex;
	/// <summary>
	/// Gives count of elements currently present in Heap
	/// </summary>
	public int Count { get { return lastItemIndex; } }
	#region Constructors
	public MinHeap() : this(DefaultHeapSize)
	{
	}
	public MinHeap(int initialSize)
	{
	//TODO: Check against predefined MaxSize and throw some checked exception
	this.heap = new T[initialSize];
	lastItemIndex = 0;
	}
	#endregion
	/// <summary>
	/// Get min element of heap without pulling it out
	/// </summary>
	/// <returns></returns>
	public T Peek()
	{
	if (lastItemIndex == 0)
	{
	throw new InvalidOperationException("Heap Empty");
	}
	return heap[0];
	}
	/// <summary>
	/// Add a new element in heap
	/// </summary>
	/// <param name="item">Item to be added</param>
	public void Push(T item)
	{
	//Validate if heap has space left for adding new element
	if (lastItemIndex == heap.Length)
	{
	//TODO: Implement Grow function and throw in case heap reaches max permissible size limit
	throw new OverflowException("Heap overflowed");
	}
	heap[lastItemIndex] = item;
	//Add element at the end of tree and increment array index pointer
	lastItemIndex++;
	//Print();
	//Console.Write("\t\t");
	//Adding a new element may break min heap property "All root elements should be smaller than their child nodes"
	HeapUp();
	//Print();
	}
	/// <summary>
	/// Remove min element of heap
	/// </summary>
	/// <returns>Min element of heap</returns>
	public T Pop()
	{
	if (lastItemIndex == 0)
	{
	throw new InvalidOperationException("Heap Empty");
	}
	T result = heap[0];
	//Print();
	//Console.Write("\t\t");
	//After removing min element we need to rebalance the tree by moving one of the child nodes up
	HeapDown();
	//Print();
	return result;
	}
	#region Private Functions
	/// <summary>
	/// Hear we begin from last item of heap and bubble it up till we find a node where both its child are bigger than it
	/// To bubble up we find Index of parent node which is equal to (index of current item - 1) / 2
	/// and swap if current item is smaller than its parent
	/// We repeat steps till heap property gets true or root node is reached
	/// </summary>
	private void HeapUp()
	{
	int itemIndex = lastItemIndex - 1;
	do
	{
	int parentIndex = (itemIndex - 1) / 2;
	if (heap[itemIndex].CompareTo(heap[parentIndex]) < 0)
	{
	Swap(itemIndex, parentIndex);
	itemIndex = parentIndex;
	}
	else
	{
	break;
	}
	}
	while (itemIndex != 0);
	}
	/// <summary>
	/// Here we move the last item of tree at top position and then rebalance tree by swapping smaller of two child nodes with root node
	/// We keep iterating till we have reached end of tree or tree gets balanced
	/// </summary>
	private void HeapDown()
	{
	lastItemIndex--;
	//Move last item at top
	heap[0] = heap[lastItemIndex];
	//replace moved item with default value, null for reference types, 0 for int, etc
	heap[lastItemIndex] = default(T);
	int currentItemIndex = 0;
	while (currentItemIndex != lastItemIndex)
	{
	int minChildIndex = FindIndexOfMinChild(currentItemIndex);
	if (minChildIndex != -1 && heap[currentItemIndex].CompareTo(heap[minChildIndex]) > 0)
	{
	Swap(currentItemIndex, minChildIndex);
	currentItemIndex = minChildIndex;
	}
	else
	{
	break;
	}
	}
	}
	/// <summary>
	/// Finds smaller of two child nodes
	/// </summary>
	/// <param name="currentItemIndex"></param>
	/// <returns>-1 if its lead node else index of smaller child or only child available</returns>
	private int FindIndexOfMinChild(int currentItemIndex)
	{
	int leftChildIndex = (2 * currentItemIndex) + 1;
	int rightChildIndex = (2 * currentItemIndex) + 2;
	//Current item is last item of heap
	if (leftChildIndex >= lastItemIndex && rightChildIndex >= lastItemIndex)
	{
	return -1;
	}
	if (leftChildIndex >= lastItemIndex && rightChildIndex < lastItemIndex)
	{
	return rightChildIndex;
	}
	if (rightChildIndex >= lastItemIndex && leftChildIndex < lastItemIndex)
	{
	return leftChildIndex;
	}
	if (heap[leftChildIndex].CompareTo(heap[rightChildIndex]) < 0)
	{
	return leftChildIndex;
	}
	else
	{
	return rightChildIndex;
	}
	}
	private void Swap(int index1, int index2)
	{
	T temp = heap[index1];
	heap[index1] = heap[index2];
	heap[index2] = temp;
	}
	private void Print()
	{
	Console.WriteLine(string.Join(",", heap));
	}
	#endregion
	}
	}

view raw .cs hosted with ❤ by GitHub

You may like to check this link for more details on heap. Stay Home, Stay Safe!