O/R mapping

http://www.agiledata.org/essays/mappingObjects.html

mapping Object to Relational databases
The easiest mapping you will ever have is a property mapping of a single attribute to a single column.

Shadow information is any data that objects need to maintain, above and beyond their normal domain data, to persist themselves. This typically includes primary key information

One type of shadow information that I have not discussed yet is a boolean flag to indicate whether an object currently exists in the database.
A common practice is for each class to implement an isPersistent boolean fla that is set to true when the data is read in from the database and set to false when the object is newly created. ( or isLocal() )

--
Shadow information doesn’t necessarily need to be implemented by the business objects, although your application will need to take care of it somehow. For example, with Enterprise JavaBeans (EJBs) you store primary key information outside of EJBs in primary key classes, the individual object references a corresponding primary key object. The Java Data Object (JDO) approach goes one step further and implement shadow information in the JDOs and not the business objects. (Do, DoImpl)

nts at an important part of the O/R impedance mismatch between object technology and relational technology. Classes implement both behavior and data whereas relational database tables just implement data.

interview questions : distributed sorting

if you have a large log which contains urls and queries, design a algorithm finding top 100 most frequent searched queries

1. extract the queries from the log first, then put in the hashmap, get the top 100

2. what is limitation of hashmap?

might be too limited if the queries are too many. in memory operation

3. what would you do instead?

add more CPUs, distributed into multiple computers

4. what if the file is still too large?

divide the file in chunks, say each file only get queries starting with A.

Memory in Java

http://www.vogella.de/articles/JavaPerformance/article.html

In the heap the Java Virtual Machine (JVM) stores all objects created by the Java application, e.g. by using the "new" operator. The Java garbage collector (gc) can logically separate the heap into different areas, so that the gc can faster identify objects which can get removed

The memory for new objects is allocated on the heap at run time. Instance variables live inside the object in which they are declared.

--

Stack is where the method invocations and the the local variables are stored. If a method is called then its stack frame is put onto the top of the call stack. The stack frame holds the state of the method including which line of code is executing and the values of all local variables. The method at the top of the stack is always the current running method for that stack. Threads have their own call stack.

Runtime runtime = Runtime.getRuntime();
  // Run the garbage collector
  runtime.gc();
  // Calculate the used memory
  long memory = runtime.totalMemory() - runtime.freeMemory();

great website for tutorial

http://www.vogella.de/java.html

Java Concurrency & Threads

http://www.vogella.de/articles/JavaConcurrency/article.html

To make a class immutable make

• all its fields final

• the class declared as final

• the this reference is not allowed to escape during construction

• Any fields which refer to mutable data objects are

  • private

  • have no setter method

  • they are never directly returned of otherwise exposed to a caller

  • if they are changed internally in the class this change is not visible and has no effect outside of the class

An immutable class may have some mutable data which is uses to manages its state but from the outside this class nor any attribute of this classes can get changed.

The base means for concurrency are "java.lang.Threads". Each thread will execute an object of type "java.lang.Runnable". Runnable is an interface with defines only the one method "run()". This method is called by "Thread" and contains the work which should be done. Therefore the "Runnable" is the task to perform. The Thread is the worker who is doing this task.

Runnable task = new MyRunnable(10000000L + i);
  Thread worker = new Thread(task);
  // We can set the name of the thread
  worker.setName(String.valueOf(i));
  // Start the thread, never call method run() direct
worker.start();

Using Threads directly has the following disadvantages.

• Creating a new thread causes some performance overhead

• Too many threads can lead to reduced performance, as the CPU needs to switch between these threads.

• You cannot easily control the number of threads, therefore you may run into out of memory errors due to too many threads.

The "java.util.concurrent" package offers improved support for concurrency compared to threads. The java.util.concurrent package helps solving several of the issues with threads.

The Executor framework provides example implementation of the
 java.util.concurrent.Executor interface, e.g.
 Executors.newFixedThreadPool(int n) which will create n worker
 threads. The ExecutorService adds lifecycle methods to the Executor,
 which allows to shutdown the Executor and to wait for termination.
  

ExecutorService executor = Executors.newFixedThreadPool(NTHREDS);
 for (int i = 0; i < 500; i++) {    Runnable worker = new MyRunnable(10000000L + i);    executor.execute(worker);   }   // This will make the executor accept no new threads   // and finish all existing threads in the queue   executor.shutdown();   // Wait until all threads are finish   while (!executor.isTerminated()) {  


import java.util.concurrent.atomic.AtomicInteger;
Non Blocking Algorithms
. The fork-join framework allows you to
  distribute a certain task on several workers and when wait for the
  result.

Binary search Tree in Java

http://www.java-tips.org/java-se-tips/java.lang/binary-search-tree-implementation-in-java.html

// BinarySearchTree class
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// void remove( x ) --> Remove x
// void removeMin( ) --> Remove minimum item
// Comparable find( x ) --> Return item that matches x
// Comparable findMin( ) --> Return smallest item
// Comparable findMax( ) --> Return largest item
// boolean isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// ******************ERRORS********************************
// Exceptions are thrown by insert, remove, and removeMin if warranted

/**
* Implements an unbalanced binary search tree.
* Note that all "matching" is based on the compareTo method.
* @author Mark Allen Weiss
*/
public class BinarySearchTree {
/**
* Construct the tree.
*/
public BinarySearchTree( ) {
root = null;
}

/**
* Insert into the tree.
* @param x the item to insert.
* @throws DuplicateItemException if x is already present.
*/
public void insert( Comparable x ) {
root = insert( x, root );
}

/**
* Remove from the tree..
* @param x the item to remove.
* @throws ItemNotFoundException if x is not found.
*/
public void remove( Comparable x ) {
root = remove( x, root );
}

/**
* Remove minimum item from the tree.
* @throws ItemNotFoundException if tree is empty.
*/
public void removeMin( ) {
root = removeMin( root );
}

/**
* Find the smallest item in the tree.
* @return smallest item or null if empty.
*/
public Comparable findMin( ) {
return elementAt( findMin( root ) );
}

/**
* Find the largest item in the tree.
* @return the largest item or null if empty.
*/
public Comparable findMax( ) {
return elementAt( findMax( root ) );
}

/**
* Find an item in the tree.
* @param x the item to search for.
* @return the matching item or null if not found.
*/
public Comparable find( Comparable x ) {
return elementAt( find( x, root ) );
}

/**
* Make the tree logically empty.
*/
public void makeEmpty( ) {
root = null;
}

/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( ) {
return root == null;
}

/**
* Internal method to get element field.
* @param t the node.
* @return the element field or null if t is null.
*/
private Comparable elementAt( BinaryNode t ) {
return t == null ? null : t.element;
}

/**
* Internal method to insert into a subtree.
* @param x the item to insert.
* @param t the node that roots the tree.
* @return the new root.
* @throws DuplicateItemException if x is already present.
*/
protected BinaryNode insert( Comparable x, BinaryNode t ) {
if( t == null )
t = new BinaryNode( x );
else if( x.compareTo( t.element ) < 0 )
t.left = insert( x, t.left );
else if( x.compareTo( t.element ) > 0 )
t.right = insert( x, t.right );
else
throw new DuplicateItemException( x.toString( ) ); // Duplicate
return t;
}

/**
* Internal method to remove from a subtree.
* @param x the item to remove.
* @param t the node that roots the tree.
* @return the new root.
* @throws ItemNotFoundException if x is not found.
*/
protected BinaryNode remove( Comparable x, BinaryNode t ) {
if( t == null )
throw new ItemNotFoundException( x.toString( ) );
if( x.compareTo( t.element ) < 0 )
t.left = remove( x, t.left );
else if( x.compareTo( t.element ) > 0 )
t.right = remove( x, t.right );
else if( t.left != null && t.right != null ) // Two children
{
t.element = findMin( t.right ).element;
t.right = removeMin( t.right );
} else
t = ( t.left != null ) ? t.left : t.right;
return t;
}

/**
* Internal method to remove minimum item from a subtree.
* @param t the node that roots the tree.
* @return the new root.
* @throws ItemNotFoundException if x is not found.
*/
protected BinaryNode removeMin( BinaryNode t ) {
if( t == null )
throw new ItemNotFoundException( );
else if( t.left != null ) {
t.left = removeMin( t.left );
return t;
} else
return t.right;
}

/**
* Internal method to find the smallest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the smallest item.
*/
protected BinaryNode findMin( BinaryNode t ) {
if( t != null )
while( t.left != null )
t = t.left;

return t;
}

/**
* Internal method to find the largest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the largest item.
*/
private BinaryNode findMax( BinaryNode t ) {
if( t != null )
while( t.right != null )
t = t.right;

return t;
}

/**
* Internal method to find an item in a subtree.
* @param x is item to search for.
* @param t the node that roots the tree.
* @return node containing the matched item.
*/
private BinaryNode find( Comparable x, BinaryNode t ) {
while( t != null ) {
if( x.compareTo( t.element ) < 0 )
t = t.left;
else if( x.compareTo( t.element ) > 0 )
t = t.right;
else
return t; // Match
}

return null; // Not found
}

/** The tree root. */
protected BinaryNode root;


// Test program
public static void main( String [ ] args ) {
BinarySearchTree t = new BinarySearchTree( );
final int NUMS = 4000;
final int GAP = 37;

System.out.println( "Checking... (no more output means success)" );

for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
t.insert( new Integer( i ) );

for( int i = 1; i <>2 )
t.remove( new Integer( i ) );

if( ((Integer)(t.findMin( ))).intValue( ) != 2 ||
((Integer)(t.findMax( ))).intValue( ) != NUMS - 2 )
System.out.println( "FindMin or FindMax error!" );

for( int i = 2; i <>2 )
if( ((Integer)(t.find( new Integer( i ) ))).intValue( ) != i )
System.out.println( "Find error1!" );

for( int i = 1; i <>2 ) {
if( t.find( new Integer( i ) ) != null )
System.out.println( "Find error2!" );
}
}
}


