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

LeetCode 435 - Non-overlapping Intervals

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
- TreeSet

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;
Arrays.sort(starts);
Arrays.sort(ends);
- Use PriorityQueue
Arrays.sort(intervals, (a, b) -> { return a.start - b.start;}});
PriorityQueue ends = new PriorityQueue();
ends.offer(intervals[0].end);
https://discuss.leetcode.com/topic/25503/java-another-thinking-process-event-queue/2
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
https://discuss.leetcode.com/topic/22482/short-java-solution
http://www.programcreek.com/2014/06/leetcode-the-skyline-problem-java/
https://discuss.leetcode.com/topic/28482/once-for-all-explanation-with-clean-java-code-o-n-2-time-o-n-space
https://discuss.leetcode.com/topic/38065/java-solution-using-priority-queue-and-sweepline

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());
        heightMap.put(0,1);
        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) {
                    heightMap.remove(h[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
https://discuss.leetcode.com/topic/16511/share-my-divide-and-conquer-java-solution-464-ms
http://www.geeksforgeeks.org/divide-and-conquer-set-7-the-skyline-problem/

 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);
    l1.removeFirst();
   } else if (l1.getFirst()[0] > l2.getFirst()[0]) {
    x = l2.getFirst()[0];
    h2 = l2.getFirst()[1];
    h = Math.max(h1, h2);
    l2.removeFirst();
   } else {
    x = l1.getFirst()[0];
    h1 = l1.getFirst()[1];
    h2 = l2.getFirst()[1];
    h = Math.max(h1, h2);
    l1.removeFirst();
    l2.removeFirst();
   }
   if (rs.size() == 0 || h != rs.getLast()[1]) {
    rs.add(new int[] { x, h });
   }
  }
  rs.addAll(l1);
  rs.addAll(l2);
  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.
https://discuss.leetcode.com/topic/35253/explanation-of-super-easy-java-solution-beats-98-8-from-pinkfloyda

    public int minMeetingRooms(Interval[] intervals) {
        int[] starts = new int[intervals.length];
        int[] ends = new int[intervals.length];
        for(int i=0; iint

rooms = 0; int endsItr = 0; for(int i=0; iif(starts[i]else endsItr++; } return rooms; }X. Using prority queue + sweep line
http://www.cnblogs.com/yrbbest/p/5012534.html
https://discuss.leetcode.com/topic/20958/ac-java-solution-using-min-heap/10

    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;
                else
                    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
            pq.add(intervals[i].end);
            while(pq.size() > 0 && intervals[i].start >= pq.peek())
                pq.remove();
                
            maxOverlappingMeetings = Math.max(maxOverlappingMeetings, pq.size());
        }
        
        return maxOverlappingMeetings;
    }

https://discuss.leetcode.com/topic/25503/java-another-thinking-process-event-queue/


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.
https://discuss.leetcode.com/topic/31306/easy-java-solution-beat-98
https://discuss.leetcode.com/topic/20959/ac-clean-java-solution

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;
}

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

http://stackoverflow.com/questions/437620/java-synchronized-methods-lock-on-object-or-class 

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.

Resources:

Java/J2EE Job Interview Companion

http://www.java-questions.com/Threads_interview_questions.html

Oracle JRockit: The Definitive Guide

Interview Questions - XML

                        Interview Questions - XML

DOM, SAX, StAX

http://geekexplains.blogspot.com/2009/04/sax-vs-dom-differences-between-dom-and.html

http://sharat.wordpress.com/2006/09/27/83-what-are-the-differences-between-sax-and-dom-parser/

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

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

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

 

Resources:

Pro XML Development with Java Technology

http://geekexplains.blogspot.com/2009/04/sax-vs-dom-differences-between-dom-and.html

http://sharat.wordpress.com/2006/09/27/83-what-are-the-differences-between-sax-and-dom-parser/

http://www.devx.com/Java/Article/30298

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

yield()

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();

executor.execute(runnable);

executor.shutdown();

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

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

Example:

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) {

fromAccount.debit(amountToTransfer);

toAccount.credit(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) {

fromAccount.debit(amountToTransfer);

toAccount.credit(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

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()

Thread.sleep

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.

Object.wait

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.

Resources:

http://java.sun.com/docs/books/tutorial/essential/concurrency/index.html

http://blogs.codehaus.org/people/jboner/archives/001135_use_total_ordering_of_objects_to_avoid_deadlocks.html