Algorithm and Data Structure (Find the winner for the sequence)

Given an input N where N is a number sequence from 1 to N.

say N= 6, so 1 2 3 4 5 6 is the sequence. In each iteration, odd position number gets eliminated until a single number is left.

E.g for sequence 1 2 3 4 5 6 

After 1st iteration :2 4 6

After 2nd iteration : 4 , so no 4 is the winner.

Constraint: N>1

E.g: 1 2 3 4 5 6 7 8

        2 4 6 8 after 1st iteration

        4 8       after 2nd iteration

        8          after 3rd iteration (winner)

Find the winner for the given N, where N can be a very large number.

Solution :

To solve this kind of problem we would go through the following steps :

 1. Write multiple test cases and the respective output. 

 2. Analyze the output for the given input and the relation between them.

 3. Once we find the relation we will try to express it in the form of mathematical expression if

     possible.

4. Write the code/algorithm for the above expression.

5. Find the time and space complexity.

 Test Cases

1. 1 2 3 4 5 6

       2 4 6

        4(winner)

2. 1 2 3 4

     2 4

     4

3. 1 2 3

     2

4. 1 2 3 4 5 6 7 8

    2 4 6 8

     4 8

      8

5. 1 2 3 4 5 6 7 8 9 10 11 12

     2 4 6 8 10 12

     4 8 12

     8

6. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

    2 4 6 8 10 12 14 16 18 20

    4 8 12 16 20

     8 16

     16

So let's create a table for the given input N and its respective winner

Input N	winner
3	2
4	4
6	4
8	8
12	8
20	16

Before you all proceed further I would like you all to analyze the table and find the relationship between input and the winner.

Analyzed Relation:

the output is in 2^i format.

2^1	2
2^2	4
2^3	8
2^4	16
2^5	32
2^6	64
….	…..

Using the above table we can create the winner table for the range of inputs

Input Range	winner
2-3	2
4-7	4
8-15	8
16-31	16
32-63	32
….	….

Algorithm:

1. Initialize a variable say winner=2

2. Iterate while winner*2<=N

     a. Multiply the variable winner by 2 and assign to the winner.

3.Return winner.

Code:

public long GetWinner(long input)

{

 long winner=2;

while(winner*2<=n)

{

  winner*=2;

}

return winner;

}

or we can also write using for loop

public long GetWinner(long input)
{
long winner;
for(winner=2;winner*2<=n;winner*=2);
return winner;
}

Time & Space Complexity:

Space Complexity: O(1) for the variable winner.

Time Complexity: log N, for average, worst and best case since we are increasing the loop by multiple of 2.

Algorithm and Data Structure ( Add Two Numbers In Linked List)

     Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Method 1:
   
This problem is straightforward where we need to traverse both the list simultaneously till we
reach the end of both the list.
Then we need to add the value of each respective node say x+y along with any carry.
Initialize carry with 0.
sum = x+y+carry

Create a new node and add sum Mod 10 as the value of the new node.
Update carry = sum/10

E.g   2 + 5 = 7  carry = 0, new node = 7,
        4+6= 10, carry=1, new node =0,
        3+4+1(carry), carry = 0, new node = 8

Output : 7=>0=>8

Remember to check any carry left after you traverse both the list till the end.
If carry > 0 then create a new node with carry as node value.

Implementation :

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */

 public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
       
       ListNode head = new ListNode(0); // dummy node
       ListNode output = head;
       int carry = 0;
       int sum=0;
           
            while (l1!= null || l2!= null)
            {
                sum = carry; // in each iteration initialize sum with any carry left
                if (l1 != null)
                {
                    sum +=  l1.val; // add node  value in sum
                    l1 = l1.next;  // move list1
                }
                if (l2 != null)
                {
                    sum+= l2.val; // add node  value in sum
                    l2 = l2.next;   // move list2
                }
              
                carry = sum/10;  // find any carry
                output.next = new ListNode(sum % 10); // create a new node with value
                output = output.next;
               
               
            }
             
                if (carry!=0)  // if any carry left than add it as new node value
                {
                     output.next = new ListNode(carry);
                     output = output.next;    
                }

            return head.next; // head is a dummy node whose next points to out output list.
       
    }

Time Complexity: O(max(m,n)) where m and n is the size of lists.
Space Complexity : O(max(m,n) + 1), here +1 is for any carry if left.

Method 2 :

