Interesting Google Videos

Here are some interesting videos that Google has produced:

How to Break Web Software

Mondrian Code Review on the Web

BigTable: A Distributed Structured Storage System

Cluster Computing and MapReduce

Java Interview Preparation

I spent close to 40 hours studying for the Google onsite interview. Here's an outline of the material I studied and how relevant it ended up being to the actual interview:

• TopCoder Algorithms Tutorials. I worked through all of these and practiced at least a couple problems related to each article. I wasn't asked any geometry problems but also hadn't mention any graphics experience on my resume. However, there was a coding question involving a greedy algorithm and another requiring depth-first search. For some code solutions, the interviewer asked for the big-O time complexity.
• Wu:Riddles CS Forum. This ended up being very important! I worked through the entire forum, paying special attention to problems that looked especially interview worthy. Going through this forum was much more effective than practicing TopCoder problems. A lot of interview material was related to topics discussed on this forum.
• Wu:Riddles in general. This is one of the best collections of classic riddles and puzzles on the web. I didn't get any interview questions that were riddle-like, but if there had been any, this web site almost certainly would either have had the exact riddle or something very similar to it. Maybe that's why they don't use riddles much any more. But solving riddles seems to be a good way to keep the creative side of problem solving sharp, and it's also a nice break from textbook study.
  
• CLR Algorithms book. I wanted to have solid preparation on algorithms and especially to be able to give textbook examples of each kind of algorithm -- e.g. problems solvable with gredy algorithms, problems that benefit from dynamic programming, how hash tables work, etc. I wasn't directly asked for examples, but knowing them did help recognize what algorithms may apply to a coding problem. Of course, I didn't have time to study the entire book, so my focus was on topics that appeared in the TopCoder tutorials and the Wu:Riddles forum.
  
• Wikipedia pages on algorithms, sorting, big O notation, and the pigeon hole principle. For me, these were a gentler intro before getting into CLR. Studying the Wikipedia pages would probably have been enough preparation, but for me diving into CLR and going deeper than necessary was a way to ensure the fundamentals were really solid.
  
• Design Patterns book. The most important part to know was the first chapter. The questions I was asked were cleverly aimed to probe for experience in using design patterns. We talked about what patterns are, why they're important, when to use them, when not to use them (a good answer shows experience), how to decide what patterns to use and not to use, etc. That part of the interview basically involved giving a 5-minute synopsis of Chapter 1, plus a few design stories to illustrate key points. I had prepared a list of JDK examples of each pattern to talk about, but was asked more about patterns I've used or avoided in my own code.
  
• Effective Java book. I read the whole thing and typed up a study sheet for each item heading, including bullets for any sentences that were in boldface. I also had stories of real-world design experiences where going against the advice of the book ended up being critical to success. The interviewer seemed to like those stories.
• Refactoring book. My resume had specific items about refactoring experience, and one interviewer did ask a lot of questions about it. Chapers 2-4 were the most important to know, especially describing what forces affect the decision of whether to refactor or not to refactor, listing what code smells were most common by my experience, identifying key techniques for successful refactoring, etc.

Below are some other hints I collected from the web and other people who've interviewed at tech companies (not necessarily at Google):

• How do ArrayList, HashMap, LinkedList, and HashSet work and what are their big-O time and space complexities?
  
• Can you take a while or for loop and wrap it inside a java.util.Iterator implementation?
• How do you use the synchronized keyword together with wait() and notify()/notifyAll()?
  
• Bit manipulation tricks
  
• Coding on a whiteboard is effective in an interview for a few reasons.
• It shows whether you know the language well enough to be productive without an IDE.
• It really exposes how clear your thinking is, especially how close you are to the final solution on the first try.
  
• It shows how good you are at stepping through your own code. Are you systematic and careful? Or ad hoc and rushed?
  
• Java language keywords/constructs and their edge cases -- e.g. try-finally, static, checked vs. runtime exceptions, where classes can be declared, etc.
  
