Tag: Algorithm

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

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

martinstanik.com

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 or 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 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. For the first one (for), I am trying to find a non-zero value in each iteration, copy the value from the current index to the Pivot index, and increment Pivot at the end of the cycle. If zero is found, the Pivot index value remains and the loop goes on to the next item. If a non-zero value is found again, the value at the current index gets copied over to the Pivot index (zero value) and the Pivot index value gets incremented by 1.

The second loop (while) is going to add zero values at all indexes between the 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 a 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 of what stands between choosing you over other tens/hundreds of candidates applying for the same role as you do.

Wishing you good luck and let me know in the 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 on what to look at before going to a technical interview

Thanks for staying, subscribe to my blog, and leave me a comment below.

cheers\