Google Interview Question Set-3

1. Given a linked list structure where every node represents a linked list and contains two pointers of its type:
(i) pointer to next node in the main list.
(ii) pointer to a linked list where this node is head.
Write a C function to flatten the list into a single linked list. (from here)

2. Hundred of millions of irregular shape objects are moving in random direction. Provide data structure and algo to detect collision. (from here)

3. You are given an array of integer A[1..n] and a maximum sliding window of size w. you need to output an array B where B[i] is the maximum in A[i, i+w-1]. (from here)

4. [Design] Find duplicate profiles in Facebook.

5. You have an array of 0s and 1s and you want to output all the intervals (i, j) where the number of 0s and numbers of 1s are equal. (from here)

6. You have a stream of random numbers that are inserted into an expanding array. How can you maintain the current median and what is the complexity.

7. Given n arrays, find n number such that sum of their differences is minimum. For e.g. if there are three arrays

A = {4, 10, 15, 20}
B = {1, 13, 29}
C = {5, 14, 28}

find three numbers a, b, c such that |a-b| + |b-c| + |c-a| is minimum. Here the answer is a = 15, b = 13, and c = 14

8. [Coding] Write a C/C++ program to create a bitmap of any size as determined by user. Say user says 64k bitmap, then create 64k long bitmap. Have set and unset methods.

9. Reorder 1st string based on 2nd string.
eg: (tractor,car)
output: carrtto or carrott or carrtot.

10. There is a straight roads with ‘n’ number of milestones. You are given an array with the distance between all the pairs of milestones in some random order. Find the position of milestones.
Example:
Consider a road with 4 milestones(a,b,c,d) :
a bcd
Distance between a and b = 3
Distance between a and c = 8
Distance between a and d = 10
Distance between b and c = 5
Distance between b and d = 7
Distance between c and d = 2
All the above values are given in a random order say 7, 10, 5, 2, 8, 3.
The output must be 3,5,2 or 2,5,3

11. Given a set of KEY->VALUE pairs such that each KEY is unique, describe a method of storing these pairs on disk, and a method for accessing the corresponding VALUE given a KEY. Assume that RAM is fixed at 1gb and the set of pairs requires 40gb.

12. Consider there is an array with duplicates and you are given two numbers as input and you have to return the minimum distance between the two in the array with minimum complexity.

13. You are given an array of integers, say array1 of size n. You have to create another array (say array2) and fill its contents by following this rule: array2[i] will hold the value of the left-most integer from the range array1[i+1] to array1[n-1] such that it is greater than array1[i]. If no such element exists, assign -1.

14. An external system has an array. You are given 3 inbuilt functions which perform their operation in O(1) time.
a) get(i): returns ith element of array
b) length(): returns length of array
c) reverse(i, j): reverses elements of subarray starting from i and ending with j (both inclusive)

Write function SortArray() using these three functions.

15. Given a binary tree, find 2 leaf nodes say X and Y such that F(X,Y) is maximum where F(X,Y) = sum of nodes in the path from root to X + sum of nodes in the path from root to Y – sum of nodes in the common path from root to first common ancestor of the Nodes X and Y.

16. Given an array, A, find if all elements in the sorted version of A are consecutive in less than O(nlogn).
eg: A: 5 4 1 2 3 on sorting 1 2 3 4 5 all elements are consecutive — true
A: 1 9 2 22 on sorting 1 2 9 22 all elements are NOT consecutive — false

17. Given a string (assume there no spaces or punctuations), write a code that returns the max. length of the string that has repeated more than once

18.Given a network of the employees of a company such that edges are between those employees who are friends to each other. Divide the employees into two teams such that no two people who are friends to each other are in the same team?

Recursion World

List of some of the best resources to learn Recursion, Backtracking and most importantly to start thinking recursively.

1. Recursion Basics, Solving Problems recursively, raise to the power example and mechanics of what is going to happen, Choosing a subset
Video Lecture

2. Thinking Recursively, Permute Code, More Examples, Tree of Recursive calls
Video Lecture http://www.youtube.com/watch?v=uFJhEPrbycQ&feature=PlayList&p=FE6E58F856038C69&index=8

