GCD Greatest Common Divisor

package com.test;

import java.util.Scanner;

public class GCDExample {
 
 
    public static void main(String args[]){
     
        //Enter two number whose GCD needs to be calculated.      
        Scanner scanner = new Scanner(System.in);
        System.out.println("Please enter first number to find GCD");
        int number1 = scanner.nextInt();
        System.out.println("Please enter second number to find GCD");
        int number2 = scanner.nextInt();
      
        System.out.println("GCD of two numbers " + number1 +" and " 
                           + number2 +" is :" + findGCD(number1,number2));
      
      
    }

    /*
     * Java method to find GCD of two number using Euclid's method
     * @return GDC of two numbers in Java
     */
    private static int findGCD(int number1, int number2) {
        //base case
        if(number2 == 0){
            return number1;
        }
        return findGCD(number2, number1%number2);
    }
  
}

Check Duplicates in Java Array

package com.test;

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

public class CheckAllDuplicatesInJavaArray {

    public static void main(String args[])  {
       
       String[] withDuplicates = new String[] {"one","two","three","one"};
        String[] withoutDuplicates = new String[] {"one","two","three"};
      
        System.out.println("Checking array with duplicate using brute force: " + bruteforce(withDuplicates));
        System.out.println("Checking array without any duplicate using brute force: " + bruteforce(withoutDuplicates));
      
        System.out.println("Checking array with duplicate using Set and List: " + checkDuplicateUsingSet(withDuplicates));
        System.out.println("Checking array without any duplicate using Set and List: " + checkDuplicateUsingSet(withoutDuplicates));

      
        System.out.println("Checking array with duplicate using Set and List: " + checkDuplicateUsingAdd(withDuplicates));
        System.out.println("Checking array without any duplicate using Set and List: " + checkDuplicateUsingAdd(withoutDuplicates));

      
    }
  
    /*
     * brute force way of checking if array contains duplicates in Java
     * comparing each elements to all other elements of array
     * complexity on order of O(n^2) not advised in production
     */
    public static boolean bruteforce(String[] input) {
        for (int i = 0; i < input.length; i++) {
            for (int j = 0; j < input.length; j++) {
                if (input[i].equals(input[j]) && i != j) {
                    return true;
                }
            }
        }
        return false;
    }
    /*
     * detect duplicate in array by comparing size of List and Set
     * since Set doesn't contain duplicate, size must be less for an array which contains duplicates
     */
    public static boolean checkDuplicateUsingSet(String[] input){
        List inputList = Arrays.asList(input);
        Set inputSet = new HashSet(inputList);
        if(inputSet.size()< inputList.size()) {
            return true;
        }
        return false;
    }
  
    /*
     * Since Set doesn't allow duplicates add() return false
     * if we try to add duplicates into Set and this property
     * can be used to check if array contains duplicates in Java
     */
    public static boolean checkDuplicateUsingAdd(String[] input) {
        Set tempSet = new HashSet();
        for (String str : input) {
            if (!tempSet.add(str)) {
                return true;
            }
        }
        return false;
    }
}

Java program to find middle element of linked list in one pass.

 Java program to find middle element of linked list in one pass. 

How do you find middle element of LinkedList in one pass is a programming question often asked to Java and non Java programmers in telephonic Interview. This question is similar to checking palindrome or calculating factorial, where Interviewer some time also ask to write code. In order to answer this question candidate must be familiar with LinkedList data structure i.e. In case of singly LinkedList, each node of Linked List contains data and pointer, which is address of next Linked List and last element of Singly Linked List points towards null. Since in order to find middle element of Linked List you need to find length of LinkedList, which is counting elements till end i.e. until you find the last element on Linked List. What makes this data structure Interview question interesting is that you need to find middle element of LinkedList in one pass and you don’t know length of LinkedList. This is where candidates logical ability puts into test,  whether he is familiar with space and time trade off or not etc. As if you think carefully you can solve this problem by using two pointers as mentioned in my last post on How to find length of Singly Linked List in Java. By using two pointers, incrementing one at each iteration and other at every second iteration. When first pointer will point at end of Linked List, second pointer will be pointing at middle node of Linked List.  In fact this two pointer approach can solve multiple similar problems e.g. How to find 3rd element from last in a Linked List in one Iteration or How to find nth element from last in a Linked List. In this Java programming tutorial we will see a Java program which finds middle element of Linked List in one Iteration.


