Distorting a Binary Tree

We know that there are 3 different ways to traverse a Binary Tree i.e. InOrder, PreOrder, and PostOrder. Let us try to ignore other traversals like LevelOrder etc for now. Each traversal has its own significance and you can never think of one traversal technique as a replacement for the other. I am going to talk here about which traversal suits better when the tree is getting distorted. I will be taking 2 examples here and proceed.

The links to left and right subtrees are as important to a tree as the next pointer for a linked list. These are all the pointers/references that keep the structure intact. Once they are lost, there is no way to recover them once again. So when it comes to distorting a tree, I would always prefer PostOrder traversal where you don't touch the current node till you are done with the sub-trees.

Deleting a Binary tree
Consider for example the problem of how to deallocating an entire Binary tree? You cant start with the root node of the tree, as if you do so, you have no way to go to the left and right subtrees. So if you deallocate the root first, you cant proceed anymore. Similarly in case of InOrder traversal, you cant deallocate the right subtree. So the most suitable procedure involves deallocating the left and right subtrees first and coming to the root at last.

Binary tree to Doubly Linked List
Now consider the problem of converting a Binary Tree into a doubly linked list where the left pointer of the tree should be made to point the InOrder predecessor node and right pointer should be altered to point the InOrder successor node.
Though the problem talks about InOrder arrangement, you should not start tackling the problem with InOrder traversal. Because as we discussed in case of delete operation, any operation that distorts the tree is best done by the PostOrder traversal.
So, you need to write a recursive procedure to convert a tree to a Doubly Linked List. You can recursively apply the procedure to the left sub-tree and get a leftDll and separately to the right sub-tree to get a rightDll.
Now, you need to form a single DLL from the leftDll, the current root node, and the rightDll. So you need to attach the last node of the leftDll to the root, and then attach the root to the rightDll's head. However, finding the last node of leftDll is O(n) operation. In order to minimize that, instead of returning a Dll, always return a circular DLL so that once you have access to its head, it is just a O(1) operation to get its tail.
Now, we have discussed that circular DLL is the best data-structure to be returned. But what exact node would you return? Remember that you expect the left subtree to return a circular DLL which is arranged InOrder. Now to preserve the InOrder property, you would want to attach the current root to the end of the Circular DLL. Similarly you would link the circular DLL that you have obtained from the right subtree and form a single circular DLL. Now you should return the head node in other words, the node returned by the left subtree's iteration if present or else the current node to maintain the invariant.

Batch calls

Batch Processing :

Consider the two services mentioned below:
UserService - As mentioned in previous post, it is used to get a social network's user details.
FeedService - Used to get feeds information for the given user.It just queries "feeds" table.

For each feed, there should be a feed owner(the guy who posted that feed),
So in order to form a complete feed information, the FeedService has to call UserService to feed owner information(such as name,profile url,photo etc) of each feed.

Problem:
Since FeedService is pinging UserService for each and every feed, we ourself will be putting so much load on UserService.

Solution:
For each call to UserService, send a batch(say 100) of feeds and get the user information of those feeds at once. (like batch processing).

Pros:
1. Load on UserService is reduced.
2. Network latency is reduced by batch size times (here 100x times).

Cons:
1. We won't get 100 feeds always. Sometimes it might be just 10 feeds. So, there is a possibility that we might not be efficiently making call to UserService.
2. Extra care to be taken during service shutdown, and ensure that all remaining feeds in cache get processed before shutdown.

The above problem can be solved as follows -
Maintain a local cache of feeds in FeedService. Whenever the cache becomes full , then make a call to UserService and get the user information. Here cache size is nothing but batch size.

Sometimes, it is possible that few feeds can be stay in cache for long time, because FeedService is waiting for cache to get filled. To avoid such scenario, we can have some threshold time within which the feeds can reside in the cache. If cache has not filled even after threshold time, then make a call to UserService irrespective of no.of feeds available in the cache.

Though, this problem looks simple, in real world , care should be taken to identify and use batch processing  wherever possible.

Push and Pull patterns

After exploiting the SOA environment in Amazon, I like to bring few patterns (you can say, principal's) observed in SOA , which everybody should be aware of, before designing the actual web services in your architecture.

Pull pattern
 Consider typical environment in Facebook,which has the below two web services.
 1.  UserService - Gets the Facebook user details like id, name, public profile url etc. The job of this service is to fetch user details from the underlying tables. Remember that the detail need not be present in a single table, but could be spread across multiple tables. This service aggregates all the details and provides a single API call to get all details of a particular user.
 2.  BotService - This service takes responsibility of updating the search engines indexes periodically whenever a user changes his profile information. So it contacts the UserService periodically to find the users who have updated their profile in the recent past, and based on their profile information the search indexes are updated.
Current Approach
BotService is a following Pull pattern in the above discussed model. It is the responsibility of the BotService to continuously get the user updates from the UserService. UserService takes no pains to send updates to BotService.

Problem with Pull Pattern
The general problem with Pull model is that there might be unnecessary fetches from the puller service, particularly when the the number updates the needs to come from the source is very minimum. In the above said service, assuming that a user will very rarely change his profile details, BotService will add unnecessary traffic on the UserService by continuously pulling details as at most of the times, UserService might have no updates to send at all.

Going with the Push Pattern - Don't call me, I will call you".  
Instead of UserService being called by BotService, let's make BotService being called by UserService. Since UserService knows whenever a user updated public profile URL, it will call the BotService informing that the particular user has updated his/her public profile URL. UserService can be made intelligent to batch the calls to the BotService to push the updates. In case latency is an issue, timeouts can be configured in the source by the end of which it is supposed to send updates.
The Rule of thumb is that the rate at which you get the data and the timeliness at which the data should be processed should guide you on which one to choose - the Push or the Pull.

Many more interesting SOA patterns to come.
Cheers,
Inba

Iterative processes

There is a fundamental difference between a recursive process and a
recursive procedure.

A recursive procedure is one where the procedure calls itself (directly or indirectly) at some point.
In contrast a recursive process is one which has to remember its history of execution.

For eg.

; clojure code
(defn sum [a b]
  (if (> a b)
      0
      (+ a (sum (inc a) b))))

This is small piece of code, written in Clojure, a lisp dialect, which sums up all
integers from a to b. The logic is quite straight forward.

If a > b then ans = 0 because there are no elements between them.
Else Find the sum of all numbers from (a+1) till b and then add 'a' to it.

Typically a function call gets its own stack frame which will be alive till the function
executes. After the function returns a value (potentially) the stack is popped.

So what would (sum 1 5) be?

Assuming stack grows from left to right, this is how to process would execute.

(sum 1 5)
(+ 1 (sum 2 5))
(+ 1 (+ 2 (sum 3 5)))
(+ 1 (+ 2 (+ 3 (sum 4 5))))
(+ 1 (+ 2 (+ 3 (+ 4 (sum 5 5)))))
(+ 1 (+ 2 (+ 3 (+ 4 (+ 5 (sum 6 5))))))
(+ 1 (+ 2 (+ 3 (+ 4 (+ 5 0)))))
(+ 1 (+ 2 (+ 3 (+ 4 5))))
(+ 1 (+ 2 (+ 3 9)))
(+ 1 (+ 2 12))
(+ 1 14)
15

Take your time to understand why the process looks like this.
[Substitute the parameters passed to the function sum at every point into the
definition and you will be able to figure out.
This model of finding out answers is called the substitution model]

In the above example what was the role that the stack played? Looking at the
process's structure we understand that the stack keeps track of the
pending operation at any point.
i.e. if there were no stack then the process would have looked like?

(sum 1 5)
(sum 2 5)
(sum 3 5)
(sum 4 5)
(sum 5 5)
(sum 6 5)
0 -> result

We got '0' because nobody remembers that there is an addition operation is to be done after the call returns.

But is it absolutely necessary to always have a stack?
If you say
"Yes, how else would I remember what operations are left to be done after the function call remembers?" then you have correctly identified the problem.

Now look at this code

(defn sum [a b acc] ;; acc should be 0 initially
  (if (> a b)
      acc
      (sum (inc a) b (+ acc a)))

[Clojure's comments start with ';']

In the above procedure we have an extra parameter, accumulator, which will collect
the answer until that point. Here, using the substitution model, we arrive at the
process structure that looks like the following.

Assuming 'no-op' is used to signify nothing is left to be done.

(sum 1 5 0)
(no-op (sum 2 5 1))
(no-op (no-op (sum 3 5 3)))
(no-op (no-op (no-op (sum 4 5 6))))
(no-op (no-op (no-op (no-op (sum 5 5 10)))))
(no-op (no-op (no-op (no-op (no-op (sum 6 5 15))))))
(no-op (no-op (no-op (no-op (no-op 15)))))
(no-op (no-op (no-op (no-op 15))))
(no-op (no-op (no-op 15)))
(no-op (no-op 15))
(no-op 15)
15

We see that after the stage (sum 6 5 15) arrives, we essentially have found the answer.
All that is to be done now is that the result '15' is to be returned by every stack frame.
In this case, since the result is carried forward there is no real need for maintaining
the stack because there is no operation pending.

Note that as stack depth increases memory consumption of the process increases.
So stacks can't be ignore.
Languages like lisp, haskell etc do a bit of 'magic' called Tail Call Optimization
where when recursion is the last step of the procedure then they
reuse the current stack frame.

So (sum 1 5 0) would look like

(sum 1 5 0)
(sum 2 5 1)
(sum 3 5 3)
(sum 4 5 6)
(sum 5 5 10)
(sum 6 5 15)
15

All the operation would happen in the same stack frame, so memory consumption
is nearly constant.

Other languages like C++, Java etc make use of the 'for' , 'while' keywords and the
like to arrive at similar characteristics.
This type of process is called an iterative process where there is constant stack usage and all the state information is remembered through parameters alone.

[Note that if we had to do any operation with the result(15 in this case) of a function call at any point then that information can be maintained only in a stack]

Architecture of Recommendation Systems

About?
I recently read a paper which talks about the high level architecture of recommendation systems. The topic was discussed in a very generic way and not related to any specific domain. Details on how the database interaction happens, or how statistics collected are represented in the Database were not discussed. However, the paper was good enough to discuss the components of any recommendation system. As expected, the architecture was very clean and each component had a purpose and did not mess up with other component and that's the reason I am discussing the architecture here.

What is it?
Recommendation system is one which identifies patterns in user behavior and makes some predictions based on them. For example, how does Facebook know who are likely to be your friends? How does Amazon know which product you are likely to buy? And how does Google know which Add to show to you? All of them are recommendation systems which try to understand your behavior. Sometimes, the rules of the recommendation systems are hard-coded and hence are static, and sometimes they are very intelligent and dynamically change the rules themselves.

Architecture of a Recommendation System
The top most layer of recommendation system is always the User interface along with privacy/security layer, and the bottom layer is the database to persist your findings. What matters is the layer in between. If you observe well, you can easily find out 3 different components working together.

1. Watcher: This component takes care of collecting patterns from the user behavior. It might either do it in a visible way by posting surveys and getting feedbacks, etc, or it might choose to hide its identity and silently do its job by tracking the page hit count or the saving links the user clicks etc. This watcher component should come up with an optimal way to represent the data in the database. It need not hit the DB all the time, as the loss of some data is tolerable in such systems. So it can cache the data in its low local machine and update the central database periodically.

2. Learner: This guy always polls the Database for updates from the Watcher and interprets the data. Remember that though the user behavior is captured by the Watcher, Learner is the one that makes some sense out of it. Learners can be very complex by having multiple heuristics and can also rank/weigh each of them differently. It can also give more weight to most recent data. It can also predict the expertise of the user from the user behavior and provide different weight to different level of expertise.

3. Advisor: This component is visible to the user, more likely a GUI shown by HTML or Swing and it shows all recommendations that learner has predicted. The Advisor need not be always a dumb system, but can again collect details on the quality of recommendation like the number of times the user has accepted a recommendation and the number of times the user has said the recommendation was useless (Again it can be either visible or invisible to the user). It can provide the details of the this input to the learner system which in turn can adjust its weight on each heuristic and hence can keep learning.

Algorithms based on majority element

What is majority element in an array?
In an array of size n, if a specific element repeats itself more than half the times (> n/2 times), then it is called the majority element. If no such element exists, then the array is said to have no majority element in it.
Examples:
[3,2,2,3,3] -> 3 is the majority element
[4,4,5,7,3,3,3,4,4] -> 4 is the majority element
[1,2,3,4,5] -> no majority element at all.
[1,1,1,2,2,2] -> no majority element as the majority element has to repeat more than half the times (i.e. 4 times at least in this array)

How to check whether a number is majority element or not?
It is very simple and obvious. Given a number X and an array A, run through the array and make the count of X's in the array. If the count is more than A.size()/2, then X is the majority element.

Logic to find majority element?
Suppose X is the majority element of an array. If you find an element Y in the same array which is not equal to X, you can cancel one occurrence of Y and one occurrence of X from the array and still the resultant array will have X as the majority element. This cancellation will reduce the size of both the parts of the array, i.e. the part (may not be contiguous) having majority element, and the one having rest of the elements.
Example: [3,1,2,3,3] -> In this array, 3 is the majority element. If you are able to find one non-majority element (say 1), you can cancel one occurrence of both 1 and 3 and still 3 will be the majority element. i.e. [2,3,3] obtained after cancelling one 3 and one 1 also has 3 as the majority element.

Similarly, take 2 elements which are not majority elements, say Y and Z. If you cancel both of them, the majority element will still be the same. i.e. in the above example, if you cancel two non majority elements 1 and 2, the resultant array will have [3,3,3] in which 3 is majority element once again.

In other words, you can pick any 2 elements from the array, and you can discard them if both of them are not the majority elements.


Solution:
Given an array A[0..n-1], your assignment is to find the majority element in it.
Let counter be the variable which records the number of occurrences of the majority element. Initially it will be 0.
Whenever the counter is less than or equal to zero, take the next element in A as majority element. Increment the counter when you see the same element and decrement it when you see a different element. Do it again if the counter becomes zero once again.

counter = 0
majority_index = -1
// Find majority element
for i in 0..Arr.size()-1
  if counter == 0
    majority_index = i
  end
  counter += Arr[i] == Arr[majority_index]
end


// Check the correctness
majority_count = 0
for j in 0..Arr.size()-1
  if Arr[j] == Arr[majority_index]
    majority_count ++
  end
end
if (majority_count > Arr.size()/2)
  return Arr[majority_index]
else
  throw "No majority element found"
end

E.g. 1,2,4,2,5,6,3,4,4,2,4,4,4,4,4
counter = 0
Start with 1 as majority element.
Next element is 2 which is not 1. So discard both.
Now 4 becomes the majority element and counter will be 1
when 2 comes again, counter will become 0, and so till now no majority element exists.
Next 5 and 6 gets discarded similarly as both are different.
Similarly, 3 and 4 will get discarded, and again 2 and 4 will get discarded.
Now the only array having majority element is [4,4,4,4,4] and the counter keeps incrementing to 5.
Now check whether 4 is the real majority element in the array. If so, you can return 4.

Problem 2 "Find element which occurs at least half the times"
Good that you now know how to find the majority element. Now, given that you need to find the element which occurs at least half the times in the array, how will you proceed? Remember, this is a different problem. As per the majority element, it should occur more than half the times, but now the problem has been modified to find that element which repeats at least half the times.
Solution:
We can use the majority algorithm that we discussed above in all the cases except when the element that needs to be found occurs exactly half the times in the array. We can change the solution a bit to catch that case also. In the array, check whether the first element is the majority element; if so, return it. Else, discard the first element in the array. Now after discarding, we can apply the above described normal majority element algorithm itself as now the majority element is guaranteed to be more than half the number of times in the array.

Thread safety

Thread safety

Definition: A class is thread safe if it behaves correctly when accessed from multiple threads, regardless of the scheduling or interleaving of the execution of those threads by the runtime environment, with no additional synchronization or other coordination on the part of the calling code.

An object in general represents a state of something (forget about behavior for now). Any thread working on that object tries to change its state. Always it is desirable to change the object from one consistent state to another. However, when two or more threads operate, the object might go to an inconsistent state. Informally, any program that doesn’t let the object to go to such an inconsistent state is considered as thread safe. As a simplest case, any stateless object is always thread-safe. Stateless objects are not difficult to find. Design patterns like Strategy, Singleton, Adaptor, Flyweight, etc. uses stateless objects only and so they are almost always thread-safe.

Atomicity

Any operation that happens as a single unit is said to be atomic. There won’t be any intermediate state while doing an atomic operation; i.e. there are only two states when doing such an atomic operation, the operation will happen fully or won’t happen at all. In reality many operations which look atomic are not really atomic. For e.g., ++j though it looks like a single atomic operation, it is not. A processor executes a series of instructions to achieve the result, and a thread switch can happen at any intermediate stage which makes the statement non-atomic. Race condition occurs when the correctness of a computation depends on the relative timing or interleaving of multiple threads at runtime. In general, race conditions can happen anytime two threads simultaneously access a shared variable. Compound actions are those actions performed in multiple steps like check-then-act (E.g. lazy initialization) and read-modify-write (increment operation), and they are problematic areas when it comes to multithreading.

Lock

To preserve state consistency, update related state variables in a single atomic operation. Use synchronized block to achieve atomicity. Every java object can act as a lock for purpose of synchronization; these built-in locks are called intrinsic locks or monitor locks. In java, locks are obtained per-thread basis rather than per-invocation basis; i.e. any thread holding a lock can make any number of invocations to obtain the same lock again and they will all succeed immediately (This is called reentrancy). This is necessary as say for example, a synchronized method of an object calls another synchronized method (lock is obtained on the same object), would result in a deadlock if there is no reentrancy.

Guarding state with locks

It is a common mistake to assume that synchronization needs to be used only when writing to shared variables. For each mutable state variable that may be accessed by more than one thread, all accesses to that variable must be performed with the same lock held. In this case, we call that variable is guarded by that lock. Every shared, mutable variable should be guarded by exactly one lock.

A common locking convention is to encapsulate all mutable states within an object and to protect it from concurrent access by synchronizing any code path that accesses mutable state using the object’s intrinsic lock. For every invariant that involves more than one variable, all the variables in that invariant must be guarded by the same lock. Use @GuardedBy annotation for easy debugging.

Performance

Make the synchronized block as small as possible without breaking the required atomicity. Otherwise it will become a performance bottleneck. Also note that acquiring and releasing a lock is costly. Avoid holding locks during lengthy computations or operations at risk of not completing quickly such as network or console I/O.

I have taken these points from the book "Java Concurrency In Practice" which has very high user rating in Amazon.

Classes and Interfaces - Part 2

Design and document for inheritance

1. Any class should document its public/protected/constructor methods indicating which overridable method it invokes and in what order and how each invocation affects the subsequent processing. Documenting the inner details is unavoidable if you expect a class to be inherited, as otherwise the inherited class might break the assumptions made by the base class.
2. A class may have to provide hooks into its internal working in the form of judicially chosen protected methods, or in rare instances protected fields.
3. While using inheritance, constructor should not use overridable methods directly or indirectly particularly in case the overridden method relies on the initialization of some subclass variables.
4. Classes designed for inheritance should avoid implementing Cloneable and Serializable interfaces as it adds to the burden of those who subclass it. Also, as clone() and readObject() methods behave like constructor, they should also not use any overridable method directly or indirectly.
5. If you implement Serializable in a possible base class, you should make readResolve and writeReplace methods protected rather than private as otherwise they will be ignored by the subclasses.
6. If a class is not designed for subclassing, it is always best to prohibit it from being subclassed by either making the constructor private or declaring the class as final.

Prefer inheritance to abstract classes

1. Existing classes can’t inherit abstract classes. Interfaces are ideal for defining mixins (mixin is a type that a class can implement in addition to its primary type to provide some optional behaviour). Interfaces can extend multiple interfaces. Interfaces enhance safe and powerful functionality enhancement via wrapper classes.
2. You can provide an Abstract implementation of the Interface always so that the clients can choose to go with any one of them. An existing class can make use of both the Abstract implementation and interfaces as follows. Make the existing class implement the interface. Create a private inner class for the existing class which extends the abstract class. Let all the calls of the existing class forward the request to the inner class. This method is called simulated multiple-inheritance. A variation of this is simple implementation where you provide a concrete class rather than an abstract implementation and the client can override the needed methods. The basis is that it is far easier to evolve an abstract class than an interface.

Use interfaces only to define types

1. The constant interface pattern (where an interface is used only to expose static final fields) is a poor use of interfaces. To export constants, always go for enums or non-instantiable utility classes. Note: You can always use static import facility to avoid qualifying a constant name with its class name.

Prefer class hierarchies to tagged classes

1. Tagged classes are those which try to handle multiple cases in a single class. For example, consider a class called Shape which provides area, circumference etc for both circle and rectangle shapes by using a lot of if-else logics. If you want to add a new shape, the class will become messy.

Use function objects to represent strategies

1. Strategies are usually stateless and hence can also be singletons.

Favour static member classes over nonstatic

1. There are 4 kinds of nested classes: static member classes, nonstatic member classes, anonymous classes, and local classes.
2. Static member classes have access to all the private members of the enclosing classes. These classes are like any other static member of the class. If it is declared private, it is accessible only within the enclosing class. Public static classes can be used as a public helper function useful only in conjunction with the enclosing class.
3. Each instance of a non-static member class is implicitly associated with an instance of the enclosing class (accessed using this instance). It is impossible to create an instance of a non-static member class without an instance of the enclosing class. Common use of such classes is to implement adaptor classes. E.g. you can use non-static member classes to define iterators. These classes are commonly used to represent components of the object represented by its enclosing class.
4. Anonymous classes have no names and can be declared anywhere an expression is allowed. They are simultaneously declared and instantiated at the point of use. They have enclosing instances if and only if they occur in a non-static context. They are mainly used to create function objects on the fly. E.g. When trying to sort an array, you can pass an anonymous class using an anonymous Comparable interface. They can also be used to create Process objects such as Runnable, Thread, Timertask etc. Static factory methods can use Anonymous classes to provide a different type of implementation of the interface.
5. Local classes are least frequently used and can be declared anywhere a local variable can be declared. They can’t contain static members.

I have taken these points from the book "Effective Java" which I consider as a MUST READ book for every JAVA developer.

Classes and Interfaces - Part 1

Minimize the accessibility of classes and members

1. Information hiding (a.k.a. encapsulation) is very important to have a very neat API and to have loosely coupled components.
2. It is advisable to make a class or member as inaccessible as possible. Top-level classes can be package-private or public. If it is being used by only one other class, make it an inner class.
3. Member variables/methods of a class can be private, protected, package-private, or public.
4. Java doesn’t allow overridden methods to have a lower scope than the super class. Also all the methods declared in an interface are assumed to be public only.
5. Classes with public mutable fields are not thread-safe. In general fields of a class must never be public. A final field with reference to a mutable object has all limitations of a non-final field. Note that a non-zero length array is always mutable. So it should never be made public or its reference should never be returned. To fix this problem use Collections.unmodifiableList(Array), or you can clone the array and then return it.

In public classes, use accessor methods, not public fields

1. If a class is accessible outside its package, provide public accessor methods. In case it is an immutable field, it can be exposed.
2. If a class is package-private or a private nested class, though it is highly recommended, you can choose to do otherwise also.

Minimize Mutability

1. Immutable classes are easier to design, test and are less prone to errors. To make a class immutable, don’t provide any method that modifies the objects internal state. Ensure that the class can’t be extended. Make all the fields of the class private and final. If the class contains references to mutable objects, ensure that the clients can never obtain a reference to those objects.
2. Immutable classes should always take functional approach by creating a new object and returning it rather than modifying the existing object itself.       Immutable classes are always thread-safe. It should also try reusing the same instances rather than creating new ones. Immutable classes should not have any copy constructor.
3. Immutable classes can also share their internal referenced objects across objects. E.g. BigInteger internally has an int to represent the sign, and an array to store the number. When you use negate() function, it creates a new BigInteger with a different sign, but will reuse the same array of the caller object for optimization reasons.
4. One disadvantage of immutable classes is that, it might become a performance overhead as new objects have to be created for every minor change in value of the object. If an operation is performed in multiple steps, it might lead to creation of many immutable objects being created.
5. Generally immutable classes expose a public mutable companion class to perform multistep operations. E.g. StringBuilder is the mutable companion of String class.
6. If an immutable class implements Serializable interface and it contains fields referring to mutable objects, you must provide an explicit readObject or readResolve method, or use the ObjectOutputStream.writeUnshared and ObjectInputStream.readUnshared methods, even if the default serialized form is acceptable.

Favour composition over inheritance

1. Unlike method invocation, inheritance violates encapsulation. Subclasses depend on the implementation of super class for proper functioning. Changes in superclass might break the subclasses.
2. Create a class called Forwarding class in which each method of the composition object has a corresponding method in the Forwarding class. So it is always better for the Forwarding class to implement the interfaces that the contained class has implemented. It becomes more like Decorator. For any value addition, instead of using inheritance, implement a Forwarding class and add the new value to that class.
3. Disadvantage: Wrapper classes are not suitable for callbacks where an object passes itself to other objects for subsequent invocations. Because a wrapped object doesn’t know of its wrapper, it passes a reference to itself and callbacks elude the wrapper. This is called a SELF problem.

I have taken these points from the book "Effective Java" which I consider as a MUST READ book for every JAVA developer.

Methods common to all objects - Part 2

Override clone judiciouslyA class that implements cloneable interface is expected to provide a fully functioning clone method and make the clone method public (Object class provide only a protected implementation of clone method). Clone creates an object without invoking the constructor.

1.      If you override clone method in a non-final class, you should return an object obtained by invoking super.clone. So internally if all classes do it, Object’s clone method will be called creating the instance of the right class.

2.      It is legal for an overriding method’s return type to be a subclass of the overridden method’s return type. This allows the overriding method to provide more information about the returned object and eliminates the need of casting in the client.

3.      Clone method functions as another constructor. You must ensure that it doesn’t harm original object and that it properly establishes invariants on the clone. Clone method should always do a deep-copy wherever it makes sense. E.g. in case of a stack, clone method will copy only the size variable but not the actual elements (it will reference the same object. So you need to clone the array/list also.)

4.      Providing clone methods will become difficult when there are final modifier variables in a class. This is because, after cloning you might want to make the variable reference a new value (or at least the cloned value) which might not be possible.

5.      Clone method should internally use only private methods and final methods.

6.      It is always preferable to use copy constructor or static factory than fixing the complexity of clone method.

Consider implementing Comparable

Comparable interface provides a natural ordering of the objects of a class. Equals() tells whether two objects are equal or not, whereas comparable tells the ordering of the two objects.

1. By implementing Comparable interface, you can make use of a lot of existing generic algorithms and collection implementation that depend on this interface.
2. CompareTo method can return a negative value, zero, or positive value as this object is less than, or equal, or greater than the specified object.
3. You should make sure that sign of x.compareTo(y) = opposite sign of y.compareTo(x). Symmetry, Reflexivity, andTranslative relationship should also hold.
4. Similar to equals(), there is no way that you can add a value component by subclassing.
5. Unlike equals(), the parameter of the compareTo is not an Object, but the instance of the specific class itself.

I have taken these points from the book "Effective Java" which I consider as a MUST READ book for every JAVA developer.

Methods common to all objects - Part 1

All the non-final methods of the Object class have explicit general contracts and any overrides of these methods should adhere to those contracts failure of which might result in abnormal behaviour.

Obey the general contracts when overriding equals()

1. In general, an object is always one and only equal to itself as per the default implementation.
2. Equals are overriden when there is a logical equality between 2 instances. This is more appropriate in case of Value classes.
3. Instance controlled classes might reuse the equivalent objects efficiently by not allowing 2 objects with equivalent values to get created. In such cases equals() need not be overriden.
4. The equals method should be reflexive, transitive, symmetric, consistent, and if x is not null then x.equals(null) should always be false.
5. There is no way to extend an instantiable class and add a value component while preserving the equals contract. The workaround is to use composition rather than inheritence and then add the value component. Remember that such problem wont exist in case of abstract parent classes as you cant create instances of them leading to such different equals() method being called.
6. Using getClass() method in the equals and comparing only when the current object's class is equal to the other object violates Liskov substitution principle.

Liskov substitution principle: Any important property of a type should also hold for its subtypes, so that any method written for the type should work equally well for its subtype.

It is very easy to break symmetry and transitivity. This is because when you compare a super class object with a subclass object, the subclass might have overriden the implementation of equals method. It might lead to breakage of symmetry behaviour.

SuperClassObject.equals(subClassObject);

A good template of equals() is as follows:

boolean equals(Object o) {

    if (o == this) return true;

    if (!(o instanceof Klass)) return false;

    Klass obj = (Klass) o;

    return obj.a == this.a;

}

While comparing, for non-float fields use ==, for references use equals(), and for float and double use Float.compare and Double.compare.

Always override hashCode when you override equals

As per the Object contract for hashCode, hashCode should always return the same code provided none of the fields used in the equals() comparison has changed. Two objects which return true for equals() should always have the same hashCode. If two objects are not equal, then as far as possible they should not have the same hashCode which might result in increased performance of the hash tables.

1. You should ALWAYS exclude fields that are not used in equals() while computing the hashCode.
2. If computing the hashcode is costly for a immutable object, you can consider caching the hashCode for furture references.

Always override toString

As per the Object contract, toString is expected to provide a concise but informative representation that is easy for a person to read. Also it is recommended that all classes override this method.

1. toString method should return details on all interesting information contained in the object.
2. Whether or not you decide to specify the format of the toString, you should clearly document your intentions. The disadvantage of specifying the format is that, client may write code which is tightly bound to the format and so changing the format at the later stage becomes difficult.
3. Also note that, provide accessors to ALL the parameters that you show in the toString. This will help the clients not to rely on just the toString method to get the detail.

I have taken these points from the book "Effective Java" which I consider as a MUST READ book for every JAVA developer.

Slab allocator

Situation:
Traditional memory allocators have always seen memory as a sequence of bytes available for use. From the layers point of view, memory allocators are below the 'Object' layer and so they have no idea on what kind of object is going to use the memory. In a way it is good, as the implementation of memory allocator becomes simpler. However, it also has a drawback. There are some object whose basic structure doesn't get changed in the course of the execution and so can be reused instead of them going through creation/destruction cycle repeatedly. Also, when the object's initialization becomes very costly, they should be reused as far as possible.

Object caching:
It makes sense for a memory allocator to understand the concept of objects so that memory can be allocated in a better way. So let us introduce a new layer above the usual memory allocator layer which is an object cache. Each type of object has its own cache. When the client requests a cache to allocate an object, the cache checks whether there are any free objects and if there are none, it asks the VM to allocate memory and creates an object and returns it. From the next time on, when the same object becomes free (i.e. when the client releases the object), object creation/initialization part is avoided and the same object is reused from the cache. If the memory manager asks the cache to free up some memory so that it can be reused by other systems, deallocate some objects and return some memory to it. On a cautious note, the object cache layer shouldn't waste memory and should return any unwanted memory to the underlying memory manager when memory manager asks for it.

Client and the central allocator:
Let us call the object caching pool the central allocator. We can split the system up into a client layer which should understand the object completely (including its name, size, how it should be constructed and destructed, its alignment etc) and requests the cache to create an object. The central allocator should take care of the underlying memory management and object caching thereby simplifying the interface for the clients.

Slab allocator:
The central allocator grows or shrinks by 1 slab size. A slab can be visualized as a contiguous memory split into equal-size chunks with a reference count on how many of those chunks are in use right now. To allocate/free a memory, just update the reference count, and return memory from the slab that has extra space. If the reference count goes to zero, the cache can shrink itself by the size of one slab. Slab allocator also reduces internal and external fragmentation issues as it already knows the size of the object it is always going to allocate.

Architecture:
A cache is always going to have similar objects only. It grows or shrinks by the size of a slab. So the cache maintains a circular doubly linked list to go to all slabs it manages right now (the node is called kmem_slab also has a reference count so that it can be deallocated later). Internally a slab is a contiguous memory whose size might span across pages. To know which objects are free to use right now, each slab maintains an additional free-list (the node is called kmem_bufctl which has the buffer address and a back pointer to the kmem_slab node). When the object size becomes very small, maintaining a free-list becomes an overhead as it occupies a lot of memory. So the kmem_slab and kmem_bufctl are all maintained at the end of the slab memory itself. Also kmem_bufctl wont be a linked list anymore but just bit vector showing whether an object in slab is in use or not.

Working of a Slab allocator:
The slabs are arranged in a particular order based on its usage; i.e. all free slabs are maintained at the end of the cache's DLL before which comes the partially used slab. The cache internally has a free-list pointer pointing to the first non-empty slab from which it can start allocating objects whenever a client places a request (remember, it also updates the reference count of the slab). The non-empty slab will then return the object from its buffer.
When an object is being returned by the client, if the reference count of the corresponding slab becomes zero, it is appended to the tail of the cache's free list. When the system runs low on memory, it will demand the slab allocator to release some memory. The slab allocator in turn releases some of its free slabs which have not been used recently. It doesn't release all free lists to avoid thrashing.

Usage:

Slab allocator are being used by many operating systems including Linux and Solaris, as it has been proven to work very efficiently. Memcached also uses this to avoid internal fragmentation.

Creating and Destroying Objects - Part 2

Avoid creating unnecessary objects

1.      You can sometimes avoid creating unnecessary objects by using static factory methods.

2.      Objects should be reused when they are immutable.

3.      Lazy initializations are NOT preferrable as it might complicate simple code unnecessarily.

4.      Any stateless object need not be created multiple times. E.g. Adaptor classes are generally stateless and can be reused.

5.      Java has a lot of classes equivalent to its primitives. E.g. Long class is similar to long primitive. As far as possible, try using primitives. Prefer using primitives to boxed primitives and watch out for unintentional autoboxing (conversion from primitive to boxed primitive).

Eliminate obsolete object references

1.      Obsolete references are those references which wont be deferenced again. Such unintentional object references might miss garbage collection.

2.      Make all the object references null once they become obsolete.

Places to watch out for memory leaks:

1.      Whenever a class matches its own memory. E.g. Stacks.

2.      Caches – nullify all the cached items once they become outdated. Make use of WeakHashMap which are designed to do exactly this. They will get cleared automatically when all the outside references have become null. Other classes which do the same are LinkedHashMap. Java.lang.ref provides more sophisticated caches.

3.      Listeners and other callbacks – Listeners might register callbacks but may not deregister. The best way to ensure that callbacks are garbage collected is to store only week references.

Avoid Finalizers

1.      Finalizers are unpredictable, often dangerous, and generally unnecessary and can lead to severe performance penality, erratic behaviour, and introduce issues in portability.

2.      JVM doesn't provide any guarantee about when it will execute finalizers. In fact it doesnt guarantee its execution at all. So any critical code like freeing an expensive resource should never be done on finalizers.

3.      System.gc and System.runFinalization might increase the probability of finalizer running, but it doesnt guarantee anything. System.runFinalizersOnExit guarantees the execution of finalizer but might be deprecated soon.

4.      When you want to free a resource, provide an explicit terminate() method which the client can use to free the resource. In case the client doesnt call it, then fall back on finalizers.

5.      Also call the terminate() method in the finally block, so that it is almost always guaranteed to work.

6.      Finalizer chaining (calling the superclass's finalizer method) is not done automatically. So when you override a superclass implementation of finalizer method, you should explicitly call the finalizer of the superclass.

When to use finalizers

1.      Finalizer can work as a fallback, but even in that case it is good to log an error as the resource hasnt terminated properly and the code bug needs to be fixed.

2.      While dealing with native objects, you can use finalizers to release some critical resources. This is because JVM doesn't keep track of native objects and so they wont be garbage collected.

I have taken these points from the book "Effective Java" which I consider as a MUST READ book for every JAVA developer.

Creating and Destroying Objects - Part 1

Consider static factory methods instead of constructors

Advantages:

1.      You can choose a meaningful name for the factory method which is not possible with constructors.

2.      Static factory methods can choose when to create an object. They can reuse the existing object instead of creating a new one by caching the instances as and when being constructed (Classes doing this are called instance-controlled).

3.      Based on the arguments, the static method factory can decide to return a different sub-type of the promised return type which need not be even public.

4.      They reduce verbosity of creating parameterized types (Shown below).

Disadvantages:

1.      If you provide only static factory method and make constructors private, you can't subclass it.

2.      The API documentation will have a list of static factory methods along with other static methods, and there is no clear way to differentiate them.

Conventions:

1.      Static factory methods are sometimes provided in a dedicated class. If the type they are going to return is called Type (E.g. Car), the class containing the static factory methods is called Types (E.g. Cars).

2.      Static factory methods usually have the following names. ValueOf, getInstance, newInstance, getType, newType.

Code where verbosity is reduced:

Map<String, List<String>> m =  new HashMap<String, List<String>>();

Can be expressed as:

public static <K, V> HashMap<K, V> newInstance() {
    return new HashMap<K, V>();
}
Map<String, List<String>> m = HashMap.newInstance();

Consider a builder when faced with many constructor parameters.

1.      Telescoping constructors (providing multiple constructors) wont scale when there are too many parameters to be added. And it will make the life of client very complicated.

2.      JavaBeans pattern (providing setters for all the fields) might leave object in an inconsistent state when client doesnt set all values well. You may want to freeze the object till it is being built correctly and then unfreeze it. However this solution is not being used in general.

3.      Using Builder Pattern is a better choise as it simulates a named optional parameter and the build() method can ensure that all required values are set properly.

4.      Disadvantage of using builder is that the client side code becomes more verbose.

Enforce singleton property with a private constructor or an enum type.

Enforce noninstantiability with a private constructor

1.      There are cases where you want a class not to have any instance. The class might just be a grouping of a collection of static utility methods, or static factory methods.

2.      You can make the class abstract and thereby prevent direct instance being created for that class. However this can be broken easily by extending the abstract class and creating objects of the inherited class.

3.      Make the constructor private and then throw an exception from within so that no one can create (even from inside the class) an instance of this class.

As a side effect, making the constructor private prevents the class from being extended.

I have taken these points from the book "Effective Java" which I consider as a MUST READ book for every JAVA developer.

Minima in a sliding window

This is the second time I am hearing about this interview question, and so I should not ignore this anymore. I personally had this question in one of my interviews where I couldn't find the most optimal solution. My friend got this question in Google interview very recently and he too failed to give the best answer. So, I took my time to surf the Internet to find out the best answer.

Question:
You are given an array of size n (may be a stream also). You have a sliding window of size k. The window first boxes the first k elements of the array and slides slowly over the array by shifting its position 1 element each time. At each position of the array, you need to find the minimum element in the sliding window. i.e. you need to give the minimum of 0 to k-1 elements, then 1 to k elements, 2 to k+1 elements etc. So if your array's size is n, you have to give me n-k+1 minimum values.
E.g. Assume that the array is 5,1,3,2,6,8,4,6, and the window size is 3
You should give me 1,1,2,2,4,4. How will you give it?

Solution #1:
As you  need to find out the minimum, my solution was to use a min-heap of size k and gave a solution with time complexity O(nlog(k)). My friend too thought in the same lines. First form a min heap with the first k elements (initial position of the window). Now as and when the window slides, you need to form a new min-heap by adding the next element and discard the first element. Addition of a new element is simple and will take O(log(k)) time. But for deleting an element, you need O(k) time which pushes the time higher. So instead of seeing the problem as a two step process, see it as changing the value of an element in the heap, i.e. you need to change the value of the element you want to discard to the new element that you want the heap to have. If the element that gets into the window knows which element to remove from heap (by maintaining a pointer), the problem can easily be solved in O(nlog(k)) time by simply calling min-heapify n times.

Solution #2:
However, there is a better solution for this problem in O(n) time. At any time, you will add exactly 1 new element from the stream to the window, and discard 1 element.

Step 1: Finding ascending minima:

Assume that the current window is 5,1,3,2. You need to form a list with the following algorithm -
1. Find the minimum element in the whole list (1 in our example). Let the index of that element in the window be i (this too is 1 if the index is zero based). Insert that element in the list.
2. Now forget about the first i elements (where W[i] = min element in the whole window).
3. From  i+1 to k elements, find the minimum value and add it to the list.
4. Repeat it till you add the last element of the window as an entry in the list.
In our example, among all the elements 1 is the least element. So, the result list should be 1.
Now discard the first two elements (ignore the prefix of the array such that the end element is the minimum element you have found. i.e. ignore 5 and 1). Now in the resultant array, find the minimum. i.e. 2. Add this element to the list. So the list will be 1,2.
Do the same step recursively (here only 2 elements are there, but if 2 is not the last element, you should have continued doing the same till you insert the last element in the list).
The new list that you have formed is called ascending minima.
Example:

Assume that the window is [6,2,1,5,3,4,8].

1. Start with an empty ascending minima array, call it ama = {}

2. In the window, find the minimum element in the window (1 at the 3rd position). Add that minimum element to the ama list, and ignore all elements till 1 in the window,

So ama = {1} and sub-window to be processed = {5,3,4,8}.

3. Find the smallest element in the sub-window to be processed (3 at the 2nd position in the sub-window). Add 3 to the ama list and discard all elements till 3 in the sub-window.

So, ama = {1,3} and sub-window to be processed = {4,8}.

4. Find the smallest element again in the sub-window (4 at the 1st position), and add it to the ama list. Ignore elements till 4.

So, ama = {1,3,4} and sub-window to be processed = {8}.

5. Find the smallest element in the window again. i.e. (8 at the 1st position). Add it to the ama list. Now discard all elements till 8 which results the sub-window as an empty array.

ama={1,3,4,8} and sub-window to be processed = {}

6. End the process as sub-window to be processed is empty.

Other examples:

[8,9,5,3,6,5,1,1,0] - ascending minima = [0]

[7,4,8,6,3,4,2,1,2] - ascending minima = [1,2]

[1,2,3,4,5,6,7,8,9] - ascending minima = [1,2,3,4,5,6,7,8,9]

[9,8,7,6,5,4,3,2,1] - ascending minima = [1]

[9,1,1,3,4,2,6,8,9] - ascending minima = [1,2,6,8,9] (In case duplicates are there, take the last one).

Algorithm:

def ascending_minima(arr, minima = [])
  return minima if arr.empty?
  return minima << arr[0] if arr.size == 1
  
  min_index = 0
  1..(arr.size-1).each { |i| min_index = i if arr[i] < arr[min_index]}
  minima << arr[min_index]
  minima = ascending_minima(arr[min_index+1..arr.size-1], minima)
  return minima
end

Note: The minimum element of the window is always present as the first element of the ascending minima list.

Step 2: Adjusting ascending minima for window shift

What happens when a window shifts by an element? The first element in the previous window gets discarded and a new element gets added at the end of the window. As, from ascending minima, you can easily find the smallest element of a window (by peeking into the first element of the ascending minima). Let us try how to get the ascending minima without reconstructing it from scratch by using the previous ascending minima itself.

1. If the element that you discard is the first element in the ascending minima, you need to get rid of that element from the ascending minima.
2. As in all the cases, we took the suffix array to find the minimum element. Now there should have been cases that the newly added element is the minimum element. Search from the end of the ascending minima start discarding all elements that are > X .
3. Insert X at the end.
Now, for 1 shift of the window, you have adjusted the minima array from which you can find the minimum element of the window in O(1) time by looking at the first element.
Example:
The ascending minima of [6,2,1,5,3,4,8] is [1,3,4,8].
If the window slides and takes in the next element say 7 and discards the first element 6. How should we reconstruct the ascending minima?
1. As 6 is getting discarded right now, in case the lowest element in window was 6, it would have been the first element in the minima list, in which case should discard the first element in the minima list. Here this is not the case.
2. After shifting, the window has the following elements [2,1,5,3,4,8,7]. Our previous minima list was [1,3,4,8]. We add an element to the minima list only when that is the SMALLEST element in the sub-window. So any number > 7 say K would have entered the minima only because at that time, the sub-window had all numbers >= K. Now that 7 has come that too as the LAST element of the window, no element > 7 should be present in the minima list as the adjusted new sub-window will have 7 also from now on, and 7 is lesser than any other element in the sub-window. i.e. When we chose 8 for the minima list, the sub-window we had was only [8]. Now, as window has shifted and 7 has entered, the sub-window will be [8,7]. So, clearly 8 can't be present in the minima list. It should be 7.
3. So adjusting for a shift is the minima list becomes [1,3,4,7].
Other examples:
[1,3,3,2,5,8,7,8,9] - minima is [1,2,5,7,8,9]
Case #1: If window moves and adds 6 at the right, then:
1. 1 gets discarded from the minima list. leaving the minima as [2,5,7,8,9]
2. As 6 has entered, remove all elements from the right that are > 6 and add 6 at the end. So minima will become [2,5,6].
Case #2: If the given window moves and adds 10 instead of 6,
1. 1 gets discarded leaving the minima as [2,5,7,8,9]
2. Pop out all elements that are > 10 at the end and insert 10 at the end. So the minima will become [2,5,7,8,9,10].
Case #3: If the given window moves and adds 0
1. 1 gets discarded leaving the minima as [2,5,7,8,9]
2. Pop out all elements that are >= 0 and insert a 0 at the end. So the new minima will become [0]


Algorithm

def get_minima_adjusted_to_shift(previous_window, new_element, previous_minima)
  previous_minima.delete(0) if previous_window[0] == previous_minima[0]
  while (previous_minima.last > new_element)
    previous_minima.delete(previous_minima.size-1)
  end
  previous_minima << new_element
  return previous_minima
end

Coming to the time complexity of the algorithm, in the worst case, all the elements might enter the minima array and all of them might get discarded from the array both of which are O(n). So the whole algorithm works in O(n) time.

Random linked list

One of my friends attended Google interview few days back, and he got this question as one of the questions. I have chosen to discuss the solution for that question in this post. I have written a dedicated post only because if you know a better solution, you can discuss it here so that many others (including myself) can learn.

Question:
There is a lined list whose node has 3 components. The trivial ones are the data and the next pointer. Apart from these two fields, the 3rd field is interesting. It is another pointer called rand which points to a random node in the list. The random node can come before/after the current node in the list, or can also be NULL. Given such a list, how will you make a copy of it? (Before jumping to see my solution, please take a couple of minutes and come up with your own solution first.)

struct node {
  int data;
  struct node *next;
  struct node *rand;
}

My Answer:
If it is just a matter of data and next fields, the solution becomes very trivial. The only challenge is the rand pointer. One crude way of doing this is to ignore the rand pointer initially and create the copy of the list. To fix the rand pointer, for each node in the given list, find out the order of the node (nth node) to which rand pointer points to. Once the n value is known, use it in the fresh list that you have created. This will take O(n^2) time and is more of a brute force type.

Here is a better solution. Assume that the list given to you is A1->A2->A3->A4 (ignoring the rand pointer).
Create a copy of the same list B1->B2->B3->B4 (Note that A1=B1, A2=B2, A3=B3, A4=B4).
Now, form a list like this A1->B1->A2->B2->A3->B3->A4->B4 (You could have created this as the first step itself, instead of creating a list with only B's).
Now assume that the rand pointers of B's are copied from A's directly. Then, if A1.rand=A3, then B1.rand=A3. Now, if you go to each odd node (i.e. nodes that are newly created), and move the rand pointer just 1 step forward, all your rand pointers will get fixed correctly.
Now the only remaining task is to break down the list once again to two lists which should be very trivial.

Any other answer?
Guys, I have shared one solution that I know of. Is there any better way of doing this?

Singleton Pattern

Situation:
When you want only one instance of a class, how would you proceed doing it?

Singleton Pattern:
Singleton pattern ensures that you have only one instance of a class. There are many ways to implement Singleton which has been discussed below. However there are so many gotchas that you need to think through. As Singleton is a very popular pattern, I am not going deep into how exactly it works, but will discuss only those points which are generally missed.

Implementation 1:

class Singleton implements Serializable {
  // Create a static instance immediately and
  // use this only
  // Make this variable transient so that
  // it can be serialized
  private static transient final Singleton INSTANCE
    = new Singleton();

  // You could have let the INSTANCE variable to be
  // public and avoided this method.
  // But doing this is a better choise as if you want
  // to make this class a non-singleton, the clients
  // wont get affected in this case.
  public static Singleton getInstance() {
    return INSTANCE;
  }

  // Make sure that you cant create an object
  // outside this class.
  // A privileged client might mess around by changing
  // the accessibility of this constructor.
  // To prevent this from happening,
  // throw an exception inside the constructor.
  private Singleton() {
    throw new IllegalAccessException()
  }

  // This method preserves the singleton property
  // when the class is deserialized.
  // If this method is not provided, when the class
  // is serialized and later deserialized,
  // each deserialization will result in a separate
  // instance.
  private Object readResolve() {
    return INSTANCE;
  }
}

Implementation 2:
A sophisticated getInstance method is provided which will lazily create the singleton instance object.

class Singleton {
  // This variable is made volatile so that this variable
  // is not cached when a processor executes it.
  // Otherwise in a multi processor environment,
  // it might cause issues as each processor will have
  // its own cached copy of this variable.
  private static volatile Singleton instance;

  public static Singleton getInstance() {
    if (instance == null) {
      synchronized(Singleton.class) {
        if (instance == null) {
          instance = new Singleton();
        }
      }
    }
    return instance;
  }

  private Singleton() { }
}

Implementation 3

This is the best way to create a singleton class. This takes care of all serialization issues and ensures that always there is only one instance. It also guarantees that nobody can hack the system to get more instances.

public enum Singleton {
  INSTANCE
}

Disadvantage:
Making a class a singleton can make it difficult to test its clients as mocking becomes very difficult. To overcome this problem, the singleton class should always be accompanied by an interface. The client should depend on the interface rather than the Singleton class directly.