Sunday, August 9, 2015

Detecting the loops in a linked list

Hello Friends today I want to take one of the question that one of my friend asked me which he faced in an interview.

How would you detect whether the linked list has the loop or not?

Let us take a basic example, so assume you have the linked list like that looks like this:

A -> B -> C -> D ->B

Now if you look at the list you find out that the last node is pointing towards B. So now the question is how would you find whether the list has a loop or not.

For this problem there are some solutions, one of them is Floyd's cycle-finding algorithm, also known as tortoise and hare algorithm.

The algorithm's idea is that, maintains 2 pointers and move with them with different speeds, one fast and one slow, if there is a loop, one time they will definitely meet.

Going forward with this idea in mind, let us see the program.


boolean hasLoop(Node first) {
    if (first == null) // list does not exist..so no loop either.
        return false;
    Node slow, fast; // create two references.
    slow = fast = first; // make both refer to the start of the list.
    while (true) {
        slow = slow.next;          // 1 hop.
        if (fast.next != null)
            fast = fast.next.next; // 2 hops.
        else
            return false;          // next node null => no loop.

        if (slow == null || fast == null) // if either hits null..no loop.
            return false;
        if (slow == fast) // if the two ever meet...we must have a loop.
            return true;
    }
}

Now the other problem is to know the start of the loop. For that we follow:

Step1: Proceed in the usual way u'll use to find the loop. ie. Have two pointers, increment one in single step and other in two steps, If they both meet in sometime, there is a loop.

Step2: Freeze one pointer where it was and increment the other pointer in one step counting the steps u make and when they both meet again, the count will give u the length of the loop.(This is same as counting the number of elements in a circular link list.)

Step3: Reset both pointers to the start of the link list, increment one pointer to the length of loop times and then start the second pointer. increment both pointers in one step and when they meet again, it'll be the start of the loop. (This is same as finding the nth element from the end of the link list.)

public class LoopInLinkedList {

    static class Node {
        public String info;
        public Node next;
        @Override
        public String toString() {
            return "Node [info=" + info + ", next=" + next.hashCode() + "]";
        }
    }
    public static void main(String[] args) throws Exception {

        Node n1 = new Node();
        n1.info = "A";
        Node n2 = new Node();
        n2.info = "B";
        Node n3 = new Node();
        n3.info = "C";
        Node n4 = new Node();
        n4.info = "D";
        Node n5 = new Node();
        n5.info = "E";
        Node n6 = new Node();
        n6.info = "F";
        Node n7 = new Node();
        n7.info = "G";
        Node n8 = new Node();
        n8.info = "H";

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = n7;
        n7.next = n8;
        n8.next = n2;

        detectLoop(n1);
    }
    public static boolean detectLoop(Node start) throws Exception {
        Node slow = start;
        Node fast = start;
        while (slow !=null && fast != null) {
            slow=slow.next;
            fast=fast.next.next;
            if (fast == slow) {
                int k = getLengthOfLoop(fast);
                Node startOfLoopNode = detectLoopStart(start, k);
                System.out.println("Length of the loop is " + k);
                System.out.println("Start of the loop is " + startOfLoopNode);
                return true;
            }
        }
        return false;
    }
    private static int getLengthOfLoop(Node loopNode) throws Exception {
        Node ptr = loopNode;
        int k=0;
        while ((ptr=ptr.next)!=loopNode) {
            k++;
        }
        return k+1;
    }
    private static Node detectLoopStart(Node start, int k) throws Exception {
        Node ptr1 = start;
        Node ptr2 = start;
        while (k-->0 && (ptr1 = ptr1.next)!=null);
        while ((ptr1=ptr1.next)!=null && (ptr2=ptr2.next)!=null && ptr1 != ptr2);
        return ptr1;
    }
}

Getting the sum of all multiples of 3 and 5 before a number n

Hello all, today we are going to look on to a problem that says the total of all the multiples of 3 and 5 before a number n.

Note: Before n

So  if I say take the sum of all numbers before 10 which are the multiples of 3 and 5 then the answer would be: 3,5,6,9 and the answer would be 23 (3+5+6+9).

