Category Archives: Computer science

House painting problem

The question

There are a row of houses, each house can be painted with one of three colors red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color. You have to paint the houses with minimum cost. How would you do it?

Note: Painting house-1 with red costs different from painting house-2 with red. The costs are different for each house and each color.

Read more »

Add one to a number without using plus or minus sign

I got asked this question in a code interview and I wanted to make sure my answer was good. Without the pressure of being in an interview I see the problem more clearly and the problem seems pretty easy now.

Lets look at the basics of adding in binary:

1
2
3
4
 0         1       1
+0        +0      +1
---       ---     ---
 0         1      10

Read more »

Maximum length palindromic subsequence

Given a sequence of characters, find the longest palindromic sub-sequence. A sub-sequence is any sequence that can be formed by removing 0 or more characters from the given sequence. For example, the possible sub-sequences for ABC are:

1
2
3
4
5
6
7
8
9
10
ABC
BC
C
B
AC
C
A
AB
B
A

Read more »

The Fibonacci sequence

The Fibonacci sequence is a sequence of numbers starting with 0 and 1 and then adding the sum of the two last numbers at the end of the sequence:

1
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

The mathematical representation of the Fibonacci sequence is:

1
F(n) = F(n-1) + F(n-2)

Read more »

Unique paths

A robot is located at the top-left corner of a m x n grid (marked ‘S’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘F’ in the diagram below). How many possible unique paths are there?

1
2
3
4
5
6
7
+---+---+---+---+---+---+---+
| S |   |   |   |   |   |   |
+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+
|   |   |   |   |   |   | F |
+---+---+---+---+---+---+---+

The first idea that came to my mind after seeing this problem was to find all the combinations for two movements down and six movements to the right(>>>>>>vv). I couldn’t remember of the top of my head the formula but after a little playing with pen and paper it came back to me. The formula is:

Read more »

Binary search

I was just going through the basics and I wanted to verify that I still knew how to do a binary search. If I remember correctly these are the steps:

– Set a left pointer at the beginning of the sorted array
– Set a right pointer at the end of the sorted array
– Calculate the middle between those two pointers(If there is no exact middle, truncate the number) and set the a middle pointer there
– Check if the middle is the number you are looking for. If it is return
– If the element at middle is greater than the element you are looking for set the left pointer to middle + 1
– If the element at middle is lower than the element you are looking for set the right pointer to middle – 1
– Repeat until the number is found or left is greater than right (not found)

Read more »

JavaScript Numbers

The title for this post might sound vague, but the reason I’m writing it is because in JavaScript this is true:

1
(.1 + .2) !== .3;

This makes my head explode so I want to understand better the reason for this.

IEEE 754

It turns out that JavaScript only has one number type, unlike other programming languages that have many types(int, long, float, etc…). The type JavaScript uses is defined by the IEEE 754 standard for floating point numbers. This format is good because many hardware manufacturers ship they chips with support for this standard which makes operations on these numbers really fast.
Read more »

Median of Integer Stream

The question

Given a stream of unsorted integers, find the median element in sorted order at any given time. So, we will be receiving a continuous stream of numbers in some random order and we don’t know the stream length in advance. Write a function that finds the median of the already received numbers efficiently at any time. We will be asked to find the median multiple times. Just to recall, median is the middle element in an odd length sorted array, and in the even case it’s the average of the middle elements.

Read more »

Search Unknown Length Array

The question

Given a sorted array of unknown length and a number to search for, return the index of the number in the array. Accessing an element out of bounds throws exception. If the number occurs multiple times, return the index of any occurrence. If it isn’t present, return -1.

My answer

Reading the question there is one question that came to my mind: Can the exception be handled?. Assuming that it can’t I think the only alternative would be to check all elements starting from the first one. I will assume the exception can be handled so I can come with a better solution.

Read more »

Kth Largest Element in Array

The question

Given an array of integers find the kth element in the sorted order (not the kth distinct element). So, if the array is [3, 1, 2, 1, 4] and k is 3 then the result is 2, because it’s the 3rd element in sorted order (but the 3rd distinct element is 3).

My solution

This doesn’t sound as a very hard problem but I couldn’t find a solution better than:

– Sort using quicksort
– Return the element at index k

The complexity of this solution is the complexity of quicksort O(nlogn).

Read more »