Puzzle - Help the Painter

Your friend is a painter and he paints houses for quite sometime. He is highly professional and highly sought after as he known for his quality work and fair painting charges. Throughout his life he has painted lot of houses that are regular sizes - rectangles, squares and circles. He charges his customer based on the area he paints. (you see calculating area for regular shapes is cake for him)

Last week, a new potential customer called him up for a huge order that will keep him and his team busy for next five to seven months. The catch here is that the customer is not willing to pay a penny more and even your friend being a professional painter wants to quote a fair pricing strategy to his new potential customer to win this order. BTW, did i tell you that the area to be painted are irregular shapes.

The painting area is

• Irregularly shaped like amoeba
• Each surface is uniquely shaped (bare minimum he needs to paint 1000 such surface different in 1000 ways)

What is the pricing strategy that your friend can offer to his customer so that both your friend and his customer is happy.

Puzzle - Which is at the Middle

There is a linked list (you can assume that it is unidirectional or bi-directional). The list is not ordered in any specific format (unsorted).

• What are the methods (or ways) by which you find the middle element of the list? (For example, if the element has 11 elements, 6th element is the middle. If you have 10 elements, 5th or 6th (whichever you like) is the middle element of the list).
• What is algorithmic complexity of each method?

Testing is Fun and Brain Intensive - Why

Why testing is fun and Why testing has to be brain intensive

Before answering it, let us do this exercise.

Let us take one of the primitive types - "int" in Java and an arithmetic operation addition (imagine that you are testing Java compiler that will be used by developers/testers worldwide). What are things that you would do to verify the correctness of addition for "int". For now, let us focus only on integer addition alone. List down the things that you will learn (meaning that you should know) for completing the task. This exercise will help us to know "why testing is fun, why it has to be brain intensive and why it is equally rewarding".

To help you with some code, this is how addition looks like and you got to test + (which is in red font)

int a = 10, b = 255, c;

c = a + b;

How will you proceed?

Puzzle - "Find Common Parent"

Puzzle

There is a binary tree. Each node has id, left and right as data. The id is unique integer representing the node, left and right are pointers/references points to left and right child respectively. Given two integers, write an algorithm/program to find the lowest common parent node.

Example:

Input - {15, 10}, Output should be {2}

Input - {19, 15}, Output should be {4}

Input - {6, 20}, Output should be {}

Puzzle - Find the Unique Number

There are two arrays - a and b. One of the arrays contains one element more than the other. The extra element is unique and all other elements are same but in different order. Find the element that is unique.

For example
a -> {10,2,3,4,6,5,8,7,9,1}
b -> a -> {1,2,3,4,5,6,7,8,9}
Unique element is {10}

Answer

public static int getUniqueKey(int[] bigger, int[] smaller) {    
    
    if(bigger == null || smaller == null || Math.abs(bigger.length - smaller.length) != 1) {
      throw new ArithmeticException("arguments passed is null.");
    }        
    
    // Till now, bigger is not necessarily bigger. let us make it bigger
    
    if(bigger.length < smaller.length) {
      int[] temp = smaller;
      smaller = bigger;
      bigger = temp;          
    }
    
    int biggerValue = 0;
    int smallerValue = 0;
    
    for(int i = 0; i < smaller.length; ++i) {
      biggerValue += bigger[i];
      smallerValue += smaller[i];
    }      
    biggerValue += bigger[bigger.length - 1];
    
    return biggerValue - smallerValue;
  }

Let us discuss one more puzzle in upcoming days in this week.

Puzzle - "Binary Addition"

Puzzle:
There are two arrays of size "n". Each array represent a number in binary form meaning that each index has "0" or "1". Write an algorithm(program) to add both the array and store the result in the third array of size "n+1". This is an exercise in Coremen et al "Introduction to Algorithms".

Example:
array1 = {1, 0 , 1}
array2 = { 1, 0 , 0)
array3 = {1, 0, 0, 1}

Variation 1
As a next step, can you write an algorithm to handle input arrays of unequal size. For example, one array has "111" and another array has "10001". Find the binary sum for the arrays of unequal size.

Variation 2
Another variation is to generalize the above algorithm (Variation 1) for any base. In previous problem statements, we did it for binary. We need to make a generic algorithm that works for any base (even base 11, base 21 etc).

Example
array1 = { 1, 0, 1}
array2 = {1, 0, 0, 1}
array3 = {1, 1, 1, 0}

Answer (see comments on how we arrived at the solution)


public static int[] binaryAddVariationNoConditional(int [] bigger, int[] smaller, int base) {
    
    if(bigger == null || smaller == null || base <= 1) {
      throw new ArithmeticException("arguments passed is null.");
    }    
    
    int max = Math.max(bigger.length, smaller.length);    
    int[] sum = new int[max + 1];
    
    // Till now, bigger is not necessarily bigger. let us make it bigger
    
    if(bigger.length < smaller.length) {
      int[] temp = smaller;
      smaller = bigger;
      bigger = temp;          
    }
    
    int biggerIndex = bigger.length - 1;
    int smallerIndex = smaller.length - 1;
    int sumIndex = sum.length - 1;
    
    
    for(; smallerIndex >= 0; biggerIndex--, smallerIndex--, sumIndex--){
      sum[sumIndex] = sum[sumIndex] + bigger[biggerIndex] + smaller[smallerIndex];
      sum [sumIndex - 1] = sum[sumIndex]/base;
      sum[sumIndex] = sum[sumIndex] % base;
    }
    
    for(; biggerIndex >=0; biggerIndex--, sumIndex--) {
      sum[sumIndex] = sum[sumIndex] + bigger[biggerIndex];
      sum [sumIndex - 1] = sum[sumIndex]/base;
      sum[sumIndex] = sum[sumIndex] % base;
    }
    
    return sum;
  }