3. Testing with different cases, subsets, subset stratergy, Exhaustive Recursion, Recursive BackTracking, Anagram Finder, N Queens
Video Lecture http://www.youtube.com/watch?v=NdF1QDTRkck&feature=PlayList&p=FE6E58F856038C69&index=9

4. Backtracking Pseudocode, Sudoku Solver, Sudoku Code, Cryptarithmetic
Video Lecture http://www.youtube.com/watch?v=p-gpaIGRCQI&feature=PlayList&p=FE6E58F856038C69&index=10

Reference: http://see.stanford.edu/see/courseInfo.aspx?coll=11f4f422-5670-4b4c-889c-008262e09e4e (Stanford Engineering Everywhere)

Google Interview Shared -Question Set 2

1. Throughout this column we have used the simple definition
that words are separated by white space. Many real documents,
such as those in HTML or RTF, contain formatting commands.
How could you deal with such commands? Are there any other
tasks that you might need to perform?
2. On a machine with ample main memory, how could you use
the C++ STL sets or maps to solve the searching problem in Section 13.8? How much memory does it consume
compared to McIlroy's structure?
3. How much speedup can you achieve by incorporating the special-purpose malloc of Solution 9.2 into the
hashing program of Section 15.1?
4. When a hash table is large and the hash function scatters the data well, almost every list in the table has only a
few elements. If either of these conditions is violated, though, the time spent searching down the list can be
substantial. When a new string is not found in the hash table in Section 15.1, it is placed at the front of the list. To
simulate hashing trouble, set NHASH to 1 and experiment with this and other list strategies, such as appending to
the end of the list, or moving the most recently found element to the front of the list.
5. When we looked at the output of the word frequency programs in Section 15.1, it was most interesting to print
the words in decreasing frequency. How would you modify the C and C++ programs to accomplish this task? How
would you print only the M most common words, where M is a constant such as 10 or 1000?
6. Given a new input string, how would you search a suffix array to find the longest match in the stored text? How
would you build a GUI interface for this task?
7. Our program for finding duplicated strings was very fast for ``typical'' inputs, but it can be very slow (greater
than quadratic) for some inputs. Time the program on such an input. Do such inputs ever arise in practice?
8. How would you modify the program for finding duplicated strings to find the longest string that occurs more
than M times?
9. Given two input texts, find the longest string that occurs in both.
10. Show how to reduce the number of pointers in the duplication program by pointing only to suffixes that start on
word boundaries. What effect does this have on the output produced by the program?
11. Implement a program to generate letter-level Markov text.
12. How would you use the tools and techniques of Section 15.1 to generate (order-0 or non-Markov) random text?
13. The program for generating word-level Markov text is at this book's web site. Try it on some of your
documents.
14. How could you use hashing to speed up the Markov program?
15. Shannon's quote in Section 15.3 describes the algorithm he used to construct Markov text; implement that
algorithm in a program. It gives a good approximation to the Markov frequencies, but not the exact form; explain
why not. Implement a program that scans the entire string from scratch to generate each word (and thereby uses the
true frequencies).
16. How would you use the techniques of this column to assemble a word list for a dictionary (the problem that
Doug McIlroy faced in Section 13.8)? How would you build a spelling checker without using a dictionary? How
would you build a grammar checker without using rules of grammar?
17. Investigate how techniques related to k-gram analysis are used in applications such as speech recognition and
data compression.

15 Puzzle Problem

Optimal 8/15-Puzzle Solver

The 8-puzzle is a classic problem in AI that can be solved with the A* algorithm.

* A* maintains two lists, called open and closed.
* At the beginning of the algorithm, the initial node is placed on the open list. The list is sorted according to an admissible heuristic that measures how close the state of the node is to the goal state.
* At each step, bestNode is removed from the open list. In this case, bestNode is always the head of the open list. If the state of bestNode is the goal state, then the algorithm terminates. Otherwise bestNode is expanded (we determine all the possible states that can be reached within a single move), and bestNode is placed on the closed list.
* The successors of bestNode are placed on the open list if either:
o the successor is not already on the open or closed list, or
o the successor is already on the open or closed list but has a lower cost.