package com.test;

/**
 * Java program to find middle element of linked list in one pass. In order to
 * find middle element of linked list we need to find length first but since we
 * can only traverse linked list one time, we will use two pointers one which we
 * will increment on each iteration while other which will be incremented every
 * second iteration. so when first pointer will point to the end of linked list,
 * second will be pointing to the middle element of linked list
 * 
 * @author captain
 */
public class LinkedListTest {

public static void main(String args[]) {
// creating LinkedList with 5 elements including head
LinkedList linkedList = new LinkedList();
LinkedList.Node head = linkedList.head();
linkedList.add(new LinkedList.Node("1"));
linkedList.add(new LinkedList.Node("2"));
linkedList.add(new LinkedList.Node("3"));
linkedList.add(new LinkedList.Node("4"));

// finding middle element of LinkedList in single pass
LinkedList.Node current = head;
int length = 0;
LinkedList.Node middle = head;

while (current.next() != null) {
length++;
if (length % 2 == 0) {
middle = middle.next();
}
current = current.next();
}

if (length % 2 == 1) {
middle = middle.next();
}

System.out.println("length of LinkedList: " + length);
System.out.println("middle element of LinkedList : " + middle);

}

}

class LinkedList {
private Node head;
private Node tail;

public LinkedList() {
this.head = new Node("head");
tail = head;
}

public Node head() {
return head;
}

public void add(Node node) {
tail.next = node;
tail = node;
}

public static class Node {
private Node next;
private String data;

public Node(String data) {
this.data = data;
}

public String data() {
return data;
}

public void setData(String data) {
this.data = data;
}

public Node next() {
return next;
}

public void setNext(Node next) {
this.next = next;
}

public String toString() {
return this.data;
}
}
}

Reverse A linked List - Recursive & Iterative

Iterative:

1. The head node’s next pointer should be set to NULL since the head will become the tail. This is an exception for the head node, and can be done outside the while loop. But, before we do this we will need a temp variable to point to the 2nd node (the node after the head node), because the only way to reference the 2nd node is through the head node’s next pointer.
2. The 2nd node (the node after the head node) should have it’s own next pointer changed to point to the head node. This will reverse the order of the nodes. But, remember that the 2nd node’s next pointer will at first be pointing to the 3rd node. This means that before we change the 2nd node’s next pointer, we have to save a reference to the 3rd node otherwise we will have no way of referencing the 3rd node. So, we simply store a reference to the 3rd node in a variable before we change the 2nd node’s next pointer.
3. The 3rd node then becomes the “first” node in the while loop and we repeat the process of changing pointers described in step 2.
4. Continue step 3 until we come across a node that has a next pointer set to NULL. When we do come across a NULL next pointer we just set the head node to point to the node that has the NULL next pointer. This node was previously the tail node, but is now the head node because we are reversing the linked list.

public reverseListIteratively(Node head) {
if (head == NULL || head.next == NULL)
return; // empty or just one node in list
Node Second = head.next;
// store third node before we change
Node Third = Second.next;
// Second's next pointer
Second.next = head; // second now points to head
head.next = NULL; // change head pointer to NULL
// only two nodes, which we already reversed
if (Third == NULL)
return;
Node CurrentNode = Third;
Node PreviousNode = Second;
while (CurrentNode != NULL) {
Node NextNode = CurrentNode.next;
CurrentNode.next = PreviousNode;

/*
* repeat the process, but have to reset the PreviousNode and
* CurrentNode
*/
PreviousNode = CurrentNode;
CurrentNode = NextNode;
}

head = PreviousNode; // reset the head node
}

