Permutations by Swapping Adjacent Pairs

References:
1) Counting and Listing All Permutations
2) An algorithm to list all the permutations

Known variously as the Steinhaus-Johnson-Trogger algorithm, the Johnson-Trotter algorithm, or the Steinhaus algorithm. Summarized in these steps:

Initialize the first permutation with <1 <2 ... <n
While there exists a mobile integer:

1. Find the largest mobile integer k.
2. Swap k and the adjacent integer it is looking at.
3. Reverse the direction of all integers larger than k.
   

To embody the traveling metaphor into action, the algorithm replaces integer as the basic element of the procedure with a structure that maintains an integer and a direction. Call the structure a directed integer, or just an integer if the context is clear. The direction may take on only one of two values, "left" or "right", and can be implemented as a boolean. It's convenient and certainly appropriate to say that a directed integer is looking left- or rightwards depending on the value of the attached field direction.

The algorithm requires one more definition: a directed integer is said to be mobile if it is greater than its immediate neighbor in the direction it is looking at.

Example output:

1 2 3 4
1 2 4 3
1 4 2 3
4 1 2 3
4 1 3 2
1 4 3 2
1 3 4 2
1 3 2 4
3 1 2 4
3 1 4 2
3 4 1 2
4 3 1 2
4 3 2 1
3 4 2 1
3 2 4 1
3 2 1 4
2 3 1 4
2 3 4 1
2 4 3 1
4 2 3 1
4 2 1 3
2 4 1 3
2 1 4 3
2 1 3 4

OO Design Methodologies

(From GoF Design Patterns, Section 1.6 "How Design Patterns Solve Design Problems")

Object-oriented design methodologies differ in their approaches:

1. Create classes and operations based on the nouns and verbs found in a written problem statement or specification.
   
2. Focus on collaborations and responsibilities. Use CRC Cards (from Kent Beck) as a design aid.
3. Translate real-world objects directly into object types and their behaviors into operations, known as the analysis model.
   

GoF says there will always be a disagreement on which approach is best, though the analysis model appears to be popular. However, the OO design still often ends up with classes that have no counterparts in the real world, so GoF warns:

Strict modeling of the real world leads to a system that reflects today's realities buyt not necessarily tomorrow's. The abstractions that emerge during design are key to making a design flexible. Design patterns help you identify less-obvious abstractions and the objects that can capture them.

For example: Design a chess system using object-oriented principles.

Coefficients of Binomial Expansion

Given a binomial of the form (x+y)ⁿ, where n >=1, write a function coefficients(int n) that prints out the coefficients of the binomial expansion in O(n) time. For example, calling coefficients(10) prints:

1 10 45 120 210 252 210 120 45 10 1

Solution

We start with the binomial theorem, which tells us that the coefficient for each term k (1 <= k <= n) is n!/(k!(n-k)!). Using coefficients(10) as an example, we can see that the term in position #1 has degree 10 and coefficient 1. The coefficient of the next term (#2 with degree 9) is:

  10!      10
------- = ----
 1!9!      1

The next term (#3 with degree 8) is:

  10!     10*9
------ = ------
 2!8!      1*2

And the next term (#4 with degree 7) is:

  10!     10*9*8
------ = --------
 3!7!      1*2*3

Notice the pattern unfolding: the coefficient for the term in position k is the ((coefficient*degree)/position) of the term in position k-1. So we can implement this quite efficiently:

public void coefficients(int n)
{
  int coeff = 1;
  int degree = n;
  int position = 1;
  do
  {
    System.out.print( coeff + " " );
    coeff = ( coeff * degree-- ) / position;
  } while ( position++ <= n );
  System.out.println();
}

Of course, this can be made even more efficient by exploiting the symmetry of the coefficients, but as it stands, this implementation runs in O(n) time.

A Coder and a Half

If a coder and a half write a module and a half in a day and a half, how many modules can 6 coders write in 7 days?

Solution

We know that 1½ coders write 1½ modules in 1½ days.
So 3 coders write 3 modules in 1½ days.
So 6 coders write 6 modules in 1½ days.
So 6 coders write 12 modules in 3 days.
So 6 coders write 24 modules in 6 days.
So 6 coders write 28 modules in 7 days.

The answer is 28 modules.

GoF Design Patterns

Motivation and Purpose

• Encapsulate internal state of objects.
• Distinguish intrinsic state from extrinsic state.
  
• Decompose a system into abstractions.
• Delegation works best when used in highly stylized ways (i.e. design patterns).
  
• Principles of reusable object-oriented design:
• Program to an interface, not an implementation. (Use loose coupling.)
  
• Favor object composition over class inheritance. (Use delegation.)
  
• Techniques for designing for change:
• Avoid dependency on type of implementation class.
• Avoid dependency on specific operation dispatch.
• Increase information hiding.
• Increase algorithm hiding.
• Decrease tight coupling; increase loose coupling.
• Increase flexibility by using object composition in general and delegation in particular instead of subclassing.
• Alter behavior of a library class without modifying the library.
  

Examples of design patterns in Java:

Creational Patterns

• Abstract Factory -- BorderFactory, Collections, org.w3c.dom.Document (create methods)
  
• Builder -- StringBuilder, ProcessBuilder
  
• Factory Method -- URLStreamHandlerFactory, InitialContextFactory
  
• Prototype -- (copyable state objects for supporting cancelable UI)
  
• Singleton -- java.lang.Runtime
  

Structural Patterns

• Adapter -- InputStreamReader, OutputStreamWriter
  
• Bridge -- Swing PLAF
  
• Composite -- java.awt.Component/Container
  
• Decorator -- BufferedReader/Writer, ZipInputStream, other java.io classes
  
• Facade -- what Swing is to java.awt.Graphics
  
• Flyweight -- Icon (when cached)
  
• Proxy -- RMI, WeakReference, ThreadLocal
  

Behavioral Patterns

• Chain of Responsibility -- KeyEvent dispatch in AWT/Swing (consume() method stops chain)
  
• Command -- javax.swing.Action (not quite - need a better example)
  
• Interpreter -- java.util.regex.Pattern
  
• Iterator
  
• Mediator -- event cascades
  
• Memento --javax.swing.undo.UndoableEdit, java.awt.datatransfer.Transferable, java.beans.XMLEncoder/Decoder
  
• Observer -- Swing/AWT event listeners
  
• State -- graphical tools (e.g. from a component palette) used in a visual editor
  
• Strategy -- dispatch of Undo; typical pattern for View-Controller interaction
  
• Template Method -- java.io.Reader/Writer
  
• Visitor -- SAX API (org.xml.sax)
  

Examples of the Pigeonhole Principle

From the Wikipedia article:

• You have a drawer with 10 black socks and 12 blue socks. Without looking in the drawer, how many socks do you need to pull out to get at least one pair of socks the same color?
• Show that there must be at least two people in London with the same number of hairs on their head.
• If there are N people (N >= 2) who can arbitrarily shake hands with one another, show that there are at least two people who shake the same number of hands.
• Show that there cannot be a lossless compression algorithm that will compress any file to a strictly smaller size.

Ties into probability theory:

• If 2 pigeons are randomly assigned to 4 pigeonholes, there is a 25% chance that at least one pigeonhole will hold more than one pigeon. For 5 pigeons and 10 holes, it's 69.76%. For 10 pigeons and 20 holes, it's 93.45%.
  
• Given a group of 23 randomly chosen people, there is more than a 50% chance that at least two of them will have the same birthday. For 60 or more people, the probability is greater than 99%. (Known as the Birthday Paradox)

Puzzles whose solutions use the pigeonhole pricniple:

• You have a chessboard with two diagonally opposite corners removed. Is it possible to cover the remaining board with domino pieces that are each two board squares in size?
• There are 500 boxes with apples, each containing no more than x apples. Find the maximal possible value of x , such that one can for sure find 3 boxes containing equal number of apples.
  
• Several math proofs using the pigeonhole principle.
• And some other interesting math problems on the PHP.
  

Clock Hands

An analog clock shows the time as 3:15. What is the angle between the hour and minute hands?

Solution

The hour hand will move 360 degrees in 12 hours, so that's 30 degrees per hour, which is 7.5 degrees per 15 minutes. So at 3:15, the hour hand is at 97.5 degrees when the minute hand is at 90 degrees. So the angle between them is 7.5 degrees.

Russian Roulette

You are forced to play a game of Russian roulette. The gun with six chambers is initially empty, and your comrade puts two bullets in the gun in adjacent chambers. He closes the barrel, spins it, and pulls the trigger. CLICK - the chamber was empty. Now he puts the gun to your head and will pull the trigger one more time. Which do you prefer - that the barrel first be spun again or that he just pull the trigger?

Solution

Your odds are better if he pulls the trigger without spinning again.

If the barrel is respun, you have a 2/3 (4 out of 6) chance of survival. However, you know that the gun was already triggered on an empty chamber. There are 4 empty chambers, and 3 of them are followed by another empty chamber; only 1 out of 4 is followed by a bullet. So, if the trigger is pulled without respinning, you have a 3/4 chance of survival.

Four Quarts

If you had an infinite supply of water and a 5 quart and 3 quart jug, how would you measure exactly 4 quarts?

Solution

1. Fill the 5Q jug.
2. Pour contents of 5Q jug to fill the 3Q jug. This leaves 2 quarts in the 5Q jug.
   
3. Empty the 3Q jug.
4. Pour remaining 2 quarts from the 5Q jug into the 3Q jug. There is 1 quart of space left in the 3Q jug.
   
5. Fill the 5Q jug.
6. Pour water from the 5Q jug into the 3Q jug until it is full.
7. The 5Q jug now has 4 quarts.

First Common Node in Intersecting Linked Lists

You have two singly linked lists, L1 and L2, which start from different head nodes. Some number of nodes into each list, they meet at a common node and share all the nodes from that point on. Describe an algorithm for finding the first common node.

Solution

The naive approach would be to start with the first node of L1 and check each node of L2 to see if it matches, iterating until a match is found. But of course, we can do better.

The key is that because L1 and L2 have a common "tail", you can just compare corresponding nodes between L1 and L2, walking down the lists in tandem, as long as they are the same distance from the tail end of the list. To get to that point, you first traverse L1 and L2 separately to determine their lengths. Then you skip over the first |L1-L2| nodes from the longer list, since those couldn't possibly be part of the common tail. Now you're looking at the same number of remaining nodes in both lists. Just walk down them together, checking corresponding nodes until the common one is found.

Sorting Algorithms Summary

• O(N²) in average and worst case; no extra memory required; stable.
  
• Bubble sort
• Uses about N²/2 comparisons and N²/2 exchanges on the average and in the worst case.
  
• Selection sort
• Find the smallest element in the array and exchange it with the element in the first position. Then repeat for 2nd, 3rd,...,nth positions.
  
• Uses about N²/2 comparisons and N exchanges.
  
• Each item is moved at most once.
• Method of choice for sorting files with very large records.
  
• Insertion sort
  
• Consider the elements one at a time, inserting each in its proper place among those already considered, keeping them sorted.
  
• Is linear for "almost sorted" files.
  
• Uses about N²/4 comparisons and N²/8 exchanges on the average; twice as many in the worst case.
• Uses sentinel value to avoid having extra boundary check in inner loop.
  

Effective Java Summary

1. Static factory methods vs. constructors.
1. Advantages
1. They have descriptive names.
1. Example: BigInteger.probablePrime
2. They can reuse existing objects.
1. Example: Boolean.valueOf(boolean)
3. They can return a subtype of the declared type - good for hiding impl classes.
1. Example: java.util.Collections methods
2. Example: service provider frameworks like Java Cryptography Extension
2. Disadvantages
1. If class has no public or protected ctors, it can't be subclassed.
2. Static factory methods are not distinguished in javadoc from other static methods.
1. Can compensate by using standard naming conventions (still evolving), e.g. valueOf, getInstance, etc.
   
2. Use private ctor to enforce singleton
1. More future flexibility if singleton obtained through static method. E.g. lets you return a unique instance per thread in the future without changing API.
2. If singleton is Serializable, must also implement readResolve().
   
3. Use private ctor to enforce noninstantiability.
1. Making class abstract for this purpose does not work.
4. Avoid duplicate objects
1. Especially if object is immutable.
2. Relates to using static factory methods instead of ctors (Item 1).
   
3. Can make it clear when objects are used as if they were constants (e.g. Calendar).
4. Relates to lazy initialization (Item 48).
5. Case: adapters that delegate to a backing object.
6. But, object pools are generally bad, except when object is extremely expensive to create (e.g. database connection).
   
5. Clean out obsolete objects
1. Mainly to prevent memory leaks (termed unintentional object retentions).
2. Essential when a class manages its own memory.
3. Common issue in caches. Possible solution strategies:
1. WeakHashMap
2. Timer-based expiration of old objects.
3. java.util.LinkedHashMap - has a removeEldestEntry method, which can expire entries based on insertion-order or access-order, depending on how the LinkedHashMap is constructed.
4. Diagnosis of memory leaks usually requires using a heap profiler.
   
6. Finalizer issues
   
1. Two legitimate uses: safety net and cleaning up noncritical native resources.
2. Finalizer guardian idiom - consider using for every nonfinal public class with a finalizer.
   
7. Contract of equals
1. When not overriding is ok:
1. Each instance of the class is inherently unique (e.g. Thread).
2. A logical equality test isn't really needed (e.g. java.util.Random).
3. A superclass alread implements equals adequately (e.g. AbstractSet, AbstractList, AbstractMap).
4. Class is private or package-private, and you're certain equals will never be called. But, could implement anyway to at least throw UnsupportedOperationException, just to make sure.
2. When overriding is recommended:
1. When there's a concept of logical equality that's different from object identity.
   
8. Override hashCode when overriding equals
1. Required if object used as key in HashMap/Hashtable or value in HashSet.
2. Equal objects must have equal hash codes.
3. 
   
9. Override toString
10. clone
1. clone() is like another constructor.
2. Callers of clone() must cope with catching an exception.
   
3. clone() is incompatible with the normal use of final fields.
4. You are probably better off providing an alternative means of object copying.
5. One alternative is the copy constructor.
   
11. Comparable
12. Minimize accessibility
1. For information hiding and encapsulation
2. Purpose is to hide design decisions, so that they may be changed in the future with no impact to the API.
   
13. Immutable objects
1. Inherently thread-safe; no synchronization required.
2. Can be shared freely.
3. Even internals can be shared
4. But they require a new object for each distinct value (e.g. BigInteger).
5. Classes should be immutable unless there's a very good reason to make them mutable.
6. If a class cannot be made immutable, limit its mutability as much as possible.
7. Constructors should create fully initialized objects with all their invariants established.
   
14. Composition vs. inheritance
1. Inheritance breaks encapsulation.
2. Inheritance must document self-use (evidence of broken encapsulation).
15. Prohibit inheritance if not designed for inheritance
1. Must document precisely the effects of overriding any method.
2. May have to provide hooks into internal workings for subclass to use.
3. Constructors must not invoke overridable methods.
4. Neither clone nor readObject may invoke an overridable method, directly or indirectly.
   
16. Interfaces vs. abstract classes
1. Existing classes can be easily retrofitted to implement a new interface.
2. Interfaces are ideal for defining mixins.
3. Interfaces allow the construction of nonhierarchical type frameworks.
4. Intefaces enable safe, powerful functionality enhancements via the wrapper class idiom.
5. It is far easier to evolve an abstract class than it is to evolve an interface.
   
17. Proper use of interfaces
1. Don't use interfaces as a means of exporting constants.
   
18. Static vs. nonstatic member classes
1. If you declare a member class that doesn't require access to an enclosing instance, put the static modifier in the declaration.
   
19. C structures => classes
20. C unions => class hierarchies
21. C enum => classes (in JDK 1.5, enum)
22. C function pointers => classes and interfaces
23. Validate method parameters
1. Document restrictions and enforce them with checks that throw runtime exceptions.
   
2. Nonpublic methods should generaly check their parameters using assertions rather than normal checks.
   
24. Defensive copies
1. You must program defensively with the assumption that clients of your class will do their best to destroy its invariants.
2. It's essential to make a defensive copy of each mutable parameter to the constructor.
3. Defensive copies are made before checking the validity of the parameters, and the validity check is performed on the copies rather than the originals -- prevents possible race with another thread.
4. Do not use the clone method to make a defensive copy of a parameter whose type is subclassable by untrusted parties.
   
25. Method signature design
1. Choose method names carefully, following standard naming conventions (item 38).
2. Don't go overboard in providing convenience methods. When in doubt, leave it out.
3. Avoid long parameter lists. Long sequences of identically typed parameters are especially harmful.
1. Break up method into multiple methods, each with fewer parameters.
2. Create helper classes (aka parameter object) to hold aggregates of parameters.
4. For parameter types, favor interfaces over classes.
5. Avoid function objects unless there is good reason to use them.
   
26. Method overloading
1. The choice of which method overload to invoke is made at compile time.
2. Note: selection among overloaded methods is static, but selection among overridden methods is dynamic.
3. Avoid confusing uses of overloading. A safe, conservative policy is nevr to export two overloadings with the same number of parameters.
1. Use differently named methods instead - e.g. ObjectOutputStream's write* and read* methods.
   
27. Returning zero-length array vs. null
1. Null causes special-case code to be in both the method and the client.
2. Zero-length arrays are immutable and thus can be shared freely.
   
3. There is no reason ever to return null from an array-valued method instead of returning a zero-length array.
   
28. Document all exported APIs
1. Every exported class, interface, and member should be preceded with a doc comment.
   
2. Method doc should succinctly describe the contract between the method and the client.
3. The contract should say what the method does rather than how it does its job.
4. Sometimes necessary to document overall architecture of a complex API in a separate document, linked from the related class or package doc comments.
   
29. Minimize local variable scope
30. Know the libraries
31. float/double and exact answers
32. String vs. non-string
33. Perf of string concatenation
34. Refer to objects by their interfaces
35. Interfaces vs. reflection
36. Avoid native methods
37. Optimizing
38. Naming conventions
39. Proper use of Exceptions
40. Checked vs. runtime exceptions
41. Proper use of checked exceptions
42. Benefits of standard exceptions
43. Exceptions and abstraction
44. Document all thrown exceptions
45. Exception message detail
46. Failure atomicity
47. Don't ignore exceptions
48. Synchronize access to shared mutable data
49. Avoid excessive synchronization
50. Never invoke wait outside a loop
51. Don't depend on the thread scheduler
52. Document thread safety
53. Avoid thread groups
1. They are basically obsolete.
2. Only useful bit is ThreadGroup.uncaughtException for handling an uncaught exception thrown from one of the threads in the group.
   
54. Implementing Serializable
55. Custom serialized form
56. Defensive readObject impl
57. When to provide readResolve

Algorithms Summary

• Sorting
• quicksort, heapsort, mergesort
  
• Shortest Path
• Dijstra's Algorithm -- O(E V log V) -- priority queue
  
• Approximate Algorithms
• NP-complete problems, e.g. TSP
  
• Find a path that is at most 10% longer than the shortest path.
  
• Random Algorithms
• Quicksort -- average O(N log N)
  
• Find median number -- average O(N)
  
• Compression
• LZW, MP3, JPG
  
• Maximum Flow, Minimum Cut
• Fastest flow of supplies through rail network.
• Minimum change needed to disrupt flow.
• How to assign N employees to M jobs so that every job gets done.
  
• Sequence Comparison
• Use DP to get O(N*M) instead of exponential.