Question

link

Given two (dictionary) words as Strings, determine if they are isomorphic.

Two words are called isomorphic if the letters in one word can be remapped to get the second word. Remapping a letter means replacing all occurrences of it with another letter while the ordering of the letters remains unchanged. No two letters may map to the same letter, but a letter may map to itself.

Example:

given "foo", "app"; returns true 
we can map 'f' -> 'a' and 'o' -> 'p' 

given "bar", "foo"; returns false 
we can't map both 'a' and 'r' to 'o' 

given "turtle", "tletur"; returns true 
we can map 't' -> 't', 'u' -> 'l', 'r' -> 'e', 'l' -> 'u', 'e' -'r' 

given "ab", "ca"; returns true 
we can map 'a' -> 'c', 'b'

Solution

My first thought was: map char to char, then check in the hashmap. However, this will not work!

input: abc, pzz
check a -> p
check b -> z
check c -> z

Using a hashmap does not show us whether 2 chars match to the same char__. In above example, b and c both match to z.

Best Solution, suggested by urik:

HashMap (char, firstSeenIndice) for each string. The encoding of firstSeenIndices shud match.

E.g. Foo and app both encode to 011

Abcd and hole both encode to 0123

Code

public boolean isomorphic(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    return (sequence(s).equals(sequence(t)));
}

private String sequence(String s) {
    HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    StringBuilder sb = new StringBuilder();

    for (int i = 0; i < s.length(); i++) {
        if (map.containsKey(s.charAt(i))) {
            sb.append(map.get(s.charAt(i)));
        } else {
            map.put(s.charAt(i), i);
        }
    }
    return sb.toString();
}

Overview

A Web server exclusively handles HTTP requests, whereas an application server serves business logic to application programs through any number of protocols (including HTTP).

Example: Apache Tomcat

web server + servlet container

Example: Glassfish

application server (that supports EJB, JSF, JSP and servlets)

Apache Tomcat

Apache Tomcat is a web server and a Web container/Servlet container/JSP container (having all these names). It is used for strictly web-based applications but does not include the entire suite of capabilities of Java EE, thus not application server.

Note: Tomcat is web container where as Apache is web server.

Servlet

A servlet is a small Java program that runs within a Web server. Servlets receive and respond to requests from Web clients, usually across HTTP.

Glassfish

Tomcat is not Java EE container, but only a servlet container. If you plan to use full Java EE (which includes security and many other things), you have to switch from Tomcat to some of full Java EE application servers. Glassfish is one of them, others are TomEE, WildFly, IBM Websphere, Oracle Weblogic etc.

Web application

A Web application runs within a Web container of a Web server. The Web container provides the runtime environment through components that provide naming context and life cycle management. A Web server may work with an EJB server to provide some of those services.

Web applications are composed of web components and other data such as HTML pages. Web components can be servlets, JSP pages created with the JavaServer Pages™ technology, web filters, and web event listeners. These components execute in a web server and may respond to HTTP requests from web clients.

Application server VS. Web server, in short

Web server just serves the web pages and it cannot enforce any application logic.

Application server maintains the application logic and serves the web pages in response to user request.

That means application server can do both application logic maintanence and web page serving.

Final conclusion: Application server also contains the web server.

Application server = Web Server + EJB container.

Web server Detail

A Web server handles the HTTP protocol. When the Web server receives an HTTP request, it responds with an HTTP response, such as sending back an HTML page.

To process a request, a Web server may respond with a static HTML page, or delegate the dynamic response such as CGI scripts, JSPs (JavaServer Pages), servlets, ASPs (Active Server Pages), server-side JavaScripts, or some other server-side technology.

Web server is used only for Jsp and Servlets and static functionality. It doesn’t support EJB and JMS and JAAS.

Application server Detail

An Application server exposes business logic to client applications through various protocols, possibly including HTTP. The clients can include GUIs (graphical user interface) running on a PC, a Web server, or even other application servers.

In most cases, the server exposes this business logic through a component API, such as the EJB (Enterprise JavaBean) component model found on J2EE (Java 2 Platform, Enterprise Edition) application servers.

Example

There’s a nice example: online store that provides real-time pricing.

Scenario 1: Web server

The Web server takes your request, then passes it to a server-side program able to handle the request. The server-side program looks up the pricing information from a database or a flat file. Once retrieved, the server-side program uses the information to formulate the HTML response, then the Web server sends it back to your Web browser.

To summarize, a Web server simply processes HTTP requests by responding with HTML pages.

Scenario 2: Web server with an application server

Scenario 2 resembles Scenario 1 in that the Web server still delegates the response generation to a script. However, you can now put the business logic for the pricing lookup onto an application server.