// Basic node stored in unbalanced binary search trees
// Note that this class is not accessible outside
// of this package.

class BinaryNode {
// Constructors
BinaryNode( Comparable theElement ) {
element = theElement;
left = right = null;
}

// Friendly data; accessible by other package routines
Comparable element; // The data in the node
BinaryNode left; // Left child
BinaryNode right; // Right child
}


/**
* Exception class for duplicate item errors
* in search tree insertions.
* @author Mark Allen Weiss
*/
public class DuplicateItemException extends RuntimeException {
/**
* Construct this exception object.
*/
public DuplicateItemException( ) {
super( );
}
/**
* Construct this exception object.
* @param message the error message.
*/
public DuplicateItemException( String message ) {
super( message );
}
}


/**
* Exception class for failed finds/removes in search
* trees, hash tables, and list and tree iterators.
* @author Mark Allen Weiss
*/
public class ItemNotFoundException extends RuntimeException {
/**
* Construct this exception object.
*/
public ItemNotFoundException( ) {
super( );
}

/**
* Construct this exception object.
* @param message the error message.
*/
public ItemNotFoundException( String message ) {
super( message );
}
}

Binary search Tree

Java

public class BSTNode {

private int value;

private BSTNode left;

private BSTNode right;

public BSTNode(int value) {

this.value = value;

left = null;

right = null;

}

}

public class BinarySearchTree {

private BSTNode root;

public BinarySearchTree() {

root = null;

}

}

C++

class BSTNode {

private:

int value;

BSTNode* left;

BSTNode* right;

public:

BSTNode(int value) {

this->value = value;

left = NULL;

right = NULL;

}

};

class BinarySearchTree {

private:

BSTNode* root;

public:

BinarySearchTree() {

root = NULL;

}

};