Archive for the ‘Easy’ Category

The most asked programming interview questions - #3

Sort an array of size N made of numbers from 0 to K

Problem statement

In this article we will be discussing another (see the previous article) very popular programming interview question. This time we are asked to sort an array of size N whose elements are in the range [0,K).

Problem statement

Given an array $A=[a_1,a_2,…a_n],\: 1 \leq a_i \leq K$
modify A s.t. it is sorted.

As usual you should ask your interviewer some clarifying questions. For example a sensible question to ask could be:

  • What is the maximum value of $K$ and of $N$? Let's assume that $N \leq 10^7$ and $K\leq 10^3$

Example

Input : A={1,8,9,66,2,1,45,12}
Output : A={1,1,2,8,9,12,45,66}

Solution

First start noticing that the question seems rather simple at first. After all all you are asked to do is to sort an array. This is an easy peasy task that can be accomplished in a one-liner in C++.

Simple sort solution

bool sort_range_K(vector<int>&amp; A)
{
  sort(begin(A), end(A));   
}

But at this point you should also notice that you are not using the information about the range of the elements, and this should make your eyebrows raise and make you think a bit harder. This means that there is a better way of solving this problem.
The complexity of the above code is of $O(n \times log_2(n))$

Linear time Solution

You might not be aware of this (and if you are not I highly encourage you to get familiar with the topic) that it is possible to achieve better asymptotic complexity for sorting than $O(n \times log_2(n))$.
If you know the range of the elements you are dealing with, sorting can be done in linear time using Counting sort.

The idea behind is really simple. For each number in the range [0,K) you count how many times it appears in the original array in an array F of size K.
W.r.t. to the example above for instance:

A={1,8,9,66,2,1,45,12}
F ={0,2,1,0,0,0,0,0,1,1,....}
  • F[0] = 0 because 0 appears 0 times in A
  • F[1] = 2 because 1 appears 2 times in A
  • $…$
  • F[9] = 2 because 9 appears 1 times in A

With that information we can easily produce the output array by putting all the zeros first, then the ones, and so on.

C++ code

The idea above can be coded as follows:

template<class T>
void sort_range_K(vector<T>&amp; A, const int K)
{
    vector<int> F(K,0);
    for(const auto&amp;x : A)
        F[x]++;

    int p = 0;
    for(int i = 0 ; i < K ; i++)
        for(int j = 0 ; j < F[i] ; j++)
            A[p++] = i;

}

The complexity of the code above is linear the length of $\Theta(A)$.
The space complexity is $\Theta(K)$
You can try the above code online on Wandbox.


Conclusions

In this article we discussed a common coding interview question asked by many tech companies. The takeaways from this exercise are:

  • If an information is provided in the problem statement, it needs to be used
  • If you know the range of the element you want to sort, you can sort them in linear time. The space complexity is linear in the biggest possible value an element of the array can take.

If you like this article check the previous article of the series (determine if a number is an Armstrong number).

Modern C++ concurrency - Returning values from Threads - std::future

Introduction

In this lesson we will talk about a way of returning values from threads, more precisely we will talk about std::future which is a mechanism that C++ offers in order to perform asynchronous tasks and query for the result in the future.
A future represents an asynchronous task, i.e. an operation that runs in parallel to the current thread and which the latter can wait (if it needs to) until the former is ready.
You can use a future all the time you need a thread to wait for a one-off event to happen. The thread can check the status of the asynchronous operation by periodically polling the future while still performing other tasks, or it can just wait for the future to become ready.

Read On…

Modern C++ Concurrency - Synchronizing threads - Condition Variables

Introduction

In the previous lesson we have seen how data can be protected using mutex. We now know how to make threads do their work concurrently without messing around with shared resources and data. But sometimes we need to synchronize their actions in time, meaning that we might want a thread t1 to wait until a certain condition is true before allowing it to continue its execution.

This lesson discusses the tools that we can use to achieve such behavior efficiently using condition variables.

Read On…

Programming Interview Question - String Permutation Test - C++

Programming Interview Question

Question: given two string write a method to decide if one is a permutation of the other.

This is a common question that could be easily solved if we know in advance which is the size of the alphabeth. A straightforward approach could be to sort both strings and then compare them. This approach has complexity due to sorting. We can do better and lower the complexity to  if we reason as follows: given a boolean sequence of the same size of the alphabet  initially false initialized.  Then what happen if  for each char we found in the  string we negate the value of the correnspoding bool in the sequence? We end up having the at position if the char appeared an odd number of times and otherwise. Now if the other string is a permutation of the first one, we all agree that for each char in it contains the same number of occurrences. This means that if we apply the same process as before on the boolean sequence using as input the string each bool is being negated an even number of times and this means that its value would be the same as the beginning of the process (all ). So if the sequence does not contains any true value, than it means that the strings contains the same elements i.e. they are permutation of each other.

Example:

  1. "abbccd" , "cbdabc" ,
  2. Apply negation using s
  3. Apply negation using v

 

A possible C++ implementation is shown here

Read On…

Programming Interview Question- Unique Characters in a string - C++

Programming Intervew Question: Unique Characters in a String

Question: implement an algorithm to determine if a string has all unique characters

The idea behing this (fairly easy) question is that whenever we found that any chars is repeated at least twice we should return false. In order to do that we have to look at each char we are loloking for a solution which complexity is at least O(n). We are free to use any support data structure. 256 is the size of the ASCII charset.

Read On…

Programming Question - Integer Parity

Programming Question: Given an integer, compute its parity(easy)
The parity of an integer is true iff number of set bits (1) is odd, false otherwise. Example: 1234_{10} = 010011010010_2 has 5 set bits and hence its parity is true.

 

Solutions:

Programming Question - 2D array spiral Fashion

Programming Question: given a 2D array, print it in spiral fashion (easy)

Given a 2D array print it in spiral fashion as shown in the picture.

Solution: