Can an interface extend another interface in Java?

Yes. Just remember that you should implement the methods in both interfaces.

Example in Java source code link1, link2:

public interface List<E> extends Collection<E> {

}

public interface Collection<E> extends Iterable<E> {

}

In conclusion, ref

An interface can extend multiple interfaces.

A class can implement multiple interfaces.

However, a class can only extend a single class.

a special case

interface A
{
    void test();
}

interface B 
{
    void test();
}

class C implements A, B
{
    @Override
    public void test() {

    }
}

Well, a single implementation works for the both methods. This implementation works no problem.

Question

link

整数的拆分问题

如，对于正整数n=6，可以拆分为：

6
5+1
4+2, 4+1+1
3+3, 3+2+1, 3+1+1+1
2+2+2, 2+2+1+1, 2+1+1+1+1
1+1+1+1+1+1+1

现在的问题是，对于给定的正整数n，程序输出该整数的拆分种类数(HDOJ 1028)。

Solution

This is very similar to another question I posted before: Coin Change Problem.

If n is total sum and k is the numbers being used, then:

q(n,k) = q(n,k-1) + q(n-k,k)

If i is the numbers used, and j is the total sum, the equation is:

dp[i][j] = dp[i-1][j] + dp[i][j-i]

(above 2 equations, k is same as i; and n is same as j)

Code

not written by me

int main(void) {  
    int n,i,j,dp[121][121];  
    for(i = 1 ; i < 121 ; ++i)  
    {  
        for(j = 1 ; j < 121 ; ++j)  
        {  
            if(i == 1 ||  j == 1)  
                dp[i][j] = 1;  
            else if(i > j)  
                dp[i][j] = dp[i][j-1] + dp[i-j][j];  
            else if(i == j)  
                dp[i][j] = dp[i][j-1] + 1;  
            else  
                dp[i][j] = dp[i][i];  
        }  
    }  

    while(scanf("%d",&n)!=EOF)  
    {  
        cout<<dp[n][n]<<endl;  
    }  
    return 0;  
}

Sometme I found the different concepts in Ruby very confusing for beginners. So I write this post to explain some terminologies in ruby setup.

RubyGems (tool)

RubyGems is a package manager for the Ruby programming language.

It is a tool to manage the installation of gems, and a server for distributing them.

RubyGems is very similar to apt-get, portage, and yum in functionality.

gem (command)

‘gem’ command allows you to interact with RubyGems. It is used build, upload, download, and install Gem packages.

Installation:

gem install mygem

Uninstallation:

gem uninstall mygem

Listing installed gems:

gem list --local

Listing available gems, e.g.:

gem list --remote

Gemfile (text file)

A Gemfile describes the gem dependencies required to execute associated Ruby code.

It is placed in the root of the directory containing the associated code.

A Gemfile is evaluated as Ruby code, in a context which makes available a number of methods used to describe the gem requirements.

gem (program)

ref1, ref2

A gem is a module/Library that you can install and use in every project on your server.

Each gem has a name, version, and platform. For example, rake gem has a 10.3.2 version on platform Ruby.

Inside a gems are the following components:

1. Code (including tests and supporting utilities)
2. Documentation
3. gemspec

Standard code structure:

% tree freewill
freewill/
├── bin/
│   └── freewill
├── lib/
│   └── freewill.rb
├── test/
│   └── test_freewill.rb
├── README
├── Rakefile
└── freewill.gemspec

Bundler (dependency manager)

ref

Bundler manages an application’s dependencies.

Bundler provides a consistent environment for Ruby projects by tracking and installing the exact gems and versions that are needed.

Question

link

Given an array of positive numbers, find the maximum sum of a subsequence that no 2 numbers should be adjacent.

Eg. (3, 2, 7, 10) should return 13 (3+10)

Eg. (3, 2, 5, 10, 7) should return 15 (3+5+7).

Solution

It is an modified version of “max sum subsequence”. Answer given on gfg is:

Loop for all elements in arr[] and maintain two sums ‘incl’ and ‘excl’ where:

incl = Max sum including the previous element

excl = Max sum excluding the previous element

Code

written by me

public int solve(int[] A) {
    if (A == null || A.length == 0) {
        return 0;
    } else if (A.length == 1) {
        return A[0];
    } else if (A.length == 2) {
        return Math.max(A[0], A[1]);
    }

    // prePreMax is the max non-adjacency sequence ending 2 position ahead
    // preMax is the max non-adjacency sequence ending 1 position ahead
    int prePreMax = A[0];
    int preMax = A[1];
    int ans = 0;

    for (int i = 2; i < A.length; i++) {
        ans = Math.max(ans, prePreMax + A[i]);
        // set the 2 variables: prePreMax, preMax
        int temp = preMax;
        preMax = Math.max(0, prePreMax + A[i]);
        prePreMax = Math.max(prePreMax, temp);
    }
    return ans;
}

