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

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

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