PROGRAMMING INTERVIEWS

I generally start with a very simple question with my interview candidates. I ask the for writing a program for giving the integer average of 2 integers using only integer type variables. Assume that input will always be with in integer limits.

The definition of integer average is the highest smaller integer if average is floating point number. Also the condition if that they can not use any typecasting or any datatype other than int.

Example:
a = 4, b = 5, avg = 4
a = 4, b = 6, avg = 5
a = -4, b = -6, avg = -5
a = 4, b = -5, avg = -1
a = -4, b = -5, avg = -5

95% of candidates smell some issues in this problem and when I say nothing is there they don't even ask any clarification and come up with something like this:

int get_average(int a, int b)
{
 return (a+b)/2;
}

Then I ask them to have a look if this is correct on definition and then they see that it is. But there test failed on very first floating point negative average. Then most of them do a quick fix and come up with something below:

int get_average(int a, int b)
{
 int sum = (a+b);
 if (sum < 0)
  return sum/2 - 1;
 return sum/2;
}

The above solution is obviously wrong if sum if a even negative number. I am disheartened to see why do these candidates just solve a test case and show the solution. They don't even care to run this with some examples.

On pointing this, most of them correct the code. Others face the rejection at this stage.

int get_average(int a, int b)
{
 int sum = (a+b);
 if (sum < 0 && sum%2 != 0)
  return sum/2 - 1;
 return sum/2;
}

Now I ask them to make it production worthy and taking care of boundary conditions. Many of them are not able to do so but some of them go through it for my second question.

Though I expect this problem to be concluded within 30 minutes depending of their experience but candidates do a lot of silly mistakes and stretch.

Lets see if you can code this correctly.

#include <iostream>
using namespace std;


int get_average (int a, int b)
{
 int a_half = a/2;
 int b_half = b/2;
 bool a_even = a%2==0? true:false;
 bool b_even = b%2==0? true:false;
 if (a>=0 && b>=0)
 {
  if (!a_even &&  !b_even)
   return a_half + b_half + 1;
  return a_half + b_half;
 }
 else if (a<0 && b<0)
 {
  if (a_even &&  b_even)
   return a_half + b_half;
  return a_half + b_half - 1;
 }
 else
 {
  int sum = a+b;
  if (sum < 0 && sum%2 != 0)
    return sum/2 - 1;
   return sum/2;
 }

}

int main()
{
 int n, a, b;
 cout << "number of test cases: ";
 cin >> n;
 for (int i=0; i<n; i++)
 {
  cout << endl << "Enter a and b: ";
  cin >> a >>b;
  cout << "average = " << get_average(a,b) << endl;
 }
}

Edit: We get a more efficient and concise solution in comments. Please go through it. 

Notably most of the solution for binary search are wrong because of above reason. This bug was fixed in Java SDK after 9 years. Please read more about it here.


Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.

Question:
Given a Tuple for eg. (a, b, c).
Output : (*, *, *), (*, *, c), (*, b, *), (*, b, c), (a, *, *), (a, *, c), (a, b, *), (a, b, c)

This question can also be asked as print all subsets of a given set.

Answer:
This looks that a character in the tuple can either be '*'' or itself. So we simply need to choose one character at a time, print combination on remaining substring and add them with '*' and earlier chosen character.

If we notice, it will be like below in reality:

This can be simply achieved by recursion. We just need to identify correct boundary conditions. Below is the code for the same. In this code, I have taken string in place of tuple but the logic stays same.

def pattern(prefix, input, len)
  # boundary condition
  if (prefix.length == len)
    puts prefix
    return
  end
 
  pattern(prefix+input[0], input[1..-1], len)
  pattern(prefix+'*', input[1..-1], len)
end

# for test, I took only abc, you can take the input as argument
input = "abc"
pattern("", input, input.length)

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.

Question: You are given a rod of length 'L' and an array of prices where price at each index is the price obtained by selling rod of length equal to that index. You need to find the maximum price, you can get by selling pieces of rod.

Note: Rod can be sold in as many pieces of integer length as you want. You may also sell the rod as a whole if that gets you maximum price.

Example: Lets say, there is rod of length 8 units with price array given below:

[0, 3, 7, 8, 9, 12, 13, 19, 20]

We have put 0 at 0th index to show price of length 0.

For this particular example, maximum selling price will be 28 by cutting the rod in 4 pieces of length 2.

Answer: How will you approach this problem?