With that change, instead of the script knowing how to look up the data and formulate a response, the script can simply call the application server’s lookup service. The script can then use the service’s result when the script generates its HTML response.

In this scenario, the application server serves the business logic for looking up a product’s pricing information. That functionality doesn’t say anything about display or how the client must use the information. Instead, the client and application server send data back and forth. When a client calls the application server’s lookup service, the service simply looks up the information and returns it to the client.

By separating the pricing logic from the HTML response-generating code, the pricing logic becomes far more reusable between applications. A second client, such as a cash register, could also call the same service as a clerk checks out a customer. In contrast, in Scenario 1 the pricing lookup service is not reusable because the information is embedded within the HTML page. To summarize, in Scenario 2’s model, the Web server handles HTTP requests by replying with an HTML page while the application server serves application logic by processing pricing and availability requests.

Easy version

[Q] Design a layer in front of a system which cache the last n requests and the responses to them from the system.

Solution:

[a] When a request comes look it up in the cache and if it hits then return the response from here and do not pass the request to the system

[b] If the request is not found in the cache then pass it on to the system

[c] Since cache can only store the last n requests, Insert the n+1th request in the cache and delete one of the older requests from the cache

[d]Design one cache such that all operations can be done in O(1) – lookup, delete and insert.

Distributed Cache

Question

link

Calculate the number of slices. Slice means that the difference between the maximum and minimum in the slice <= 2.

eg. Given array 3 5 7 6 3.

There’re 10: (0,0) (1,1) (2,2) (3,3) (4,4) (5,5) (0,1) (1,2) (1,3) (2,3).

Solution

If only asked to output the total number of such slices, we can do it in O(n) using sliding-window-like algorithm, with the help of addtional queue-like data structure.

This is a very difficult question! Quoted from the top answer:

The basic idea is that you can start with arr[0] and then see how many more elements you can include before you violate the max -min <= K constraint. When you reach some index j you can no longer include, you know the maximum subarray starting at index 0 is arr[0…j-1], and you can count j different subarrays there.

… you then start with a[1]. Now [1…j-1] has to be valid, so you try to advance the right boundary again (try arr[1…j], then arr[1…j+1]) and so on until again you reach a point past which you can’t advance. Then you’ll try string at a[2], and so on. This is what they mean when they talk about “crawling” over the array.

The key issue here is how you will check whether a particular subarray is valid efficiently…

Sliding window is explained above. Now, the minMaxQueue explain in this pdf:

The PDF … have 1 queue each (i.e. 2 queues in total) for min and max (the min is treated analogous to the max case).

For maxQueue, whenever a new value comes in the max queue, they remove all values less than the value, since those can never be the max. For that reason the queue’s values are in descending order. And the max at any given time is the first element.

In this way, getting min/max is O(1), thus entire solution is O(n). Nice question!

Code

Not written.

Spanner

Spanner is Google’s globally distributed NewSQL database, the successor to BigTable. Google describes Spanner as not a pure relational system because each table must have a primary-key column.

Currently, F1, Google’s advertisement platform, uses Spanner. Gmail and Google Search will also use it soon.

NewSQL VS. NoSQL

NewSQL, a wholly different database architecture, differentiated from NoSQL, is beginning to emerge.

NoSQL

There are many reasons why NoSQL products have been popular. As there are a variety of NoSQL products. As you can see in Hadoop or Cassandra, main advantages of NoSQL is its horizontal scalability.

As these NoSQL products don’t provide Strong Consistency, they cannot be used where high-level data consistency is required.

NewSQL

NewSQL has as excellent scalability as NoSQL, and at the same time it guarantees ACID like RDBMS which is performed in a single node.

What is Spanner?

Spanner is a NewSQL created by Google. It is a distributed relational database that can distribute and store data in Google’s BigTable storage system in multiple data centers. Spanner meets ACID (of course, it supports transaction) and supports SQL.

Data R/W eff: When you read data, Spanner connects you to the data center that is geographically closest to you, and when you write data, it distributes and stores it to multiple data centers.

Failure: If the data center you try to access has a failure, of course, you can read the data from another data center that has a replica of the data (in US, 5 replica).

The Spanner client automatically performs a failover between replicas. When the number of servers storing data is changed or a failure occurs in equipment, Spanner automatically re-distributes data through data transfer among the equipments.

More details of Spanner: will come later.

Question 1

link

Convert a BST to max heap.

Solution

The second answer:

a simple (reversed) in-order traversal of the BST. It would produce a sorted array which is indeed a max-heap!

Question 2

link

Converting a heap to a BST in O(n) time?

possible?

Solution

Impossible. Because otherwise, we can do this:

