Interval - Algorithm

When to use interval
- Sort by start or end first
- Kind of Greedy
- sort interval, then binary search (LeetCode 436 - Find Right Interval)
  -- Sort Interval
  -- Or sort start, end separately
  -- Or sort start, end at one array
- Use TreeMap or TreeMap> to store intervals and compare based on start
- Use Priorityqueue
- Sweep line algorithm
- Interval operation: insert, merge interval

X. Interval Binary Search Tree
- How to remove an interval
private class Node {
 Interval interval; // or directly store start, end; start is used as the key to build BST
 Node left, right;
 int maxValue; // the max value of all intervals rooted in this node

Unlimited switches
isToggled(long idx)
toggle(long start, long end)

Sort by start
Given n appointments, find all conflicting appointments

LeetCode 616 - Add Bold Tag in String

LettCode 452 - Minimum Number of Arrows to Burst Balloons

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

LeetCode 436 - Find Right Interval
Sort by start then binary search

Google – Remove Alarm
Google – Find a Path Among Circles
- Only merge interval when two circles intersects

LeetCode 352 - Data Stream as Disjoint Intervals
Given a data stream input of non-negative integers a1, a2, ..., an, ..., summarize the numbers seen so far as a list of disjoint intervals.
TreeMap intervals to merge interval based on start

LeetCode 436 - Find Right Interval
Use TreeMap to store intervals
- Use TreeMap> to handle duplicate start
Sort Intervals based on start + binary search

LeetCode 253 - Meeting Rooms II
find the minimum number of conference rooms required.
starts[i] = intervals[i].start;
ends[i] = intervals[i].end;
- Use PriorityQueue
Arrays.sort(intervals, (a, b) -> { return a.start - b.start;}});
PriorityQueue ends = new PriorityQueue();
pq.offer(new Event(interval.start, 1));
pq.offer(new Event(interval.end, 0));

LeetCode 252 - Meeting Rooms
determine if a person could attend all meetings.

LeetCode 56 - Merge Intervals
LeetCode 57 - Insert Interval