Since we can cut the rod in pieces of any integer length, then we can start by thinking in a top-down fashion. First we will cut the rod in 2 pieces, which have maximum price of themselves. The cut should be in such a position that addition of prices for these 2 pieces obtain maximum selling price. Now we have to find the maximum prices of these 2 pieces by taking a piece at a time.

In this process, these 2 pieces can be of length L (original length of rod) and ZERO as well. Now we will repeat the process for these 2 pieces as well recursively until we get pieces of length 1 or ZERO.

find_maximum_price(L) = MAX(
                        for x in 0..L
                        find_maximum_price(x) + find_maximum_price(L-x)
                        )

But if we notice, there will be a lot of similar problem in order to solve all the problems for different length pieces of the rod. If we go bottom up, solve smaller problems first and save results for them, we can avoid solving same problem again and again. As many of you may get it by now, this is simple Dynamic Programming problem now. Where you solve for smaller problems, memoize results and solve actual problem using these results.

Code:
Below is the ruby code for the same. The logic is very simple. First iterate the rod length from 0 to L and save maximum selling price for each sub part in the result array. Once your result array is filled, return value for of result array for length L.

# @param [Array<Fixnum>] price Price array for rod
# @return [Fixnum] maximum selling price
def find_maximum_price(price)
  # initialize result array as 0 for price of rod length 0
  maxprice = [0]

  for i in 1..(price.length-1)
      maxprice[i] = price[i]
    for j in 0..i
      p = maxprice[j] + maxprice[i-j]
      if p > maxprice[i]
        maxprice[i] = p
      end
    end
  end
  return maxprice[-1] # return maxprice for length L
end

price = [0, 3, 7, 8, 9, 12, 17, 17, 20]  # input price array
puts "maximum price obtained = #{find_maximum_price(price)}"

Complexity: As we can see there are 2 loops, outer loop from 0 to L and intter from 0 to outer-loop-index. So the run time complexity is O(n²).

We can also find the length of rod pieces to obtain maximum selling price. I am leaving that part to readers.


Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.

Question: You are given 2 identical eggs such that eggs always break if dropped from floors above a particular floor of a 100-storey building. You need to find that particular floor in minimum number of egg droppings.

Answer: What would be the minimum number of drops in worst case if we have only one egg. We have to drop the egg from every floor starting from 1st floor up to 100^th. So in worst case scenario, number of droppings will be 100.

And What would be the minimum number of drops in worst case if we have infinite supply of eggs. In that case, we can follow a binary search approach; drop from 50^th floor, if broken drop from 25^th else from 75^th and so on. So in this case, minimum number of drops will be 7 (log₂100) in worst case.

Coming back to original problem of 2 eggs, we need to divide the floors in some blocks but will that be optimal. For example, if we divide building in 10 floor groups, drop from 10^th floor; if egg doesn't break then drop from 20^th else start from 1 to 9. Now if the egg breaks from 20^th floor, we need to check only for floors 11^th to 19^th. In worst case, there will be 19 drops for floor number 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 91, 92, 93, 94, 95, 96, 97, 98, 99.

If we want optimal results, we should divide the building such that for every additional drop, remaining max drop decreases by 1. If our starting floor for first egg is 'k', there are 2 cases:

The egg breaks:  In this case, total number of drops will be 1 + (k-1) i.e.  k as we have to drop from each floor from 1 to (k-1).

The egg doesn't break: In this case, we are remaining with (100-k) floors and for optimal performance, max number of drops should be k. Also we verified that the egg doesn't break till k floors, so we need to check floors (k+1) to 100. If we choose i^th floor for 2nd drop of first egg again and egg breaks here, then max droppings needed = 1 + (i-k) (1 for k^th floor in first attempt and (i-k) for (k+1)^st to i^th floor)

As we have discussed it should be equal to k.

k = 1 + (i-k)
i = 2k - 1

This means i^th floor is (k-1) floors above kth. So this tell us that every time, we need to go up by (f-1) floors, where f is floors went up in last drop.

This means that for minimum droppings, egg should be dropped after k floors, then (k-1) floors, then (k-2) floors and so on. The sum of this series should equal 100 and last entry in this series should be 1.

  k + (k-1) + (k-2) ... + 1 = 100
  k(k+1)/2 = 100
  k2 + k - 200 = 0;
  k2 + k + (0.5)2 = 200 + (0.5)2
  (k + 0.5)2 = 200.25
  k = 200.25 1/2 - 0.5
  k = 13.65

