Wednesday, September 27, 2017

Design Pattern- Comparison between MVC,MVP and MVVM in Android Application Development?

Comparison between MVC,MVP and MVVM in Android Application Development?

I often get questions that which one is better MVC,MVP and MVVM when you are developing Android application.So i have decided to give the overview on all of them.

The best practices approach for developing Android applications into logical components has evolved over the last few years. The community has largely moved away from the monolithic Model View Controller (MVC) pattern in favor of more modular, testable patterns.

Model View Presenter (MVP) & Model View ViewModel (MVVM) are two of the the most widely adopted alternatives, but developers are often divided  as to which one better.So lets take a look into it.

MVC

The model, view, controller approach separates your application at a macro level into 3 sets of responsibilities.

Model

The model is the Data + State + Business logic of any application. It’s the brains of any application so to speak. It is not tied to the view or controller, and because of this, it is reusable in many contexts.

View

The view is the Representation of the Model. The view has a responsibility to render the User Interface (UI) and communicate to the controller when the user interacts with the application. In MVC architecture, Views are generally pretty "dumb" in that they have no knowledge of the underlying model and no understanding of state or what to do when a user interacts by clicking a button, typing a value, etc. The idea is that the less they know the more loosely coupled they are to the model and therefore the more flexible they are to change.

Controller

The controller is basically a Glue that ties the app together. It’s the master controller for what happens in the application. When the View tells the controller that a user clicked a button, the controller decides how to interact with the model accordingly. Based on data changing in the model, the controller may decide to update the state of the view as appropriate. In the case of an Android application, the controller is almost always represented by an Activity or Fragment.


             ----> Notify                                        --------->Interact with
View<------------------------>Controller------------------------------------>Model
          Setup View  <-----


Evaluation

MVC does a great job of separating the model and view. Certainly the model can be easily tested because it’s not tied to anything and the view has nothing much to test at a unit testing level.

The Controller has a few problems however.
Controller Concerns

Testability - The controller is tied so tightly to the Android APIs that it is difficult to unit test.

Modularity & Flexibility - The controllers are tightly coupled to the views. It might as well be an extension of the view. If we change the view, we have to go back and change the controller.

Maintenance - Over time, particularly in applications with anemic models, more and more code starts getting transferred into the controllers, making them bloated and brittle.

How can we address this? MVP to the rescue!

MVP

MVP breaks the controller up so that the natural view/activity coupling can occur without tying it to the rest of the “controller” responsibilities. More on this below, but let’s start again with a common definition of responsibilities as compared to MVC.

Model

Same as MVC / No change

View

The only change here is that the Activity/Fragment is now considered part of the view. We stop fighting the natural tendency for them to go hand in hand. Good practice is to have the Activity implement a view interface so that the presenter has an interface to code to. This eliminates coupling it to any specific view and allows simple unit testing with a mock implementation of the view.

Presenter

This is essentially the controller from MVC except that it is not at all tied to the View, just an interface. This addresses the testability concerns as well as the modularity/flexibility concerns we had with MVC. In fact, MVP purists would argue that the presenter should never have any references to any Android APIs or code.

                         ----> Notify                         --------->Interact with
View<----------------------------->Presenter------------------------------------>Model
         Ask view to Setup Itself

Evaluation

This is much cleaner. We can easily unit test the presenter logic because it’s not tied to any Android specific views and APIs and that also allows us to work with any other view as long as the view implements the interface.

Presenter Concerns

Maintenance - Presenters, just like Controllers, are prone to collecting additional business logic, sprinkled in, over time. At some point, developers often find themselves with large unwieldy presenters that are difficult to break apart.

Of course, the careful developer can help to prevent this, by diligently guarding against this temptation as the application changes over time. However, MVVM can help address this by doing less to start.

MVVM

MVVM with Data Binding on Android has the benefits of easier testing and modularity, while also reducing the amount of glue code that we have to write to connect the view + model.

Let’s examine the parts of MVVM.

Model

Same as MVC / No change

View

The view binds to observable variables and actions exposed by the viewModel in a flexible way. More on that in minute.

ViewModel

The ViewModel is responsible for wrapping the model and preparing observable data needed by the view. It also provides hooks for the view to pass events to the model. The ViewModel is not tied to the view however.


               ---->Invoke Action                                          --------->Interact with
View----------------------------->ViewModel(Interface)------------------------------------>Model
              ----->Bind To Data


page for some more great examples of MVVM & Data Binding.

Evaluation

Unit testing is even easier now, because you really have no dependency on the view. When testing, you only need to verify that the observable variables are set appropriately when the model changes. There is no need to mock out the view for testing as there was with the MVP pattern.

MVVM Concerns

Maintenance - Since views can bind to both variables and expressions, extraneous presentation logic can creep in over time, effectively adding code to our XML. To avoid this, always get values directly from the ViewModel rather than attempt to compute or derive them in the views binding expression. This way the computation can be unit tested appropriately.

Conclusions

Both MVP and MVVM do a better job than MVC in breaking down your app into modular, single purpose components, but they also add more complexity to your app. For a very simple application with only one or two screens, MVC may work just fine. MVVM with data binding is attractive as it follows a more reactive programming model and produces less code.

So which pattern is best for you? If you’re choosing between MVP and MVVM, a lot of the decision comes down to personal preference, but seeing them in action will help you understand the benefits and tradeoffs.



Tuesday, September 26, 2017

Reverse a string in Java in 5 Different Ways?

Reverse a string in Java in 5 Different Ways?.

Ans: its very easy though and very popular question in interview.So thought of giving my inputs
on it.

Examples:

Input :  abhinaw
Output : wanihba

Input: Abhinaw Tripathi
Output: ihtapirT wanihbA