LeetCode 218 - The Skyline Problem
Using TreeMap
Sweepline is used in solving the problem. List height is used to save each of the line segments including both start and end point. The trick here is to set the start segment as negative height. This has a few good uses:
first, make sure the start segment comes before the end one after sorting.
second, when pushing into the queue, it is very each to distinguish either to add or remove a segment.
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> heights = new ArrayList<>();
        for (int[] b: buildings) {
            heights.add(new int[]{b[0], - b[2]});
            heights.add(new int[]{b[1], b[2]});
        Collections.sort(heights, (a, b) -> (a[0] == b[0]) ? a[1] - b[1] : a[0] - b[0]);
        TreeMap heightMap = new TreeMap<>(Collections.reverseOrder());
        int prevHeight = 0;
        List<int[]> skyLine = new LinkedList<>();
        for (int[] h: heights) {
            if (h[1] < 0) {
                Integer cnt = heightMap.get(-h[1]);
                cnt = ( cnt == null ) ? 1 : cnt + 1;
                heightMap.put(-h[1], cnt);
            } else {
                Integer cnt = heightMap.get(h[1]);
                if (cnt == 1) {
                } else {
                    heightMap.put(h[1], cnt - 1);
            int currHeight = heightMap.firstKey();
            if (prevHeight != currHeight) {
                skyLine.add(new int[]{h[0], currHeight});
                prevHeight = currHeight;
        return skyLine;
X. Divide and Conquer
 public List<int[]> getSkyline(int[][] buildings) {
  if (buildings.length == 0)
   return new LinkedList<int[]>();
  return recurSkyline(buildings, 0, buildings.length - 1);

 private LinkedList<int[]> recurSkyline(int[][] buildings, int p, int q) {
  if (p < q) {
   int mid = p + (q - p) / 2;
   return merge(recurSkyline(buildings, p, mid),
     recurSkyline(buildings, mid + 1, q));
  } else {
   LinkedList<int[]> rs = new LinkedList<int[]>();
   rs.add(new int[] { buildings[p][0], buildings[p][2] });
   rs.add(new int[] { buildings[p][1], 0 });
   return rs;

 private LinkedList<int[]> merge(LinkedList<int[]> l1, LinkedList<int[]> l2) {
  LinkedList<int[]> rs = new LinkedList<int[]>();
  int h1 = 0, h2 = 0;
  while (l1.size() > 0 && l2.size() > 0) {
   int x = 0, h = 0;
   if (l1.getFirst()[0] < l2.getFirst()[0]) {
    x = l1.getFirst()[0];
    h1 = l1.getFirst()[1];
    h = Math.max(h1, h2);
   } else if (l1.getFirst()[0] > l2.getFirst()[0]) {
    x = l2.getFirst()[0];
    h2 = l2.getFirst()[1];
    h = Math.max(h1, h2);
   } else {
    x = l1.getFirst()[0];
    h1 = l1.getFirst()[1];
    h2 = l2.getFirst()[1];
    h = Math.max(h1, h2);
   if (rs.size() == 0 || h != rs.getLast()[1]) {
    rs.add(new int[] { x, h });
  return rs;

X. Thought as different kinds of evet: start/end event
LeetCode 253 - Meeting Rooms II
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.
    public int minMeetingRooms(Interval[] intervals) {
        int[] starts = new int[intervals.length];
        int[] ends = new int[intervals.length];
        for(int i=0; iint
rooms = 0int endsItr = 0for(int i=0; iif(starts[i]else endsItr++; } return rooms; }X. Using prority queue + sweep line
    public int minMeetingRooms(Interval[] intervals) {
        if(intervals == null || intervals.length == 0)
            return 0;
        Arrays.sort(intervals, new Comparator() {
            public int compare(Interval t1, Interval t2) {
                if(t1.start != t2.start)
                    return t1.start - t2.start;
                    return t1.end - t2.end;
        int maxOverlappingMeetings = 0;
        PriorityQueue pq = new PriorityQueue<>();      // min oriented priority queue
        for(int i = 0; i < intervals.length; i++) {         // sweeping-line algorithms
            while(pq.size() > 0 && intervals[i].start >= pq.peek())
            maxOverlappingMeetings = Math.max(maxOverlappingMeetings, pq.size());
        return maxOverlappingMeetings;

LeetCode 252 - Meeting Rooms
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.
public boolean canAttendMeetings(Interval[] intervals) {
  if (intervals == null)
    return false;

  // Sort the intervals by start time
  Arrays.sort(intervals, new Comparator() {
    public int compare(Interval a, Interval b) { return a.start - b.start; }
  for (int i = 1; i < intervals.length; i++)
    if (intervals[i].start < intervals[i - 1].end)
      return false;
  return true;

TCP/IP Miscs

TCP/IP Miscs

What is this flags(In packet): URG, ACK, PSH, RST, SYN, FIN?
# CWR - Congestion Window Reduced
# ECE - Explicit Congestion Notification echo
# URG - Urgent
# ACK - Acknowledgement
# PSH - Push
# RST - Reset
# SYN - Synchronize
# FIN - Finished
A TCP connection is managed by an operating system through a programming interface that represents the local end-point for communications, the Internet socket. During the lifetime of a TCP connection it undergoes a series of state changes:
1. LISTEN : In case of a server, waiting for a connection request from any remote client.
2. SYN-SENT : waiting for the remote peer to send back a TCP segment with the SYN and ACK flags set. (usually set by TCP clients)
3. SYN-RECEIVED : waiting for the remote peer to send back an acknowledgment after having sent back a connection acknowledgment to the remote peer. (usually set by TCP servers)
4. ESTABLISHED : the port is ready to receive/send data from/to the remote peer.
10. TIME-WAIT : represents waiting for enough time to pass to be sure the remote peer received the acknowledgment of its connection termination request. According to RFC 793 a connection can stay in TIME-WAIT for a maximum of four minutes.

Three-way Connection Establishment Handshake

A (virtual) connection is established via what is commonly known as a three-way handshake.
To establish a TCP connection:
1. (B) --> [SYN] --> (A)
The requesting end (normally called the client) sends a SYN segment specifying the port number of the server that
the client wants to connect to, and the client's initial sequence number.
Note: A SYN packet is a TCP packet with the SYN flag set only (see TCP header diagram in Resources). It's important to note that unless a SYN packet is received by A from B, there is no way to establish a TCP connection. Therefore, if your firewall drops all SYN packets to your internal network (and to itself), there is no way for anyone to establish a TCP connection to you.
2. (B) <-- [SYN/ACK] <--(A)
The server responds with its own SYN segment containing the server's initial sequence number. The
server also acknowledges the client's SYN by ACKing the client's ISN plus one. A SYN consumes one sequence
Note: A SYN/ACK packet is a TCP packet with the SYN and ACK flag set and no other TCP flags.
3. (B) --> [ACK] --> (A)
When the (B) receives the SYN/ACK packet from (A), The client completes the final part of the three-way handshake, returns acknowledge this SYN from the server by ACKing the server's ISN plus one.
Note: An ACK packet is a TCP packet with the ACK flag set only. The important thing to note here is that after the three-way handshake is completed, and the connection is complete, every packet that is part of this TCP connection will always have the ACK bit set.
This is also the reason why connection tracking is so important. Without connection tracking, there is no way for your firewall to know whether an arriving ACK packet is really a part of an established connection. When simple packet filters (and Ipchains) receives a packet with the ACK flag set, it simply allows the packet through (does this sound like a good idea?). When a stateful firewall received an ACK packet, it'll consult a connection table to see if the packet belongs to an established connection. If it does not, the packet is dropped.
Four-way Connection Termination Handshake
What goes up, must come down. A four-way handshake tears down a previously established TCP connection. Again, using the same scheme as above:
1. (B) --> ACK/FIN --> (A)
2. (B) <-- ACK <-- (A)
3. (B) <-- ACK/FIN <-- (A)
4. (B) --> ACK --> (A)
Note: Since a TCP connection is a two way connection, it needs to be torn down in both directions. An ACK/FIN packet (ACK and FIN flags set) is sometimes referred to as a FIN (Finish) packet . However, since the connection is not yet torn down, it is always accompanied by the ACK flag. A packet with only the FIN flag set is NOT legal and is likely maliciously generated.
Resetting a connection
The four-way handshake is not the only way to tear down an established TCP connection. Sometimes, if either hosts need to tear down the connection quickly (timeout, port or host unreachable, etc.), a RST (Reset) packet is sent. Note that since a RST packet is not necessarily always part of a TCP connection, it can be sent by itself. RST packets that are part of a TCP connection is usually accompanied by the ACK flag as well.
Note that RST packets are not acknowledged.
Normal TCP Flag combination
* SYN, SYN ACK, and ACK are used during the three-way handshake which establishes a TCP connection.
* Except for the initial SYN packet, every packet in a connection must have the ACK bit set.
* FIN ACK and ACK are used during the graceful teardown of an existing connection.
* RST ACK can be used to immediately terminate an existing connection.
* Packets during the "conversation" portion of the connection (after the three-way handshake but before the teardown or termination) contain just an ACK by default.
* Optionally, they may also contain PSH and/or URG.
Abnormal TCP Flag combination
* SYN FIN is probably the best known illegal combination. Remember that SYN is used to start a connection, while FIN is used to end an existing connection. It is nonsensical to perform both actions at the same time. Many scanning tools use SYN FIN packets, because many intrusion detection systems did not catch these in the past, although most do so now. You can safely assume that any SYN FIN packets you see are malicious.
* SYN FIN PSH, SYN FIN RST, SYN FIN RST PSH, and other variants on SYN FIN also exist. These packets may be used by attackers who are aware that intrusion detection systems may be looking for packets with just the SYN and FIN bits set, not additional bits set. Again, these are clearly malicious.
* Packets should never contain just a FIN flag. FIN packets are frequently used for port scans, network mapping and other stealth activities.
* Some packets have absolutely no flags set at all; these are referred to as "null" packets. It is illegal to have a packet with no flags set.
What is a FIN_WAIT_1, FIN_WAIT_2 state?
FIN_WAIT_2 seems to occur when the server has an active connection with a client and it wants to shut down the TCP connection (probably in response to a normal application layer "exit"). The server sends the client a packet with a "FIN" bit set. At this point, the server is in FIN_WAIT_1 state. The client gets the FIN packet and goes into CLOSE_WAIT state, and sends an acknowledgment packet back to the server. When the server gets that packet, it goes into FIN_WAIT_2 state. From the server's perspective, the connection is now closed, and the server can't send any more data. However, under the TCP protocol, the client needs to shut down also by sending a FIN packet, which the server TCP implementation should ACK. The server should close about two milliseconds later.

Interview Questions – Thread

Interview Questions – Thread
Java Synchronization
Every object can be used as a limiting resource or monitor object, and to constrain access to code in a critical section.
[Implementation - Each object has header represented by two 32-bit words - Lock word and Class word. In Lock word (which also contains GC state information), it carries synchronization information, such as whether the object is used in a lock right now.]
How synchronization is implemented?
Synchronization is implemented using monitors. Each object's header is associated with a monitor, which a thread can lock or unlock.
Only one thread at a time may hold a lock on a monitor. Any other threads attempting to lock that monitor are blockeduntil they can obtain a lock on that monitor.
The synchronized statement computes a reference to an object; it then attempts to perform a lock action on that object's monitor and does not proceed further until the lock action has successfully completed. After the lock action has been performed, the body of the synchronized statement is executed.
If execution of the body is ever completed, either normally or abruptly, an unlock action is automatically performed on that same monitor.
Class lock vs Object lock
A synchronized method acquires a monitor before it executes. For a class (static) method, the monitor associated with the Class object for the method's class is used. For an instance method, the monitor associated with this (the object for which the method was invoked) is used.
Synchronizing an instance method uses the object's lock, since we assume we're modifying the state of a specific object - and each object is separate from every other of the same class. If a class has two instance synchronized methods, then it is possible to access each of these synchronized methods by two different objects simultaneously. If the synchronized method is a static method, a class lock is used (since the method is assumed to act the same for all instances). 
If 2 different threads hit 2 different synchronized methods in an object at the same time will they both continue? 
No. Only one method can acquire the lock. 2 different threads can not access instance synchronized method on same object simultaneously. 2 different threads can access instance synchronized method on 2 different objects simultaneously. Because of Class lock, 2 different threads can NOT access static synchronized method on 2 different objects simultaneously. If a thread goes to sleep, it holds any locks it has—it doesn't release them. If a class has both synchronized and non-synchronized methods, multiple threads can still access the class same object's synchronized method and non-synchronized method simultaneously.
One point you have to be careful about is that there is no link between synchronized static methods and synchronized non static methods
class A { static synchronized f() {...} synchronized g() {...} } f() and g() are not synchronized with each other and thus can execute totally concurrently.
On an instance method, to implement mutual exclusion between different instances of the object - for example when accessing an external resource):
g() {synchronized(MyClass.class) {}}
Explain ways of creating a thread, what is the difference? Which is better? 
There are two ways to create a new thread: First, Extends the Thread class, and override the run() method in your class. In order to start a new thread, we need initialize an instance of the subclass and invoke the start() method on it. Second, Implements the Runnable interface, The class will have to implement the run() method in the Runnable interface. In order to start a new thread, we need create an instance of this class. Pass the reference of this instance to the Thread constructor a new thread of execution will be created. Implementing the runnable interface is preferred, as it does not require your object to inherit a thread. When you need multiple inheritance, for example, if you are already inheriting a different class, then only interfaces can help you.
How can threads communicate with each other in java? 
The wait(), notify(), and notifyAll() methods are used to provide an efficient way for threads to communicate with each other. 
What is the difference between yield() and sleep()? 
When a task invokes yield(), it changes from running state to runnable state. It allows the current the thread to release its lock from the object and scheduler gives the lock of the object to the other thread with same priority. When a task invokes sleep(), it changes from running state to waiting/sleeping state. It allows the thread to go to sleep state for the specified milliseconds. When a thread goes into sleep state it doesn't release the lock.
What is difference between notify() and notfiyAll()?
When notify is called, one of the threads waiting for the synchronized resource will be arbitrarily selected and woken up by the thread scheduler in the JVM.
When notifyAll is called, all threads waiting for the lock will be woken up. Only one of them will succeed in acquiring the lock and the rest will go to sleep again.
The notifyAll method is safer than notify but carries a greater overhead than notify.
What is daemon thread and which method is used to create the daemon thread? 
Threads are divided into two types: normal threads and daemon threads. When a new thread is created, it inherits the daemon status of the thread that created it, so by default any threads created by the main thread are also normal threads. Normal threads and daemon threads differ only in what happens when they exit. Daemon threads are sometimes called "service" threads. These are threads that normally run at a low priority and provide a basic and helper service to a program. You don't want the existence of this thread to prevent the JVM from shutting down. This is what daemon threads are for. An example of a daemon thread that is continuously running is the garbage collector thread. This thread is provided by the JVM. When a thread exits, the JVM performs an inventory of running threads, and if the only threads that are left are daemon threads, it initiates an orderly shutdown. When the JVM halts, any remaining daemon threads are abandoned, finally blocks are not executed, stacks are not unwound the JVM just exits.
The setDaemon() method is used to create a daemon thread. These threads run without the intervention of the user. 
Is there a separate stack for each thread in Java?
 Yes. Every thread maintains its own separate stack, called Runtime Stack but they share the same memory. Elements of the stack are the method invocations, called activation records or stack frame. The activation record contains pertinent information about a method like local variables. 
What is synchronization?
With respect to multithreading, Synchronization is a process of controlling the access of shared resources by the multiple threads in such a manner that only one thread can access a particular resource at a time. In non synchronized multithreaded application, it is possible for one thread to modify a shared object while another thread is in the process of using or updating the object’s value. Synchronization prevents such type of data corruption which may otherwise lead to dirty reads and significant errors. 
What is synchronization advantage and disadvantage? 
Without synchronization, it is possible for one thread to modify a shared object while another thread is in the process of using or updating that object’s value. This often causes dirty data and leads to significant errors. The disadvantage of synchronization is that it can cause deadlocks when two threads are waiting on each other to do something. Also synchronized code has the overhead of acquiring lock, which can adversely the performance.

Interview Questions - XML

                        Interview Questions - XML


There are three distinct approaches to parsing XML documents:

• DOM parsing

• Push parsing - SAX

• Pull parsing – StAX

DOM means Document Object Model, SAX stands for Simple API for XML.

DOM was developed by W3C, whereas SAX, StAX were developed by an informal group of participants of mailing list.

They have advantages and disadvantages and should be used depending on the situation.

DOM Parsing

The DOM approach has the following notable aspects:

1.        An in-memory DOM tree representation of the complete document is constructed before the document structure and content can be accessed or manipulated.

2.        Document nodes can be accessed randomly and do not have to be accessed strictly in document order.

3.        Random access to any tree node is fast and flexible, but parsing the complete document before accessing any node can reduce parsing efficiency.

4.        If an XML document needs to be navigated randomly or if the document content and structure needs to be manipulated, the DOM parsing approach is the most practical approach.

5.        DOM is convenient when applications need to traverse the document multiple times.

6.        DOM supports XPath.

7.        For large documents ranging from hundreds of megabytes to gigabytes in size, the in-memory  DOM tree structure can exhaust all available memory, making it impossible to parse such large documents under the DOM approach.

Push Approach -- SAX

1.        SAX was developed by an informal group of participants of the XML-DEV mailing list.

2.        Under the push parsing approach, a push parser generates synchronous events as a document is  parsed, and these events can be processed by an application using a callback handler model.

3.        No no random access, SAX can be used only for a sequential processing of an XML document, it can only traverse XML from top to bottom.

4.        SAX doesn't retain all the information of the underlying XML document such as comments whereas DOM retains almost all the info.

5.        SAX doesn't support XPath.

6.        SAX doesn't retain all the information of the underlying XML document such as comments whereas DOM retains almost all the info.

7.        Comparewd with DOM, SAX is efficient, and consumes lower memory.

Pull Approach -- StAX

1.        Under the pull approach, events are pulled from an XML document under the control of the application using the parser.

2.        StAX is similar to the SAX API in that both offer event-based APIs. However,

3.        StAX differs from the SAX API in the following respects:

4.        In SAX, data is pushed via events to application code handlers.

5.        In StAX, the application "pulls" the data from the XML data stream at its convenience. Application code can filter, skip tags, or stop parsing at any time. The application--not the parser--is in control, which enables a more intuitive way to process data.

5.StAX offers two event-based APIs: a cursor-based API and an iterator-based API.

6.        Unlike the SAX API, the StAX API can be used both for reading and for writing XML documents.

SAX, StAX are good choices for dealing with large documents.


XPath is a language for addressing node sets within an XML document.

The XPath data model treats an XML document as a tree of various node types, such as an element node, an attribute node, and a text node.


XSLT specifies a language for transforming XML documents into other XML documents.

XSLT language constructs are completely based on XML. Therefore, transformations written in  XSLT exist as well-formed XML documents. An XML document containing XSLT transformations is commonly referred to as a style sheet.

An XSLT style sheet merely specifies a set of transformations. Therefore, you need an XSLT processor to apply these transformations to a given XML document. An XSLT processor takes an XML document and an XSLT style sheet as inputs, and it transforms the given XML document to its target output, according to transformations specified in the style sheet. The target output of XSLT transformations is typically an XML document but could be an HTML document or any type of text document. Two commonly used XSLT processors are Xalan-Java and Saxon.

To use an XSLT processor, you need a set of Java APIs, and TrAX is precisely such an API set.

XML Libraries

Xerces, jdom, Sun’s XML parser

JAXP - Java API for XML Processing

Sun packages its XML APIs as the Java API for XML Processing (JAXP). JAXP is included in Jdk5.0 and later.

Its XSLT processor is actually Xalan from Apache.

Using factory classes, JAXP allows you to plug in any conforming XML or XSL parse.

JAXB - Object Binding

XML Schema Binding to Java Representation



Pro XML Development with Java Technology

Java Network Miscs

Java Network Miscs

About Too many open files

The number of open files allowed is an Operating System dependent setting. This is a limited resource that is shared by all processes on the machine. The standard programming practice is to make sure to close all files that the program opens. On Unix systems this applies to socket connections as well.

A very common mistake is to assume that the runtime garbage collector (GC) will look after resources in the same way that it looks after memory references. However, wshile the memory associated with the object itself is collected by the GC, the resources associated with that object may not be cleaned up.

There are at least two types of resource that are collected under the stream object:

* Memory associated with the stream object itself, and with managing state within the stream

* An operating system file descriptor or handle that relates to the underlying file within the file system

The GC will take care of the first aspect while leaving the underlying descriptor open, thus consuming valuable system resources over time and eventually resulting in a denial-of-service scenario.

when use Runtime.getProcess() method to get a process and then exec() an external script,

API automatically opens three streams (stdout, stderr, stdin) each time the getProcess() is called. It is the responsibility of the caller to close those streams when done.


see sample code for how to close. Scan for "close".

Avoid use nameless InputStream/OutputStream, instead explicitly close it.

Properties prop = new Properties(); prop.load(new FileInputStream(propertyFile));

The specified stream remains open after this method returns.

From Elliote Rusty Harold's Java IO:

Not all streams need to be closed -- byte array output streams do not need to be closed, for example. However, streams associated with files and network connections should always be closed when you're done with them.

For example, if you open a file for writing and neglect to close it when you're through, then other processes may be blocked from reading or writing to that file.

Does closing a BufferedOutputStream also close the underlying OutputStream?

Yes, it closes it.

The behaviour is actually inherited from FilterOutputStream. The Javadocs for for FilterOutputStream.close state:

Closes this output stream and releases any system resources associated with the stream.

The close method of FilterOutputStream calls its flush method, and then calls the close method of its underlying output stream.

BufferedOutputStream extends FilterOutputStream, Closing the BufferedOutputStream will also close the underlying OutputStream. You should close the BufferedOutputStream not underlying OutputStream so that it flushes its contents before closing the underlying stream.

Notes from Fundamental Networking in Java:

Closing a connected socket

In fact there are several ways to close a socket:

(a) close the socket itself with Socket.close();

(b) close the output stream obtained from the socket by calling the method Socket.getOutputStream().close().

(c) close the input stream obtained from the socket by calling the method Socket.getIutputStream().close().

Any one of these is sufficient, and exactly one of them is necessary, to close the socket and release all its resources. You can't use more than one of these techniques on any given socket. As a general rule you should close the output stream rather than the input stream or the socket, as the output stream may require flushing.

Object Stream Deadlock

The following code fragment will always deadlock if present at both client and server:

ObjectInputStream in = new ObjectInputStream(socket.getInputStream());

ObjectOutputStream out = new ObjectOutputStream(socket.getOutputStream());

The ObjectInputStream constructor calls readStreamHeader to read and verifies the header and version written by the corresponding ObjectOutputStream.writeStreamHeader method. The ObjectInputStream constructor blocks until it completes reading the serialization stream header. Code which waits for an ObjectInputStream to be constructed before creating the corresponding ObjectOutputStream for that stream will deadlock, since the ObjectInputStream constructor will block until a header is written to the stream, and the header will not be written to the stream until the ObjectOutputStream constructor executes.

So Always create an ObjectOutputStream before an ObjectInputStream for the same socket.

Socket Output

All output operations on a TCP socket are synchronous as far as the local send buffer is concerned, and asynchronous as far as network and the remote application are concerned.

After writing to a socket, there is no assurance that the data has been received by the application (or TCP) at the other end. The only way an application can be assured that a data transmission has arrived at the remote application is by receiving an acknowledgement explicitly sent by the remote application.

It is best to attach a BufferedOutputStream to the output stream obtained from the socket.Ideally the BufferedOutputStream’s buffer should be as large as the maximum request or response to be transmitted, if this is knowable in advance and not unreasonably large; otherwise it should be at least as large as the socket’s send-buffer. This minimises context-switches into the kernel, and it gives TCP more data to write at once, allowing it to form larger segments and use the network more efficiently. It also minimizes switching back and forth between the JVM and JNI. You must flush the buffer at appropriate points, ie, after completing the writing of a request message and before reading the reply, to ensure that any data in the BufferedOutputStream’s buffer gets to the socket.

Ideally the BufferedIunputStream’s buffer should be at least as large as the socket’s receive buffer so that the receive buffer is drained as quickly as possible.

Don't mix-use readObject/writeObject and readUnshared/writeUnshared.

os.writeObject("Hello World");


os.writeObject("Hello World");

what gets written to the file is something like this:


for the third entry, it just writes a special flag which says use the same Object as found at position 1

in this object stream. It's bascially doing a compression for you of the data being written.

Using writeUnshared, you get something like this:


All this means that you can't mix readObject/writeObject and readUnshared/writeUnshared.

If you want to readUnshared then you must writeUnshared.

If you write them without unshared (using the compression) and then readUnshared (as if it did not have the compression) you are going to have problems because it's going to hit that flag and not know what to do.

This would output error like: cannot read back reference as unshared






writeUnshared, then readObject is ok.

BufferedIutputStream/BufferedOutputStream just add a local buffer to improve network read/write performance, and would not affect remote side.
So one side can use buffered stream and remote side still can use un-buffered stream.
This can happen when you update existing code, thus cause different code version between two nodes.


Fundamental Networking in Java

Java Thread Miscs

Java Thread Miscs

Multi-thread considerations
1-     Synchronize access to shared mutable data and be ware of insufficient synchronization
When multiple threads share mutable data, each thread that reads or writes the data must perform synchronization.
The synchronized keyword ensures that only a single thread can execute a method or block at one time and prevent an object from being observed in an inconsistent state while it's being modified by another thread, also it ensures one thread's changes would be visible to other threads.
2-     Avoid excessive synchronization
Excessive synchronization can cause reduced performance, deadlock, or even nondeterministic behavior.
Avoid synchronization by other approaches.
1. Don't share mutable data, but share immutable data or a cloned one.
2. Use utilities in java.util.concurrent package, such as AtomicLong
3-     Limit the amount of work within synchronized regions.
Do as little work as possible inside synchronized, If we must perform some time-consuming activity, find a way to move the activity out of the synchronized block.
4-     Prefer executors and tasks to threads
5-     Never use suspend, resume and stop of thread.
6-     For interval timing, always use System.nanoTime
7-     Document thread safety
8-     Avoid multiple locking.
9-     Acquire lock in some consistent well-defined order
volatile keyword
volatile is used to indicate that a variable's value will be modified by different threads.
Declaring a volatile Java variable means: it will not be stored in the thread's local cache. Whenever thread is updating the values, it is updated to the main memory. So, other threads can access the most recently written value.
The value of this variable will never be cached thread-locally: all reads and writes will go straight to "main memory".
ps: When multiple threads using the same variable, each thread will have its own copy of the local cache for that variable. So, when it's updating the value, it is actually updated in the local cache not in the main variable memory. The other thread which is using the same variable doesn't know anything about the values changed by the another thread.
Avoid busy-wait
busy-wait is the code repeatedly checks a shared object waiting for
something to happen.
API on thread
Causes the currently executing thread object to temporarily pause and allow other threads to execute.  
Other methods such as suspend, resume and stop are deprecated, and not recommended to use as they are deadlock-prone and not safe.
Thread.stop can result in data corruption.
public final void join() throws InterruptedException
Waits for this thread to die.
public final void join(long millis)
Waits at most millis milliseconds for this thread to die.
Difference between notify and notifyAll
notify wakes a single waiting thread, and notifyAll wakes all waiting threads.
It is safer to use notifyAll.
It will always yield correct results. You may wake some other threads, too, but this won't affect the correctness of your program. These threads will check the condition for which they're waiting and, finding it false, will continue waiting.
Using notifyAll in place of notify protects against accidental or malicious waits by an unrelated thread. Such waits could otherwise “swallow” a critical notification, leaving its intended recipient waiting indefinitely.
As an optimization, you can choose to invoke notify instead of notifyAll.
Timer and ScheduledThreadPoolExecutor
A timer uses only a single thread for task execution, which can hurt timing accuracy in the presence of long-running tasks. If a timer's sole thread throws an uncaught exception, the timer ceases to operate.
A scheduled thread pool executor supports multiple threads and recovers gracefully from tasks that throw unchecked exceptions.
For interval timing, always use System.nanoTime
System.nanoTime is used to time the activity rather than System.currentTimeMillis. For interval
timing, always use System.nanoTime  in preference to System.currentTime-
Millis. System.nanoTime is both more accurate and more precise, and it is not
affected by adjustments to the system's real-time clock.
Improve Performance for Lazy initialization
Under most circumstances, normal initialization is preferable to lazy initialization.
Use lazy initialization holder class idiom on a static field
// Lazy initialization holder class idiom for static fields
private static class FieldHolder {
static final FieldType field = computeFieldValue();
static FieldType getField() { return FieldHolder.field; }
When the getField method is invoked for the first time, it reads  Field-
Holder.field for the first time, causing the FieldHolder class to get initialized.

A modern VM will synchronize field access only to initialize the class.
Once the class is initialized, the VM will patch the code so that subsequent access to the field does not involve any testing or synchronization.
Use Double-check idiom on an instance field
This idiom avoids the cost of locking when access-
ing the field after it has been initialized.
It is critical that the field be declared volatile
private volatile FieldType field;
    FieldType getField() {
    FieldType result = field;
    if (result == null) { // First check (no locking)
        synchronized(this) {
        result = field; // this is important
        if (result == null) // Second check (with locking)
            field = result = computeFieldValue();
return result;
Prefer concurrency utilities to wait and notify
The higher-level utilities in java.util.concurrent fall into three categories: the Executor Framework, concurrent collections; and synchronizers.
The concurrent collections provide high-performance concurrent implementations of standard collection interfaces such as ConcurrentHashMap, ConcurrentSkipListMap, ConcurrentLinkedQueue, ConcurrentSkipListSet.
They combine several primitives into a single atomic operation.
For example, ConcurrentMap extends Map and adds several methods, including putIfAbsent(key, value).
Prefer executors and tasks to threads
It provide thread pool, various kinds of executors.
ExecutorService executor = Executors.newSingleThreadExecutor();
In a lightly loaded server, use Executors.newCachedThreadPool.
In a cached thread pool, submitted tasks are not queued but immediately handed off to a thread for execution. If no threads are available, a new one is created.
In a heavily loaded server, use Executors.newFixedThreadPool.
Use executor service provided in java.unit.concurrent package.
The key abstraction is the unit of work, which is called a task. There are two kinds of tasks: Runnable and Callable (which is like Runnable, except that it returns a value).
Deadlock is a situation where two or more threads are blocked forever, waiting for each other. When a thread holds a lock forever, other threads attempting to acquire that lock will block forever waiting. When thread A holds lock L and tries to acquire lock M, but at the same time thread B holds M and tries to acquire L, both threads will wait forever.
How to avoid deadlocks
Acquire lock in some consistent well-defined order
Deadlock usually occurs when multiple threads need the same locks but obtain them in different order.
Shrink synchronized blocks to avoid multiple locking
Do as little work as possible inside synchronized regions.
If you must perform some time-consuming activity, find a way to
move the activity out of the synchronized region.
Never leave control to the client within a synchronized method or block. 
Don't call an alien method from within a synchronized region.
Use Open Calls to Avoiding Deadlock Between Cooperating Objects
Inconsistent Lock-ordering Deadlocks
public class LeftRightDeadlock {
private final Object left = new Object();
private final Object right = new Object();
public void leftRight() {
synchronized (left) {
synchronized (right) {doSomething();}
public void rightLeft() {
synchronized (right) {
synchronized (left) {doSomethingElse();}
Dynamic Lock Order Deadlocks
The lock order depends on the order of arguments passed to transferMoney, and these in turn might depend on external inputs. Deadlock can occur if two threads call transferMoney at the same time, one transferring from X to Y, and the other doing the opposite.
public void transferMoney(Account fromAccount,Account toAccount,DollarAmount amountToTransfer) {
synchronized (fromAccount) {
synchronized (toAccount) {
if (fromAccount.hasSufficientBalance(amountToTransfer) {
Consider what happens when thread A executes:
transferMoney(accountOne, accountTwo, amount);
While at the same time, thread B executes:
transferMoney(accountTwo, accountOne, anotherAmount);
Again, the two threads try to acquire the same two locks, but in different orders.
Use an ordering to acquire locks in a fixed sequence
public void transferMoney(Account fromAccount,Account toAccount,DollarAmount amountToTransfer) {
Account firstLock, secondLock;
if (fromAccount.accountNumber() == toAccount.accountNumber())
throw new Exception("Cannot transfer from account to itself");
else if (fromAccount.accountNumber() < toAccount.accountNumber()) {
firstLock = fromAccount; secondLock = toAccount;}
else {
firstLock = toAccount; secondLock = fromAccount;}
synchronized (firstLock) {
synchronized (secondLock) {
if (fromAccount.hasSufficientBalance(amountToTransfer) {
Another way to induce an ordering on objects is to use System.identityHashCode, which returns the value that would be returned by Object.hashCode.
Starvation describes a situation where a thread is unable to gain regular access to shared resources and is unable to make progress. This happens when shared resources are made unavailable for long periods by "greedy" threads.
Difference between Thread.sleep() and Object.wait()
1.       Thread.sleep is static method of Thread class and Thread.sleep would throw InterruptedException when it is awaken by other thread prematurely.
2.       Thread.sleep can be used anywhere in the code to halt the current thread execution for the specified time.
3.       Thread.sleep causes the current thread into Non-Runnable state, but, it doesn't release ownership of the acquired monitors. So, if the current thread is into a synchronized block/method, then no other thread will be able to enter that block/method.
4.       Thread.sleep(n) guarantees to sleep for at least n milliseconds. But it may sleep for considerably more if the system is busy.
5.       If somebody changes the system time, you may sleep for a very long time or no time at all. The behavior is OS and JDK-dependent.
1.     Object.wait is instance method of Object class.
2.     The wait method is used to put the thread aside for up to the specified time. It could wait for much lesser time if it receives a notify() or notifyAll() call.
3.     Object.wait have to be called inside synchronized block, otherwise it would throw IllegalMonitorStateException.
4.     Object.wait causes the current thread into Non-Runnable state, like Thread.sleep, but Object.wait releases the locks before going into Non-Runnable state. This causes the current thread to wait either another thread invokes the 'notify()' method or the 'notifyAll()' method for this object, or a specified amount of time has elapsed.
5.     Using sleep makes your codes non-scalable across hardwares, where a nicely written wait/notify code scales well.



Java (162) Lucene-Solr (112) Interview (63) J2SE (53) Algorithm (45) Soft Skills (39) Eclipse (32) Code Example (31) Troubleshooting (27) JavaScript (23) Linux (22) Spring (22) Tools (22) Windows (22) Web Development (20) Nutch2 (18) Bugs (17) Dev Tips (17) Debug (16) Defects (14) Text Mining (14) J2EE (13) Network (13) PowerShell (11) Chrome (10) Problem Solving (10) Google (9) How to (9) Learning code (9) Performance (9) Security (9) UIMA (9) html (9) Design (8) Http Client (8) Maven (8) bat (8) blogger (8) Big Data (7) Database (7) Guava (7) JSON (7) Shell (7) System Design (7) ANT (6) Coding Skills (6) Lesson Learned (6) Programmer Skills (6) Scala (6) css (6) Algorithm Series (5) Cache (5) Continuous Integration (5) IDE (5) Testing (5) adsense (5) xml (5) AIX (4) Become a Better You (4) Code Quality (4) Concurrency (4) GAE (4) Git (4) Good Programming Practices (4) Jackson (4) Life (4) Memory Usage (4) Miscs (4) OpenNLP (4) Project Managment (4) Review (4) Spark (4) ads (4) regular-expression (4) Android (3) Apache Spark (3) Distributed (3) Dynamic Languages (3) Eclipse RCP (3) English (3) Happy Hacking (3) IBM (3) J2SE Knowledge Series (3) JAX-RS (3) Jetty (3) Mac (3) Python (3) Restful Web Service (3) Script (3) regex (3) seo (3) .Net (2) Android Studio (2) Apache (2) Apache Procrun (2) Architecture (2) Batch (2) Bit Operation (2) Build (2) Building Scalable Web Sites (2) C# (2) C/C++ (2) CSV (2) Career (2) Cassandra (2) Fiddler (2) Google Drive (2) Gson (2) How to Interview (2) Html Parser (2) Http (2) Image Tools (2) JQuery (2) Jersey (2) LDAP (2) Logging (2) Software Issues (2) Storage (2) Text Search (2) xml parser (2) AOP (1) Application Design (1) AspectJ (1) Chrome DevTools (1) Cloud (1) Codility (1) Data Mining (1) Data Structure (1) ExceptionUtils (1) Exif (1) Feature Request (1) FindBugs (1) Firefox (1) Greasemonkey (1) HTML5 (1) Httpd (1) I18N (1) IBM Java Thread Dump Analyzer (1) Invest (1) JDK Source Code (1) JDK8 (1) JMX (1) Lazy Developer (1) Machine Learning (1) Mobile (1) My Plan for 2010 (1) Netbeans (1) Notes (1) Operating System (1) Perl (1) Problems (1) Product Architecture (1) Programming Life (1) Quality (1) Redhat (1) Redis (1) RxJava (1) Solutions logs (1) Team Management (1) Thread Dump Analyzer (1) Tips (1) Visualization (1) boilerpipe (1) htm (1) ongoing (1) procrun (1) rss (1)

Popular Posts