1. Take an array and build the heap in O(n) time
2. Converting the heap to a BST in O(n) time (assuming)
3. Walking the BST in O(n) time to get a sorted sequence.

Thus we sort array in O(n) time, it can’t happen.

Right way to do, is to repeatedly dequeueing maximum value from the BST, then generate the BST recursively (bottom-up approach).

Question

link

N是一个很大的正整数——可能到10¹⁵次方，

简单起见，不考虑溢出，或者假设用python

A 是一个array，里面存着一些正整数，up to 1000个

从1 - N这N个数，有多少个数，不能被A中的任何一个数整除的？

Solution

It’s a very difficult question.

We can’t do it like a Sieve of Eratosthenes, cuz N is too large. The best solution is at this post, level 9:

Consider the simplest case: A={2}, then any odd number below N is OK, so the result would be (N - N/2). Then consider A={2, 3}, any number below N that is not mutiply of 2 or 3 is OK, so the result would be (N - N/2 - N/3 + N/6). Then consider A={2, 3, 5}, the result would be (N - N/2 - N/3 - N/5 + N/6 + N/10 + N/15 - N/30).

So there is a general rule:

for A={a1, a2, …, aN}, if ai is not dividable by aj for any i != j, then we could:

1. for i from 1 to N, calc r1 = N - SUM(N/ai);
2. for i, j from 1 to N, i != j, calc r2 = r1 + SUM(N/(ai*aj));
3. for i, j, k from 1 to N, i != j != k, calc r3 = r2 - SUM(N/(aiajak));
4. …
5. until all numbers in A are chosen.
6. then the final rN is the result.

So for the problem, first we preprocess A to eliminate any multiplies in A. For example, A={2, 4, 5}, we can eliminate 4 because it is a mutiply of 2 which is also in A. So A'={2, 5}, then we calc:

r1 = 10 - 10/2 - 10/5 = 10 - 5 - 2 = 3; r2 = r1 + 10/10 = 3 + 1 = 4;

then the final result is 4.

Refer to [Question] Multiples of 3 and 5.

Code

not written

Question

link

You are given an array of n elements [1,2,….n]. For example {3 2 1 4 6 5 7}.

Now we create a signature of this array by comparing every consecutive pair of elements. If they increase, write “I” else write “D”.

For example for the above array, the signature would be “DDIIDI”. The signature thus has a length of N-1.

Now given a signature, compute the lexicographically smallest permutation of [1,2,….n].

Solution

A great answer:

Take the above case. Signature = DDIIDI.

Take original permutation as 1 2 3 4 5 6 7.

Then for first continuous sequence DD reverse the strip 1 2 3 to 3 2 1 hence sequence becomes 3 2 1 4 5 6 7.

Then for second sequence D reverse strip 5 6 to 6 5 hence sequence becomes 3 2 1 4 6 5 7.

There is no continuous D left we are done and reached the answer.

Code

Not written.

Definition

An abstract class is a class that is declared abstract —it may or may not include abstract methods. Abstract classes cannot be instantiated, but they can be subclassed.

with NO abstract method?

In JDK 1.0 it was indeed necessary to have at least one abstract method in an abstract class.

This restriction was removed in JDK 1.1 (1997? (I’m old)) and such classes added to the Java library, such as java.awt.event.KeyAdapter.

So, no abstract method is fine. Doing it prevents you from instantiation - you can only inherit.

However, different opinions are:

is subjective and a matter of style. Personally I would say yes. If your intent is to prevent a class (with no abstract methods) from being instantiated, the best way to handle this is with a privateprotected constructor, not by marking it abstract.

how about abstract variable?

There is no such thing in Java.

For more on abstract class, read [Java OOP] Template method pattern.

A short answer

In Java, all classes must have a constructor.

Can abstract class have constructor

Yes, it can. However, if we create an instance using it, it’s error.

Consider this example:

abstract class Base {
    Base() { System.out.println("Base Constructor Called"); }
    abstract void fun();
}

class Derived extends Base {
    Derived() { System.out.println("Derived Constructor Called"); }
    void fun() { System.out.println("Derived fun() called"); }
}

class Main {
    public static void main(String args[]) { 
       Derived d = new Derived();
    }
}

Output:

Base Constructor Called
Derived Constructor Called

More info on constructor:

The constructor in an abstract class:

1. is used when you want to perform some initialization
2. you may define more than one constructor (with different arguments)
3. if you don’t define a constructor, then the compiler will automatically generate one for you.
4. your subclass constructor have to call a constructor from the abstract class
5. you can define all your constructors protected (cuz making them public is pointless)

For more on abstract class, read [Java OOP] Template method pattern.