Many 15-puzzles cannot be solved with the A* algorithm, since it generates too many new states and consumes a lot of memory maintaining these lists. To solve this larger puzzle, Iterative-Deepening-A* (IDA*) can be used. Like the A* algorithm, it finds optimal solutions when paired with an admissible heuristic but is much more efficient with respect to space. IDA* is described as follows:

* Set threshold equal to the heuristic evaluation of the initial state.
* Conduct a depth-first search, pruning a branch when the cost of the latest node exceeds threshold. If a solution is found during the search, return it.
* If no solution is found during the current iteration, increment threshold by the minimum amount it was exceeded, and go back to the previous step.

Three heuristics have been implemented for comparison's sake:

* Manhattan Distance
* Manhattan Distance + Linear Conflict
* O. Hansson, A. Mayer, and M. Yung, "Criticizing Solutions to Relaxed Models Yields Powerful Admissible Heuristics," Information Sciences, Vol. 63, Issue 3, pp. 207-227, 1992. Additive Pattern Database Heuristic with Static 6-6-3 Partitioning
A. Felner, R. Korf, and S. Hanan, "Additive Pattern Database Heuristics," Journal of AI Research, Vol. 22, pp. 279-318, 2004.


This JAR file is about 5.6 MB. Please be patient while it loads.
You must accept the certificate in order to run multi-threaded IDA*.

Download standalone version: PuzzleSolver.jar


15-Puzzle
Screenshot of 8/15-Puzzle Solver.


Source Code

* AStar.java
* AStarNode.java
* AboutDialog.java
* Algorithm.java
* Application.java
* ApplicationStarter.java
* BFSNode.java
* Centerable.java
* CenterableDialog.java
* DFSWorker.java
* Entry.java
* FibonacciHeap.java
* GUI.java
* IDAStar.java
* IDAStarNode.java
* ImagePanel.java
* MessageBox.java
* Node.java
* PatternDatabaseGenerator.java
* PrimitiveHashMap.java
* Puzzle.java
* PuzzleConfiguration.java
* PuzzleSolver.java
* Utility.java

Source http://www.brian-borowski.com/Software/Puzzle/

Implementation

This applet provides a means of comparing how different algorithms and heuristics perform on the sliding-tile puzzles. A* is more than acceptable for solving the the 8-puzzle, with its 9! / 2 = 181,440 states and optimal solutions of up to 31 moves. It becomes painfully slow, however, for even average length solutions of the 15-puzzle, which has 16! / 2 = 10,461,394,944,000 states and optimal solutions of up to 80 moves.

IDA* works well on most 15-puzzle configurations, especially when paired with the additive pattern database heuristic. 6-6-3 partitioning provides a good compromise between speed and the amount of memory required to hold the state-to-cost mappings, of which there are 11,534,880. The application runs slightly faster on 64-bit systems running a 64-bit JVM, since there are operations on long primitives.

Starting with version 2.2.0, multi-threaded IDA* can be used to more efficiently solve puzzles. This new alogrithm starts with a breadth-first search of the tree to a level that has a number of nodes greater than or equal to the number of threads. Any nodes that contain the same board configuration are pruned before starting the thread pool. Then multiple depth-first search workers crawl through the search space, looking for a solution of up to threshold moves, as discussed above.

The number of threads is curently hard-coded at twice the number of available cores. This seemingly unusual number has provided the best performance in most cases on my AMD Phenom II x6. Ideally, we want the algorithm to minimize CPU idle time. Idle time occurs toward the end of an iteration in IDA*, when the depth-first search workers start to taper off. Without more complicated code, the next iteration cannot start until we are certain there is no solution for the given threshold. Thus, starting more threads than cores keeps the CPU at max capacity over most of the iteration and generally performs better than when starting fewer threads, even with the added cost of context switching.

Why bother with multi-threading? A single-threaded Java implementation of IDA* cannot compete with the same C implementation. When profiling this code, one will observe that a large majority of execution time is spent in looking up costs in Node.h(). This section of this method that implements with the pattern database heuristic is simple, but Java's array bounds checking truly hinders performance. In a simple test of Java versus C (compiled with gcc, -O2) where array elements are accessed in random order millions of times, C outperformed Java by a factor of 8. When applying the applet's pattern database heuristic, arrays are used only for cost lookups and to store the path to the goal state. Everything else has been implemented with primitives and shift operations. So, in order to improve performance, one must turn to multi-threading.