Overview

Polymorphism is to use common interface instead of concrete implementation while coding.

The most common use of polymorphism in OOP occurs when a parent class reference is used to refer to a child class object.

Quick Summary:

ref

1. A subclass instance can be assigned to a superclass' reference.

2. Once substituted, we can invoke methods defined in super-class; we CANNOT invoke methods from sub-class.

3. if sub-class overrides inherited methods from the super-class, the overridden versions will be invoked.

4. Reference cannot point to superclass.

Advantages

1. Simpler programs

   eg. superRef[] = new Circle[2]; superRef[0] = new Cylinder(); superRef[1] = new Circle();

   Just 1 single array to represent different objects

2. Better re-usability

A practical example

Cylinder is a subclass of Circle. We gonna do this:

Circle c1 = new Cylinder();

The code is below:

public class PolymorphismSubstitutabilityDemo {

    public static void main(String[] args) {
        Circle c1 = new Cylinder(1, "white", 10);
        System.out.println(c1.getClass());
        System.out.println(c1.getRadius());
        System.out.println(c1.getArea());
    }
}

class Circle {
    int radius;
    String color;

    public Circle(int a, String b) {
        this.radius = a;
        this.color = b;
    }

    public int getRadius() {
        return radius;
    }

    public double getArea() {
        return 3.14159 * Math.pow(radius, 2);
    }
}

class Cylinder extends Circle {
    int height;

    public Cylinder(int a, String b, int c) {
        super(a, b);
        this.height = c;
    }

    public double getArea() {
        return super.getArea() * height;
    }
}

The output of execution:

class Cylinder
1
31.4159

Question

DLL - link

Inorder - link

Given a BST, write a function that returns true if there is a triplet that sums to 0, returns false otherwise.

Solution

We will solve the question just like we do [LeetCode 15] 3Sum. What is missing is an random access of tree nodes.

In fact, we do not need random access. Tree traversal (one after another in sequence) would be good enough.

Now there’re 2 solution. First is to convert the tree to Double-linked list, then do 3Sum. The conversion takes O(n) time and O(logn) extra space, and 3Sum take O(n²). however doing this modifies the original tree.

Second solution is to to inorder traversal and reversed inorder traversal. For me, this solution is preferred. Time and space used is same.

Code

DLL way, written by me

public void findTriplet(TreeNode root, int target) {
    TreeNode[] dll = convertToDll(root);
    TreeNode head = dll[0];
    TreeNode tail = dll[1];
    // note that the bst inorder dll should already in sorted by value
    TreeNode first = head;
    while (first.right != null) {
        TreeNode left = first.right;
        TreeNode right = tail;
        while (left.val < right.val) {
            int diff = first.val + left.val + right.val - target;
            if (diff == 0) {
                System.out.println("Found triplet: " + first.val + " "
                        + left.val + " " + right.val + " for sum of "
                        + target);
            }
            if (diff <= 0) {
                left = left.right;
            }
            if (diff >= 0) {
                right = right.left;
            }
        }
        first = first.right;
    }
}

private TreeNode[] convertToDll(TreeNode node) {
    TreeNode[] ans = new TreeNode[2];
    // do the left side of node
    if (node.left == null) {
        ans[0] = node;
    } else {
        TreeNode[] preAns = convertToDll(node.left);
        ans[0] = preAns[0];
        node.left = preAns[1];
        preAns[1].right = node;
    }
    // do the right side of node
    if (node.right == null) {
        ans[1] = node;
    } else {
        TreeNode[] postAns = convertToDll(node.right);
        ans[1] = postAns[1];
        node.right = postAns[0];
        postAns[0].left = node;
    }
    return ans;
}

inorder way - basically is just iterator of binary tree.

Question

link

In a 2D matrix of dimensions M*N, find number of “equilibrium” points. A point (i, j) is said to be an “equilibrium” point only if all following conditions hold:

a) sum of rows 1…(i-1) = sum of rows (i+1)…M

b) sum of columns 1…(j-1) = sum of columns (j+1)…N

Solution

This is a generalize question of Equilibrium index.

Refer to Equilibrium index, read this. The idea is to get total sum of array first. Then Iterate through the array calculate left sum == sum / 2.

