PROGRAMMING INTERVIEWS

Find integer average of 2 integers

noreply@blogger.com (Akash) — Mon, 25 Jan 2016 08:26:00 +0000

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.

Print all tuple combinations for a given tuple

noreply@blogger.com (Akash) — Sun, 02 Aug 2015 13:18:00 +0000

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)

Max price by selling pieces of a rod

noreply@blogger.com (Akash) — Mon, 28 Apr 2014 15:07:00 +0000

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.

2 Egg Puzzle

noreply@blogger.com (Akash) — Wed, 23 Apr 2014 13:23:00 +0000

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;
}

[Backtracking] place N queens on NxN chess board

noreply@blogger.com (Akash) — Tue, 15 Apr 2014 10:59:00 +0000

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:

There is no queen in same row.
There is no queen in same column.
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

Find the presence of a given word in a given grid

noreply@blogger.com (Akash) — Sat, 05 Apr 2014 13:22:00 +0000

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);
  }
}

Checking your Ubuntu Version

noreply@blogger.com (Akash) — Fri, 21 Mar 2014 10:40:00 +0000

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

Is Quora wasting too many ajax calls to implement its live search feature?

noreply@blogger.com (Akash) — Sat, 08 Sep 2012 19:21:00 +0000

I love Quora as a product. This is a Q&A site where each question or answer is created, edited, and organized by everyone who uses it. Quora has a live search box in its top navigation bar. This box is it's single point of interaction with user input: for searching a question, for asking a question etc. You start getting suggestions as soon as you start typing in this box.

I was looking into Quora's live search feature and found something unusual. I noticed that as soon as I put my cursor in the search box on top navigation bar, browser starts sending search ajax calls to quora servers. It also sends ajax calls too frequently for a live search feature.

(Quora search calls)

After noticing above stuff from Quora, I decided to compare Quora and StackOverflow live search feature. Results are given below. For the same text in a question (assuming same typing speed), Stackoverflow sent 6 calls to their servers while Quora sent 29 ajax calls to their servers.

(stackoverflow search calls)

(Quora search calls)

On studying further, I found that stackoverflow waits for a minimum number of characters before showing any result but that's not true in case of quora. Quora sent ajax calls as soon as I put my cursor in search box. This means that Quora send an ajax call for blank search box also.

(an ajax call for blank search box)

My concerns are:

Can Quora better their frequency of ajax calls for search?
Why should user pay for unnecessary bandwidth in this case (even if it is few bytes)?
What is the use of search with insignificant number of characters in search box? Does it gives any relevant results in that case. For example: try typing "what" in search box.

Had Quora search results been personal, this feature might be much more benefitial but I don't think that we need this much speed for sending ajax calls.

PS: I have posted a same question on Quora and am waiting for response on that.

How did identifying descriptive log file name save us?

noreply@blogger.com (Akash) — Sat, 02 Jun 2012 18:20:00 +0000

We had a task to batch process around 10 million old slideshows at Slideshare. These slideshows were being processed in parallel and we are supposed to maintain logs to debug if something fails during the process. Each slideshow has an id associated with it and these ids were ranged from 1 to 13 million. It means we have some deleted slideshows in between.

Everything went fine when we were in early stage. We had processed from 1 to 100 thousand slideshows without any problem. When an engineer declared that first 1 million are done, we were happy that 1mn mark is reached much before anticipated time. While verification, we noticed that there were around 300 thousands slideshows, which were not processed. To add more problems, these slideshows were not in continuous range but divided almost equally between 100,000 and 1 mn.

Irrespective of how good logs we captured, It was not easy to parse logs and make a list of unprocessed slideshows. To add more problems, we captured really detailed logs so it was a nightmare to parse logs. Also we learnt that these 3 lakh slideshows were missed and not failed and finding them in DB wasn’t a option.

When we were writing this script, we did a good thing. We wrote script to ask start and end slideshow id as arguments and process slideshows between them. We created separate log file for each script instance (for each batch) and appended start and end slidehow_id in log file name. Log filenames followed the nomenclature ‘batch_process_start#_end#.log’. This also gave us flexibility to run script paralelly for small batches.

When we identified missing 3 lakh slideshows problem, we arranged log files in order of their start id. When we draw a sequence from start_id to end_id for each log file, we noticed some gaps between end_id of one batch and start_id of next batch. There were many batches for which we noticed this gap.

Once we identified all the missing batches, we ran our script only for missing batches. After completion, when we rearranged log file as earlier, we saw no gaps between end_id of one batch and start_id of next batch. Also while verifying if all the data is processed, we find it was so.

This particular naming convention saved us from parsing log files and identifying which files are missing. So not only identifying which logs are going to help, it helps how are you saving those logs.

Catch a linux signal in a C program

noreply@blogger.com (Akash) — Tue, 20 Mar 2012 18:59:00 +0000

Did you ever wonder what happens when an user hits ctrl-c? A SIGINT signal is generated and sent to the process running. This is the way to terminate programs from terminal.

When the signal occurs, the process has to tell the kernel what to do with it. Your process can ignore signal, catch signal or let the default action apply.