• What techniques do you use to maximize unit test coverage in your code? Have you experienced any situations where achieving a high level of unit test coverage was difficult? What made it difficult and what did/could you do to lessen the difficulty?
• You are investigating a bug, but when you try the reported steps, sometimes the bug occurs and sometimes it does not.
• In your experience, what are the most common reasons that a bug might be inconsistently reproducible? Come up with at least 5 types of causes and give an example of each.
  
• For each potential reason, what techniques would you use to identify the cause of the bug and its fix?
• Have you ever fixed a bug which you never actually observed directly? If yes, how were you able to locate the problem and fix it?
  

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.

Greedy Algorithms

A greedy algorithm is very similar to a dynamic programming algorithm. Both require the problem to have optimal substructure. However, whereas DP also needs overlapping subproblems, a greedy algorithm must have the opposite -- subproblems are not interdependent. Furthermore, the subproblems must be structured in such a way that making a locally optimal decision at each step in constructing the solution always leads to the globally optimal solution. This is known as the greedy-choice property. To know that a greedy algorithm will correctly solve a problem, you generally need to prove that the problem has the greedy-choice property. According to CLR, that proof can sometimes require "some cleverness."

The textbook examples are:

• Activity Scheduling
• Fractional Knapsack Problem (but not 0-1 Knapsack Problem)
  
• Huffman Codes
• Dijkstra's Algorithm
  

Dynamic Programming Algorithms

Notes on dynamic programming, from CLR Algorithms Ch 16.

Key points:

• Solves problems by combining solutions to subproblems.
• Requires that the problem possess optimal substructure.
  
• Differs from divide-and-conquer in that subproblems are overlapping.
• Can use table lookup (memoization) to avoid solving a subproblem more than once.
• Memoization allows for a top-down strategy, instead of DP's usual bottom-up approach.
  
• DP is typically used for optimization problems, where a minimum or maximum value is sought.

Four steps to developing a dynamic programming algorithm:

1. Describe the structure of an optimal solution.
   
2. Recursively define the value of an optimal solution.
3. Compute the value of an optimal solution in bottom-up fashion.
4. Construct an optimal solution from the computed information.

Textbook examples where dynamic programming solutions apply:

• Matrix-chain multiplication
• Longest common subsequence of two sequences
• Optimal triangulation of a convex polygon

CLR says: "In general practice, if all subproblems must be solved at least once, a bottom-up DP algorithm usually outperforms a top-down memoized algorithm by a constant factor, because there is no overhead for recursion and less overhead for maintaining the table. Moreover, there are some problems for which the regular pattern of table accesses in the DP algorithm can be exploited to reduce time or space requirements even further. Alternatively if some subproblems in the subproblem space need not be solved at all, the memoized solution has the advantage of only solving those subproblems that are definitely required."

class Enum<K extends Enum<K>>

In Java, the java.lang.Enum class is declared as:

public abstract class Enum<E extends Enum<E>>

Why is the type parameter declared as <E extends Enum<E>>? What would happen if it were declared as <E extends Enum> instead?
Solution


This pattern is used when a generic base class needs to reference the type of the subclass. For example, suppose we had:

public enum CardSuit { HEARTS, CLUBS, DIAMONDS, SPADES }

This gets compiled as something like:

public class CardSuit extends Enum<CardSuit>....

which then means that every occurrence of type parameter E in Enum's declaration becomes CardSuit. Thus, the superclass (Enum) is able to reference subclass types in its method signatures and return types this way through the type parameter.

If just <E extends Enum> were used instead, that would still be the case, but some information would be lost. The type parameter E is mentioned in three places in Enum:

1. implements Comparable<E>
2. public int compareTo(E o)
3. public Class<E> getDeclaringClass()

If the class declaration just had E extends Enum, then the Comparable interface is only aware of Comparable<Enum> instead of Comparable<CardSuit>. So E extends Enum<E> contains some extra information, making it more typesafe.