Recursive:

public void recursiveReverse(Node currentNode) {

// check for empty list

if (currentNode == NULL)

return;

/*

* if we are at the TAIL node: recursive base case:

*/

if (currentNode.next == NULL) {

// set HEAD to current TAIL since we are reversing list

head = currentNode;

return; // since this is the base case

}

recursiveReverse(currentNode.next);

currentNode.next.next = currentNode;

currentNode.next = null; // set "old" next pointer to NULL

}

Algorithms & Data Structures IQ

Data structures and algorithm questions are important part of any programming job interview, be it a Java interview, C++ interview or any other programming language. Since data structures is core programming concept, its mandatory for all programmers, to know basic data structures like stack, linked list, queue, array, tree and graph. Though tree and graph are on tough side, I still see programmers to get familiar will all these. Any list of programming job interview questions is incomplete without questions from data structures and algorithms. Similarly while going on questions from data structure you may get some programming exercise as well e.g. swapping numbers without temp variable .

Linked list and arrays are favorite topics in any data structure interview, questions like reversing linked list, traversing linked list or deleting nodes from linked list, which involves algorithm and data structures are quite common. 
Similarly, finding duplicates in array, finding missing numbers, sorting arrays are very popular. 

You can also expect questions from stack, queue, array, linked list, tree, graph and HashMap are most common in any data structure interview. 

Ques 01 : How to find middle element of linked list in one pass?

Ques 02 : How to find if linked list has loop ?
Ans  02 : This question has bit of similarity with earlier algorithm and data structure interview question. I mean we can use two pointer approach to solve this problem. If we maintain two pointers, and we increment one pointer after processing two nodes and other after processing every node, we are likely to find a situation where both the pointers will be pointing to same node. This will only happen if linked list has loop.

Ques 03 : How to find 3rd element from end in a linked list in one pass?
Ans  03 : This is another frequently asked linked list interview question. This question is exactly similar to finding middle element of linked list in single pass. If we apply same trick of maintaining two pointers and increment other pointer, when first has moved upto 3rd element, than when first pointer reaches to the end of linked list, second pointer will be pointing to the 3rd element from last in a linked list.

Ques 04 : In an integer array, there is 1 to 100 number, out of one is duplicate, how to find ?
Ans  04 : This is a rather simple data structures question, especially for this kind of. In this case you can simply add all numbers stored in array, and total sum should be equal to n(n+1)/2. Now just subtract actual sum to expected sum, and that is your duplicate number. Of course there is a brute force way of checking each number against all other numbers, but that will result in performance of O(n^2) which is not good. By the way this trick will not work if array have multiple duplicates or its not numbers forming arithmetic progression. Here is example of one way to find duplicate number in array.

Ques 05 : What is difference between Stack and Queue data structure ?
Ans  05 : One of the classical datastrucutre interview question. I guess every one know, No? Any way main difference is that Stack is LIFO(Last In First Out) data structure while Queue is a FIFO(First In First Out) data structure.

Ques 06 : How do you find duplicates in array if there is more than one duplicate?
Ans  06 : Sometime this is asked as follow-up question of earlier datastrucutre interview question, related to finding duplicates in Array. One way of solving this problem is using a Hashtable or HashMap data structure. You can traverse through array, and store each number as key and number of occurrence as value. At the end of traversal you can find all duplicate numbers, for which occurrence is more than one. In Java if a number already exists in HashMap then calling get(index) will return number otherwise it return null. this property can be used to insert or update numbers in HashMap.

Ques 07 : What is difference between Singly Linked List and Doubly Linked List data structure?
Ans  07 : This is another classical interview question on data structure, mostly asked on telephonic rounds. Main difference between singly linked list and doubly linked list is ability to traverse. In a single linked list, node only points towards next node, and there is no pointer to previous node, which means you can not traverse back on a singly linked list. On the other hand doubly linked list maintains two pointers, towards next and previous node, which allows you to navigate in both direction in any linked list.

Ques 08 : Write Java program to check if a number is palindrome or not?
Ans   08 : division operator can be used to get rid of last digit e.g. 1234/10 will give you 123, and modulus operator can give you last digit e.g. 1234%10 will return 4.

Ques 09 : What is binary search tree?
Ans  09 : This is a data structure question from Tree data structures. Binary Search Tree has some special properties e.g. left nodes contains items whose value is less than root , right sub tree contains keys with higher node value than root, and there should not be any duplicates in the tree. Apart from definition, interview can ask you to implement binary search tree in Java and questions on tree traversal e.g. IN order, pre-order, and post order traversals are quite popular data structure question.

Ques 10 : Write a Java program to implement Stack in Java? 
Ans   10: You can implement Stack by using array or linked list. This question expect you to implement standard method provided by stack data structure e.g. push() and pop().  Both push() and pop() should be happen at top of stack, which you need to keep track. It’s also good if you can implement utility methods like contains(), isEmpty() etc. By the way JDK has java.util.Stack class and you can check it’s code to get an idea.

Ques 11: Priority Queue ?

Ques 12: Sorting Algorithms ?

Ques 13: Complexity / Algorithms ?

Ques 14: "Transpose A Matrix", "Swap Number", "Reverse Number", "Print Alphabets", "Linear Search", "System Commands", "Prime Number", "Palindrome", "Largest Number", "Floyd Triangle", "Factorial", "Calculator", "Bubble Sort", "Binary Search", "Armstrong Number", "Add Matrix", "GCD (Greatest Common Divisor)", "Fibonacci", Reverse a linked list (recursive & iterative). 

LINUX - File Permissions (chmod)

Linux has inherited from UNIX the concept of ownerships and permissions for files. This is basically because it was conceived as a networked system where different people would be using a variety of programs, files, etc. Obviously, there's a need to keep things organized and secure. The big advantage that Linux has is its multi-user concept- the fact that many different people can use the same computer or that one person can use the same computer to do different jobs. That's where the system of file permissions comes in to help out in what could be a very confusing situation.

File permission symbols 

If we run following command:
$ ls -l [in your home directory, you will get a list of files that may include something like this]
$ -rw-r--r--  1  bob  users  1892  Jul 10  18:30 linux_course_notes.txt

This basically says, interpreting this from RIGHT to LEFT that the file, linux_course_notes.txt was created at 6:30 PM on July 10 and is 1892 bytes large. It belongs to the group users (i.e, the people who use this computer). It belongs to bob in particular and it is one (1) file. Then come the file permission symbols.

Let's look at what these symbols mean:
The dashes - separate the permissions into three types

1. The first part refers to the owner's (bob's) permissions: The dash - before the rw means that this is a normal file that contains any type of data. A directory, for example, would have a d instead of a dash. The rw that follows means that bob can read and write to (modify) his own file.
2. The second part of the these symbols after the second dash, are the permissions for the group.
3. After the two dashes (two here because there is no write permissions for the group) come the overall user permissions. Anyone who might have access to the computer from inside or outside (in the case of a network) can read this file.

Let's take a look at some other examples. An interesting place to look at different kinds of file permissions is the /bin directory. Here we have the commands that anybody can use on the Linux system. Let's look at the command for gzip, a file compression utility for Linux.
$ -rwxr-xr-x  1 root    root        53468 May  1  1999 gzip

As we see here, there are some differences: The program name, date, bytes are all standard. Even though this is obviously different information, the idea is the same as before.

The changes are in the owner and group. Root owns the file and it is in the group "root". Root is actually the only member of that group. The file is an executable (program) so that's why the letter x is among the symbols. This file can be executed by everybody: the owner (root), the group (root) and all others that have access to the computer, file is a program, so there is no need for anybody other than root to "write" to the file, so there is no w permissions for it for anybody but root.

If we look at a file in /sbin which are files that only root can use or execute, the permissions would look like this:
$-rwxr--r--  1 root    root        1065 Jan 14  1999 cron

