Abstract class v.s. Interface in Java

The difference between abstract class and interface is frequently asked in interviews.

Characteristics of abstract class 

1.Both abstract class and abstract method needs to be declared with 「abstract」

2.Using「new」to generate object on abstract class is not allowed.

3.Abstract class needs declaration but not necessary to be implemented.

4.The derived class needs to implement the abstract method in the base class. 

Otherwise it's merely another abstract class.

 abstract class Shape{

      String name;
      double length, width, heigh;
      double radius;

      abstract double area();            // calculate area
      abstract double perimeter();    // calculate perimeter

      // In abstract class, constructor is allowed. For quardrangle
      public Shape(double length, double width, String name){
            this.length = length;
            this.width = width;
            this.name = name;
      }
      
      // For triangle
      public Shape(String name, double width, double height){
            this.height = height;
            this.width = width;
            this.name = name;
      }
}


class Rectangular extends Shape{      
     public Rectangular(double length, double width, String name){
            super(length, width, name);     //use super to call constructor of base class
     } 

     //Area and perimeter functions need to be implemented.
     double area(){     
            return length * width;
     } 
    
     double perimeter(){
            return (length + width) * 2; 
     }
} 

class EqualTriangle extends Shape{      //Triangle
      public EqualTrangle(String name, double width, double height){
              super(name, width, height);
      } 

      double area(){
            return (width * height) / 2 ;
     } 
    
     double perimeter(){
            return 3 * width; 
     }
}

Characteristics of interface

1.No constructor in the interface.

2.All the data members need to be initiated

3.The parameters need to be declared  as public and final,or static.

4.Abstract methods need to be public or abstract.

interface Shape {
    public double Shape_PI = 3.14;
     
    public double area();
    public double perimeter();
}
 
class Circle implements Shape {
    private double radius;
     
    public Circle(double r) {
        setRadius(r);
    }
     
    public Circle() {
        this(10.0);
    }
     
    public double getRadius() {
        return radius;
    }
     
    public void setRadius(double r) {
        if (r > 0.0) {
            radius = r;
        }
        else {
            radius = 1;
        }
    }
     
    public double area() {
        return radius * radius * Shape_PI;
    }
     
    public double perimeter() {
        return 2 * radius * Shape_PI;
    } 
}
 
class Rectangle implements Shape {
    private double length;
    private double width;
     
    public Rectangle(double l, double w) {
        setLength(l);
        setWidth(w);
    }
     
    public Rectangle(double a) {
        this(a, 10.0);
    }
     
    public Rectangle() {
        this(10.0, 10.0);
    }
     
    public double getLength() {
        return length;
    }
     
    public double getWidth() {
        return width;
    }
     
    public void setLength(double l) {
        if (l > 0) {
            length = l;
        }
        else {
            length = 1.0;
        }
    }
     
    public void setWidth(double w) {
        if (w > 0) {
            width = w;
        }
        else {
            width = 1.0;
        }
    }
     
    public double area() {
        return length * width;
    }
     
    public double perimeter() {
        return 2 * (length + width);
    }
}




Note to avoid confusion
1. Class in java can only inherit one base class.
(While in C++, multi-inheritance of class is supported but not recommended) 
2. Interface can do multi-inheritance on interfaces.
3. Class can implements multiple interfaces. 

When to use abstract class or interface ?

It's been widely discussed for long time about when to user abstract class or interface.As for me, I will intend to use abstract class and inheritance to describe the characteristic of the class.And I will use interface to define functions that can represent the capability or behavior of it. That's my principle,depending on the project,developers can have their own style or principles to use abstract class and interface flexibly.

Read More

Leetcode-Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree 

in which the depth of the two subtrees of every node never differ by more than 1.

=======================================================================

Solution :

The Top-down solution is to check all the sub tress from the root whether

the difference of the two sub tress more than 1.

class solution {
public:
    int depth (TreeNode *root) {
        if (root == NULL) return 0;
        return max (depth(root -> left), depth (root -> right)) + 1;
    }

    bool isBalanced (TreeNode *root) {
        if (root == NULL) return true;
        
        int left=depth(root->left);
        int right=depth(root->right);
        
        return abs(left - right) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }
};

Read More

Quicksort-instant reveiw

You may checked this video to see how quicksort is working.

There are many similar forms of quicksort.

You can randomly choose one pivot or two pivot to go while the code below only

deals with the single pivot case. Like the video, we burn the the candle from one side.