Before,dig in would like to tell you some interesting facts about String and StringBuffer classes:

1. Objects of String are immutable.

2. String class in Java does not have reverse() method, however StringBuilder class has built in reverse() method.

3. StringBuilder class do not have toCharArray() method, while String class does have toCharArray() method.

So the first ways is using:

1)Converting String into Bytes:

getBytes() method is used to convert the input string into bytes[].

Method:

 1. Create a temporary byte[]  of length equal
   to the length of the input string.
 
2. Store the bytes (which we get by using
   getBytes() method) in reverse order into
   the temporary byte[] .
 
3. Create a new String abject using byte[] to
   store result.
 
   Sample Code:
 
 
import java.lang.*;
import java.io.*;
import java.util.*;

class ReverseStringTest
{
public static void main(String[] args)
{
String input = "abhinaw";

byte [] strAsByteArray = input.getBytes();

byte [] result =
new byte [strAsByteArray.length];

for (int i = 0; i<strAsByteArray.length; i++)
result[i] =
strAsByteArray[strAsByteArray.length-i-1];

System.out.println(new String(result));
}
}

Output:

wanihba

2)Using built in reverse() method of the StringBuilder class: 

String class does not have reverse() method, we need to convert the input string to StringBuilder, which is achieved by using the append method of StringBuilder. After that, print out the characters of the reversed string by scanning from the first till the last index.

Sample Code:

import java.lang.*;
import java.io.*;
import java.util.*;

class ReverseStringTest
{
public static void main(String[] args)
{
String input = "abhinaw";

StringBuilder input1 = new StringBuilder();

input1.append(input);

input1 = input1.reverse();

// print reversed String
for (int i=0; i<input1.length(); i++)
System.out.print(input1.charAt(i));
}
}

Output:
wanihba

3) Converting String to character array: 

The user input the string to be reversed.

Method:
1. First, convert String to character array
   by using the built in Java String class
   method toCharArray().
2. Then, scan the string from end  to start,
   and print the character one by one.
 
 SampleCode:


import java.lang.*;
import java.io.*;
import java.util.*;

class ReverseString
{
public static void main(String[] args)
{
String input = "Abhinaw";
char[] try1 = input.toCharArray();

for (int i = try1.length-1; i>=0; i--)
System.out.print(try1[i]);
}
}

Output: wanihbA

4) Convert the input string into character array by using the toCharArray(): 

Convert the input string into character array by using the toCharArray() – built in method of the String Class. Then, scan the character array from both sides i.e from the start index (left) as well as from last index(right) simultaneously.

1. Set the left index equal to 0 and right
   index equal to the length of the string -1.
2. Swap the characters of the start index
   scanning with the last index scanning
   one by one. After that, increase the left
   index by 1 (left++) and decrease the right
   by 1 i.e., (right--) to move on to the next
   characters in the character array .
3. Continue till left is less than or equal to
   the right.
   
   SampleCode:
 
import java.lang.*;
import java.io.*;
import java.util.*;

class ReverseStringTest
{
public static void main(String[] args)
{
String input = "Abhinaw Tripathi";
char[] temparray = input.toCharArray();
int left, right=0;
right = temparray.length-1;

for (left=0; left < right ; left++ ,right--)
{
char temp = temparray[left];
temparray[left] = temparray[right];
temparray[right]=temp;
}

for (char c : temparray)
System.out.print(c);
System.out.println();
}
}

Output:

ihtapirT wanihbA

5)Using ArrayList object:

 Convert the input string into the character array by using toCharArray() built in method. Then, add the characters of the array into the ArrayList object. Java also has built in reverse() method for the Collections class. Since Collections class reverse() method takes a list object , to reverse the list , we will pass the LinkedList object which is a type of list of characters.

1. We copy String contents to an object
   of ArrayList.
1. We create a ListIterator object by using
   the listIterator() method on the LinkedList
   object.
2. ListIterator object is used to iterate over
   the list.
3. ListIterator object helps us to iterate
   over the reversed list and print it one
   by one to the output screen.
   
SampleCode:

import java.lang.*;
import java.io.*;
import java.util.*;

class ReverseStringTesting
{
public static void main(String[] args)
{
String input = "Abhinaw Tripathi";
char[] hello = input.toCharArray();
List<Character> trial1 = new ArrayList<>();

for (char c: hello)
trial1.add(c);

Collections.reverse(trial1);
ListIterator li = trial1.listIterator();
while (li.hasNext())
System.out.print(li.next());
}
}

Output: ihtapirT wanihbA

Swap two Strings without using third user defined variable in Java

Ans:

Given two string variables a and b, swap these variables without using temporary or third variable in Java. Use of library methods is allowed.

Examples:

Input: a = "Hello"
       b = "World"

Output:

Strings before swap: a = Hello and b = World
Strings after swap: a = World and b = Hello

Solution Algorithm:

1) Append second string to first string and
   store in first string:
   a = a + b

2) call the method substring(int beginindex, int endindex)
   by passing beginindex as 0 and endindex as,
      a.length() - b.length():
   b = substring(0,a.length()-b.length());

3) call the method substring(int beginindex) by passing
   b.length() as argument to store the value of initial
   b string in a
   a = substring(b.length());
 
   
 Sample Code:

import java.util.*;

class SwapTest
{
public static void main(String args[])
{
String a = "Hello";
String b = "World";

System.out.println("Strings before swap: a = " + a + " and b = "+b);
a = a + b;
b = a.substring(0,a.length()-b.length());
a = a.substring(b.length());
System.out.println("Strings after swap: a = " + a + " and b = " + b);
}
}

Output:

