Tuesday, April 17, 2018

A bit different solution for 3SUM problem

The 3SUM problem asks if a given set of n real numbers contains three elements that sum to zero.

It is a bit different solution comparing to known ones, time complexity is O(k2 + m2) where k + m <= n; what actually is the same as O(n2) but the solution is rather fast (beats 92.97% C# solutions on LeetCode).

The solution is based on the idea that in order to get zero sum we need at least one positive and one negative number. We can split the input into 2 sets, for positive and negative numbers. Zeros affect the output in the following way: 1 zero gives ability to combine triplets of positive number + negative number + zero; 3 and more zeros gives one additional result: a triplet consisting of zeros only. 


using System;
using System.Collections.Generic;

class Solution
{
    public IList<IList<int>> ThreeSum(int[] nums)
    {
        var result = new List<IList<int>>();

        int negativeEnd = -1;
        int positiveStart = -1;

        Array.Sort(nums);

        //hash containing negative numbers
        var negativeHash = new HashSet<int>();
        //hash containing positive numbers
        var positiveHash = new HashSet<int>();

        for (int i = 0; i < nums.Length; i++)
        {
            var item = nums[i];
            if (item > 0)
            {
                if (positiveStart == -1)
                {
                    positiveStart = i;

                    for (; i < nums.Length; i++)
                        positiveHash.Add(nums[i]);
                }
            }
            else if (item < 0)
            {
                negativeEnd = i;
                negativeHash.Add(item);
            }
        }

        var zerosCount = (positiveStart != -1 ? positiveStart : nums.Length) - negativeEnd - 1;
        //check if the result completed from zeros only is possible 
        if (zerosCount > 2)
            result.Add(new[] { 0, 0, 0 });

        //if either negative or positive numbers are absent is it not possible to create any combinations
        if (negativeEnd == -1 || positiveStart == -1)
            return result;

        //check if sum of 2 negative numbers has complementary positive number  
        CheckThree(ref nums, 0, negativeEnd, ref positiveHash, ref result);

        //check if sum of 2 positive numbers has complementary negative number
        CheckThree(ref nums, positiveStart, nums.Length - 1, ref negativeHash, ref result);

        //check if there are pairs of complementary negative and positive numbers 
        if (zerosCount > 0)
            CheckTwo(ref positiveHash, ref negativeHash, ref result);

        return result;
    }

    private void CheckTwo(ref HashSet<int> positiveHash, ref HashSet<int> negativeHash, ref List<IList<int>> result)
    {
        foreach (var item in positiveHash)
        {
            var checkedItem = -item;
            if (negativeHash.Contains(checkedItem))
                result.Add(new[] { item, 0, checkedItem });
        }
    }

    private void CheckThree(ref int[] nums, int start, int end, ref HashSet<int> opposite, ref List<IList<int>> result)
    {
        for (var i = start; i < end; i++)
        {
            var a = nums[i];
            if (i == start || a != nums[i - 1])
            {
                var jStart = i + 1;
                for (var j = jStart; j <= end; j++)
                {
                    var b = nums[j];
                    if (j == jStart || b != nums[j - 1])
                    {
                        var c = -a - b;

                        if (opposite.Contains(c))
                        {
                            result.Add(new[] { a, b, c });
                        }
                    }
                }
            }
        }
    }

}

Thursday, October 12, 2017

JSON Viewer: JSONPath Expressions Evaluation


Added a new feature to JSON Viewer extension: evaluation of JSONPath expressions.



The source code: https://github.com/marss19/json-viewer-visual-studio-extension
The latest release in Visual Studio Marketplace: https://marketplace.visualstudio.com/items?itemName=MykolaTarasyuk.JSONViewer
 

Sunday, May 28, 2017

Reference Conflicts Analyzer - Visual Studio Extension

This is an extension to Visual Studio for easy visual analysis of the "Could not load file or assembly or one of its dependencies" problem and issues related to referenced assemblies. The tool allows selecting a .Net assembly (.dll or .exe file) and get a graph of all referenced assemblies with hightlighted conflicting references.

Source code: https://github.com/marss19/reference-conflicts-analyzer
Download: https://marketplace.visualstudio.com/vsgallery/051172f3-4b30-4bbc-8da6-d55f70402734

Documentation

After installation, it is available in the main menu: Tools -> Analyze Assembly Dependencies.

Screenshot 1. Tool settings

Assembly to analyse: .Net DLL or EXE file which dependencies should be analysed.
Related config file: .exe.config for EXE file or web.config in case a web application DLL is selected. The extension inserts the related config automatically after the assembly is selected but it is also possible to select it manually.
Ignore system assemblies: by default the tool ignores assemblies which names start with "System..." to keep the graph clear.

Screenshot 2. Example of output


Thursday, March 2, 2017

Search for Movies and TV-series from the Chrome Context Menu

I noticed that sometimes, having a free evening and wishing to spend it watching a movie, I spent a lot of time selecting this movie, checking online movie databases for ratings, reviews, etc. As it was rather unproductive wasting of the time I created a simple Chrome extension helping to do the search easier and faster.

The extension adds context menu items executing search for a selected text (movie name).

There are also lots of sites which web masters overcomplicated them with scripts and CSS and made a simple selection of text quite a tricky thing. For these particular cases it is also possible to search without selection; for a focused text at cursor.

The extension is configurable: you can select preferable online movies databases.

Link:  https://chrome.google.com/webstore/detail/movies-tv-series-search/miploifkaagebhdlcdaaomgnenchiocf?hl=en&gl=PL

Preview:

Wednesday, April 27, 2016

Caching HTTP Handlers

There comes a time in an ASP.Net developer's life when he must write own HTTP handler. Quite often the handler has to return a static or a rarely changable content and the developer should implement caching of it.

Step 1. Specify how long data should retain cached.

Someone does it this way:

  context.Response.Cache.SetExpires(DateTime.Now.AddDay(1));

Someone likes this approach:

  context.Response.Cache.SetMaxAge(86400); //1 day in seconds

The most careful developers use both:

  context.Response.Cache.SetExpires(DateTime.Now.AddDay(1));
  context.Response.Cache.SetMaxAge(86400);

All the above are correct in their own way. The first example sets an absolute expiration date. In the list of headers it looks like this:

Expires: Mon, 25 Jul 2016 19:50:09 GMT
This header was introduced in the HTTP/1.0 specification but it is supported by HTTP/1.1 too. A small pitfall related to this header is that the expiration date and time are set explicitly and it may cause issues if time at an application server and proxy servers differ.

In order to fix the above issue a new header was introduced in HTTP/1.1: max-age. It specifies expiration time relatively to response time, i.e. an interval, in seconds, after elapsing it cached data are considered stale (expired).

Cache-Control: max-age=86400
In case both headers are set max-age has priority even if an Expires value is more restrictive.

At this stage many developers consider their work done and switch to other tasks. However...

Step 2. Define where to store cached content.

Let's run a HTTP trafic analyser, e.g. FireBug and look how our cached resource is loaded. Quite often we can notice that the resource is loaded again and again on each refresh with the 200(OK) status but without the (from cache) remark. Look at this header:

Cache-Control: private, max-age=86400
Private means that data can be cached by browsers only and cannot be cached at servers. Assuming that the browser cache is limited (e.g. the default size of the cache of Firefox is 50 MB) a browser you use may decide that letting a web site to occupy too much space is not the best idea and purge cached data. So if cached data are not "user sensitive" it makes sense to store them on servers.
context.Response.Cache.SetCacheability(HttpCacheability.Public);
More sophisticated options are described here: HttpCacheability Enumeration

At this stage even more developers conclude that their work done and switch to other tasks. However...

Step 3. Handle renewval of cached data.

Let's consider the following cases:

  • Proxy servers are overloaded and remove entries from the cache from time to time;
  • Cached entries are expired but still are not changed.
As a result the cached entries will be retrieved from the application server; this will increase traffic and reduce perfomance.

A proper approach is to avoid loading all data but just to return a response with 304 (Not changed) status. In order to do this set the Last Modified header:

context.Response.Cache.SetLastModified(new DateTime(2016, 4, 1));
which produces the output like this:
Last Modified: Fri Apr 1 2016 00:00:00 GMT
A server discovering that a cache entry is stale (expired) requests for a fresh copy of the entry and sends the If-Modified-Since header with the current date/time. We can handle this case and return a light-weight 304 response instead of sending the whole content.
var ifModifiedSinceHeader = context.Request.Headers["If-Modified-Since"];
if (!string.IsNullOrEmpty(ifModifiedSinceHeader))
{
    var ifModifiedSinceDate = DateTime.Parse(ifModifiedSinceHeader);
 
    if (/*cached data are not modified since this date*/)
    {
        context.Response.StatusCode = 304;
        context.Response.StatusDescription = "Not Modified";
        return;
    }
}
 
//otherwise return the normal response containing data and 
//do not forget about setting the Last Modified header...

Actually the above approach is basic one; it does not describe a lot of useful headers which can be used for tune adjustments of the caching process, e.g.: ETag, must-revalidate, etc.