First Word

A multilayered software architecture is a software architecture that uses many layers for allocating the different responsibilities of a software product.

Layers

1. Presentation layer
   1. UI layer, view layer
   2. presentation tier in multitier architecture
2. Application layer
   1. also called service layer/GRASP Controller Layer
3. Business layer
   1. also called business logic layer/domain layer
4. Infrastructure layer
   1. data access layer/persistence layer
   2. logging, networking, and other services which are required to support a particular business layer

Conventions

Application layer (or service layer) is sometimes considered a sublayer of business layer.

If there’s no explicit distinction between first 3 tiers, then it’s a traditional client-server(two-tier) model.

The application/business layers can, in fact, be further subdivided to emphasize distinct responsibility (eg. MVC).

Sometimes there’s business infrastructure layer(BI), located between the business layer and infrastructure layer.

Infrastructure layer can be partitioned into different levels (high-level or low-level). Developers focus on only the persistence capabilities, therefore only talk about persistence layer or data access layer.

Question

link

Design a web application to represent hierarchy of solar system.

Give details of Persistence layer, business layer, presentation layer and Client-server protocol.

Solution

First, OOD part is very well covered in this site. There’re 2 abstract class: OrbitalSystem, where ‘Star/Sun’ is an instance, and GravityObject, where ‘Planet/Earch’ is an instance. Though this does not take satellite into consideration.

Second, the multi-layer structure. It’s cover in another post Multilayered architecture

Third, the protocol. We use HTTP protocol, because:

HTTP(S) is the best protocol to use. The overhead (i.e. headers) is pretty small, the transfer can be gzipped, the connection can be secured (via SSL). Also, ports 80 (HTTP) and 443 (HTTPS) will be open in 99% of cases. Other ports are not – for example some carriers block all other ports unless you pay extra.

More info on HTTP communication comes later.

Code

from here

public abstract class GravityObject {
    double xPosition;
    double yPosition;
    double degreeInOrbit;
    double distanceFromParent;

    GravityObject() {
    this.distance = 0;
    }

    GravityObject(double distance) {
    this.distance = distance;
    }
}

import java.util.ArrayList;

public abstract class OrbitalSystem extends GravityObject {
    private ArrayList children = new ArrayList(); // Objects within the system. They will orbit the parent.

    public void add(GravityObject child) { children.add(child); }

    public void tick() {
        for (int x = 0; x < children.size(); x++) {
            GravityObject current = children.get(x);
            current.degree += 1
            current.xPosition = this.xPosition + Math.cos(degree/180 * Math.PI)* current.distance;
            current.yPosition = this.yPosition - Math.sin(degree/180 * Math.PI) * current.distance;
        }
    }
}

public class Star extends OrbitalSystem { 

};

public class Planet extends GravityObject { 

};

public static int main(String[] args) {
    Star s = new Star(); // Create a new star.
    s.add(new Planet(20)); // Add a planet to the star's orbital system which orbits at a distance of 20 units.
    s.add(new Planet(66)); // Add another planet to the star's orbital system which orbits at a distance of 66 units.

    while (true) {
        s.tick();
    }
}

Question

link

Given a NxN matrix which contains all distinct 1 to n² numbers, write code to print sequence of increasing adjacent sequential numbers.

ex: 
1 5 9 
2 3 8 
4 6 7 

should print: 6 7 8 9

Solution

Make an array of booleans (or bits) of same size as the input, where arr[i-1] indicates whether i is adjacent to i+1. Then, iterate over the matrix, checking for each cell the four neighbors and populating the relevant entry in the boolean array.

Last, look for the longest run of “true” values in the boolean array, which can be done with one pass. O(n) time.

Note that this algorithm is valid only if input integers are distinct, which is true here.

Code

not written

Question

link

Output top N positive integer in string comparison order. For example, let’s say N=1000, then you need to output in string comparison order as below:

1, 10, 100, 1000, 101, 102, … 109, 11, 110, … 998, 999.

Solution

Thought for a while, and realize it’s stanard DFS.

Code

written by me

public static void main(String args[]) {
    for (int i = 1; i < 10; i++) {
        dfs("" + i);
    }
}