Strings before swap: a = Hello and b = World
Strings after swap: a = World and b = Hello

Java.util.StringJoiner in Java 8 Example

Java.util.StringJoiner in Java 8 Example

Ans:I hope everybody knows about it.i am just giving my inputs on it.So

StringJoiner is a class in java.util package which is used to construct a sequence of characters(strings) separated by a delimiter and optionally starting with a supplied prefix and ending with a supplied suffix.
Though, this can also be with the help of StringBuilder class to append delimiter after each string, but StringJoiner provides easy way to do that without much code to write.

Constructors of StringJoiner :

1)StringJoiner(CharSequence delimiter) : 

Small description of it.

Syntax :

public StringJoiner(CharSequence delimiter)
Parameters :
delimiter - the sequence of characters to be used between
each element added to the StringJoiner value

Throws:
NullPointerException - if delimiter is null

2)StringJoiner(CharSequence delimiter,CharSequence prefix,CharSequence suffix) : 

Syntax :

public StringJoiner(CharSequence delimiter,
       CharSequence prefix, CharSequence suffix)
 
Parameters :
delimiter - the sequence of characters to be used between
each element added to the StringJoiner value
prefix - the sequence of characters to be used at the beginning
suffix - the sequence of characters to be used at the end

Throws:
NullPointerException - if prefix, delimiter, or suffix is null

Methods : There are 5 methods in StringJoiner class.

1)String toString() : 

Syntax :

public String toString()
Parameters :
NA
Returns :
the string representation of this StringJoiner
Overrides :
toString in class Object

2)StringJoiner add(CharSequence newElement) :

Syntax :
public StringJoiner add(CharSequence newElement)
Parameters :
newElement - The element to add
Returns :
a reference to this StringJoiner

3)StringJoiner merge(StringJoiner other) :

Syntax :
public StringJoiner merge(StringJoiner other)
Parameters :
other - The StringJoiner whose contents should be merged
into this one
Returns :
This StringJoiner
Throws :
NullPointerException - if the other StringJoiner is null

4)int length() : 

Syntax :
public int length()
Parameters :
NA
Returns :
This StringJoiner

5)StringJoiner setEmptyValue(CharSequence emptyValue) :

Syntax :
public StringJoiner setEmptyValue(CharSequence emptyValue)
Parameters :
emptyValue - the characters to return as the value
of an empty StringJoiner
Returns :
this StringJoiner itself so the calls may be chained
Throws:
NullPointerException - when the emptyValue parameter is null

Sample Program for StringJoiner:

import java.util.ArrayList;
import java.util.StringJoiner;

public class SampleProgram
{
public static void main(String[] args)
{
ArrayList<String> al = new ArrayList<>();

al.add("Abhinaw");
al.add("Abhishek");
al.add("Ram");
al.add("VirtualRelaity");

StringJoiner sj1 = new StringJoiner(",");

// setEmptyValue() method
sj1.setEmptyValue("sj1 is empty");
System.out.println(sj1);

// add() method
sj1.add(al.get(0)).add(al.get(1));
System.out.println(sj1);

// length() method
System.out.println("Length of sj1 : " + sj1.length());

StringJoiner sj2 = new StringJoiner(":");
sj2.add(al.get(2)).add(al.get(3));

//merge() method
sj1.merge(sj2);

// toString() method
System.out.println(sj1.toString());

System.out.println("Length of new sj1 : " + sj1.length());

}
}

Output:

sj1 is empty
Abhinaw,Abhishek
Length of sj1 : 16
Abhinaw,Abhishek,Ram:VirtualRelaity
Length of new sj1 : 35


Monday, September 25, 2017

Covariant return types in Java with Example

Covariant return types in Java Example

Its a very trending interview question now so thought of sharing some of my inputs
on it.

So,before going deep into it.i would like to answer this question very generic ways like
before java JDK verion 5.0.It was not possible to override a method by changing the return type.

When we override a parent class method, the name, argument types and return type of the overriding method in child class has to be exactly same as that of parent class method. Overriding method was said to be invariant with respect to return type.Now if you have notice
two keyword such as Covariant and Invariant So what are those two keywords?.

Covariant return types

Java JDK version 5.0 onwards it is possible to have different return type for a overriding method in child class, but child’s return type should be sub-type of parent’s return type. Overriding method becomes variant with respect to return type.

So all this concept is based on one PRINCIPLE which is Liskov substitution principle.
Now what is this PRINCIPLE?
Let me give breife of this principle.

Liskov substitution principle:

Substitutability is a principle in object-oriented programming stating that, in a computer program, if S is a subtype of T, then objects of type T may be replaced with objects of type S (i.e. an object of type T may be substituted with any object of a subtype S) without altering any of the desirable properties of T (correctness, task performed, etc.).

 More formally, the Liskov substitution principle (LSP) is a particular definition of a subtyping relation, called (strong) behavioral subtyping, that was initially introduced by Barbara Liskov in a 1987 conference keynote address titled Data abstraction and hierarchy. It is a semantic rather than merely syntactic relation because it intends to guarantee semantic interoperability of types in a hierarchy, object types in particular.

 Subtype Requirement: Let {\displaystyle \phi (x)} \phi (x) be a property provable about objects {\displaystyle x} x of type T. Then {\displaystyle \phi (y)} {\displaystyle \phi (y)} should be true for objects {\displaystyle y} y of type S where S is a subtype of T.

 In Layman term,i would rather say this.have a look.

Liskov Substitution Principle,As per the LSP, functions that use references to base classes must be able to use objects of the derived class without knowing it. In simple words, derived classes must be substitutable for the base class. To illustrate the LSP, let’s take an example of rectangles and squares. One tends to establish the ISA relationship, thus, you can say that a square a rectangle. However, there arises a problem (hence, a violation of the LSP).Lets not
go in fuirther details of it.Just keep the above points in your mind for Covariant return types in Java.