Usage

The 8/15-Puzzle Solver is easy to use. The options should be straightforward. To enter the configuration of a puzzle, simply list the numbers of the tiles from left to right, top to bottom, each separated by a comma. Enter 0 for the space. For example, "2,4,0,1,8,5,3,6,7" is what you would enter for the board configuration below:

2 4
1 8 5
3 6 7

Note that you must use IDA* to solve 15-puzzles, as the A* option has been purposefully disabled. Multi-threading is not available unless you accept the certificate, since the thread pool cannot be shutdown with the default policy settings, and is not available with the 8-puzzle (since a single thread is more than sufficient).

Google Interview Shared -Question Set 1

Question #1) Given k sorted streams where each stream could possibly be infinite in length, describe an efficient algorithm to merge the k streams into a new stream (also in sorted order).

Question #2) Given a set of KEY->VALUE pairs such that each KEY is unique, describe a method of storing these pairs on disk, and a method for accessing the corresponding VALUE given a KEY. Assume that RAM is fixed at 1gb and the set of pairs requires 40gb.

HINT: we are trying to minimize page-transfers

Question #3) Given N computers networked together, with each computer storing N integers, describe a procedure for finding the median of all of the numbers. Assume that a computer can only hold O(N) integers (i.e. no computer can store all N^2 integers). Also assume that there exists a computer on the network without integers, that we can use to interface with the computers storing the integers.

Question #4) Given the sequence S1 = {a,b,c,d,...,x,y,z,aa,ab,ac.... } and given that this sequence corresponds (term for term) to the sequence S2 = {1,2,3,4,....}
Write code to convert an element of S1 to the corresponding element of S2. Write code to convert an element of S2 to the corresponding element of S1.

Question #5) Given a binary tree with the following constraints:
a) A node has either both a left and right child OR no children
b) The right child of a node is either a leaf or NULL

write code to invert this tree. HINT: Draw this out

Question #6) Given a square with side length = 1, describe all points inside square that are closer to the center of the square than to the edge of the square.

Question #7) How many 0's are at the end of N!

hint: look at the prime factorization of N!

Question #8) Given an array A[string], an array of strings where each string represents a word in a text document. Also given 3 search terms T1, T2, and T3 and 3 corresponding sorted sequences of integers S1, S2, and S3 where each integer in Si represents an index in A where search term Ti occured (i.e. S1, S2, and S3 contain the locations of the search terms in our array of words). Now find a minimal subarray of A that contains all of the search terms T1, T2, and T3. Extend this algorithm for an arbitrary number of search terms.

hint: think of the brute force algorithm first

Question #9) Design a data structure that supports push(), pop(), and min() all in O(1) time

Q: "You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do?"

Q: "How would you find out if a machine's stack grows up or down in memory?"

Q: "Explain a database in three sentences to your eight-year-old nephew."

Q: "How many gas stations would you say there are in the United States?"
================================================== =======


In case you were wondering, no, i didn't get the job. I attended one of their "College Days" a couple weeks back for my second round of interviews. I was only asked 6 of the above questions (#1, #2, #3,#4, #5, #8) and out of them i answered 3 correctly, 2 sorta correctly after receiving hints, and 1 i didnt answer at all (this was also my first interview on campus and my first real tech interview ever.) Basically my impression is: if you want a job at Google, you better eventually arrive at complete and optimal solutions to all of the questions.

I feel like i could of done better ( i was nervous and only got 3 hours of sleep the night before), but i learned a lot about technical interviews and here are some tips:

**** IMPORTANT TIPS FOR INTERVIEWING AT TECH COMPANIES:

#1) If you're asked to write code, first forumlate an algorithm in your head. Next DOUBLE check that algorithm, even if it takes 5 minutes, and even if it takes drawing some detailed example cases. Whatever you do, make 100% SURE that what you're going to code is correct, THEN write the code.