public static void dfs(String path) {
    if (Integer.parseInt(path) > 1000) {
        return;
    }
    System.out.println(path);
    for (int i = 0; i < 10; i++) {
        dfs(path + i);
    }
}

Question

link

Given an array, generate a random permutation of array elements.

Solution

O(n) time complexity.

To shuffle an array a of n elements (indices 0..n-1):
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

Note the RNG is having limit from 0 to i, and number i keeps decreasing.

Proof

This is called Fisher–Yates shuffle. Proof can be seen at question post:

The probability that ith element goes to second last position can be proved to be 1/n by dividing it in two cases.

Case 1: i = n-1 (index of last element):

The probability of last element going to second last position is = (probability that last element doesn’t stay at its original position) x (probability that the index picked in previous step is picked again so that the last element is swapped)

So the probability = ((n-1)/n) x (1/(n-1)) = 1/n

Case 2: 0 < i < n-1 (index of non-last):

The probability of ith element going to second position = (probability that ith element is not picked in previous iteration) x (probability that ith element is picked in this iteration)

So the probability = ((n-1)/n) x (1/(n-1)) = 1/n

We can easily generalize above proof for any other position.

Updated on Sep 10th, 2014: analysis of the approach. This question is on CC150v4 Q20.2.

Note that when we generate a new number between 0 and i, we swap it (with the last ‘alive’ number (ith number). After this, ith number is ‘dead’.

By doing it this way, we get a perfect shuffle! Idea is from cc150.

Updated again on Oct 2nd, 2014: I re-wrote the code for CC150v5 Q18.2. It’s very important to note that:

if (a == b) {
    return;
}

When a == b, do not swap, otherwise the XOR swap method will product an zero!

Code

code form G4G, link

def sattoloCycle(items):
    i = len(items)
    while i > 1:
        i = i - 1
        j = randrange(i)  # 0 <= j <= i-1
        items[j], items[i] = items[i], items[j]
    return

written by me

public static void shuffleArrayInteratively(int[] cards) {
    for (int i = 0; i < cards.length; i++) {
        // all nums to the left of (i) is 'dead', don't consider them
        int choose = rand(i, cards.length - 1);
        swap(cards, i, choose);
        // now (i) is also 'dead'
    }
}

private static int rand(int from, int to) {
    int count = to - from + 1;
    return from + (int) (Math.random() * count);
}

private static void swap(int[] nums, int a, int b) {
    if (a == b) {
        return;
    }
    nums[a] ^= nums[b];
    nums[b] ^= nums[a];
    nums[a] ^= nums[b];
}

Question

link

Can we overriding private method in Java?

Analysis

Overriding private methods in Java is invalid because a parent class’s private methods are “automatically final, and hidden from the derived class”. source

Solution

You can’t override a private method, but you can introduce one in a derived class without a problem. Read more below.

Code

not a problem

public class OverridePrivateMethod {
    private void foo() {
    }
}

class Child extends OverridePrivateMethod {
    private void foo() {
    }
}

add @Override annotation and get error

public class OverridePrivateMethod {
    private void foo() {
    }
}

class Child extends OverridePrivateMethod {
    @Override
    private void foo() {
    }
}

Question

link

Given a 2D array, find the maximum sum subarray in it. For example, in the following 2D array, the maximum sum subarray is highlighted with blue rectangle and sum of this subarray is 29.

Analysis

Note that this is a difficult(and high-frequency) question.

Try convert this question to “max sum in 1D array” by sum up all numbers in the same column. (we know that in 1D array, the algo runs O(n) time)

There’s in total O(n²) combinations of ways to sum up a column. So the total time complexity is O(n³).

Solution

1. Traverse matrix at row level.

2. have a temporary 1-D array and initialize all members as 0.

3. For each row do following

   1. add value in temporary array for all rows below current row
   2. apply 1-D kadane on temporary array
   3. if your current result is greater than current maximum sum, update.

Code

written by me

public int maxSum(int[][] A) {
    int m = A.length;
    int n = A[0].length;
    int maxResult = Integer.MIN_VALUE;
    for (int i = 0; i < m; i++) {
        int[] temp = new int[n];
        for (int j = i; j < m; j++) {
            // from row#i to row#(m-1), add the number into temp[]
            for (int k = 0; k < n; k++) {
                temp[k] += A[j][k];
            }
            // find max sum for 1D array
            maxResult = Math.max(maxResult, maxSum(temp));
        }
    }
    return maxResult;
}

private int maxSum(int[] B) {
    int sumSoFar = 0;
    int maxSum = Integer.MIN_VALUE;
    for (int i = 0; i < B.length; i++) {
        maxSum = Math.max(maxSum, sumSoFar + B[i]);
        sumSoFar = Math.max(0, sumSoFar + B[i]);
    }
    return maxSum;
}

Question

link

We have an array of 2n elements like “a1 a2…an b1 b2…bn”. WAP to rearrange the array as “a1 b1 a2 b2…an bn”

time complexity is O(n) no extra array or memory can be taken.

Input : 1 2 3 4 5 6 7 8 9 10 11 12 (even number input)

Output: 1 7 2 8 3 9 4 10 5 11 6 12

Input : 1 2 3 4 5 6 7 (odd number input)

Output: 1 5 2 6 3 7 4

Analysis

This is a difficult question.

I did not find enough resources online, but have come up with 2 solutions.

Solution

First is like bubble sort (read it somewhere before). Always swap in pairs (starting from the middle):

1st: 1 2 3 4 5 6 7
2nd: 1 2 3 5 4 6 7
3rd: 1 2 5 3 6 4 7
4th: 1 5 2 6 3 7 4
done

Second solution is to swap in cycles (put current value in its ‘successor’ position, and continue from there). But in order to identify cycles, additional space is used. I wrote the solution making use of ‘visited’ array. The time complexity is between O(n) and O(n²).

More info on this topic can be found on wikipedia.

Code

written by me

public void rearrange(int[] A) {
    int effLength = A.length;
    if (A.length % 2 == 0) {
        // for even number of input, last element is unchanged
        effLength--;
    }
    // make sure 'effLength' is an odd number.
    int half = effLength / 2 + 1;
    int pos = 1;
    int posValue = A[pos];
    int numSwaps = 0;
    boolean[] visited = new boolean[effLength];
    // visited is used as flag to avoid repeat swap
    // eg. when input is { 1, 2, 3, 4, 5, 6, 7 }, repeat swap as below:
    // 2 -> 3 -> 5 -> 2 -> 3 ...
    while (numSwaps < effLength - 1) {
        // swap (effLength - 1) times because 1st position is unchanged
        int newPos = getNewPosition(A, pos, half);
        if (visited[newPos]) {
            // if this new position is swap already, skip it
            pos = (pos + 1) % effLength;
            posValue = A[pos];
            continue;
        }
        int temp = A[newPos];
        A[newPos] = posValue;
        posValue = temp;
        pos = newPos;

        visited[newPos] = true;
        numSwaps++;
    }
}

private int getNewPosition(int[] array, int pos, int half) {
    if (pos < half) {
        return 2 * pos;
    } else {
        return 2 * (pos - half) + 1;
    }
}

Question

link

You are given a string like “aaaabbbcc”, do an in place conversion which write frequency of each charater(which come continuosly) with that character.

Example:

input: aaabbbcc

output: a3b2c2

Solution

The most important point is whether or not you find the special cases, and did you clarify how to handle them.

First special case is only 1 character, should you append a ‘1’ or not. Note that this question requires ‘in place’ conversion. So ‘1’ is not supposed to be appended after single-occurance character. This is really important to know, if the question does not specify. (though sometimes, the question asks you to apppend a ‘1’, eg. here).

Second case is when occurance >= 10. We could not simply append (‘0’ + numberOfOccurance), because the number could be 12. This is another very important case to take note.

The code can be seen anywhere.

Question

link

How many points are there on the globe where, by walking one mile south, one mile east, and one mile north, you reach the place where you started?

Solution

One point in the North Pole, and many circles in the South Pole.

Read more at question post.