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

Why every Software Developer should learn these 3 languages

We are living in a very fast and dynamic world now. The days when software developer could have just a narrow set of skillset are gone and in order to “do good” on the market, everyone must adopt.

It does not have to be a radial adaptation process (phew!) but having a reasonable good knowledge about certain development languages, patterns, frameworks and “way of doing stuff” ala trends is the must.

That is why YOU as a software developer should know these languages at least an intermediate level to be able to code some basics without googling.

Alright, enough of initial sauce of words, let’s get into these three languages according to 2020 Dev survey.

Must languages to learn

Python

1. Believe it or not, the best option for you is Python. I am not going to write what this language is in detail but in brief, this interpreted and high-level and generic-purpose language has become integrated into almost any type of solution you can think of (cross-platform). Well, that is not surprising to me as been with us for almost 3 decades now (1991). What is more interesting in it is the actual philosophy which stands on these points:

  • Beautiful is better than ugly
  • Explicit is better than implicit
  • Simple is better than complex
  • Complex is better than complicated
  • Readability counts

You can read more about the language here https://en.wikipedia.org/wiki/Python_(programming_language)
You can get yourself quickly into it by looking at this repo (my recommendation) https://github.com/microsoft/c9-python-getting-started

JavaScript

2. Honestly, I am surprised that JavaScript made it to second place (and not to the top). I personally think that this multiparadigm language has a lot of potential for the future and so every developer should learn it.

Read more about JavaScript here https://en.wikipedia.org/wiki/JavaScript
My recommendation howto get started is to follow this sites:
* https://developer.mozilla.org/en-US/docs/Learn/Getting_started_with_the_web/JavaScript_basics
* https://www.w3schools.com/js/

Go (Golang)

3. And probably my favourite one over these two is Go (Golang). Not because of my experience (just started to learn this) but because of what is capable of in very short time (hey I am C# dev, I know what I am talking about!). This would not be my surprise if Go makes its way to the top of the ladder in the next 3 years.

Read more about it here https://golang.org/
And after that go and install Go on your desktop, and hit this page of how to get started https://golang.org/doc/tutorial/getting-started

Used data source

Survey conducted by 65k of tech geeks


For more information have a look at this page https://insights.stackoverflow.com/survey/2020#technology-most-loved-dreaded-and-wanted-languages-wanted

Just remember, that data has been collected from an active society contributing to Stackoverflow. That means that these results do not EXACTLY reflect the market situation globally nor in your region. Always do your homework and look at the different data sources, related to the place you live (and going to be for the next 5 years).

New Zealenders this does not apply for you. You cannot go wrong with these three ones. Just for reference, NZ based company Rocket Lab is constatly hiring Software Engineers with Golang experience https://www.rocketlabusa.com/careers/positions/.

Overall Stackoverflow survey rating

  • it’s great to have an actual IT pros attending in this survey
  • Stack overflow holds a big audience
  • in my opinion, data were collected from younger generation as oppose to older and so segregated datasets might not be in required balance for reports
3/5 Rambo rating

How much ACR (Azure Container Registry) costs?

Well, believe it or not, this Azure service has no free subscription. The ‘cheapest’ one is about $0.252/day with total of 10 GiB of storage and 2 Web hooks. Unfortunatelly, with no support for Geo replication.

As pricing can change over the time, this site should give you the most up-to-date details: https://azure.microsoft.com/en-us/pricing/details/container-registry/

_BASICSTANDARDPREMIUM
Price per day$0.252$1.008$2.520
Included storage (GiB)10100500
Premium offers enhanced throughput for docker pulls across multiple, concurrent nodes
Total web hooks210500
Geo ReplicationNot SupportedNot SupportedSupported
$2.520 per replicated region
Azure Container Registery pricing

Do I like ACR?

Yes and no …

For a big projects in size, where the biggest proportion of the solution services is getting provisioned in Azure – Yes, definetely. The level of convinience of having ‘everything’ (source code, tool-set, hosting environment, …) in one place plays a big role in here. The assumption is that if Devs/DevOps are happy with tool-set within the same platform, the overall progress on the project should be faster as there is no need for an extra work for system integration and shaping diametrically different skill set (theory but works in many cases).

And for the projects hungry for disk space and tight to budget – No. There are cheaper alternatives on the market, for example Docker.com (with one private repository in Free plan – whoop, whoop!). Pricing starts as low as USD $5/month (with annual plan) which is insanely CHEAP! So if Azure is not your dime in solution, Docker.com wold be my choice to pick.

More details about Docker pricing (and most updated) can be found here: https://www.docker.com/pricing

Docker pricing and subscriptions
Docker pricing and subscriptions

Overall rating of this technology

5/5 Rambos

Committing and Pushing Docker image changes to Azure Container Registry

Docker image

If you made it this far, then you must know something about the Docker (Containerization). That is great because this post is not about what Docker really is but how to work with image revisions in conjunction with the Azure Container Registry (aka repo).

I am assuming you have your own repository in Azure created already and know the basic commands of how to spin up the container (or leave the comments below).

Also that a Docker desktop is installed on your PC and has docker image ready to be used for this exercise.

User story

You as a developer want to create a starting (based) image out of the running container on your localhost (image type regardless of this exercise) for your co-workers. Image is going to be parked in ACR for easy access. The initial version is going to have a tag ‘v1’.

Steps to follow

1. Download MS Azure Command Prompt, the latest version can be found here or just use google search


2. Validate that installation has been succesful by starting the MS Azure Promp and run

az --version
If you see this, then you did well!


3. Log in to Azure by using this command below (you should be redirected onto the browser app with portal.azure.com as URL. Now, use your user credentials and wait for callback redirect back to the terminal (MS ACP)

az acr login --name <your ACR name> 

Example:

az acr login --name webcommerce22


4. Commit the latest changes on the top of running docker container (docker desktop) with tag v1 (this operation creates a new image). Remember that only these characters are allowed in naming ‘a-z0-9-_.’

docker commit <docker container hash id> <repository URL>[/<new image name>][:<tag name>]

Example:

docker commit 2cbbb6f54f4b webcommerce22.azurecr.io/web-api-pricing:v1
The created new image out of running container


5. Push the changes to ACR

docker push <repository URL>[/<image name>][:<tag id>]

Example:

docker push webcommerce22.azurecr.io/web-api-pricing:v1
Pushing image to Azure Container Registery
New container repository is created with v1 image in it


And here you are. Great way how to keep your changes over the container image revisioned.

For more details about the docker commands, I can recommend to follow this URL https://docs.docker.com/engine/reference/commandline/docker/

Overall feature rating

5/5 Rambo rating