Since floor can not be in fraction, we need our first drop from 14t^thfloor then from (14 + 13 =) 27^th, then (27 + 12 =) 39^th and so on. Also for 2 eggs, maximum number of droppings will be 14.


How to solve for generalized case?
We can see that if we drop an egg form k^th floor, there are 2 possibilities:

egg breaks: then we have (k-1) floors and 1 less egg.
egg doesn't break: then we have (100-k) floors and same number of eggs.

We can apply this logic to any number of building and any number of floors.

Code:
A recursive solution is quite easy. If maxdrop(f, e) implies maximum drops with 'e' eggs for a 'f' floor building then:

maxdrop(F, E) = for k from 1..F minimum of
                            1 + MAX(
                                       maxdrop(F-k, E),         //if egg doesn't break
                                       maxdrop(k-1, E-1)       // if egg breaks
                                    )

but there will be many redundant calls while calculating this. So lets go for a dynamic programing approach and save previously calculated maxdrop(f, e).

#include <iostream>
using namespace std;

#define max(a,b) (a>b?a:b)

int min_num_drops(int num_floors, int num_eggs)
{
  int min_throws[num_floors+1][num_eggs+1];
  int f, e, i;
  if (num_eggs == 1)
    return num_floors;
  
  for(i=0; i<num_floors+1; i++){
    min_throws[i][1] = i;
    min_throws[i][0] = 0;
    }
    
  for(i=0; i<num_eggs+1; i++)
  {
    min_throws[0][i] = 0;
    min_throws[1][i] = 1;
  }
  
  for(e=2; e<=num_eggs; e++)
  {
    for(f=2; f<=num_floors; f++)
    {
      min_throws[f][e] = INT_MAX;
      for(i=1; i<=f; i++)
      {
        int drops = 1 + max(min_throws[i-1][e-1], min_throws[f-i][e]);
        if(drops < min_throws[f][e])
          min_throws[f][e] = drops;
      }
    }
  }
  
  return min_throws[num_floors][num_eggs];
}

int main()
{
  int num_floors, num_eggs;
  cout << "Enter number of floors: ";
  cin >> num_floors;
  cout << "Enter number of eggs: ";
  cin >> num_eggs;
  cout << "minimum number of drops: " << min_num_drops(num_floors, num_eggs) << endl;
}

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.

Question: N queen problem is a very famous problem in computer science. This problem ask user to place N chess queens on a NxN chessboard so that no two queens attack each other.

Answer: As the queen can move in any of the eight directions and any number of steps in a single move, there are few solutions, which fit the bill. For N=8, there are 92 distinct solutions. And if solutions that differ only by symmetry operations (rotations and reflections) of the board are counted as one, the puzzle has only 12 solutions.

Lets assume that we already have some queens placed on the chess board so that no queen can attack each other. Now if we need to place another queen on the board, how will we go about it? Please note that a queen is safe if:

1. There is no queen in same row.
2. There is no queen in same column.
3. There is no queen in diagonal paths going from that queen.

Lets say that there are 2 queens at position (i, j) and (x, y). By above theory, that are NOT safe if:

• i = x               same row
• j = y               same row
• |i-x| = |j-y|   same diagonal paths

We can simply avoid the first constraint by placing each queen in different rows. So lets put 1st queen in 1st row, 2nd queen in 2nd row and so on. Now we need to check for same column and same diagonal. Lets have an array 'pos[]' of size N showing where pos[i] is column for i^th queen. Now if (k-1) queens are already placed in first (k-1) rows and we need to place k^th queen in k^th row then we need to check its column and diagonals with all previously placed (k-1) queens.

If we find no place for k^th queen in k^th row because of placement of earlier queens, we will go back to (k-1)^th queen and place it in a different column. Then we try again to place k^th queen. If we still have problem in placing k^th queen, we will go back to (k-1)^th queen and try another safe position for it. This process will be repeated till we try all the possible position for (k-1)^th queen. If there is no safe position to place (k-1) and k^th queen, we will go 2 step back and find alternate safe column for (k-2)^th queen.

This process will be repeated till 1^st queen until we don't find a solution. Since we are going back and finding alternate safe place, this kind of algorithmic approach is called backtracking. Below is an animated figure for the same. (source: Wikipedia)


Below is the ruby implementation for the same:

require 'pp'

@pos = []