Let me provide a simple Code for better understanding:

class A {}
class B extends A {}

class Base
{
    A fun()
    {
        System.out.println("Base fun()");
        return new A();
    }
}

class Derived extends Base
{
    B fun()
    {
        System.out.println("Derived fun()");
        return new B();
    }
}

public class Main
{
    public static void main(String args[])
    {
       Base base = new Base();
       base.fun();

       Derived derived = new Derived();
       derived.fun();
    }
}

Output:

Base fun()
Derived fun()

Note : If we swap return types of Base and Derived, then above program would not work.

Advantages:

1)It helps to avoid confusing type casts present in the class hierarchy and thus making the code readable, usable and maintainable.

2)We get a liberty to have more specific return types when overriding methods.
3)Help in preventing run-time ClassCastExceptions on returns.








Saturday, September 23, 2017

NullPointer Exception(null) and its facts in JAVA with example

Facts about null in Java with example

So let me tell you some interesting facts about null in Java

Almost all the programming languages are bounded with null. There is hardly a programmer, who is not troubled by null.

In Java, null is associated java.lang.NullPointerException.

it is a class in java.lang package, it is called when we try to perform some operations with or without null and sometimes we don’t even know where it has happened.

Below are some important points about null in java which every Java programmer should know:

1. null is Case sensitive: null is literal in Java and because keywords are case-sensitive in java, we can’t write NULL or 0 as in C language.

public class Test
{
    public static void main (String[] args) throws java.lang.Exception
    {
        // compile-time error : can't find symbol 'NULL'
        Object obj = NULL;
       
        //runs successfully
        Object obj1 = null;
    }
}


Output:

5: error: cannot find symbol
 can't find symbol 'NULL'
                 ^
   variable NULL
 class Test
1 error


2. Reference Variable value: Any reference variable in Java has default value null.

public class Test
{
    private static Object obj;
    public static void main(String args[])
    {
        // it will print null;
        System.out.println("Value of object obj is : " + obj);
    }
}

Output:

Value of object obj is : null


3. Type of null: common misconception, null is not an Object or neither a type. It’s just a special value, which can be assigned to any reference type and you can type cast null to any type

Examples:

    // null can be assigned to String
    String str = null;
   
    // you can assign null to Integer also
    Integer itr = null;
   
    // null can also be assigned to Double
    Double dbl = null;
       
    // null can be type cast to String
    String myStr = (String) null;
   
    // it can also be type casted to Integer
    Integer myItr = (Integer) null;
   
    // yes it's possible, no error
    Double myDbl = (Double) null;

4. Autoboxing and unboxing : During auto-boxing and unboxing operations, compiler simply throws Nullpointer exception error if a null value is assigned to primitive boxed data type.

public class Test
{
    public static void main (String[] args) throws java.lang.Exception
    {
            //An integer can be null, so this is fine
            Integer i = null;
           
            //Unboxing null to integer throws NullpointerException
            int a = i;
    }
}

Output:

 Exception in thread "main" java.lang.NullPointerException
    at Test.main(Test.java:6)


5. instanceof operator: The java instanceof operator is used to test whether the object is an instance of the specified type (class or subclass or interface). At run time, the result of the instanceof operator is true if the value of the Expression is not null.
This is an important property of instanceof operation which makes it useful for type casting checks.

public class Test
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Integer i = null;
        Integer j = 10;
           
        //prints false
        System.out.println(i instanceof Integer);
       
        //Compiles successfully
        System.out.println(j instanceof Integer);
    }
}

Output:

false
true

6. Static vs Non static Methods: We cannot call a non-static method on a reference variable with null value, it will throw NullPointerException, but we can call static method with reference variables with null values. Since static methods are bonded using static binding, they won’t throw Null pointer Exception.

public class Test
{            
    public static void main(String args[])
    {
        Test obj= null;
        obj.staticMethod();
        obj.nonStaticMethod();                            
    }
   
    private static void staticMethod()
    {
        //Can be called by null reference
        System.out.println("static method, can be called by null reference");
       
    }
       
    private void nonStaticMethod()
    {
        //Can not be called by null reference
        System.out.print(" Non-static method- ");
        System.out.println("cannot be called by null reference");
       
    }

}

Output:

static method, can be called by null referenceException in thread "main"
java.lang.NullPointerException
    at Test.main(Test.java:5)


7. == and != The comparision and not equal to operators are allowed with null in Java. This can made useful in checking of null with objects in java.

public class Test
{            
    public static void main(String args[])
    {
   
    //return true;
    System.out.println(null==null);
   
    //return false;
    System.out.println(null!=null);
       
    }
}

Output:

true
false



Friday, September 22, 2017

Question:Forward declarations in Java?


So what is Forward Declaration?

Ans:

 A forward declaration is a declaration of an identifier (denoting an entity such as a type, a variable, a constant, or a function) for which the programmer has not yet given a complete definition.

It is required for a compiler to know certain properties of an identifier (size for memory allocation, data type for type checking, such as type signature of functions), but not other details, like the particular value it holds (in case of variables or constants) or definition (in the case of functions). This is particularly useful for one-pass compilers and separate compilation.

Forward declaration is used in languages that require declaration before use; it is necessary for mutual recursion in such languages, as it is impossible to define such functions (or data structures) without a forward reference in one definition: one of the functions (respectively, data structures) must be defined first. It is also useful to allow flexible code organization, for example if one wishes to place the main body at the top, and called functions below it.

In other languages forward declarations are not necessary, which generally requires instead a multi-pass compiler and for some compilation to be deferred to link time. In these cases identifiers must be defined (variables initialized, functions defined) before they are used in execution, but do not need to be defined before they are used in source code for compilation or interpretation: identifiers do not need to be immediately resolved to an existing entity.

Example::

A basic example in C is:

void printThisInteger(int);

In C and C++, the line above represents a forward declaration of a function and is the function's prototype. After processing this declaration, the compiler would allow the program code to refer to the entity printThisInteger in the rest of the program. The definition for a function must be provided somewhere (same file or other, where it would be the responsibility of the linker to correctly match references to a particular function in one or several object files with the definition, which must be unique, in another):

void printThisInteger(int x)
{
   printf("%d\n", x);
}

Now,Come to JAVA,Let me give you an example:

class Test2
{    
    public static void main(String[] args)
{  
         Test1 t1 = new Test1();
         t1.fun(5);      
    }
}  
class Test1
{
    void fun(int x)
{
        System.out.println("fun() called: x = " + x);
    }
}

Predict the output: fun() called: x = 5

The Java program compiles and runs fine. Note that Test1 and fun() are not declared before their use. Unlike C++, we don’t need forward declarations in Java. Identifiers (class and method names) are recognized automatically from source files. Similarly, library methods are directly read from the libraries, and there is no need to create header files with declarations. Java uses naming scheme where package and public class names must follow directory and file names respectively. This naming scheme allows Java compiler to locate library files.


Wednesday, September 13, 2017

Memory Management – Mapping Virtual address to Physical addresses?

Memory Management – Mapping Virtual address to Physical addresses?

Memory is basically a large array of words or arrays. each of which has address associated with it. Now the work of CPU is to get the instructions from the memory based program counter. Now further these instruction may cause loading or storing to specific memory address.

Address binding is the process of mapping from one address space to another address space. Logical address is address generated by CPU during execution whereas Physical Address refers to location in memory unit(the one that is loaded into memory).

Note that user deals with only logical address(Virtual address). The logical address undergoes translation by the MMU or address translation unit in particular. The output of this process is the appropriate physical address or the location of code/data in RAM.

An address binding can be done in three different ways:

Compile Time – It work is to generate logical address(also known as virtual address). If you know that during compile time where process will reside in memory then absolute address is generated.

Load time – It will generate physical address.If at the compile time it is not known where process will reside then relocatable address will be generated. In this if address changes then we need to reload the user code.

Execution time- It helps in differing between physical and logical address.This is used if process can be moved from one memory to another during execution(dynamic linking-Linking that is done during load or run time).

MMU(Memory Management Unit)-

The run time mapping between Virtual address and Physical Address is done by hardware device known as MMU.

In memory management, Operating System will handle the processes and moves the processes between disk and memory for execution . It keeps the track of available and used memory.

Instruction-execution cycle Follows steps:

First instruction is fetched from memory e.g. ADD A,B

Then these instructions are decoded i.e., Addition of A and B

And further loading or storing at some particular memory location takes place.

Basic Hardware

As main memory and registers are built into processor and CPU can access these only.So every instructions should be written in direct access storage
devices.

If CPU access instruction from register then it can be done in one CPU clock cycle as registers are built into CPU.

If instruction resides in main memory then it will be accessed via memory bus that will take lot of time. So remedy to this add fast memory in between CPU and main memory i.e. adding cache for transaction.

Now we should insure that process resides in legal address.
Legal address consists of base register(holds smallest physical address) and limit register(size of range).

For example:

Base register = 300040
limit register = 120900
then legal address = (300040+120900)= 420940(inclusive).
legal address = base register+ limit register

How processes are mapped from disk to memory

Usually process resides in disk in form of binary executable file.
So to execute process it should reside in main memory.
Process is moved from disk to memory based on memory management in use.
The processes waits in disk in form of ready queue to acquire memory.


Procedure of mapping of disk and memory

Normal procedure is that process is selected from input queue and loaded in memory. As process executes it accesses data and instructions from memory and as soon as it completes it will release memory and now memory will be available for other processes.

MMU Scheme –

 CPU->MMU->Memory



 CPU will generate logical address for eg: 346
 MMU will generate relocation register(base register) for eg:14000
 In Memory physical address is located eg:(346+14000= 14346)






length vs length() in Java

length vs length() in Java

Let me give you brief about length and length().

array.length : length is a final variable applicable for arrays. With the help of length variable, we can obtain the size of the array.

string.length() : length() method is a final variable which is applicable for string objects. length() method returns the number of characters presents in the string.

length vs length()

The length variable is applicable to array but not for string objects whereas the length() method is applicable for string objects but not for arrays.

Examples:

// length can be used for int[], double[], String[]
// to know the length of the arrays.

// length() can be used for String, StringBuilder, etc
// String class related Objects to know the length of the String

So to directly accesses a field member of array we can use .length ; whereas .length() invokes a method to access a field member.

Sample Code:

public class Test {
public static void main(String[] args)
    {
        int[] array = new int[4];
        System.out.println("The size of the array is " + array.length);

        String str = "GeeksforGeeks";
        System.out.println("The size of the String is " + str.length());
    }
}

Output: 

The size of the array is 4
The size of the String is 13


Tuesday, September 12, 2017

Yatra.com Interview Experience | The Celebrity Problem

Yatra.com Interview Experience|The Celebrity Problem

The Celebrity Problem

In a party of N people, only one person is known to everyone. Such a person may be present in the party, if yes, (s)he doesn’t know anyone in the party. We can only ask questions like “does A know B? “. Find the stranger (celebrity) in minimum number of questions.

We can describe the problem input as an array of numbers/characters representing persons in the party. We also have a hypothetical function HaveAcquaintance(A, B) which returns true if A knows B, false otherwise.

How can we solve the problem?.

We measure the complexity in terms of calls made to HaveAcquaintance().

There are many solution to this question.Let us see below:

Solution 1 (Graph)

We can model the solution using graphs. Initialize indegree and outdegree of every vertex as 0. If A knows B, draw a directed edge from A to B, increase indegree of B and outdegree of A by 1. Construct all possible edges of the graph for every possible pair [i, j]. We have NC2 pairs. If celebrity is present in the party, we will have one sink node in the graph with outdegree of zero, and indegree of N-1. We can find the sink node in (N) time, but the overall complexity is O(N2) as we need to construct the graph first.

Solution 2 (Recursion)

We can decompose the problem into combination of smaller instances. Say, if we know celebrity of N-1 persons, can we extend the solution to N? We have two possibilities, Celebrity(N-1) may know N, or N already knew Celebrity(N-1). In the former case, N will be celebrity if N doesn’t know anyone else. In the later case we need to check that Celebrity(N-1) doesn’t know N.

Solve the problem of smaller instance during divide step. On the way back, we find the celebrity (if present) from the smaller instance. During combine stage, check whether the returned celebrity is known to everyone and he doesn’t know anyone. The recurrence of the recursive decomposition is,

T(N) = T(N-1) + O(N)

T(N) = O(N2). You may try writing pseudo code to check your recursion skills.

Solution 3 (Using Stack)

The graph construction takes O(N2) time, it is similar to brute force search. In case of recursion, we reduce the problem instance by not more than one, and also combine step may examine M-1 persons (M – instance size).
We have following observation based on elimination technique (Refer Polya’s How to Solve It book).

If A knows B, then A can’t be celebrity. Discard A, and B may be celebrity.
If A doesn’t know B, then B can’t be celebrity. Discard B, and A may be celebrity.
Repeat above two steps till we left with only one person.
Ensure the remained person is celebrity. (Why do we need this step?)
We can use stack to verity celebrity.

Push all the celebrities into a stack.
Pop off top two persons from the stack, discard one person based on return status of HaveAcquaintance(A, B).
Push the remained person onto stack.
Repeat step 2 and 3 until only one person remains in the stack.
Check the remained person in stack doesn’t have acquaintance with anyone else.
We will discard N elements utmost (Why?). If the celebrity is present in the party, we will call HaveAcquaintance() 3(N-1) times. Here is code using stack.

Sample Code:

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */
import java.util.Stack;

public class CelebrityTest
{
    // Person with 2 is celebrity
    static int MATRIX[][] = { { 0, 0, 1, 0 },
                              { 0, 0, 1, 0 },
                              { 0, 0, 0, 0 },
                              { 0, 0, 1, 0 } };

    // Returns true if a knows b, false otherwise
    static boolean knows(int a, int b)
    {
        boolean res = (MATRIX[a][b] == 1) ? true : false;
        return res;
    }

    // Returns -1 if celebrity is not present.
    // If present, returns id (value from 0 to n-1).
    static int findCelebrity(int n)
    {
        Stack<Integer> st = new Stack<Integer>();
        int c;

        // Step 1 :Push everybody onto stack
        for (int i = 0; i < n; i++)
        {
            st.push(i);
        }

        while (st.size() > 1)
        {
            // Step 2 :Pop off top two persons from the
            // stack, discard one person based on return
            // status of knows(A, B).
            int a = st.pop();
            int b = st.pop();

            // Step 3 : Push the remained person onto stack.
            if (knows(a, b))
            {
                st.push(b);
            }

            else
                st.push(a);
        }

        c = st.pop();

        // Step 5 : Check if the last person is
        // celebrity or not
        for (int i = 0; i < n; i++)
        {
            // If any person doesn't know 'c' or 'a'
            // doesn't know any person, return -1
            if (i != c && (knows(c, i) || !knows(i, c)))
                return -1;
        }
        return c;
    }

    // Driver program to test above methods
    public static void main(String[] args)
    {
        int n = 4;
        int result = findCelebrity(n);
        if (result == -1)
        {
            System.out.println("No Celebrity");
        }
        else
            System.out.println("Celebrity ID " + result);
    }
}

OutPut:Celebrity ID 2

Complexity O(N). Total comparisons 3(N-1).

Try the above code for successful MATRIX {{0, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 1}}.

Note: You may think that why do we need a new graph as we already have access to input matrix. Note that the matrix MATRIX used to help the hypothetical function HaveAcquaintance(A, B), but never accessed via usual notation MATRIX[i, j]. We have access to the input only through the function HaveAcquiantance(A, B). Matrix is just a way to code the solution. We can assume the cost of hypothetical function as O(1).

If still not clear, assume that the function HaveAcquiantance accessing information stored in a set of linked lists arranged in levels. List node will have next and nextLevel pointers. Every level will have N nodes i.e. an N element list, next points to next node in the current level list and the nextLevel pointer in last node of every list will point to head of next level list. For example the linked list representation of above matrix looks like,

L0 0->0->1->0
             |
L1           0->0->1->0
                       |
L2                     0->0->1->0
                                 |
L3                               0->0->1->0
The function HaveAcquanintance(i, j) will search in the list for j-th node in the i-th level. Out goal is to minimize calls to HaveAcquanintance function.


Word Break Problem Java Solution

Word Break Problem Java Solution

Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words. See following examples for more details.
This is a famous Google interview question, also being asked by many other companies now a days.

Consider the following dictionary 

{ i, like, sam, sung, samsung, mobile, ice, 
  cream, icecream, man, go, mango}

Input:  ilike
Output: Yes
The string can be segmented as "i like".