1. Candle burned from one side

1. void quick_sort(int array[], int left, int right)
2. {
3.     if (left < right)
4.     {
5.         // divide (partition)
6.         int pivot = array[(left+right)/2];  
7.       // Can choose any number you want
8.         swap(array[right], array[(left+right)/2]);
9.       // to the rightmost
10.         int i = left, j = left;
11.         for (; j < right; ++j)
12.             if (array[j] <= pivot)
13.             {
14.                 if (i < j) swap(array[i], array[j]);    
15.                 i = i + 1;
16.             }
17.         if (i < right) swap(array[i], array[right]);   
18.  
19.         // then conquer
20.         quick_sort(array, left, i-1);
21.         quick_sort(array, i+1, right);
22.  
23.         // no need to combine sub-solutions
24.     }
25. }

Read More

Leetcode-Swap nodes in pair

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Subscribe to see which companies asked this question

----------------------------------------------------------------------------------------

Solution:

The dummy node is used to keep the swap_pair function work in consistent way at the 

very beginning. In other words, to satisfy the function at the very first initialization state.

Noted that we need to pass the pointer by reference so that the structure 

of the list will actually change.

class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        head = dummy;
        while(head) head = swapNodes(head->next);
        head = dummy->next;
        delete dummy;
        return head;
    }
    
    ListNode *swapNodes(ListNode *&head) {
        if(!head || !head->next) return NULL;
        ListNode *tail = head;
        ListNode *nextHead = head->next->next;
        head = head->next;
        head->next = tail;
        tail->next = nextHead;
        return tail;
    }
};

Read More

Indeed interview-Reverse string but let the html entity remain unchanged

One of the popular interview questions of Indeed

is to reverse the string but let the html entity remain unchanged.

For example :

The result of  "123&TWD;432&JPY;"should be &TWD;234&JPY;321


Solution: What we need to do is store the entities and insert them into the reversed string.

Read More

Leetcode--Excel Sheet Column Title

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 

Solution:

This is a 26-ary system. However if we use 1-26. 26 can not be consistent with other numbers ahead.

For example: 25/26=0, but 26/26=1. So we need to apply 0-based policy in this problem.

Each number from 1-26 minuses 1 to conform A-Z. But new problems occur, AA should be 27

orginally, 27-1=26, 26%26=0. This is incorrect. So every number should minus 1 in each loop to

make sure it's 0-based.

1. class Solution {
2. public:
3.     string convertToTitle(int n) {
4.        
5.         string ans;
6.         while (n--!= 0) {
7.             ans = char(int('A') + n % 26) + ans;
8.             n /= 26;
9.         }
10.         return ans;
11.  
12.     }
13. };

Read More

Leetcode-Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:

• Each element in the result must be unique.
• The result can be in any order.

Solution : 

The idea to solve this problem is quite simple.  We can just move all the elements of nums1 to one

container then check every element in nums2 to derive the result. Noted that the result should not 

contain duplicate values. So we can use SET in STL to accomplish this work since the set will ignore

the duplicate values when adding new elements into it.

1. class Solution {
2. public:
3.     vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
4.        
5.         set<int> SET (nums1.begin(),nums1.end());
6.         set<int> result;
7.        
8.         for(auto i:nums2)
9.             if(SET.count(i)) result.insert(i);
10.        
11.         return vector<int>(result.begin(), result.end());
12.        
13.     }
14. };

Read More

Leetcode--Summary Range

Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].

Solution: 

We can use two pointers to record the start and the end of each range.

1. class Solution {
2. public:
3.     vector<string> summaryRanges(vector<int>& nums) {
4.        
5.        
6.         vector<string> result;
7.        
8.         int n = nums.size();
9.         if(n == 0)return result;
10.         if(n == 1){
11.              result.push_back(to_string(nums[0]));
12.              return result;
13.         }
14.        
15.         int start=nums[0];
16.         int end=nums[0];
17.  
18.        
19.        for(int i = 0; i < n;){
20.              
21.             while( i+1 < n && nums[i+1] == end + 1){
22.                 end++;
23.                 i++;
24.             }
25.             if(start != end){
26.                 result.push_back(to_string(start) + "->" + to_string(end));
27.             }
28.             else{
29.                 result.push_back(to_string(start));
30.             }
31.            
32.             i++;
33.             start = end = nums[i];
34.            
35.         }
36.        
37.         return result;
38.  
39.     }
40. };

Read More