Before going to the implementation lets go back and make some points:
  1. The multiples of 3 and to make a sum of them would be:
    • 3 + 6 + 9 + 12 + 15 ...... which cuts down to : 3 * (1 + 2 + 3 + 4 + 5 ......). Now if you look at this series it is an Arithmetic Progression or you can say that it is the sum of n natural numbers, multiplied by 3.
    • Now the second part which is quite important to notice is that if I say that you have to add all the multiples of  3 before 10 (excluding 10) then then total numbers to be added is 3 * (1 + 2 + 3), which means that the n-1(since we don't have to include n)(for us ,10-1, 9) is divided by 3 and then we consider it to be the part where we can say that apply the formula of addition of first n natural numbers multiplied by 3.
    • So in total the formula would be 3 * (sum of first (n-1)/3 natural numbers), this part is a bit tricky so please give more attention to it.
  2. Same will be the case of numbers divisible by 5 as well.
  3. One more important thing is that if the n is 16 and we have to add all the multiples of 3 and 5 together then the answer would be:
    (3 + 6 + 9 + 12 +15) + (5 + 10 + 15)
    if you notice the expression the digit 15 is added twice since, 3 & 5 both are the multiples of 15 and so added twice.
  4. Now in order to do correct solution we have to remove the digits those are the multiple of 15(i.e 3*5)
  5. So the case would be like this:
        3 * (sum of first (n-1)/3 natural numbers)
    5 * (sum of first (n-1)/5 natural numbers)
    15 * (sum of first (n-1)/15 natural numbers)
Now lets prepare the code :


public class Solution {
    public static Scanner ins = new Scanner(System.in);
    public static sumOfNNaturalNumbers(int n) {
        return (n*(n+1)/2);
    }
    public static int readInt() {
        int result = ins.nextInt();
        ins.nextLine();
        return result;
    }
    public static int readString() {
        return ins.readLine();
    }
    public static void main(String[] args) {
        int n = readInt();
        int answer = 3 * (n-1)/3 + 5 * (n-1)/5 - 15 * (n-1)/15;
        System.out.println(answer);
    }
}

Friday, July 24, 2015

Getting different objects from Jackson

Hello All, today I want to explain you a special case when we want to get different objects from Jackson Library.

What is Jackson API and how it works?
     It is a standard JSON library for Java (or JVM platform in general), or, as the "best JSON parser for Java". Or simply as "JSON for Java". It is very useful and flexiblt in nature. It takes JSON string in to consideration and changes it to Java object or vice versa.

What is a JSON string?
    JSON is a special format of representing the data in a string format, you can think it as a refined version of XML.

Eg:
    In XML:
        <user>
            <author>Ankur</author>
            <name>Codepool</name>
         </user>
    In JSON:
        user:{
                "author" : "Ankur",
                "name" : "Codepool",
        }
     

Now before going further lets us take a basic example of how Jackson works to and forth?

User.java
public class User {
    private String name;
    private String author;

    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public String getAuthor() {
        return author;
    }
    public void setAuthor(String author) {
        this.author = author;
    }
    @Override
    public String toString() {
        return "User [name=" + name + ", author=" + author + "]";
    }
}

ExampleJackson.java
public class ExampleJackson {
    public static void main(String[] args) throws Exception {
        User user = new User();
            user.setName("Ankur");
            user.setAuthor("Codepool");

        //Writing a Java object as a Json String
        ObjectMapper objectMapper = new ObjectMapper();
        System.out.println(objectMapper.writeValueAsString(user));
        //Output: {"name":"Ankur","author":"Codepool"}

        //Now reading from Json string to Java object
        String jsonString = "{\"name\":\"NewAnkur\", \"author\":\"NewAuthor\" }";
        User newUser = objectMapper.readValue(jsonString, User.class);
        System.out.println(newUser);
        //Output: User [name=NewAnkur, author=NewAuthor]
    }
}

Now let us take a case, where we want to get the object on the basis of data inside the JSON string, that means if the name value is Ankur, I want AnkurUser object and if name value is John, we want the JohnUser object.

For this type of functionality we have the annotations defined in Jackson library, those are :
  • @JsonTypeInfo
  • @JsonSubTypes
  • @JsonSubTypes.Type
Now lets edit the User class in a way like this:

User.java
@JsonTypeInfo(
    use = JsonTypeInfo.Id.NAME,
    include = JsonTypeInfo.As.PROPERTY,
    property = "name", // (A)
    visible = true  // (B)
)
@JsonSubTypes( {
    @JsonSubTypes.Type(name = "ankur", value = AnkurUser.class), //(C)
    @JsonSubTypes.Type(name = "john", value = JohnUser.class)  //(D)
})
abstract class User {
    private String name;
    private String author;
    protected abstract void show();

    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public String getAuthor() {
        return author;
    }
    public void setAuthor(String author) {
        this.author = author;
    }
    @Override
    public String toString() {
        return "User [name=" + name + ", author=" + author + "]";
    }
}

AnkurUser.java
class AnkurUser extends User{

 public AnkurUser(){
   System.out.println("Ankur Created");
  }
  @Override
 protected void show() {
  System.out.println("This is ankur user");
 }

 @Override
  public String toString() {
   return "AnkurUser [name=" + super.getName() + ", author=" + super.getAuthor() + "]";
  }
}

JohnUser.java
class JohnUser extends User {
    public AnkurUser() {
        System.out.println("Ankur Created");
    }
    @Override protected void show() {
        System.out.println("This is john user");
    }
    @Override
    public String toString() {
        return "JohnUser [name=" + super.getName() + ", author=" + super.getAuthor() + "]";
    }
}
Now lets see the usage and output:

ExampleJackson .java
public class ExampleJackson {
    public static void main(String[] args) throws Exception {
        ObjectMapper objectMapper = new ObjectMapper();

        //Now reading from Json string to Java object
        String jsonString = "{\"name\":\"ankur\", \"author\":\"NewAuthor\" }";
        User newUser = objectMapper.readValue(jsonString, User.class);
        newUser.show();
        /*
        * Output: (E)
        *  Ankur Created
        *  This is ankur user
        */
    }
}

If you notice the equation (C) tells you that the object that is created, is of AnkurUser class and returns you the same, this transition is because of the annotation configuration that we did at the creation of the User class, which says check for the property named name (equation (A)), and if its value is Ankur  create the AnkurUser object and so on, at equation (C) and (D). The equation (B) states that the field is also going to be visible for further calls  normally the field that is used as a deciding factor of the object, is never visible for further manipulations.

Thanks

Wednesday, July 15, 2015

Zookeper Installation

Hello friends let us look at the basic installation of the Zookeeper


  1. First download the package from Zookeeper site(link here)
  2. Extract the package anywhere.
  3. tar zxvf zookeeper-3.4.6.tar.gz
  4. cd zookeeper-3.4.6/conf/ 
  5. We are assuming that the data folder is /etc/analytics/data and is present.
  6. tickTime=2000
    dataDir=/etc/analytics/data
    clientPort=2181
    initLimit=5
    syncLimit=2
    server.1=<ip:1>:<start_port>:<end_port>
    #have to specifly all the servers with id (server.<id>) format
  7. Now the id of the current machine is decided by the text file content specified at /etc/analytics/data.  Name of that file is myid with content 1, that's it
  8. Now start the zookeeper process.
  9. To start the server use the following
    - bin/zkServer.sh start
  10. To start the client in order to check the things gone perfectly or not use this:
    - bin/zkCli.sh -server <ip>:2181
  11. To check the installation to be correct or not
  12. Connect to any of the zookeeper client
    [zkshell: 9] create /zk_test my_data
    Created /zk_test
  13. And check whether it is being created in other nodes or not :
    [zkshell: 12] get /zk_testmy_datacZxid = 5ctime = Fri Jun 05 13:57:06 PDT 2009mZxid = 5mtime = Fri Jun 05 13:57:06 PDT 2009pZxid = 5cversion = 0dataVersion = 0aclVersion = 0ephemeralOwner = 0dataLength = 7numChildren = 0
  14. If this is the output then  installation is perfect
Thanks

Gradle installation

Hello friends let us look at the installation of Gradle.

For this tutorial I am just explaining in Windows machine, but the steps are pretty much same for Linux as well.
  1. Download the package from Gradle website (link here)
  2. Then extract it to any folder.
  3. Have to  add the Gradle bin folder in to the Path variable of the environment
  4. For that follow my other post here.
  5. Make a variable name GRADLE_HOME and give its value as the base folder of the extracted package
  6. Then add the %GRADLE_HOME%/bin in to the path variable.
  7. Open a shell and type gradle -v  and if everything is correct it will show you something like this:
Thanks

Installing maven in Windows

Hello friends lets take a look at how to install maven in Windows.

  1. Download the Maven from the Maven website (link)
  2. Extract it to any folder, lets say E:/Maven
  3. It will get extracted as:
  4. Now after this you have to add 1 environment variables named MVN_HOME and attach %MVN_HOME%/bin in the PATH variable.(follow this)
  5. If everything goes well, on opening a new command window and typing mvn --version will return you something like this

Thanks

Checking a number as it is Fibonacci number or not

Hello Friends, today I want to give you a basic information that is very useful in letting know whether the number is a fibonacci number just by simple formula.

Here it goes,

Let us suppose we have to check whether the number n is a fibonacci number or not, then the condition 5n^2 + 4 or 5n^2 - 4 should be a perfect square.

 // A utility function that returns true if x is perfect square  
 bool isPerfectSquare(int x)  
 {  
   int s = sqrt(x);  
   return (s*s == x);  
 }  
 // Returns true if n is a Fibinacci Number, else false  
 bool isFibonacci(int n)  
 {  
   // n is Fibinacci if one of 5*n*n + 4 or 5*n*n - 4 or both  
   // is a perferct square  
   return isPerfectSquare(5*n*n + 4) ||  
       isPerfectSquare(5*n*n - 4);  
 }  
 int main()  
 {  
  for (int i = 1; i <= 10; i++)  
    isFibonacci(i)? cout << i << " is a Fibonacci Number \n":  
            cout << i << " is a not Fibonacci Number \n" ;  
  return 0;  
 }  

Now once you pass the number to the function it will tell you whether or not the number is a part of fibonacci series or not.

Thanks