Input:  ilikesamsung
Output: Yes

The string can be segmented as "i like samsung" or
"i like sam sung".

i have given two solution in my sample code.you can use any of them.i have given solution is
using HashSet and other one using simple logic.

Sample Code:

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */
public class WordBreakProblemApp
{
private static Set<String> DICTIONARY = new HashSet<String>();
static
{
DICTIONARY.add("mobile");
DICTIONARY.add("samsung");
DICTIONARY.add("sam");
DICTIONARY.add("sung");
DICTIONARY.add("man");
DICTIONARY.add("mango");
DICTIONARY.add("icecream");
DICTIONARY.add("and");
DICTIONARY.add("go");
DICTIONARY.add("i");
DICTIONARY.add("love");
DICTIONARY.add("ice");
DICTIONARY.add("cream");
}

private static boolean existInDictionary(String string)
{
return DICTIONARY.contains(string.toLowerCase());
}

private static void wordutil(String input)
{
processInputString(input, input.length(), "");
}

private static void processInputString(String input, int size, String result)
{

for (int i = 1; i <= size; i++)
{
if (existInDictionary(input.substring(0, i)))
{
if (i == size)
{
  System.out.println(result + " " + input);
  break;
}

else
{
  processInputString(input.substring(i, size), size - i,
  result + " " + input.substring(0, i) + " ");
}
}
 }
}

public static void main(String[] args)
{
   wordutil("ilovesamsungmobile");
}


/*********You can use this method too.it is optional****************/

   public boolean wb(int start, String str, List<String> wordDict, StringBuilder sb)
   {
        for(int i=start; i<str.length(); i++)
        {
                String sub = str.substring(start,i+1);
                System.out.println(sub);
                if(wordDict.contains(sub))
                {
                    sb.append(sub);
                    if(sb.length() == str.length())
                    {
                        return true;
                    }
                 
                    boolean r = wb(i+1, str, wordDict, sb);
                    if(r) return r;
                    sb.setLength(sb.length()-sub.length());
                }
        }
        return false;
    }
}

Output:

 i  love  sam  sung  mobile
 i  love  samsung  mobile


Trending Interview Question Puzzle | Pirates and Gems

Trending Interview Question Puzzle | Pirates and Gems

Question:

Seven pirates attacked the British ship and looted some rare gems from them. They decided to rest for some time and then divide the gems later. While everyone was resting, two pirates wake up and planned to divide gems equally between the two. When they divided gems equally, one gem was left. So, they decided to wake up the third pirate and divide among three, but alas again one gem was left. They decide to wake up the fourth pirate to divide the gems and again one gem was left. The same happened again with the fifth and sixth. Finally, they woke up the 7th pirate and this time the gems were divided equally.

How many minimum gems did they stole in total ?


Solution:

301

Explanation:

1. When there are two pirates, 301/2 = 1 (Remainder)
2. When there are three pirates, 301/3 = 1 (Remainder)
3. When there are four pirates, 301/4 = 1 (Remainder)
4. When there are five pirates, 301/5 = 1 (Remainder)
5. When there are six pirates, 301/6 = 1 (Remainder)
6. When there are seven pirates, 301/7 = 0 (Remainder)


Check Whether a number is Duck Number or not java solution

Check Whether a number is Duck Number or not?

A Duck number is a number which has zeroes present in it, but there should be no zero present in the beginning of the number. For example 3210, 8050896, 70709 are all duck numbers whereas 02364, 03401 are not.

The task is to check whether the given number is a duck number or not.

Examples:

Input : 707069
Output : It is a duck number.
Explanation: 707069 does not contains zeros at the beginning.

Input : 02364
Output : It is not a duck number.
Explanation: in 02364 there is a zero at the beginning of the number.

Sample code:

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */
public class DuckeNumberApp
{
public static void main(String[] args)
{
String num1 = "1023";

        char first_digit1 = num1.charAt(0);
       
        if( check_duck(num1) > 0 && first_digit1 != '0')
            System.out.println("It is a duck number");
        else
            System.out.println("It is not a duck number");
}

public  static int check_duck( String num)
       {
       int len = num.length();
       int count_zero = 0 ;
       char ch;

       for(int i = 1;i < len ;i++)
       {    
           ch=num.charAt(i);
           if(ch=='0')
               count_zero++;
       }
       return count_zero ;
    }
}


Output:

It is a duck number

Trending Interview Puzzle | Truth and Lie Question

Trending Interview Puzzle | Truth and Lie Question

There are two tribes, “Lie tribe” and “Truth Tribe”. “Lie tribe”, as per the name, always lie and “Truth tribe” always speak the truth. You meet three of the persons from these tribes and ask the first person: “Which tribe do you belong to ?”. He replies something in his language which you don’t understand. Second person translates to you that, he is saying that he belongs to the “Lie Tribe”. Third person says that second person is lying.

Question is : Which tribe does the third person belong to?


Solution: Truth Tribe

Explanation: 

As per question we dont know the first person belongs to which tribe.So now if we assume the
first person is from Truth Tribe then he will be definetley saying that he is from "truth tribe".
So in this case the second person must be lying.

Now again, if we assume the first person is from"Lie tribe" then also he will say that he belongs
to truth tribe.So second person is lying again in this case.

SO the conclusion is in both the cases,he belongs to "truth tribe".

Trending Puzzle in Interview | Black and White Balls

Black and White Balls Puzzle

You have 20 white and 13 black balls in a bag. You pull out 2 balls one after another. If the balls are of same color, then you replace them with a white ball – but if they are of different color, you replace them with a black ball. Once you take out the balls, you do not put them back in the bag – so the balls keep reducing. What would be the color of the last ball remaining in the bag.