def print(size)
  for i in 0..size
    s = ""
    for j in 0..size
      if @pos[i] == j
        s << 'Q '
      else
        s << '_ '
      end
    end
    puts s
  end
  # exit #remove this exit if u want to see all solutions
end

# check if putting a queen in (row, col) is safe
def is_safe(row, col)
  for i in 0..(row-1)
    if (col == @pos[i]) or ((row-i).abs == (col-@pos[i]).abs)
      return false
    end
  end
  return true
end

# place queen in row r
def nqueen(r, n)
  for i in 0..n
    if is_safe(r, i)
      @pos[r] = i
      if (r == n)
        print(n)
        puts ""
      else
        nqueen(r+1, n)
      end
    end
  end
end

if __FILE__ == $0
  if ARGV.length < 1
    puts "Usage: ruby #{$0} size"
    exit
  end
  size = ARGV[0].to_i-1
  if size < 3
    puts "No solution possible"
  else
    nqueen(0, size)
  end
end

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.

Question: There is a 2D grid of characters. You need to find if a given word can be matched in any direction in the grid. The direction can be up-down, down-up, left-right, right-left, both diagonals up and down. This problem is also famous with the name 'Where's Waldorf?'.

Example: You are given a character grid like below. You need to find patterns 'Akash and 'coDe' in this grid. They can appear in any direction. Also the search should be case insensitive.

Below are the result of finding 'Akash and 'coDe'.



Input: The input begins with a pair of integers, m followed by n, 1 < m,n < 50 in decimal notation on a single line. The next m lines contain n letters each; this is the grid of letters in which the words of the list must be found. After that another integer k appears on a line by itself (1 < k < 20). The next k lines of input contain the list of words to search for, one word per line to be found in the grid in case insensitive manner.

For our example, sample input will be:
5 5
HQWCS
ESPKD
DXAFL
OCHKH
CTYCA
2
Akash
coDe

Output:
For each word in the word list, a pair of integers representing the location of the corresponding word in the grid must be output.

For our example, sample output will be:
5 5
5 1

Algorithm:
This is a very straight forward problem. We first need to find the first character match of word (to be found) in the grid. One we find the start point, we need to go in all 8 directions till the end of word (or the grid). If we reach end of the word, print the starting coordinates and move on to next word.

Code (C++):

#include <iostream>

using namespace std;
#define N 50

// We can search is all 8 directions
char DIR[8][2] = {
  {1,0}, {1,-1}, {1,1}, {0,-1}, {0,1}, {-1,0}, {-1,-1}, {-1,1}
};
// for toal array size
int m, n;

// method for finding word presence in the array in a specific direction
bool match(char CharMat[50][50], char word[], int i, int j, int dir_index)
{
  int k=0;
  for( ; i<m  && j<n  && i>=0  && j >=0  && word[k] != '\0'; i = i+DIR[dir_index][0],  j = j+DIR[dir_index][1], k++)
    if(toupper(word[k]) != toupper(CharMat[i][j]))
      return false;

  if (word[k] == '\0')
    return true;

  return false;  
}

void find_presence(char CharMat[50][50], char word[])
{
  for(int i=0; i<m; i++)
    for(int j=0; j<n; j++)
      if (toupper(CharMat[i][j]) == toupper(word[0]))
        for (int k=0; k<8; k++)
          if (match(CharMat, word, i, j, k))
          {
            cout << i+1 << " " << j+1 << endl;
            return;
          }
  cout << "'" << word << "' was not found in the grid" << endl;
}

int main()
{
  char CharMat[N][N];
  cin >> m;
  cin >> n;
  for (int i=0; i<m; i++)
    cin >> CharMat[i];
  
  int num_words;
  char word[N];
  cin >> num_words;
  for (int j=0; j<num_words; j++)
  {
    cin >> word;
    find_presence(CharMat, word);
  }
}

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.

To find out Ubuntu version you are running, you can run a short command in the Terminal.

lsb_release -a

You will get detailed information about your Linux distribution here. There is a 'Release' field in the out, which have the version of Ubuntu, you are running.


'lsb_release' command prints distribution-specific information. Here are other option you can use with this command:

Usage: lsb_release [options]

Options:
  -h, --help                 show this help message and exit
  -v, --version            show LSB modules this system supports
  -i, --id                      show distributor ID
  -d, --description       show description of this distribution
  -r, --release              show release number of this distribution
  -c, --codename        show code name of this distribution
  -a, --all                     show all of the above information
  -s, --short                 show requested information in short format


Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.