There are other ways also where you traverse each list and form the number.
After forming the number, you add the two numbers and create the list in reverse order.
For forming the number you can use place value of each number in list

e.g 2=>4=>3 

2 * 10^0 + 4* 10^1 + 3* 10^2 = 2 + 40 + 300 = 342 

5 * 10^0 + 6* 10^1 + 4* 10^2 = 5 + 60 + 400 = 465 
                                                                     sum= 807

Create the list for each digit from sum in reverse order 7=>0=>8

Time Complexity : O(max(m,n)) +  O(max(m,n) + 1) where m and n is the size of lists.

= 2O(max(m,n))+1

Time is twice because first, we create the respective sum for each list in O(max(m,n)) and then
 break the sum in O(max(m,n)+1) time for creating output list.

Space Complexity : O(max(m,n) + 1), here +1 is for any carry if left.

                  

Algorithm and Data Structure (Two Number)

Two Number

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
There can be duplicate elements in the array of integers. If your solutions have one of this element than consider the position of the first element.
If no such elements exist then return [-1,-1].

Given input = [1, 3, 6, 8, 2], target = 10,

Because input [3] + input [4] = 8 + 2 = 10,
Output : [3, 4].

Do not use the element with same position twice.
e.g input = [2, 7, 2, 8, 6], target = 4
Output =[0,2] is correct, where index 0 and 2 both has element 2 but in different position.
Output= [0,0] is wrong. Here we are repeating the element with the same position.

Method 1 (Brute Force):

We can use brute force approach to solve this problem. We take each element and add with
other elements in the array and check if their sum is equal to the target value.
If we have such sum than we break from the loop and return the positions in the array.