Note: SIGKILL and SIGSTOP cannot be ignored.

If a process wishes to handle a signal then in the code, the process has to register a signal handling function to the kernel. The following is the prototype of a signal handling function :

void <signal handler function> (int sig)

You can specify in this function how you want to handle it.

To invoke above function when a signal occurs, you need to register this function to kernal. To get the signal handler function registered to the kernel, the signal handler function pointer is passed as second argument to the ‘signal’ function. The prototype of the signal function is :

void (*signal(int signo, void (*func )(int)))(int);

Where func is the signal handler function, we defined.

Below is a program to handle SIGTERM signal. Run this program and send a SIGTERM signal to this to see what happens.

#include<cstdio>
#include<csignal>

void sig_handler(int signo)
{
 if (signo == SIGTERM)
   printf("received SIGTERM\n");
}

int main(void)
{
 if (signal(SIGTERM, sig_handler) == SIG_ERR)
 printf("\ncan't catch SIGTERM\n");
 // wait so that we can easily issue a signal to this process
 while(1)
   sleep(1);
 return 0;
}

As told earlier that KILL and STOP cannot be handled. Change above program to handle these two signals to see how the ‘signal’ system call responds in that case.

PS: Apart from handling the standard signals, we can also have user defined signals that can be sent and handled.

Some lesser known but useful Unix commands

noreply@blogger.com (Akash) — Tue, 27 Dec 2011 17:17:00 +0000

less: You might be familiar with ‘cat’. ‘less’ is a much better way to inspect large files on the command line. You’ll get a screen-full of text at a time, but no more. You can move a line or window up or down. You can search for a pattern by typing /pattern. When you’re done, hit q to exit the less viewer.

touch: ‘touch’ is basically for changing file access and modification times. But it’s a bonus that if the file doesn’t exist, it will create it.

history, !!, and !$: ‘history’ shows a numbered list of many of your recent commands on console. Then, to execute one of them, just type an exclamation mark and the history number. It’s even quicker to access the last command and last argument you used. For the latest command, use !!; the usual use case given for this is adding sudo to the front of a command. For the latest argument, use !$;

yes: ‘yes’ outputs argument forever. By default, it prints ‘y’ forever.

cal: Displays a very nice calendar with current date highlighted.

seq: This command prints sequences of numbers. User can define start number, interval, end number and many other options.

bc: A very precise calculator. Really useful for performing calculations on large numbers.

factor: A very good mathematical utility for finding prime integer factors.

stat: display file or file system status

tac: reverse of 'cat', print a file line by line in reverse order.

ldd: prints shared library information. In OS X, we use otool for the same purpose.

iostat: CPU and disk usage stats

lsof: List Open Files

netstat: show network status

PS: I've not given examples but linked to man pages on purpose, so that readers can learn by experiment.

Print a Binary Tree in Zig Zag Level Order

noreply@blogger.com (Akash) — Sat, 19 Nov 2011 18:11:00 +0000

Question: Print a binary tree in zig-zag level order. Zig-zag means print 1st level from left to right, then 2nd level right to left and alternate thereafter.

Example: zig-zag level order traversal of below tree will be
0 2 1 3 4 5 6 14 13 12 11 10 9 8 7

Answer: We usually use a queue for level order traversal of a queue. If we want to use the same here, how will we change direction of traversal on every alternate level?

If we think logically then we will see that we need stack in place of queue. Now again a single stack won’t serve our purpose here, we need 2 stacks: stack1 for right to left and stack2 for left to right. For identifying, whether we need to put data in stack1 or stack2, we need a flag (left2right) to indicate direction (after a level finishes).

Initially, left2right is true and we push root node in stack1 and that’s our beginning point. Now since after root node, first level fished, we toggle left2right. Until stack1 is empty, we pop values from stack1 and push values based on left2right flag. Once stack1 finishes, we toggle left2right again and switch stack’s role.

For clarification, when left2right is true, push left node first in stack and then right node. Similarly left2right is false, push right node first in stack and then left node.

Code:

void ZigZagLevelOrder(tree *root) {
 stack<tree*> stack1, stack2, *cur_level, *next_level, *temp;
 bool left2right = true;

 cur_level = &stack1;
 next_level = &stack2;

 // push root in stack
 cur_level->push(root); 
 while (!cur_level->empty()) {
   tree *node = cur_level->top();
   cur_level->pop();
   if (node) {
     cout << node->data << " ";
     if (left2right) {
       next_level->push(node->left);
       next_level->push(node->right);
     } else {
       next_level->push(node->right);
       next_level->push(node->left);
     }
   }
   if (cur_level->empty()) {
     left2right = !left2right;
     // swap stacks
     temp = Cur_level;
     cur_level = next_level;
     next_level = temp;     
   }
 }
}

Find largest sub-matrix with all 1s (not necessarily square)

noreply@blogger.com (Akash) — Mon, 05 Sep 2011 17:32:00 +0000

