Print 2D matrix in spiral order

Given a 2D array, print it in spiral form.

Input:
        1    2   3   4
        5    6   7   8
        9   10  11  12
        13  14  15  16 

Output: 
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 

Below is the java implementation 

public class PrintMatrixInSpiral {

 private static int [][] matrix = { 
   {1,2,3,4},
   {5,6,7,8},
   {9,10,11,12},
   {13,14,15,16}};
 
 public static void main(String arg[])
 {
  printSpiral(matrix);
 }
 
 public static void printSpiral(int [][]matrix)
 {
  int top = 0;
  int bottom = matrix.length - 1;
  int left = 0;
  int right = matrix[0].length - 1;
  
  int loop = 0;
  
  while ( top < bottom && left < right )
  {
   /* print row horizontally */
   for( loop = top; loop <= right; loop++)
    System.out.println(matrix[top][loop]);
   
   top++;
   
   /* print last column in all rows */
   for( loop = top; loop <= bottom ; loop++ )
    System.out.println(matrix[loop][right]);
   
   right--;
   
   for( loop = right ; loop >= left; loop--)
    System.out.println(matrix[bottom][loop]);
   
   bottom--;
   
   for(loop = bottom; loop >= top; loop --)
    System.out.println(matrix[loop][left]);
   
   left++;
  }
 }
} 

Coin change problem

Find the minimum number of coins required to make change of N, given currencies of different values.

E.g.,

Input: Denominations {1,3,5,8,9},   Value: 28
Output: 4


This problem can be solved using dynamic programming approach. This is similar to Knapsack problem.

Below is Java implementation

public class CoinChange {

    public static void main(String args[])
    {
        int []denominations = {1,3,5,8,9};
        int value = 28;
        System.out.println("The minimum number of coins required to make change of "+value+" is:"+findMinimumCoinsRequired(denominations,value));
    }

    private static int findMinimumCoinsRequired(int[] denominations, int value) {
       
        int []dp = new int[value+1];       
        dp[0] = 0;

        for(int i = 1; i <= value; i++ )
        {
            dp[i] = Integer.MAX_VALUE;
            for( int j = 0; j < denominations.length; j++ )
            {
                if( denominations[j] <=  i  )
                {
                    dp[i] = Math.min(dp[i], dp[i - denominations[j]]+1);
                }
            }
        }
        return dp[value];
    }
}
 

Find minimum number of hops required to reach end of array.

Given an array of integers where each element represents the max number of steps that can be made forward from that element. Write a function to return the minimum number of jumps to reach the end of the array (starting from the first element).

E.g.
Input : {2,3,1,1,4}
Output: 2

We can solve this problem in multiple approaches. Here i am going to provide solution in greedy and dynamic programming model.

In greedy approach we find the maximum value to maximize the jump. In dynamic programming approach we compute the minimum number of hops required to reach each element and use these values for computing the result.

Below is the Java implementation of both approaches.

public class FindMinimumHops {
   
    public static void main(String args[])
    {
        int [] array = {2,3,1,1,4};
        System.out.println("Minimum number of hops to reach end is:"+findMinHopsUsingGreedy(array));       
        System.out.println("Minimum number of hops to reach end is:"+findMinHopsUsingDP(array));
    }

    private static int findMinHopsUsingGreedy(int[] array) {
        int maxHops = 0;
        int currentIndex = 0;
        int max = 0;
        int location = 0;
        while (currentIndex < array.length) {
            maxHops++;
            max = 0;
            for (int ctr = currentIndex + 1; ctr <= currentIndex
                    + array[currentIndex]; ctr++) {
                if (max < array[ctr]) {
                    max = array[ctr];
                    location = ctr;
                }
            }
            currentIndex += location;
        }
        return maxHops;
    }

    private static int findMinHopsUsingDP(int[] array) {
        int []dp = new int[array.length];
        dp[0] = 0;
        for(int i = 1; i < array.length; i++)
        {
            dp[i] = Integer.MAX_VALUE;
            for(int j= 0; j < i ; j++ )
                if( ( i-j ) <= array[j] )
                    dp[i] = Math.min(dp[i], dp[j]+1);
        }
       
        return dp[array.length - 1];
    }

}

