Blog

Programming Interview Question - Merge Intervals (InterviewCake#4)

by Davide Spataro
2nd June 20163rd March 2019

Programming Interview Question - Merge Intervals

This post will explore the solutions to the question #4 of the famous website cakeinreview (here the link).

Programming Interview Question - Merge Intervals - Problem Statement

Given a list of pair of integers return a list of merged or condensed intervals.

Given for instance the following input list

$(0,1),(3,5),(4,8),(10,12),(9,10)$

your solution should return:

$(0,1),(3,8),(9,12)$

Your function should take care of corner cases like merging two intervals like the following $(0,1),(1,2)$ in $(0,2)$ . Give a $O(n^2)$ solution first. Then try to solve it in $O(nlog(n))$ .

Tower of Hanoi - C++

by Davide Spataro
27th May 20163rd March 2019

Tower of Hanoi - C++

This brief article is about the tower of Hanoi. Wrote this super simple C++ for a student and thought maybe it could be helpful.

It works on the idea that in order to move n disks from pile 1 to 3 we need to first move the first $n-1$ disks to a support pole (choosing the right on is part of the solution, see the code for further detail), then move disk $n$ in the correct position, and finally move the first $n-1$ disks from support pole to the correct location. Let the recursion does the magic!

The base case is when we have only one disk to move. Simply move the disk in the correct pile.

Tower of Hanoi - C++ Code

Construct a binary Tree from its inorder and preorder traversal

by Davide Spataro
19th May 20163rd March 2019

Construct a Binary Tree from its inorder and preorder

This article will investigate the problem of reconstructing a binary tree given its inorder and preorder traversal.

Let's say for instance that we have the following binary tree (see figure)

Binary Tree

which has the following in order and preorder traversal respectively.

$PRE = \{8,5,9,7,1,12,2,4,11,3\}$

$IN = \{9,5,1,7,2,12,8,3,11,4\}$

Given IN and PRE how can we construct the original tree?

The key idea is to observe that the first element in $PRE$ is the root of the tree and that the same element appears somewhere in $IN$ , let's say at position $k$ . This means that in order traversal has processed k element before to process the root, meaning that the number of nodes of the left tree of the root is $k$ . Obviously, if the first $k$ element belongs to the left subtree then all the others belongs to the right tree.

We will use this idea to write a recursive algorithm that builds the tree starting from its traversals. The algorithm works as follows:Read More »Construct a binary Tree from its inorder and preorder traversal

List Cycle Detection

by Davide Spataro
17th May 201612th March 2019

List Cycle Detection Linked list cycle detection problem is a very instructive and fun problem to reason about. This article will state the problem first and then explains how we can solve it efficiently while giving some insight on the underlying math. A list can gets corrupted and some node can be linked by more than one node, as in the following figure. This could lead to never ending traversal of the list. So it make sense to solve the following problem: List Cycle Detection - Problem Statement Given a linked list, detect if the list is circular i.e. contains a cycle Find the starting… Read More »List Cycle Detection

Dynamic Message of the Day - motd - Fedora Linux

by Davide Spataro
7th April 20163rd March 2019
2 Comments

HOW-TO: Dynamic Message of the day

This article is about setting up a dynamic message of the day (possibly informative and fun) as header of each newly opened shell.

The final result will be something like the following:

It mixes a fun message using fortune and cowsay which you can install using


sudo dnf install fortune-mod cowsay

utility and some informative info about the status of the system as:

System load
Ram and Swap available and used
Disk space
Ip address

The script file can be easily configured and extended to suits the your needs. Colors can also be easily customized.

Distributed Hadoop installation - Fedora Linux

by Davide Spataro
5th April 20166th April 2016

Distributed Hadoop and HBase installation - Fedora Linux

In this post I will describe how to get started with the latest versions of hadoop and hbase describing all the step to obtain a working hadoop installation. The steps described here can be easily used to perform a working installation on a large cluster (even tough it can requires additional steps as shared filesystem for instance).

Prerequisites

Java 1.7+ (you can use the instructions at the following link: http://tecadmin.net/install-java-8-on-centos-rhel-and-fedora/ )
SSH client/server

 sudo dnf install openssh openssh-askpass openssh-clients openssh-server

Don't forget to start the ssh service using the following command:

 sudo service sshd start

Add a dedicated Hadoop/HBase User (optional but reccomended)

Programming Interview Question - Set Row and Column if - C/C++

by Davide Spataro
17th March 201617th March 2016

Programming Inteview Question

Question: write an algorithm that take as input a matrix of type T and size , M, a value of type T, (v) and a unary predicate P.

Then if holds, the entire rows and column are set to .

For examples if the following is used as input matrix

4 9 14 19 24
3 8 13 18 23
2 7 12 17 22
1 6 11 16 21
0 5 10 15 20

using the following equality predicate (==3) (i.e. returns true if the passed parameter is 3) and the resulting matrix is:

-1 9 14 19 24
-1 -1 -1 -1 -1
-1 7 12 17 22
-1 6 11 16 21
-1 5 10 15 20

Hint use template for make the procedure as general as possible.

Programming Inteview Question Solution

Programming Inteview Question - Rotate Matrix - C/C++

by Davide Spataro
17th March 20163rd March 2019

Question: Given a square matrix of size M and type T, rotate the matrix by 90 degrees counterclockwise in place.

For example the algorithm should return the right matrix if is left one is passed as input.

0	1	2	3	4
5	6	7	8	9
10	11	12	13	14
15	16	17	18	19
20	21	22	23	24

4	9	14	19	24
3	8	13	18	23
2	7	12	17	22
1	6	11	16	21
0	5	10	15	20

Solution:

Programming Interview Question - String Permutation Test - C++

by Davide Spataro
16th March 201616th March 2016

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:

"abbccd" , "cbdabc" ,
Apply negation using s
Apply negation using v

A possible C++ implementation is shown here

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

by Davide Spataro
16th March 20163rd March 2019

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.