In last post, we saw a dynamic programming approach to for finding maximum size square sub-matrix with all 1s. In this post, we will discuss how to find largest all 1s sub-matrix in a binary matrix. The resultant sub-matrix is not necessarily a square sub-matrix.

Example:

1  1  0  0  1  0
0  1  1  1  1  1
1  1  1  1  1  0
0  0  1  1  0  0

Largest all 1s sub-matrix is from (1,1) to (2,4).

1  1  1  1
1  1  1  1

Algorithm: If we draw a histogram of all 1’s cells in above rows (until we find a 0) for a particular row, then maximum all 1s sub-matrix ending in that row will the equal to maximum area rectangle in that histogram. Below is the example for 3rd row in above discussed matrix:

If we calculate this area for all the rows, maximum area will be our answer. We can extend our solution very easily to find start and end co-ordinates.

For above purpose, we need to generate an auxiliary matrix S[][] where each element represents the number of 1s above and including it, up until the first 0. S[][] for above matrix will be as shown below:


1  1  0  0  1  0
0  2  1  1  2  1
1  3  2  2  3  0
0  0  3  3  0  0

Now we can simple call our maximum rectangle in histogram on every row in S[][] and update the maximum area every time.

Also we don’t need any extra space for saving S. We can update original matrix (A) to S and after calculation, we can convert S back to A.

Code: I am not writing the code for largestArea() function. One can find its definition in this post.

#define ROW 10
#define COL 10

int find_max_matrix(int A[ROW][COL])
{
 int i, j;
 int max, cur_max;
 cur_max = 0;

 //Calculate Auxilary matrix
 for (i=1; i<ROW; i++)
     for(j=0; j<COL; j++)
     {
         if(A[i][j] == 1)
             A[i][j] = A[i-1][j] + 1;
     }

 //Calculate maximum area in S for each row
 for (i=0; i<ROW; i++)
 {     
     max = largestArea(A[i], COL);
     if (max > cur_max)
         cur_max = max;
 }

 //Regenerate Oriignal matrix
 for (i=ROW-1; i>0; i--)
     for(j=0; j<COL; j++)
     {
         if(A[i][j])
             A[i][j] = A[i][j] - A[i-1][j];
     }

 return cur_max;
}

Complexity: Lets say that total number of rows and columns in A are m and n respectively and N = m*n

Complexity of calculating S = O(m*n) = O(N)

Complexity of LargestArea() for every row = O(n) since there are n elements in every row. Since we called LargestArea() m times so total complexity of calculating largest area = O(m*n) = O(N)

Complexity of converting S to A = O(m*n) = O(N)

So total time complexity = O(N)

Since we are not using any extra space, so space complexity is O(1).

Note: Above function only returns largest area, which can be very easily modified to get start and row indexes as well.

Maximum size square sub-matrix with all 1s

noreply@blogger.com (Akash) — Sat, 03 Sep 2011 16:50:00 +0000

Question: Given a matrix consisting only 0s and 1s, find the maximum size square sub-matrix with all 1s.

Example: Consider the below matrix.

   0  1  1  0  1
   1  1  0  1  0
   0  1  1  1  0
   1  1  1  1  0
   1  1  1  1  1
   0  0  0  0  0

The maximum square sub-matrix with all '1' bits is from (2,1) to (4,3)

    1  1  1
    1  1  1
    1  1  1

Answer: This is a classic Dynamic Programming problem. Lets calculate the maximum size square sub-matrix as we traverse the original matrix M[][]. We will use a auxiliary matrix S[][] of same size for memoization. S[i][j] represents size of the square sub-matrix with all 1s including M[i][j]. 'i' and 'j' will be the last row and column respectively in square sub-matrix.

How to calculate S[i][j]:
We should note that if M[i][j] is '0' then S[i][j] will obviously be '0'. If M[i][j] is '1' then S[i][j] depends on earlier values.

If M[i][j] is '1' then it will contribute to the all 1s square sub-matrix ending at either M[i][j-1] or M[i-1][j] or M[i-1][j-1]. If we visualize the conditions then, we will see:

S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1

How did we arrive at above relationship?
Note if we include M[i][j] in earlier calculated sub-matrix then we are adding S[i][j] elements from i^th row and j^th columns. They all should be '1' if we wanna include M[i][j]. On visualizing with some examples, readers will analyze why, minimum of 3 neighbors is taken.

For the given M[][] in above example, constructed S[][] would be:

   0  1  1  0  1
   1  1  0  1  0
   0  1  1  1  0
   1  1  2  2  0
   1  2  2  3  1
   0  0  0  0  0

The value of maximum entry in above matrix is 3 and coordinates of the entry are (4, 3). Using the maximum value and its coordinates, we can find out the required sub-matrix.

Code:

#define ROW 10
#define COL 10