Equilibrium index of an array is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes. For example, in an arrya A:

A[0] = -7, A[1] = 1, A[2] = 5, A[3] = 2, A[4] = -4, A[5] = 3, A[6]=0

3 is an equilibrium index, because: A[0] + A[1] + A[2] = A[4] + A[5] + A[6]

6 is also an equilibrium index, because sum of zero elements is zero, i.e., A[0] + A[1] + A[2] + A[3] + A[4] + A[5]=0

Well, for Equilibrium Points in 2D Array, should be similar. DIY and leave me a comment!

Code

code for findning EI in 1-D array

public List<Integer> findEI(int[] array) {
    List<Integer> ans = new ArrayList<Integer>();
    int sum = 0;
    for (int i = 0; i < array.length; i++) {
        sum += array[i];
    }
    int runningSum = 0;
    for (int i = 0; i < array.length; i++) {
        if (2 * runningSum + array[i] == sum) {
            ans.add(i);
        }
        runningSum += array[i];
    }
    return ans;
}

Question

link

Given a binary tree, print it vertically. The following example illustrates vertical order traversal.

           1
        /    \
       2      3
      / \    / \
     4   5  6   7
             \   \
              8   9 

The output of print this tree vertically will be:
4
2
1 5 6
3 8
7
9 

Solution

1. Traverse the tree once and get the minimum and maximum horizontal distance with respect to root.

2. Iterate the tree and for each vertical line, fill in the values.

Now, getting the width of tree requires O(n) time. And entire solution is O(n) using a HashMap.

Code

public List<List<Integer>> printVertically(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    // 1. find the range of left bound and right bound
    int[] range = new int[2];
    findRange(root, range, 0);

    // 2. calculate number of columns in the result
    int rootIndex = 0 - range[0];
    int columns = range[1] - range[0] + 1;
    for (int i = 0; i < columns; i++) {
        ans.add(new ArrayList<Integer>());
    }

    // 3. fill in vertically in a recursive manner
    fillNode(ans, root, rootIndex);

    return ans;
}

private void fillNode(List<List<Integer>> ans, TreeNode node, int index) {
    if (node == null) {
        return;
    }
    ans.get(index).add(node.val);
    fillNode(ans, node.left, index - 1);
    fillNode(ans, node.right, index + 1);
}

private void findRange(TreeNode node, int[] range, int position) {
    if (node == null) {
        return;
    }
    if (position < range[0]) {
        range[0] = position;
    }
    if (position > range[1]) {
        range[1] = position;
    }
    findRange(node.left, range, position - 1);
    findRange(node.right, range, position + 1);
}

Question

link

Suppose N patients and M diseases. N is sufficiently large number and M is relatively small, say 30-ish. Each patient can have possible 0 to M kinds of diseases.

Given one patient’s name, show me a list of similar patients sharing same deseases within 2-3 seconds.

Solution

Use 1 bit to represent a disease. So every patient’s conditin can be put into an integer of 32 bits.

How do we calculate the similarity of 2 patients?

Refer to [CC150v5] 5.5 Calculate Bits Conversion Required for a special bit operation (remove last ‘1’ from bit):

c = c & (c - l) clears the least significant bit of ‘1’.

Keep doing this until all ‘1’s are cleared.

For each patient, we simply calculate the XOR and count ‘1’s.

Code

no code.

Question

link, MIT handouts Person_A

Describe an algorithm that takes an unsorted array of axis-aligned rectangles and returns any pair of rectangles that overlaps, if there is such a pair.

Axis-aligned means that all the rectangle sides are either parallel or perpendicular to the x- and y-axis.

Each rectangle object has two variables: the x-y coordinates of the upper-left corner and the bottom-right corner.

Analysis

A lot of different solutions on the internet, example 1 and example 2, and some questions asks you to return all overlapping pairs. For now, we just return any pair that overlaps.

Solution

I concluded some solution and come up with this (the idea of BST is covered in the end of this pdf):

1. Sort the input by left edge.
2. One by one, get one rectangle from the sorted input, and make a pair (rect.top, rect.bottom).
3. Insert this pair into a Interval Search Tree.
4. This tree is a BST, and use first value of the pair as BST key.
5. Insert pair at the correct BST location. If conflicts, we’ve found 1 overlapping pair.

The code for searching a intersect, and insert a pair looks like this:

Node x = root;
while (x != null) {
    if (x.interval.intersects(lo, hi)) 
        return x.interval;
    else if (x.left == null)  x = x.right;
    else if (x.left.max < lo) x = x.right;
    else                      x = x.left;
}
return null;