Declaration,definition, Initialization

Declaration tells compilers about the name and type of something but omits certain details.

E.g.

extern int x;                    //object declaration
class ABC;                    // Class declaration
template<typename T> struct XYZ;   //template declaration

Declarations introduce new names into a program. Topics covered in this section include the following uses for declarations.

• Specify storage-class, type, and linkage for an object or function.
• Declare a function as inline or virtual.
• Qualify a declaration as const or volatile.
• Associate a name with a constant (enumeration declaration).
• Declare a new type (class, struct, or union declaration).
• Specify a synonym for a type (typedef declaration).
• Specify a namespace.

A definition provides compilers with the details the declaration omits. It is different for different types as follows:

1) For an object, the definition is where the compiler set aside the memory for the object.
2) For a function or function template, the definition provides the code body.
3) For a class or class template, the definition lists the member of the class  or templates.

e.g.

int x;                       // object definition
class ABC {           // class definition

private:
     int i;

}

template <typename T> struct XYZ {     // template definition

int i;

}

Initialization is the method of giving an object its first value. For objects generated from structs and classes, initialization is performed by constructors. Copy constructor is used to initialize an object with a different object of the same type.


References:

1) http://msdn.microsoft.com/en-us/library/sc8yf29y.aspx
2) Scott Meyers Effective C++ Chapter 0

Restricting the Copy constructor and assignment operator for a class object

Declare the copy constructor and copy assignment operator as private. By declaring a member function explicitly, you prevent compilers from generating their own version, and by making the functions private, you keep people from calling it.

Now the question comes, if we should declare them as protected or private. The advantage we get from declaring them private is that the error is generated at the compilation time and in case of the protected type access, it will be a linker time error.

So as Gopal says, earlier the better [:)]

Example follows:


class Base1 {

public:

        Base1():m_i(0) {}

private:
        Base1(const Base1&);
       Base1& operator=(const Base1&);

private:
        int m_i;
};

class Derived1 : public Base1 {

public:

Derived1():Base1(){}
Derived1(const Derived1& rhs):Base1(rhs) {}
Derived1& operator=(const Derived1& rhs){
   Base1::operator=(rhs);
}
};

int main ( void ) {

Base1 b1;
Derived1 d2;
Derived1 d1(d2);   // Compilation error here as base class copy constructor is private
return 0;
}

This will have compiler error.

If you declare the copy functions as protected, the linker error will be generated as follows:


/tmp/ccawBuy5.o: In function `Derived1::Derived1(Derived1 const&)':
test3.cpp:(.gnu.linkonce.t._ZN8Derived1C1ERKS_+0x14): undefined reference to `Base1::Base1(Base1 const&)'
collect2: ld returned 1 exit status

Access Specifiers Inheritance Behavior

BASE CLASS Member	Inheritance Type
	Public	Private	protected
Public	Public	Private	Protected
Private	Not possible	Not possible	Not possible
Protected	Protected	Private	Protected

Default Constructors

Default constructors are constructors that doesn't accept any arguments. User can provide the default constructor, if user doesn't provide the default constructor compiler can automatically generate one based on the program needs if the class doesn't contain any const and reference members

Below are the conditions in which compiler will generate default constructor

1) If the class has member objects that has default constructor
2) If the base class of the class has default constructor
3) If the class has any virtual functions
4) If the class is derived from virtual base class


Note:

If you explicitly provide a constructor to the class then compiler wont generate default constructor and destructor. Its the programmers responsibility to provide all the necessary constructors and destructors.

This is applicable to the copy constructors as well.

For e.g. :


class Base1 {

public:

Base1(const Base1&);
Base1& operator=(const Base1&);

private:
        int m_i;

};

int main () {

Base1 b;

}

This will throw compiler error:


test3.cpp:19: error: base `Base1' with only non-default constructor in class without a constructor
test3.cpp: In function `int main()':
test3.cpp:38: error: no matching function for call to `Base1::Base1()'
test3.cpp:10: note: candidates are: Base1::Base1(const Base1&)

References:

1) http://www.informit.com/guides/content.aspx?g=cplusplus&seqNum=363
2) Effective C++ by Scott Meyers