void FindMaxSubSquare(bool M[ROW][COL], int &max_i, int &max_j, int &size)
{
    int i,j;
    int S[ROW][COL];
 
    /* Set first column of S[][]*/
    for(i = 0; i < ROW; i++)
        S[i][0] = M[i][0];
 
    /* Set first row of S[][]*/
    for(j = 0; j < COL; j++)
        S[0][j] = M[0][j];
 
    /* Construct other entries of S[][]*/
    for(i = 1; i < ROW; i++)
    {
        for(j = 1; j < COL; j++)
        {
            if(M[i][j] == 1)
                S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1;
            else
                S[i][j] = 0;
        }
    } 
 
    /* Find the maximum entry, and indexes of maximum entry in S[][] */
    size = S[0][0]; max_i = 0; max_j = 0;
    for(i = 0; i < ROW; i++)
    {
        for(j = 0; j < COL; j++)
        {
            if(size < S[i][j])
            {
                size = S[i][j];
                max_i = i;
                max_j = j;
            }
        }
    }     
    return
}

Complexity:
Time Complexity: O(m*n) where m is number of rows and n is number of columns in the given matrix.
Space Complexity: O(m*n) where m is number of rows and n is number of columns in the given matrix.

Note: Part of this post is taken from geeksforgeeks.

Weekend Miscellany

noreply@blogger.com (Akash) — Wed, 24 Aug 2011 16:11:00 +0000

Maths:
The Secret of the Fibonacci Sequence in Trees

C/C++:
The most stupid C bug ever

Computer Science:
The Busy Beaver Problem - good coders code, great reuse

Sorting Algorithm Animations

Music produced by different sorting algorithms

Divisibility by 7

noreply@blogger.com (Akash) — Wed, 24 Aug 2011 12:14:00 +0000

How can you tell whether a number is divisible by 7? Almost everyone knows tricks to test divisibility by 2, 3, 5, or 9. Testing divisibility by 4, 6, 8, or 11 is a bit trickier. But not many people have ever seen a trick for testing divisibility by 7.

How to test: Remove the last digit from the number, double it, and subtract it from the first part of the number. Do this repeatedly until you get something you recognize as being divisible by 7 or not.

Example: Lets test for 826. Split 826 into 82 and 6. Subtract 12(6*2) from 82 to get 70. Since 70 is divisible by 7, so is 826.

Another Example: For 8632. Split 8632 into 863 and 2. Subtract 4(2*2) from 863 to get 859.

Now split 859 into 85 and 9. Subtract 18(9*2) from 85 to get 67, which isn’t divisible by 7. Hence, we conclude that 8632 isn’t divisible by 7.

Why does this work? Let b be the last digit of a number n and let a be the number we get when we split off b. That says n = 10a + b. Now n is divisible by 7 if and only if n – 21b is divisible by 7. But

n – 21b = 10a + b - 21b = 10(a – 2b)

Above is divisible by 7 if and only if a – 2b is divisible by 7.

Similarly, we can find divisibility by 13, 17, 19 etc.

Divisibility by 13: Add four times the last digit to the remaining leading truncated number to make it (n + 39b) = 10(a + 4b)

Divisibility by 17: Subtract five times the last digit from the remaining leading truncated number to make it (n - 51b) = 10(a - 5b)

Divisibility by 19: Add two times the last digit to the remaining leading truncated number to make it (n + 19b) = 10(a + 2b)

Test above divisibility yourselves with examples.

PS: Thanks John D. Cook for this trick.

Change Headers Of S3 Object

noreply@blogger.com (Akash) — Tue, 23 Aug 2011 10:46:00 +0000

Sometimes, we need to change header info for S3 objects. One solution is to download file locally and upload it again with new header information.

Using Amazon API COPY functionality, it is possible to change headers on an S3 object without downloading the entire object. We need to set x-amz-metadata-directive as REPLACE to copy a S3 key to the same location.

But if we do this using right_aws ruby gem, ACL information is not preserved. For preserving ACL information as well, we need to preserve ACL permission before changing headers and then apply ACL again after changing headers.


#!/usr/bin/env ruby

require 'rubygems'
require 'right_aws'

@s3 = RightAws::S3Interface.new('AWS_ACESS_KEY', 'AWS_SECRET_KEY', :logger => STDOUT)

#In this example, I'm changing the mime-type to image/png.
#You can change whatever header you want.
update_s3_object_headers(bucket, key, {'Content-Type' => 'image/png'})

def update_s3_object_headers(bucket, key, headers)
      #Saving current ACL
      acl_xml = @s3.get_acl(bucket, key)[:object]
      # Performing a copy with directive REPLACE
      @s3.copy(bucket, key, bucket, key, :replace, headers)
      #Restore ACL
      @s3.put_acl(bucket, key, acl_xml)
end

Copy Files Between Separate AWS Accounts

noreply@blogger.com (Akash) — Mon, 22 Aug 2011 12:06:00 +0000

Sometimes, we need to copy S3 data between separate AWS accounts. Though Amazon API provides COPY functionality but that is only for buckets under same account.

It seems that if we want to copy data between buckets in different accounts, only option is to download the file to local system and then upload it to destination bucket.

Since bucket names are unique across all S3, we can copy a public-read file to destination bucket (in different account) using COPY. I tested this and it works perfectly.

For copying a private file, we need to temporarily give public-read permission on the file and then COPY it to different AWS accounts. Don’t forget to change permissions for file in source and destination bucket once copy is done.