Implementation(c#) :

     public int[] TwoSum(int[] input, int target)
        {
        
              for(int i=0;i<n-1;i++)
                {
                     for(int j=i+1;j<n;j++)
                       {
                          if(input[i]+input[j] == target)
                           return new int[]{i,j};
                        }
                }
               return new int[]{-1,-1};
         }

Time Complexity is O(n-1) * O(n) = O(n^2).
Space Complexity is O(1).

Method 2 (Sorting): First we can sort the array using MergeSort which has the time complexity of      O(n Log n) in all best, worst and average case.
After sorting we will run a loop  and find pair of elements as shown below :

      if input[i]+ input[n-1] == target , n is the length if the array.
        a = input[i];
        b = input[n-1]

     if input[i]+ input[n-1] > target
        n--;

     else
        i++

Input = [1, 3, 6, 8, 2 ], target = 10

After Sorting : [1,2,3,6,8], i=0, n=5
Now check if input[i]+input[n-1]
i.e 1+8=9<10 so increase I
      2+8 =10 so assign 2 and 8 to some temporary variable;

Now try to find their actual position in the original unsorted input array and return their actual positions in sorted order.

Remember to keep a copy of the original input.

Time Complexity =  O(n log n)
Space Complexity = O(n) + O(n) +2C = O(2n)

Implementation

public int[] TwoSum(int[] nums, int target)
        {
            var nums1 = (int[])nums.Clone(); // copy of original input
            var result = new int[2]{-1,-1};
            Array.Sort(nums);
            int a = 0, b = 0;
            int n = nums.Count();
            int i = 0;
            while (i < n)
            {
                if (nums[i] + nums[n - 1] == target)
                {
                    a = nums[i];
                    b = nums[n - 1];
                    break;
                }
                else if (nums[i] + nums[n - 1] > target)
                    n--;
                else
                    i++;
            }
            int apos = -1, bpos = -1;
            i = 0;
             n = nums.Count();
            while (i < n)
            {
                if (apos == -1 && a == nums1[i])
                {
                    apos = i;
                    i++;
                }
                  
                if (bpos == -1 && b == nums1[i])
                    bpos = i;
                if (apos != -1 && bpos != -1)
                    break;
                i++;
            }
            if (apos <= bpos)
            {
                result[0] = apos;
                result[1] = bpos;
            }
            else
            {
                result[1] = apos;
                result[0] = bpos;
            }  
          
            return result;
        }

Method 3 (Hash Table) :

Using the hash table to solve this problem will be the best approach.
Here we will create a hash table with a key as the number and its index as the value in the input array.
Then check if the target- input[i] is present in the table or not.

E.g target = 10, input[i] starting from 1 in array [1,3,6,8,2]
                                                                                                   hashtable(number,position)
check 10-1 =9 is in hastable, if no than add 1 in table                    1,0                    

check 10-3 = 7 is in a hashtable if no then add 3 in table               3,1

check 10-6 = 4 is in the hash table if no then add 6 in table           6,2

check 10-8 = 2 is in the hash table if no then add 8 in table           8,3

check 10-2 = 8 is in the hashtable, if yes then return i and value of key 8 from a table.

i.e index of 2 is 4 and  index of 8 is 3 so return [3,4]

Remember: If there are any duplicate numbers than do not add in the hash table as it will not support.
*If the problem would have been to find only pairs, not their position than we could have used the only hash set instead of the hash table.

Time Complexity: O(n)
Space Complexity: O(n)

Implementation :

public int[] TwoSum(int[] nums, int target)
        {
            int[] result = new int[2]{-1, -1};
            var map = new Dictionary<int, int>();
            for (int i = 0; i < nums.Count(); i++)
            {
                if (map.ContainsKey(target - nums[i]))
                {
                    result[1] = i;
                    result[0] = map[(target - nums[i])];
                    return result;
                }
                if(!map.ContainsKey(nums[i])) // add only if its not present
                map.Add(nums[i], i);
            }
           return result;
        }

    

Creating and Deploying .Net core application in Windows/Linux/Mac

 Hello friends, I have just learned .Net Core last week and created a Web API application in windows and deployed the same as standalone in windows, ubuntu, and Mac. It worked without any issue on all three platforms, so I thought of writing my first blog on creating a simple Web API application using dotnet CLI(Command-Line Interface) and visual studio in windows and deploying them on all other platforms.

Let's get started........

Creating a sample WEB API project:

First, we will install .net core 2.0.0 in our windows system
Go to link: https://www.microsoft.com/net/core 
Download .Net Core SDK for windows and install by executing the dotnet-SDK-2.0.0(downloaded file name)
Now check if it's installed with version 2.0.0 by running command “dotnet –version” in cmd.

Check dotnet core version

We can create dotnet core application using dotnet core cli, visual studio code or visual studio

To create sample Web API project using dotnet core CLI:

1.Open a command prompt and create a folder name which you want to be your application name and move to that folder directory using below commands.

    D:\  mkdir SampleWebApi

    D:\ cd SampleWebApi

    D:\SampleWebApi\

2. Now create project using command: dotnet new webapi

      

Navigate to the folder to verify the project got created.

Congrats.....Your sample web api got created using dotnet cli.

new: it is used to create a new project

webapi: it is the template for creating sample web api project

To know detail about different template use command  dotnet new help

You can also create an empty project and implement web API controller.

Running the application :

Restore package: dotnet restore

Build:    dotnet build

Run:  dotnet run

You can directly type dotnet run to build and run the application.

The application started and listening on default port 5000.

Here application is using default web server called Kestrel of Asp.NET Core.

Kestrel is a cross-platform web server for ASP.NET Core based on libuv, a cross-platform asynchronous I/O library. Kestrel is the web server that is included by default in ASP.NET Core project templates.

For more detail on Kestrel go to https://docs.microsoft.com/en-us/aspnet/core/fundamentals/servers/kestrel?tabs=aspnetcore2x

Let's create the same using visual studio 2017 :

1.Open visual studio 2017

2.File->New Project

3.Select Asp.Net Core Web Application under.Net Core project templates.

4.Give a project and solution name say SampleWebApi

5. Select WebApi as the project type and click Ok.

Congrats...project got created.

Running the application using visual studio :

First, rebuild the solution by right clicking on solution and click Rebuild Solution.

Running the Application:

1. You can click on Run button with the IISExpress option selected.

It is the lightweight version of IIS used by developers to develop and test application.

More detail : https://docs.microsoft.com/en-us/iis/extensions/introduction-to-iis-express/iis-express-overview

2. You can also run on kestrel webserver just by changing from IIS express to the application name from dropdown tool next to start button.

Now you can test your api from browser or postman: http://localhost:5000/api/values

The default port is 5000 for the kestrel. IIS express may run on a different port or you can change the port if you want.

Modify the Program.cs to use specific url by adding   .UseUrls("http://localhost:5001")

public static IWebHost BuildWebHost(string[] args) =>

            WebHost.CreateDefaultBuilder(args)

                .UseStartup<Startup>()

                .UseUrls("http://localhost:5001")

                .Build();

There are other ways to too like passing using command line arguments or creating a hosting.json.

and setting the content as

{

"server": "Microsoft.AspNetCore.Server.Kestrel",

"server.urls": "http://localhost:5050"

}

For details please visit: https://github.com/aspnet/KestrelHttpServer/issues/639

Till now we have created and run sample application using dotnet core Cli and Visual Studio 2017.

Let's Start with Deployment.....

Framework Dependent Deployment:

Framework dependent deployment relies on the presence of .NET Core on the target system.

Your application which you want to deploy will only contain its own code and third-party libraries which are not part of .NET Core libraries. It included.dll files which can be launched using dotnet utility command.

E.g dotnet SampleWebApi.dll

Publishing the application using dotnet cli

Debug mode :

D:\SampleWebApi> dotnet publish

Release mode:

D:\SampleWebApi> dotnet publish -c release

You can also specify output folder

D:\SampleWebApi> dotnet publish -o "D:\publish" -c release

Now navigate to specific folder where your app is published, and copy the folder to the target machine where you want to run say Linux, windows, ubuntu.

Run the application by typing below given command using cmd or bash

dotnet SampleWebApi.dll

Publish the application using Visual Studio

1. Right-click the project and click on publish

2. Create a publish profile and select the publish output folder destination for your app.

3. Click on publish button.

Your app is published successfully.

Now you can copy the publish output folder and move the target machine where you want to deploy.

This deployment requires.Net Core installed on target machine.

Now navigate to the folder using cmd or bash and run dotnet SampleWebApi.dll

Self-Contained Deployment:

Self-Contained deployment does not rely on the presence of .NET Core library on the target system.

Your application will contain all components along with.Net Core libraries and runtime.

It includes an executable file with application name and .dll file.

To run the executable on windows simply double click the .exe, say SampleWebApi.exe

To create a standalone application first decide which target machine you want the app to run and then add the <RuntimeIdentifier> tag under <PropertyGroup> section of your .csproj file.

Please check the different runtime id for target machine in the below link.

https://docs.microsoft.com/en-us/dotnet/core/rid-catalog

Edit your application .csproj and add the below  <RuntimeIdentifier> to target windows 10,

Mac Os and Ubuntu 14.04

 <PropertyGroup>
    <RuntimeIdentifiers>win10-x64;osx.10.11-x64,ubuntu.14.04-x64</RuntimeIdentifiers>
  </PropertyGroup>

After that run the below command to build an application for each target machine.

dotnet publish -c Release -r win10-x64 for windows 10 platform

dotnet publish -c Release -r ubuntu.14.04 for Ubuntu 14.04

dotnet publish -c Release -r osx.10.10-x64 for Mac Os

This creates the Release version of your app for each target platform. The resulting files are placed in a subdirectory named publish that's in a subdirectory of your project's .\bin\Release\netcoreapp2.0 <runtime_identifier> subdirectory. Note that each subdirectory contains the complete set of files (both your app files and all .NET Core files) needed to launch your app.

Publish using Visual Studio 2017:

1. First add the above <RuntimeIdentifiers> in .csproj and build the application

2. Right click the solution and click on publish. Create a publish profile if not created.

3. Click settings link.
4. Go to settings tab and choose the target machine and click on save.

5. Now the application got published to the location you choose or default location

\SampleWebApi\bin\Release\netcoreapp2.0\win10-x64

Running application without .NET Core installed: 

Windows :

Double-click the executable file which got created say SampleWebApi.exe in publish folder of win10-x64 runtime folder.

Ubuntu :

Copy the file to Ubuntu machine.

First, give the file or folder executable permission using command chmod +x file

Than run using ./file

E.g:  chmod +x SampleWebApi    (file in the Ubuntu.14.04 publish folder)

       ./SampleWebApi

The application will start running

If you get an error saying: libunwind.so.8: cannot open shared object file: No such file or directory. Please install libunwind8 using below command and again run.

sudo apt-get install libunwind8

Mac OSX:

First, give the file or folder executable permission using command chmod +x file
Than run using ./file

E.g:  chmod +x SampleWebApi    (file in the osx.10.10-x64 publish folder)
       ./SampleWebApi

The application will start running.

 Hope you all will be able to create sample WebApi application and deploy the same in different platform using dotnet core. If you find any difficulties please feel free to comment and I will try to resolve.

Here is the download link for source code :