Programming Interview

The most asked coding interview - #5

Transform array such that each element contains the greatest element on its right side Problem statement In this article we will be discussing how to solve an easy problem that has been asked at Amazon coding interviews. This is a must do problem for your coding interview preparation. The problem statement goes as follows: You are given an array A of size N. You have to modify A in place s.t. A[i] = M where M is the maximum value among all elements A[j], j > i. If such element does not exists set A[i] = -1. Example Solution Since this is a quite easy… Read More »The most asked coding interview - #5

The most asked coding interview - #4

Return the Maximum absolute difference of values and indices

In this article we will be discussing one of the most asked coding interview question asked at Amazon.
The problem statement goes as follows:

Problem statement

Given an array A determine the maximum possible value of the following expression:
$f(i,j) =| A[i]-A[j] | +|i-j|$

Example

Input : A = {1, 3, -1} 
Output : 5
because the maximum value obtainable is:
=> f(1,2) = |3 - (-1)| + |1-2| = 5
Input : A={3, -2, 5, -4}
Output : 10
=> f(1, 4) = f(4, 1) = |3 - (-4)| + |1 - 4| = 10
Note that in this case we can also obtain 10 from
=> f(3, 4) = f(4, 3) = |5 - (-4)| + |3 - 4| = 10
Read More »The most asked coding interview - #4

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… Read More »The most asked programming interview questions - #3

The most asked coding interview - #2

Coding interview question: Determine if number is an Armstrong number

Problem statement

In this article we will be discussing another (see the previous article counting triples with a given sum) of the most common coding interview questions. The problem statement is really simple and goes as follows:

Given an positive integer N determine if it is an Armstrong number?
A number $x_1x_2…x_n$ (1 \leq x_i \leq 9 $ is a digit ) of length $n$ is an Armstrong number if the following is true:
$x_nx_{n-1}…x_2x_1 = pow(x_1,n) + pow(x_2,n) + … pow(x_n,n)$

In other words if raising all digits to power $n$ and sum all them up you obtain the original number, then $N$ is an Armstrong number.

Read More »The most asked coding interview - #2

The 10most asked coding interview at Google - #1

Coding interview at google

Problem statement

In this article we will be discussing one of the most common coding interview question asked in many google interviews, especially during one of the first stages. The problem statement goes as follows:

Given an array N of distinct integers and a integer K, print on the standard output the number of triples (N[i], N[j], N[l]) whose sum is equal to K. In other words how many triples(i,j,k), i < j < k s.t. N[i] + N[j] + N[l] = K are in N?

Read More »The 10most asked coding interview at Google - #1

Modern C++ concurrency - parallel quick-sort with std::future

In this short lesson we will discuss how to parallelize a simple and rather inefficient (because this is not an in-place version) implementation of quick-sort using asynchronous tasks and futures. We will perform some benchmarking and performance analysis and we will try to understand how we can further improve our implementation. Quick sort In this section, I will briefly refresh your memory on quick-sort. I will do so by showing you a simple and self-explicative Haskell version first. We will also write a C++ (serial) version of the same code implementation C++ that we will use as a basis for our parallelization. Here it goes… Read More »Modern C++ concurrency - parallel quick-sort with std::future

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 More »Modern C++ concurrency - Returning values from Threads - std::future

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 More »Modern C++ Concurrency - Synchronizing threads - Condition Variables

Solution to the Codility Common Prime divisors Set Problem

This article discusses (a problem that I recently solved on codility ).

The core of the problem is the following:
Given two non negative integers N and M, 1 \leq M \leq N \leq 2147483647, the task is to check whether they have the same set of prime divisors.
A prime divisor of an integer P is a prime d s.t. d \times k = P for some positive k. You are given up to 6 \times 10^3 of such queries, and should return the total number of them that evaluates to true.

For instance given if N = 156 and M = 78 then our function should return *true* because the set of prime divisor of N is equal the
the set of primal divisor of M i.e. \{2,13,3\} while for N=45 and M=120 the function should return *false*.

Read More »Solution to the Codility Common Prime divisors Set Problem

Tree Vertex Cover Problem

Weighted Tree Vertex Cover Problem

Vertex cover of graph is defined as s.t. . In other word a subset of the vertices such that all vertices are incident to a vertex in the vertex cover.
We will derive an algorithm for finding the weight of a minimal (yes is not unique) vertex cover for a subclass of graphs i.e. tree (which are acyclic graphs with the property that only one path between each vertex exists).

Remember that vertex cover for graphs is an NP-Complete (NP-hard and NP, hard at least as all NP problems and it is an NP problem itself) problem i.e. no deterministic polynomial tyme algorithm was discovered (if you discover one, contact me, we will be millionaire).

Tree Vertex Cover - Problem Definition

Given a weighted tree with write an algorithm for computing a vertex cover with minimum weight i.e. V' is a vertex cover and the sum of the weight of its element is minimal.

The following is the tree structure that we will use throughout the article.

template<typename T,int DEGREE>
struct node{
       array<node*,DEGREE> children;

       T data;
       int weight;

        node(const T& v , int _weight) : weight(_weight){
               data=v;
               mincover=0;
       }
};

What if the weight is equal to the degree of the node?

The first observation we can make is that the root node can weather be or not be in the vertex cover. If we include it in the solution then we are sure that all the edges from it to its children have been covered and to solve the problem we need only to compute the cover of its children (which is a simpler problem).Read More »Tree Vertex Cover Problem