After you're finished writing the code, the interviewer will probably have you explain the code and illustrate a test run of the code, possibly on a white board. If your code is incorrect, you both will eventually arrive at that conclusion, and by the time you've found out its incorrect, there won't be enough time to fix the code. This is why its 100% important to get it the first time. This exact scenario happened to me - i tried writing up a solution real fast (#5) , but it back fired on me.

#2) If you're asked to describe an algorithm for solving a particular problem efficiently, FIRST think of the brute-force inefficient case. The brute force algorithm will most likely be very obvious, so go over the brute force approach in detail first. This is key, because a thorough investigation of the brute force algorithm will help you understand the problem space better, and may lead you directly to the efficient algorithm. I didn't do this during my first interview (problem #8) and i didnt arrive at the answer. I tried doing the same problem at home one night, worked out the brute force algorithm, and within minutes i had the optimal solution.

#3) Don't try to rush, just stay calm and go through things methodically.
[/b]
ones3k is offline Reply With Quote

P & NP Problmes of Computer Science

http://www.cs.gsu.edu/~cscskp/Algorithms/NP/NP.html

Solving Sudoku Using Object Oriented programming Java & Tree Data Structure

Solving Sudokus with Java and tree data structures

with one comment

A few weeks ago I published Java and tree data structures a post where I mentioned that I would try to put together some code to handle tree data structures… Well, this is the first installment of what I hope it will become a series of articles/code that will look into creating this tree library.

This first article/code is going to be about building trees dynamically. It is going to be illustrated by an example on how to use dynamic tree building to find the solution for a Sudoku. All the source code is available for downloading in a SVN repository, the URLs are:

Tree source code: https://subversion.assembla.com/svn/making-good-software/trunk/mgsTrees
Sudoku source code: https://subversion.assembla.com/svn/making-good-software/trunk/mgsSudoku
Dynamic tree building to find a solution

One widely used technique in computer science is to use a tree data structure to find the solution for something that needs to be solved but which solution is not obvious and requires many steps. One example could be chess, or a puzzle, a crossword, or like in this case, a sudoku.

The premise is simple, given an initial state, start building a tree of developed states from this original step until we find the state we were looking for. In the specific case of a sudoku, start building a tree where the branches are the different valid developments for that sudoku and stop when we find the solution.

The key element for building a tree dynamically is recursivity, starting from the original state, we find what the next candidate are, and them we do the same with each of them. In the mgsTrees library this can be easily accomplished by implementing an interface:
view plaincopy to clipboardprint?

1. public interface ExpandTreeStrategy {
2. public ExpandAction expand (T toExpand);
3. }

public interface ExpandTreeStrategy {
public ExpandAction expand (T toExpand);
}

The return type of the ExpandTreeStrategy is an ExpandAction. An ExpandAction has 3 flavors.

* stopBranch: It signals that this node is not expandable. In the Sudoku solver this is used when an ilegal Sudoku is reached.
* stopTree: It signals that is not necessary to keep building the tree. In the sudoku solver this is used when the solution is found.
* continueWith: This is used to specify what are the next states to look at. In the sudoku solver this is used when a intermediate sudoku is reached to specify what the next candidates are.

This is how to create the ExpandTreeStrategy Implementation for the Sudoku solver.
view plaincopy to clipboardprint?

1. public class ExpandSudokuLookingForSolutionStrategy implements ExpandTreeStrategy {
2. private final SudokuAnaliser sudokuAnaliser;
3.
4. public ExpandSudokuLookingForSolutionStrategy(SudokuAnaliser sudokuAnaliser) {
5. this.sudokuAnaliser = sudokuAnaliser;
6. }
7.
8. @Override
9. public ExpandAction expand(Sudoku toExpand) {
10. SudokuAnalysis sudokuAnalysis = sudokuAnaliser.analise(toExpand) ;
11.
12. if (sudokuAnalysis.isSolved()) return ExpandAction.stopTree ();
13. if (! sudokuAnalysis.isLegal()) return ExpandAction.stopBranch ();
14.
15. if (sudokuAnalysis.hasDirectSolutions()) {
16. return continueWithSudokuWithAllDirectSolutionsFilled(sudokuAnalysis);
17. } else if (sudokuAnalysis.hasNextCandidates()){
18. return continueWithSudokuVariantsForSquareLocationWithLessPossibleValues(sudokuAnalysis);
19. }else{
20. throw new RuntimeException("Is not possible to have a sudoku not solved, legal and without direct soluctions or candidates");
21. }
22. }
23.
24. private ExpandAction continueWithSudokuVariantsForSquareLocationWithLessPossibleValues(SudokuAnalysis sudokuAnalysis) {
25. List movements = sudokuAnalysis.getPossibleMovementsForSquareWithLessPossibleValues();
26. List nextSudokus = new ArrayList();
27. for (SudokuMovement movement : movements) {
28. nextSudokus.add(sudokuAnalysis.getSudoku().with(movement));
29. }
30. return ExpandAction.continueWith(nextSudokus);
31. }
32.
33. private ExpandAction continueWithSudokuWithAllDirectSolutionsFilled(SudokuAnalysis sudokuAnalysis) {
34. List movements = sudokuAnalysis.getAllDirectSolutionMovements();
35. return ExpandAction.continueWith(sudokuAnalysis.getSudoku().with(movements));
36. }
37. }

