Immutable data types after .NET 5 release

Just couple weeks ago, Microsoft released RC of .NET 5 which is (unfortunately) not going to be an LTS (Long Term Support) release but on the other hand, it’s coming with some great features in it (yep yep).

One of them comes as a part of the new release of C# 9.0 (part of the .NET 5 release) which is Immutable Objects and Properties (records and init-only properties). Quite a smart concept in my opinion …

Recap on immutable data type

The immutable data type is basically data type of the variable of which the value cannot be changed after creation.

How does it look in reality?

Well, once immutable data typed object is created then only way how to change its value is to create a new one with a copied value of the previous instance.

What are the current immutable (and mostly used) data types from .NET CLR?

Primitive types

  • Byte and SByte
  • Int16 and UInt16
  • Int32 and UInt32
  • Int64 and UInt64
  • IntPtr
  • Single
  • Double
  • Decimal

Others

  • All enumeration types (enum, Enum)
  • All delegate types
  • DateTime, TimeSpan and DateTimeOffset
  • DBNull
  • Guid
  • Nullable
  • String
  • Tuple<T>
  • Uri
  • Version
  • Void
  • Lookup<TKey, TElement>

As you can see, we have quite a few to choose from already. How this list is going to look like after .NET 5 full release in November 2020?

Well, it’s going to be a revolutionary change in my 2 cents.

Principally, any object using .NET 5 runtime (and C# 9.0) can be immutable and also implement its own immutable state – and that is HOT feature.

The syntax of the immutable properties looks like in this example:

public class ObjectName
{
    public string FirstProperty { get; init; }
    public string SecondProperty { get; init; }
}

On the other hand, the syntax of immutable object (called a record) looks this:

public data class ObjectName
{
    public string FirstProperty { get; init; }
    public string SecondProperty { get; init; }
}

As you can see, the syntax is very clear and intuitive to use.

More details about new C# 9.0 features can be found here https://docs.microsoft.com/en-us/dotnet/csharp/whats-new/csharp-9#record-types.

What type of coding challenge to expect on technical interview with Google

It has been a while since being interviewed by Google and got to answer a lot of technical questions. The essence of being successful is to be prepared! Especially now, in these Covid-19 difficult times, when getting a job is even harder than before for young developers with no professional network nor working experience (hey, YOU are not alone in this!)

And so, I am writing this Post for you, the NEXT DEV GENERATION! But just to be clear, this post is not about to leak the hiring questions to the public. It is about to give YOU an idea of what sort of coding challenges you may get along the way.

The most given questions (and tricky ones) are how to efficiently solve the problems with the algorithm. You as a Dev must show understanding of what a time complexity is, how to work with data structures and how to write (and write less) readable code, and all of that while people on another side of the conference meeting are WATCHING! (feel the stress but stay CALM, stay COOL)

Remember that this task assignment was given to me a couple of years ago and don’t rely on getting exactly the same coding Task on your D-Day. The assignment will be different but the level of (solution) the complexity of the task is more likely going to be the same.

Coding challenge

Task assignment

You have a collection of numeric item values among which are numbers ‘0’. Build the algorithm which shifts all zeros to the end of the array with the best time complexity possible. You are not allowed to use any additional data structures in the solution. Also, keep the items at the same order as they are.

Design

Always do design first!

Normally, it is a good practice to ask as many questions as possible to clarify all the requirements at the beginning (these are all positive points). Some of them can be (not explicitly written ones in task description):

  • should my solution be structured as for production use?
  • do you want me to write a unit test, too?
  • can I use Google? – NOPE, don’t ask this one. All good companies usually structure the technical questions in the way that any (capable) candidate should be able to answer them. Don’t take it personally if failed, you are not just there yet.

Coding

The solution I have used was based on swapping the items within the array:

using System;

namespace TestApp
{
    class Program
    {
        static void Main(string[] args)
        {
            var array = new int[] { 1, 0, 4, 5, 0, 4, 5, 3, 0 };

            var iterations = 0;
           
            int j = 0;
            for (int i = 0; i < array.Length; i++)
            {
                ++iterations;
                if (array[i] != 0)
                {
                    array[j++] = array[i];
                }
            }

            while (j < array.Length)
            {
                ++iterations1;
                array[j++] = 0;
            }

            Console.WriteLine($"Array: '{string.Join(",", array)}'");
            Console.WriteLine($"Time complexity: O({iterations})"); 
            Console.ReadLine();
        }
    }
}

Let’s examine the code.

As you can see, I have two loops. By the first one (for), I am trying to find a non-zero value in each iteration, copy the value from the current index to Pivot index and incrementing Pivot at the end of the cycle. If zero is found, Pivot index value remains and the loop goes onto the next item. If a non-zero value is found again, the value at the current index gets copied over to Pivot index (zero value) and Pivot index value gets incremented by 1.

The second loop (while) is going to add zero values at all indexes between Pivot index value and the last array index (that many zeros have to be placed back to an array).

What is the time complexity of this solution? Let’s do an analysis of it.

First loop (for) goes over 9 items within an array. The array has 3 zero values (while loop). Total number of iterations is: 9 + 3 = 12 => O(12) => O(n)

Linear time complexity? THIS IS PRETTY GOOD TO ME! But do I want to gain an extra point (and I WANTED to) by building a slightly different approach with fewer loop iterations?

So, I asked Google Hiring Technical Manager whether I can compromise the last requirement and reorder the non-zero values in the array a little bit. He has agreed…

Why am I doing this?! The answer is optimization … As you can see, the while loop might not be a part of the solution (now) if going thru an array in a reverse way and swapping the zero-value items with the one sitting at the last (examined) array index:

using System;

namespace TestApp
{
    class Program
    {
        static void Main(string[] args)
        {
            var array = new int[] { 1, 0, 4, 5, 0, 4, 5, 3, 0 };

            var iterations = 0;

            var end = array.Length - 1;
            var index = end;
            for (int i = end; i >= 0; i--)
            {
                ++iterations;
                if (array[i] == 0)
                {
                    var left = array[index];
                    var right = array[i];

                    array[i] = left;
                    array[index--] = right;
                }
            }

            Console.WriteLine($"Array: '{string.Join(",", array)}'");
            Console.WriteLine($"Time complexity: O({iterations})");
            Console.ReadLine();
        }
    }
}

What is the time complexity now?

Algorithm is using one loop (for) and goes over 9 items within an array => O(9) => O(n)

Not a bad approach and another plus point going towards my credit bank (Yep, Yep!).

Conclusion

The second approach might not sound like huge performance achievement (and it is NOT for such a small dataset) but it shows the Technical Recruiter Manager your way of thinking! Remember, it can be only a good impression what stands between choosing you over another tens/hundreds of candidates applying for the same role as you do.

Wishing you good luck and let me know in comments below how the technical interview did go along!

You can download the code from my GitHub repo here: https://github.com/stenly311/Moving-Zero-Value-Items-To-The-End-Of-Array

Few tips what to look at before going to technical interview