'cron' is a program on Linux systems that allows programs to be run automatically at certain times and under certain conditions. As we can see here, only root, the owner of the file, is allowed to use this program. There are no xpermissions for the rest of the users.

We hope you enjoyed this little walk-through of file permissions in Linux. Now that we know what we're looking for, we can talk about changing certain permissions.

chmod

chmod is a Linux command that will let you "set permissions" (aka, assign who can read/write/execute) on a file. [chmod permissions file] or [chmod permission1_permission2_permission3 file]

When using chmod, you need to be aware that there are three types of Linux users that you are setting permissions for. Therefore, when setting permissions, you are assigning them for "yourself", "your group" and "everyone else" in the world. These users are technically know as:

1. Owner
2. Group
3. World

Therefore, when setting permissions on a file, you will want to assign all three levels of permissions, and not just one user. Think of the chmod command actually having the following syntax...
$ chmod owner group world FileName

Now that you understand that you are setting permissions for THREE user levels, you just have to wrap your head around what permissions you are able to set!. There are three types of permissions that Linux allows for each file. ie READ, WRITE, EXECUTE. Putting it all together:

So, in laymen terms, if you wanted a file to be readable by everyone, and writable by only you, you would write the chmod command with the following structure.
COMMAND : OWNER : GROUP : WORLD : PATH

chmod read & write read read FileName [$ chmod 644 myDoc.txt]
Wait! What are those numbers?!? Computers like numbers, not words. Sorry. You will have to deal with it. Take a look at the following output of `ls -l`
$ -rw-r--r-- 1 gcawood iqnection 382 Dec 19 6:49 myDoc.txt

You will need to convert the word read or write or execute into the numeric equivalent (octal) based on the table below.
4 - read (r)
2 - write (w)
1 - execute (x)

Practical Examples
chmod 400 mydoc.txt read by owner
chmod 040 mydoc.txt read by group
chmod 004 mydoc.txt read by anybody (other)
chmod 200 mydoc.txt write by owner
chmod 020 mydoc.txt write by group
chmod 002 mydoc.txt write by anybody
chmod 100 mydoc.txt execute by owner
chmod 010 mydoc.txt execute by group
chmod 001 mydoc.txt execute by anybody


Wait! I don't get it... there aren't enough permissions to do what I want!. Good call. You need to add up the numbers to get other types of permissions...So, try wrapping your head around this!!
7 = 4+2+1 (read/write/execute)
6 = 4+2 (read/write)
5 = 4+1 (read/execute)
4 = 4 (read)
3 = 2+1 (write/execute)
2 = 2 (write)
1 = 1 (execute)

chmod 666 mydoc.txt read/write by anybody! (the devil loves this one!)
chmod 755 mydoc.txt rwx for owner, rx for group and rx for the world
chmod 777 mydoc.txt read, write, execute for all! (may not be the best plan in the world...)

[dixit@cmpint-dt-4i ~]$ ls -latr
total 60
-rw-r--r--  1 dixit dixit   124 Feb 15 00:38 .bashrc
-rw-r--r--  1 dixit dixit   176 Feb 15 00:38 .bash_profile
-rw-r--r--  1 dixit dixit    33 Feb 15 00:38 .bash_logout
drwx------  2 dixit dixit  4096 Feb 15 05:07 .ssh
-rw-------  1 dixit dixit 12920 Feb 16 05:37 .viminfo
lrwxrwxrwx  1 dixit dixit     9 Feb 20 20:19 .bash_history -> /dev/null
drwxr-x---  6 dixit dixit  4096 Feb 20 20:19 .

2nd column is --> Number of links (2,9)
3rd Column is --> File/directory owner (root)
4th Column is --> File/directory group (root)

Good luck! Hope this helps.

Fibonacci Series