public class ExpandSudokuLookingForSolutionStrategy implements ExpandTreeStrategy {
private final SudokuAnaliser sudokuAnaliser;

public ExpandSudokuLookingForSolutionStrategy(SudokuAnaliser sudokuAnaliser) {
this.sudokuAnaliser = sudokuAnaliser;
}

@Override
public ExpandAction expand(Sudoku toExpand) {
SudokuAnalysis sudokuAnalysis = sudokuAnaliser.analise(toExpand) ;

if (sudokuAnalysis.isSolved()) return ExpandAction.stopTree ();
if (! sudokuAnalysis.isLegal()) return ExpandAction.stopBranch ();

if (sudokuAnalysis.hasDirectSolutions()) {
return continueWithSudokuWithAllDirectSolutionsFilled(sudokuAnalysis);
} else if (sudokuAnalysis.hasNextCandidates()){
return continueWithSudokuVariantsForSquareLocationWithLessPossibleValues(sudokuAnalysis);
}else{
throw new RuntimeException("Is not possible to have a sudoku not solved, legal and without direct soluctions or candidates");
}
}

private ExpandAction continueWithSudokuVariantsForSquareLocationWithLessPossibleValues(SudokuAnalysis sudokuAnalysis) {
List movements = sudokuAnalysis.getPossibleMovementsForSquareWithLessPossibleValues();
List nextSudokus = new ArrayList();
for (SudokuMovement movement : movements) {
nextSudokus.add(sudokuAnalysis.getSudoku().with(movement));
}
return ExpandAction.continueWith(nextSudokus);
}

private ExpandAction continueWithSudokuWithAllDirectSolutionsFilled(SudokuAnalysis sudokuAnalysis) {
List movements = sudokuAnalysis.getAllDirectSolutionMovements();
return ExpandAction.continueWith(sudokuAnalysis.getSudoku().with(movements));
}
}

At the end the entire tree building logic is wired in the TreeFactory class, which has a method, buildTree, that takes the starting point for the tree, and which constructor takes the ExpandStrategy to be used to build the tree. The result of this call is a TreeResult, which contains three main methods;

* getTree(): The resulting tree
* isBuildInterrupted(): Will tell you if the build is interrupted, in the case of the SudokuSolver this would mean that the solution was found.
* getLastBranch(): A sequential ordered list of all the last branch nodes startging from the root node, the original node. In the case of the sudoku solver this is used to retrieve in case that the solution is found (isBuildInterrupted == true) the sequence of Sudokus from the original one to the solution.

view plaincopy to clipboardprint?