Solution: Black

How?

So the solution is very simple,the trick is in the solution itself.Let me give you hint again

"You pull out 2 balls one after another. If the balls are of same color, then you replace them with a white ball – but if they are of different color, you replace them with a black ball."

So, the black balls would always be odd in numbers – either you remove 2 together or remove 1 and add 1 – so they remain odd always. So, the last ball in the bag would be a black ball only.

Monday, September 11, 2017

Number of jumps for a thief to cross walls?


Number of jumps for a thief to cross walls?.

A thief trying to escape from a jail. He has to cross N walls each with varying heights (every height is greater than 0). He climbs X feet every time. But, due to the slippery nature of those walls, every time he slips back by Y feet. Now the task is to calculate the total number of jumps required to cross all walls and escape from the jail.


Examples:

Input : heights[] = {11, 11}
                X = 10;
                Y = 1;
Output : 4

He needs to make 2 jumps for first wall
and 2 jumps for second wall.

Input : heights[] = {11, 10, 10, 9}
                 X = 10;
                 Y = 1;
Output : 5

Sample Code:


public class Test
{
static int jumpcount(int x, int y, int n, int height[])
{
int jumps = 0;
for (int i = 0; i < n; i++)
{

// Since all heights are
// greater than 1, at-least
// one jump is always required
jumps++;

// More jumps required if height
// is greater than x.
if (height[i] > x)
{
// Since we have already counted
// one jump
int h = height[i] - (x - y);

// Remaining jumps
jumps += h/(x - y);

// If there was a remainder greater
// than 1. 1 is there to handle cases
// like x = 11, y = 1, height[i] = 21.
if (h % (x-y) > 1)
jumps++;
}
}
return jumps;
}

public static void main(String args[])
{
int x = 10;
int y = 1;
int height[] = { 11, 34, 27, 9 };
int n = height.length;
System.out.println(jumpcount(x, y, n, height));
}
}

Output: 10

Wednesday, September 6, 2017

Main thread in Java

Main thread in Java

Java provides built-in support for multithreaded programming. A multi-threaded program contains two or more parts that can run concurrently. Each part of such a program is called a thread, and each thread defines a separate path of execution.

In detail,a thread of execution is the smallest sequence of programmed instructions that can be managed independently by a scheduler, which is typically a part of the operating system.The implementation of threads and processes differs between operating systems, but in most cases a thread is a component of a process. Multiple threads can exist within one process, executing concurrently and sharing resources such as memory, while different processes do not share these resources. In particular, the threads of a process share its executable code and the values of its variables at any given time.

Main Thread

When a Java program starts up, one thread begins running immediately. This is usually called the main thread of our program, because it is the one that is executed when our program begins.

Properties :

It is the thread from which other “child” threads will be spawned.

Often, it must be the last thread to finish execution because it performs various shutdown actions



How to control Main thread

The main thread is created automatically when our program is started. To control it we must obtain a reference to it. This can be done by calling the method currentThread( ) which is present in Thread class. This method returns a reference to the thread on which it is called. The default priority of Main thread is 5 and for all remaining user threads priority will be inherited from parent to child.

Sample Code:

// Java program to control the Main Thread
public class Test extends Thread
{
public static void main(String[] args)
{
// getting reference to Main thread
Thread t = Thread.currentThread();

// getting name of Main thread
System.out.println("Current thread: " + t.getName());

// changing the name of Main thread
t.setName("Geeks");
System.out.println("After name change: " + t.getName());

// getting priority of Main thread
System.out.println("Main thread priority: "+ t.getPriority());

// setting priority of Main thread to MAX(10)
t.setPriority(MAX_PRIORITY);

System.out.println("Main thread new priority: "+ t.getPriority());


for (int i = 0; i < 5; i++)
{
System.out.println("Main thread");
}

// Main thread creating a child thread
ChildThread ct = new ChildThread();

// getting priority of child thread
// which will be inherited from Main thread
// as it is created by Main thread
System.out.println("Child thread priority: "+ ct.getPriority());

// setting priority of Main thread to MIN(1)
ct.setPriority(MIN_PRIORITY);

System.out.println("Child thread new priority: "+ ct.getPriority());

// starting child thread
ct.start();
}
}

// Child Thread class
class ChildThread extends Thread
{
@Override
public void run()
{
for (int i = 0; i < 5; i++)
{
System.out.println("Child thread");
}
}
}

Output:

Current thread: main
After name change: Geeks
Main thread priority: 5
Main thread new priority: 10
Main thread
Main thread
Main thread
Main thread
Main thread
Child thread priority: 10
Child thread new priority: 1
Child thread
Child thread
Child thread
Child thread
Child thread

Relation between the main() method and main thread in Java

For each program, a Main thread is created by JVM(Java Virtual Machine). The “Main” thread first verifies the existence of the main() method, and then it initializes the class. Note that from JDK 6, main() method is mandatory in a standalone java application.

Deadlocking with use of Main Thread(only single thread)

We can create a deadlock by just using Main thread, i.e. by just using a single thread. The following java program demonstrate this.

// Java program to demonstrate deadlock
// using Main thread
public class Test
{
    public static void main(String[] args)
    {
        try
        {
           
            System.out.println("Entering into Deadlock");
           
            Thread.currentThread().join();
           
            // the following statement will never execute
            System.out.println("This statement will never execute");
           
        }
       
        catch (InterruptedException e)
        {
            e.printStackTrace();
        }
    }
}

Output:

Entering into Deadlock

Explanation : 

The statement “Thread.currentThread().join()”, will tell Main thread to wait for this thread(i.e. wait for itself) to die. Thus Main thread wait for itself to die, which is nothing but a deadlock.