Also, we don't have to worry about bandwidth charges since COPY operation is internal to AWS. No download of the actual file required.

Code:

#!/usr/bin/env ruby

require 'rubygems'
require 'right_aws'

srcBkt = 'SourceTest'
srcKey = 'test.ppt'
destBky = 'DestTest'
destKey = 'test.ppt'

# Put credentials of destination account
s3 = RightAws::S3Interface.new('access_key', 'secret_key)  

begin
    #We can do a move operation as well if both the accounts are linked
    s3.copy(srcBkt, srcKey, destBkt, destKey)
rescue Exception => e
    puts e.inspect
end

Update: Please not that you will be able to COPY public content but can't MOVE (copy + delete) content across different accounts. If these accounts are linked with each other, you can MOVE as well.

How To Add Facebook Comment Box To Blogger Blogs

noreply@blogger.com (Akash) — Sat, 13 Aug 2011 15:45:00 +0000

Facebook comment box is one of the very useful tool for bloggers to increase engagement of readers. You may find many other blog posts teaching to add Facebook comment box to blogger blog. But still people are getting problem as I did. In this post, I will talk about how to integrate Facebook comment box to your blogger blog in very simple steps.

Step 1: Setup an application at Facebook developer page and enter your blog name, URL. Save the APP-ID for future reference.

Step2: Get your Facebook USER-ID. If you are using a custom username for your Facebook profile or page, you can get your profile Id from http://graph.facebook.com/<your username>. Here is the same page for Programming Interviews.

Step 3: Login to you Blogger dashboard and navigate to Layout > Edit HTML and check on Expand Widget Templates. Search for <head> and add following lines just after it:

To moderate comments across a site, all moderators must be added as admins of the app:


<meta property="fb:app_id" content="{YOUR_APP_ID}">

To receive notifications on every comment posted to the Comment Box, add:


<meta property="fb:admins" content="{YOUR_USER_ID}">

Change {YOUR_APP_ID} and {YOUR_USER_ID} with earlier saved values.

Step 4: Search for <data:post.body/> and add following lines just after it:


<!-- Facebook comment start -->
<b:if cond='data:blog.pageType == &quot;item&quot;'>
  <script src='http://connect.facebook.net/en_US/all.js#xfbml=1'>
  </script>
  <fb:comments expr:href='data:post.url' num_posts='5' width='600'/>
</b:if>
<!-- Facebook comment end -->

Line 2 adds a check so that Facebook comment box doesn't appear on home page of your blog but only on the post pages. If you are familiar with blogger template you may want to add above code somewhere else. Please note to use expr:href in place of just href in line 5.

Step 5: You may or may not want to hide your blogger comment box. If you want to hide Blogger comment box, navigate to Settings > Comments and select hide and save settings.

PS: If you like this tutorial or have any question, please use below Facebook comment box to start conversation.

Find optimal number of jumps to reach last element

noreply@blogger.com (Akash) — Thu, 11 Aug 2011 06:34:00 +0000

Question: Given an array, start from the first element and reach the last by jumping. The jump length can be at most the value at the current position in the array. Optimum result is when you reach the goal in minimum number of jumps.

Example:

Given array A = {2,3,1,1,4}

Possible ways to reach the end (index list)

0,2,3,4 (jump 2 to index 2, and then jump 1 to index 3 and then jump 1 to index 4)
0,1,4 (jump 1 to index 1, and then jump 3 to index 4)

Since second solution has only 2 jumps it is the optimum result.

Answer: This problem is a classic example of Dynamic Programming. Though we can solve this by brute-force but complexity in that case will be horrendous. If you remember LIS problem or my first post on dynamic programming then we can solve this by using same process.

As soon as we traverse the array, we should find the minimum number of jumps for reaching that position (index) and update our result array. Once we reach at the end, we have the optimum solution at last index in result array.

How to find optimum number of jump for every position (index)?

For first index, optimum number of jumps will be zero. Please note that if value at first index is zero, we can’t jump to any element and return infinite.

For (N+1)^th element, initialize result[N+1] as infinite. Then we should go through a loop from 0…N, and at every index (i), we should see if we are able to jump to (N+1) from there (i) or not. If possible then see if total number of jump (result[i] + 1) is less than result[N+1], then update result[N+1] else just continue to next index.

Code: I skipped algorithm but commented code properly.


//Define MAX 1 less so that adding 1 doesn't make it 0
#define MAX 0xFFFFFFFE;

unsigned int jump(int *array, int n)
{
  unsigned int
*result = new unsigned int[n];
  int i, j;
  
  //Boundry conditions
  if (n==0 || array[0] == 0)
    return MAX;
    
  result[0] = 0;  //no need to jump at first element
  for (i = 1; i < n; i++)
  {
    result[i] = MAX; //Initialization of result[i]
    for (j = 0; j < i; j++)
    {
      //check if jump is possible from j to is
      if (array[j] >= (i-j))      {

        //check if better solution available
        if ((result[j] + 1) < result[i]) 
          result[i] = result[j] + 1;  //updating result[i]
      }
    }
  }
  
  //return result[n-1]
  unsigned int answer = result[n-1];
  delete[] result;
  
  return answer;
}

Above code will return optimum number of jumps only. If we want to have the jump indexes as well, we can very easily modify the code as per requirement.

Efficiency: Since we are running 2 loops here and iterating from 0 to I in every loop then total time takes will be 1 + 2 + 3 + 4 + … + (N-1).

So time efficiency O(n) = O(n*(n-1)/2) = O(n^2)

We also need O(n) space for result array.

Matrix Madness - smallest non-negative number

noreply@blogger.com (Akash) — Sun, 07 Aug 2011 11:14:00 +0000

Question: There is an N x N matrix with the property that each entry in the matrix is the smallest non-negative number, which does not appear either above the entry or to its left. Write a method to find the entry in a particular row and column.

For example, for N=8, we might have the matrix:

0    1    2    3    4    5    6    7
1    0    3    2    5    4    7    6
2    3    0    1    6    7    4    5
3    2    1    0    7    6    5    4
4    5    6    7    0    1    2    3
5    4    7    6    1    0    3    2
6    7    4    5    2    3    0    1
7    6    5    4    3    2    1    0

Answer: From the question statement, it is clear that the top left corner starts things off with 0 and the top row and the leftmost column are each completed with the positive integers 1,2,3,..., in order.

Secondly, if every time we fill another cell, we use the smallest non-negative integers that have not so far appeared in the same column and the same row, then it is impossible to get a repeated integer in either the same column or the same row. Square matrix of order n, in which every symbol occurs exactly once in each row and column of the array, is called latin square. So we can say that above matrix is a latin square in different setting.

Lets see if we can find some pattern in the sequence. If we write the matrix in binary number system an 8*8 matrix will look like below matrix:

If we split this 2ⁿ square matrix in 4 parts of size 2^n-1 and call them as M_tl, M_tr, M_br, M_bl (top-left, top-right, bottom-left, bottom-right respectively), each of these sub-matrixes is a latin square in itself.

If we took the highest power of 2 from these values, we can also write this matrix as

Lets see how this works. First, fill the corner square of size 1x1 with the number 0. On the next step, we get a square of size 2x2. The latter consists of four squares (M_tl, M_tr, M_br, M_bl ) equal in size to the square on the previous step. M_tl is the square from the previous step. Copy it into three other squares, and lastly add 1 (2^o) to every element of M_tr and M_bl.

Now at every step for generating a square matrix of size 2ⁿ⁺¹, we can expand the matrix by assuming that a corner square of size 2ⁿ (M_tl)has been filled. Copy it into adjacent squares M_tr, M_br and M_bl and add 2ⁿ to every element of M_tr and M_bl. Final relationship will be like shown below:

How can we prove that resultant matrix has the required property?

Lets prove it my using mathematical induction. We have seen that M₀ adhere to the property. Now assume that M_N-1 follow the property, lets show that M_N also follow the same:

Since we assumed that M_N-1 (i.e. M_tl for M_N) follows theis rule and entries of M_tr are formed by adding 2^N-1 to M_tl. So M_tr is a latin square in itself. Also since elements from 0 to (2^N-1 - 1) have already been used in M_tl, candidates for M_tr are only values greater than or equal to 2^N-1. So we can say that M_tr adheres to the given rule. Similar argument can be given for M_bl.

For M_br, we see that value for 0..(2^N-1 -1) are not used in these row and column yet, We can use them and we used M_tl as it is. Hence we prove that M_Nthe given conditions.

Now we can calculate value at any row and column in O(logN) time as on every step we can reduce the matrix size by half.

Can we do it in constant time?

Assume that rows and columns starting with 0 as in C/C++. Let M_(m,n) denotes the number that appears in the (m, n) cell. Since we can denote any number with addition of power of 2, lets say

m = 2^a + 2^b + 2^c + ... where a > b > c...
n = 2^x + 2^y + 2^z + ... where x > y > z...

If a = x: then (m, n) lies in the M_br square of the smallest square M_N that contains (m, n). By dropping 2^a from m and 2^x from n, the point is moved into M_N-1. So we don’t bother about a^th and x^th bit from m and n respectively.

If a < x: then (m, n) lies in the M_tr square of the smallest square M_N that contains (m, n). As we saw earlier, we can move it into M_N-1 by dropping 2^a from m and add 2^a to result. So we don’t bother about a^th bit if it diffres.

If a > x: then (m, n) lies in the M_bl square of the smallest square M_N that contains (m, n). As we saw earlier, we can move it into M_N-1 by dropping 2^x from n and add 2^x to result. So we don’t bother about x^th bit if it differs.

The process will continue while either m or n are not zero. Every time one of them has a binary bit which is 0 in the other, this bit is removed from the number but added to result. So we see that whenever any bit of m and n differs, we need to add it to result and just drop it if it’s same. In Boolean mathematics, XOR operator does the same. At the end of the day, m = n = 0 whereas result contains (m XOR n) of the original m and n. So finally

M_(m,n) = m^n

Hence, we see that we can calculate the entry in a particular row and column in constant time and space.

Convert binary tree in circular doubly linked list

noreply@blogger.com (Akash) — Wed, 03 Aug 2011 12:22:00 +0000

Question: Take a binary tree and rearrange left and right pointers to make a circular doubly linked list.

Convert a BST to a sorted circular doubly-linked list in-place.

You are supposed to play with pointers only. Assume left and right pointers of tree as previous and next pointers of doubly-linked list.

Answer: This is one of the most asked problems in programming interviews. Microsoft asks this question very frequently, I was asked the same when I rejected SDE-2 offer from Microsoft a few months ago. You can also find this problem at Stanford CS education library page as The Great Tree List Recursion Problem.

Below is original tree, which we have to convert in a circular doubly linked list.

And below is the original tree converted to circular doubly linked list with "next" and "previous" list arrows added.

Above drawing shows the all of the problem state -- the original tree is drawn with plain black lines and the desired next/previous pointers are added in as arrows. Notice that starting with the head pointer.

Looking at the last figure, you might have already started thinking about in-order traversal. If not then please notice that in final linked list (shown below), all the nodes left to a node were actually the nodes from left-sub-tree in original tree. Similarly, all the nodes right to a node were actually the nodes from right-sub-tree in original tree. This is similar to in-order traversal of tree:

process left sub tree
process current node
process right sub tree.

Here extra task is to modify pointers accordingly to create a link list.

As we traverse the tree in-order, we can modify a node’s left pointer to point to its predecessor. We also have to modify the predecessor’s right pointer to point to the current node to maintain the doubly linked list behavior.

In this manner, we will be creating a list but that won’t be circular. We can solve this problem by creating a circular doubly linked list at every step in place of creating only doubly linked list. For this, we need to update the current node’s right pointer to point back to the head and the head’s left pointer to point to current node in each recursive call. As the recursion ends, the list’s head and tail would be automatically updated with the correct pointers.

Code:

struct node {
   int data;
   struct node* left;
   struct node* right;
};
typedef struct node* Node;

//root: Current tree node
//prev: this pointer should have the address of in-order predecessor of root
//head: this denoted head of final link list
void treeToDoublyList(Node root, Node & prev, Node & head)
{
   if (!root) return;
   treeToDoublyList(root->left, prev, head);

   // current node's left points to previous node
   root->left = prev;
   if (prev)
       prev->right = root; // previous node's right points to current node
   else
       head = root;        // if previous is NULL that current node is head

   Node right = root->right; //Saving right node

   //Now we need to make list created till now as circular
   head->left = root;
   root->right = head;

   //For right-subtree/parent, current node is in-order predecessor
   prev = root;
   treeToDoublyList(right, prev, head);
}

//Wrapper function
Node treeToDoublyList(Node root)
{
   Node prev = NULL;
   Node head = NULL;
   treeToDoublyList(root, prev, head);
   return head;
}

Complexity: As this is nothing but in-order traversal with some extra steps at every node, we are traversing each node just once. Hence time complexity is O(n).

Credits: All the images are copied from Stanford CS library page.

Truth or lie?

noreply@blogger.com (Akash) — Tue, 26 Jul 2011 12:25:00 +0000

Question: There are 100 people in a room. A person always speaks either lie or truth. When asked:

1st person says => all are liars
2nd person says => at most 1 speaks truth
3rd person says => at most 2 speak truth
4th person says => at most 3 speak truth
.
.
.
.
100th person says => at most 99 speak truth

How many people speak only truth?

Answer: Lets assume that person 1 speaks truth then all including him should be liar. It means he doesn’t speak truth.

Before moving forward, we should make it clear what does “at most” mean? “at most N” means N or less.

Lets assume that 2nd person speaks truth then he is the only person who speaks truth coz at most 1 means 1 or less. But if this statement is true then statements by all others are also true. Coz if “at most 1 person speaks truth” is true then “at most N speak truth” is also true, where N >= 1. This contradicts his own statement, so person 2 is also a liar.

Now lets say that 3rd person is speaking truth. But then the statements of person 4-100 are also true, which contradicts his own statement. It means that person 3 is also a liar.

This process will continue since 50th person. So 1-50 people are liars.

51st person says “at most 50 speak truth”. Lets say he is speaking truth. “at most 50” means any number from 0-50. It means that statements like “at most 51 speak truth” and “at most 70 speak truth” are also true. It means that people from 51 to 100 are speaking truth.

Hence, 50 people speak truth.

Count Number of Blobs

noreply@blogger.com (Akash) — Tue, 19 Jul 2011 05:11:00 +0000

Question: You are given a 2D array like below:

x o o o o x
x x x o o x
o o x o x o
o o x o o o

A blob is defined as 1 or more adjacent (8 adjacent) Xs. Find the number of blobs in the most efficient manner.

Example: Below 2D array has 2 blobs. One blob consists of cells which have red 'x' and another consists of cells which have blue 'x'.

Extension: This question is also asked as to count the number of islands in an ocean where ocean is represented as a grid. Cells, having a part of any island, are marked as 'x' otherwise 'o'.

Answer: There is a recursive solution to check 'x' cells every time you encounter 'x' in any cell. But this solution is very inefficient coz you will be checking 8 cells for every 'x' cell and will result in a number of recursive loops. Also keeping count of blobs in this case is a bit difficult.

An efficient solution will be to mark all the cells in a single blob as used and increase the count by 1 for every blob. For this we need a data structure, which we can use to find cells in a single blob. This can be achieved by using a queue as described below.

While traversing the array in row/column major order, as soon as you encounter an unused 'x' cell, push it in queue. Also increment the count by 1 and mark this cell as used. Now pop front element from queue and check for its 8 neighbors, if they contain 'x' and not used, put them in queue. Repeat this process until queue is empty.

Using above method, you will be able to mark all cells of a blob as used. Now traverse array further and repeat the same process if you encounter any unused 'x' cell.

Algorithm:

count = 0
while row < total rows
while column < total columns
 if  cell[row][column] is unused
  put in queue
  increase count by 1
  while queue is not empty
   tmp = front element of queue
   pop from queue
   push unused 'x' neighbors of tmp in queue
  end while
 end if
end while
end while
return count

Code:

I have used MSB of every cell to use as a flag for used and unused cell. You can always use a different method.

#define MAX 100
#define USED 0x80

struct point
{
    int x,y;
};

void push_in_queue(int x, int y, queue<struct point> *q, char mat[MAX][MAX], int nrow, int ncol) 
{
    if(x < 0 || x >= nrow || y < 0 || y >= ncol)
      return;
    struct point pnt;
    if (mat[x][y] == 'X' && !(USED & mat[x][y]))
    {        
        mat[x][y] = USED | mat[x][y];
        pnt.x = x;
        pnt.y = y;
        q->push(pnt);
    }
}

int count_blob(char mat[MAX][MAX], int nrow, int ncol)
{   
    queue<struct point> que;
    int cnt = 0;
    int x, y;
    point pnt, tmp;
    if (nrow == 0 && ncol == 0)
        return 0;
        
    for(x = 0; x < nrow; x++)
    {
        for(y = 0; y < ncol; y++)            
        {
            if (USED & mat[x][y])
                continue;
                
            if (mat[x][y] == 'X')
            {
                cnt += 1;
                mat[x][y] = USED | mat[x][y];
                pnt.x = x;
                pnt.y = y;
                que.push(pnt);

                while( !que.empty() )
                {
                    tmp = que.front();
                    que.pop();                    
                    push_in_queue(tmp.x - 1, tmp.y,     &que, mat, nrow, ncol);
                    push_in_queue(tmp.x - 1, tmp.y - 1, &que, mat, nrow, ncol);
                    push_in_queue(tmp.x - 1, tmp.y + 1, &que, mat, nrow, ncol);
                    push_in_queue(tmp.x + 1, tmp.y,     &que, mat, nrow, ncol);
                    push_in_queue(tmp.x + 1, tmp.y - 1, &que, mat, nrow, ncol);
                    push_in_queue(tmp.x + 1, tmp.y + 1, &que, mat, nrow, ncol);
                    push_in_queue(tmp.x,     tmp.y - 1, &que, mat, nrow, ncol);
                    push_in_queue(tmp.x,     tmp.y + 1, &que, mat, nrow, ncol);                   
                }                 
            }                    
        }
    }
    return cnt;
}

Complexity: Since every element of the matrix is processed at the most twice, once while putting in queue and once while normal 2D array traversal, time complexity is O(n) where n is total number of cells. You may argue that we are checking a few element more than 2 times while pushing in the queue, in that case also complexity will be O(n).

Space complexity: Extra space is occupied by queue. Please notice that queue size will never be more than 'n'. You can also deduce that queue size will always be much lesser than 'n' in worst case as well. So space complexity is of order 'n' = O(n).

Detect where the loop starts in a singly link list

noreply@blogger.com (Akash) — Fri, 15 Jul 2011 09:03:00 +0000

In last post, we found how to detect if there is a loop in singly link list or not. Now we will see how to detect where the loop starts.In above figure, we see that loop starts at node (a) after length x and loop length is z. So the total length of link list is (x+z). Also as we saw in last post that slow and fast iterator will meet at some node (b).

Please note if we move a pointer (one node per iteration) from (b) and keep count of nodes until we visit (b) again, we will be able to calculate z.

After finding z, start an iterator itr1 form head and move it z nodes from head at (c). Take another iterator itr2 and start it from head. Now if you move itr1 and itr2 in parallel one node at a time, they will meet first at start of the loop (a).

Explanation is based on following invariance:

"In a circle if we start from some point and move the distance equal to circumference along circle periphery, we will be at the same point again."

Both the iterators are meeting at (a) coz itr1 is z nodes ahead from itr2. Once itr1 is at (a), itr2 is z nodes behind (a). After z iterations, itr2 will reach (a) and itr1 also reaches (a) because of above invariant.

This solution has been suggested by Saket in comments to last post. Great solution Saket!