1. public class TreeFactory {
2. private final ExpandTreeStrategy expandTreeStrategy;
3.
4. public TreeFactory(ExpandTreeStrategy expandTreeStrategy) {
5. this.expandTreeStrategy = expandTreeStrategy;
6. }
7.
8. public TreeResult buildTree (T seed){
9. System.out.println(seed);
10. ExpandAction expandActionResult = expandTreeStrategy.expand (seed);
11. if (expandActionResult.isStopBranch ()) return TreeResult.stopBranch (seed);
12. if (expandActionResult.isStopTree ()) return TreeResult.stopTree (seed);
13.
14. Node rootNode = new Node (seed);
15. List> currentBranch = new ArrayList>();
16. currentBranch.add(rootNode);
17.
18. Iterator childIterator = expandActionResult.getChildIterator();
19. TreeResult lastSubTreeResult = null;
20. while (childIterator.hasNext()){
21. Node next = new Node (childIterator.next());
22. lastSubTreeResult = buildTree(next.getContent());
23. rootNode.addChild(lastSubTreeResult.getTree().getRootNode());
24. if (lastSubTreeResult.isBuildInterrupted()) {
25. currentBranch.addAll(lastSubTreeResult.getLastNodeBranch());
26. return TreeResult.interrupt (rootNode, currentBranch);
27. }
28. }
29.
30. currentBranch.addAll(lastSubTreeResult.getLastNodeBranch());
31. return TreeResult.buildCompleted (rootNode, currentBranch);
32. }
33. }

public class TreeFactory {
private final ExpandTreeStrategy expandTreeStrategy;

public TreeFactory(ExpandTreeStrategy expandTreeStrategy) {
this.expandTreeStrategy = expandTreeStrategy;
}

public TreeResult buildTree (T seed){
System.out.println(seed);
ExpandAction expandActionResult = expandTreeStrategy.expand (seed);
if (expandActionResult.isStopBranch ()) return TreeResult.stopBranch (seed);
if (expandActionResult.isStopTree ()) return TreeResult.stopTree (seed);

Node rootNode = new Node (seed);
List> currentBranch = new ArrayList>();
currentBranch.add(rootNode);

Iterator childIterator = expandActionResult.getChildIterator();
TreeResult lastSubTreeResult = null;
while (childIterator.hasNext()){
Node next = new Node (childIterator.next());
lastSubTreeResult = buildTree(next.getContent());
rootNode.addChild(lastSubTreeResult.getTree().getRootNode());
if (lastSubTreeResult.isBuildInterrupted()) {
currentBranch.addAll(lastSubTreeResult.getLastNodeBranch());
return TreeResult.interrupt (rootNode, currentBranch);
}
}

currentBranch.addAll(lastSubTreeResult.getLastNodeBranch());
return TreeResult.buildCompleted (rootNode, currentBranch);
}
}

The final code to solve any given Sudoku will look like:
view plaincopy to clipboardprint?

1. public static void main(String[] args) {
2. Sudoku sudoku = new Sudoku(
3. new SquareValue [][]{
4. {__, __, __, __, __, __, _6, __, __},
5. {__, __, _3, _7, __, __, __, __, _1},
6. {__, _8, __, _1, __, _6, _9, _4, __},
7.
8. {_7, __, __, _5, __, __, __, __, __},
9. {__, __, _5, __, _4, __, _8, __, __},
10. {__, __, __, __, __, _2, __, __, _7},
11.
12. {__, _2, _9, _6, __, _4, __, _3, __},
13. {_6, __, __, __, __, _8, _4, __, __},
14. {__, __, _4, __, __, __, __, __, __}
15. }
16. );
17.
18. IteratorStrategy rowNavigator = OneLineIteratorStrategy.horizontal();
19. IteratorStrategy columnNavigator = OneLineIteratorStrategy.vertical();
20. IteratorStrategy matrixNavigator = MatrixIteratorStrategy.instance();
21. SudokuProcessor sudokuProcessor = new SudokuProcessorImpl(rowNavigator, columnNavigator, matrixNavigator);
22. SudokuAnaliser sudokuAnaliser = new SudokuAnaliserImpl(sudokuProcessor );
23. ExpandTreeStrategy expandTreeStrategy = new ExpandSudokuLookingForSolutionStrategy(sudokuAnaliser);
24. TreeFactory treeFactory = new TreeFactory(expandTreeStrategy);
25.
26. TreeResult buildTree = treeFactory.buildTree(sudoku);
27. List lastBranch = buildTree.getLastBranch();
28. System.out.println("Solution: " + lastBranch.get(lastBranch.size()-1));
29. }

Source
Tree :https://subversion.assembla.com/svn/making-good-software/trunk/mgsTrees
Sudoku:https://subversion.assembla.com/svn/making-good-software/trunk/mgsSudoku