Fibonacci series is series of natural number where next number is equivalent to sum of previous two number e.g. fn = fn-1 + fn-2. First two numbers of Fibonacci series is always 1, 1. In this Java program example for Fibonacci series we create function to calculate Fibonacci number and then print those numbers on Java console. Another twist in this questions is that some time interviewer ask to write Java program for Fibonacci numbers using recursion, so its better you prepare for both iterative and recursive version of Fibonacci number.

package com.test;

import java.util.Scanner;

/**
 * Java program to calculate and print Fibonacci number using both recursion and Iteration.
 * Fibonacci number is sum of previous two Fibonacci numbers fn= fn-1+ fn-2
 * first 10 Fibonacci numbers are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
 * @author
 */
public class Test2 {

    public static void main(String args[]) {
    
       //input to print Fibonacci series upto how many numbers
        System.out.println("Enter number upto which Fibonacci series to print: ");
        int number = new Scanner(System.in).nextInt();
      
        System.out.println("Fibonacci series upto " + number +" numbers : ");
        //printing Fibonacci series upto number
        for(int i=1; i<=number; i++){
            System.out.print(fibonacci2(i) +" ");
        }
    } 
  
    /*
     * Java program for Fibonacci number using recursion.
     * This program uses tail recursion to calculate Fibonacci number for a given number
     * @return Fibonacci number
     */
    public static int fibonacci(int number){
        if(number == 1 || number == 2){
            return 1;
        }
        return fibonacci(number-1) + fibonacci(number -2); //tail recursion
    }
  
    /*
     * Java program to calculate Fibonacci number using loop or Iteration.
     * @return Fibonacci number
     */
    public static int fibonacci2(int number){
        if(number == 1 || number == 2){
            return 1;
        }
        int fibo1=1, fibo2=1, fibonacci=1;
        for(int i= 3; i<= number; i++){
            fibonacci = fibo1 + fibo2; //Fibonacci number is sum of previous two Fibonacci number
            fibo1 = fibo2;
            fibo2 = fibonacci;
        }
        return fibonacci; //Fibonacci number
    }  
}

After asking to write simple Java program to print Fibonacci series and later asking for Fibonacci series using recursion, another important question interviewer ask is how do you improve your Fibonacci function both iterative and recursive one? A technique called memorization can be used to drastically improve performance of method which calculates Fibonacci number. if you look at the method it repetitive creates same Fibonacci number e.g. In order to calculate 10th Fibonacci number function first create first 9 Fibonacci number, this could be very time consuming if you just increase the upper limit from 10 to 10K. In memorization programming technique result of earlier calculation is cached and reused. So you don't need to create same Fibonacci number if you already have calculated it. You can write code for Fibonacci series with memorization by just using a HashMap  and checking if Fibonacci number for a corresponding number is already exits or not and calculate only if it doesn't exist.

    /*
     * Java Program to calculate Fibonacci numbers with memorization
     * This is quite fast as compared to previous Fibonacci function especially for
     * calculating factorial of large numbers.
     */
    public static int improvedFibo(int number){
        Integer fibonacci = cache.get(number);
        if(fibonacci != null){
            return fibonacci; //fibonacci number from cache
        }
        fibonacci = fibonacci2(number); //fibonacci number not in cache, calculating it
        cache.put(number, fibonacci); //putting fibonacci number in cache for future request
        return fibonacci;
    }

Comparison
        //comparison of performance of Fibonacci number with memorization
        int number = 100000000;
        long startTime = System.nanoTime();
        int result = fibonacci2(number); //fibonacci number with memorization
        long elapsedTime = System.nanoTime() - startTime;
        System.out.println("Time taken to calculate Fibonacci number upto 100M without memorization:" + elapsedTime);
      
        startTime = System.nanoTime();
        result = improvedFibo(number); //Fibonacci number with memorization
        elapsedTime = System.nanoTime() - startTime;

        System.out.println("Time taken to calculate Fibonacci number upto 100M with memorization:" + elapsedTime);

Interesting point is that improved method only shows better performance for large numbers like 100M otherwise iterative version of Fibonacci method is faster. That could be explained by extra work done by improved method in terms of storing value in cache and getting it from there.