Data Structures and Algorithm Interview Questions for Java Developers

How 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 (currect_pointer) will point to the end of linked list, second (middle_pointer) will be pointing to the middle element of linked list.

If the list the length is odd or even, if its odd then middle_pointer=middle_pointer+1;
e.g: suppose, if length =6, then after traversing, current=6 and middle_pointer=3.
if length =5, then after traversing, current=5 and middle_pointer=2. As the length is odd, we need to increment the middle_pointer, hence the 3rd element is the middle one.

How to find nth element from end of linked list?
Maintain two pointers-reference pointer and main pointer. Initialize both reference and main pointers to head. First move reference pointer to n nodes from head. Now move both pointers one by one until reference pointer reaches end. Now main pointer will point to nth node from the end. Return main pointer.

public static void main(String args[]) {
        LinkedList < String >  empNames=new LinkedList < String > ();
        empNames.add("Mario");
        empNames.add("Stephan");
        empNames.add("Andreas");
        empNames.add("Michael");
        empNames.add("Marino");
        empNames.add("Thomas");
        empNames.add("Himaanshu");
     
        /*
         * elementIndex is the index of element which need to be searched from the end.
         * Here we are finding 3rd employee from the end, which is Marino.*/
        int elementIndex=3;
     
        /*Initialize both reference and main pointers to head*/
        int refPointer=1, mainPointer=1;
        ListIterator < String >  itr=empNames.listIterator();
        while(itr.hasNext())
        {
            itr.next();
            if(refPointer<=elementIndex)
            {
                refPointer=refPointer+1;
            }
            else
            {
                refPointer=refPointer+1;
                mainPointer=mainPointer+1;
            }
        }
        System.out.println("3rd employee from the end is : "+empNames.get(mainPointer-1));
    }

How to find if linked list has a loop?
1). Traverse through each node till end , tracking visited node using visited flag. If you find node that is already visited, then there is a loop in LinkedList and if you reach till end while traversing then there is no loop in LinkedList. But problem with above approach is, in most cases you can not change data structure of LinkedList node, so you won’t be able to add visited flag to it.
2). 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.

Write a program to check if LinkedList is palindrome or not?
Steps:
1). Create Stack, traverse the LinkedList and add the values in Stack.
2). Again traverse the LinkedList, ompare the current value with the value which is optained from Stack.pop().
public static void main(String[] args) {
        LinkedList linkList=new LinkedList();
        linkList.add("m");
        linkList.add("a");
        linkList.add("d");
        linkList.add("a");
        linkList.add("m");
        Stack stack=new Stack();
        Iterator iterator=linkList.iterator();
        while(iterator.hasNext())
        {
            stack.add(iterator.next());
        }
      
        String tempStack, tempLinkVal;
        iterator=linkList.iterator();
        Boolean ispalindrome=true;
        while(iterator.hasNext())
        {
            tempStack=stack.pop();
            tempLinkVal=iterator.next();
            if(!(tempStack!=null && tempStack.equals(tempLinkVal)))
            {
                ispalindrome=false;
                break;
            }
        }
        System.out.println("ispalindrome="+ispalindrome);
    }

How to check or detect duplicate elements in Array in Java
By using brute force method which compares each element of Array to all other elements and returns true if it founds duplicates. Though this is not an efficient choice it is the one which first comes to mind.


Another quick way of checking if a Java array contains duplicates or not is to convert that array into Set. Since Set doesn’t allow duplicates size of the corresponding Set will be smaller than original Array if Array contains duplicates, else the size of both Array and Set will be same.

public static void main(String args[]) {
        String[] empNames={"Mario", "Stephan", "Andreas", "Himaanshu", "Michael", "Himaanshu"};     
        HashSet < String >  empNamesSet=new HashSet < String > (Arrays.asList(empNames));
        if(empNamesSet.size()        {
            System.out.println("Array has duplicate elements");
        }
        else
        {
            System.out.println("Array don't have duplicate elements");
        }
    }

One more way to detect duplication in java array is adding every element of the array into a Hashtable or HashMap data structure. Traverse through array, and store each number as key and number of occurrence as value. At the end of traversal we 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.

How to reverse a linked list in Java?
1). Three nodes previousNode, currentNode and nextNode will be used. When currentNode is starting node, then previousNode will be null.

Assign currentNode.next to previousNode to reverse the link. In each iteration move currentNode and previousNode by  1 node.
 
public static Node reverseLinkedList(Node currentNode)
{
// For first node, previousNode will be null
Node previousNode=null;
Node nextNode;
while(currentNode!=null)
{
   nextNode=currentNode.next;
   //reversing the link
   currentNode.next=previousNode;
   /moving currentNode and previousNode by 1 node
   previousNode=currentNode;
   currentNode=nextNode;
}
return previousNode;
}
2). By using recursion: Base case for this would be either node is null or node.next is null. For recursive solution, replace reverseLinkedList of above program to below function.

public static Node reverseLinkedList(Node node) {
if (node == null || node.next == null) {
 return node;
}
Node remaining = reverseLinkedList(node.next);
node.next.next = node;
node.next = null;
return remaining;
}
How to reverse String in Java ?
By using StringBuffer reverse() method. But they may ask you to reverse String without using StringBuffer, it can be done using iterative or recursive function (but it may result in StackOverFlowError if String to be reversed is very long String).

//recursive way
public static String reverseRecursively(String inputString) {
    if (inputString == null) {
        return "";
    } else if (inputString.length() < 2) {
        return inputString;
    }
    return reverseRecursively(inputString.substring(1))+ inputString.charAt(0);
}

//iterative way
public static String reverse(String inputString) {
    StringBuilder strBuilder = new StringBuilder();
    char[] strChars = inputString.toCharArray();

    for (int i = strChars.length - 1; i >= 0; i--) {
        strBuilder.append(strChars[i]);
    }
    return strBuilder.toString();
}
 
Write fibonacci series in Java using Recursion.
Fibonacci series is series of natural number where next number is equivalent to the sum of previous two number e.g. fn = fn-1 + fn-2. The first two numbers of Fibonacci series is always 1, 1.

/* Java program for Fibonacci number using recursion*/
public static int fibonacci(int number){
    if(number == 1 || number == 2){
        return 1;
    }
    return fibonacci(number-1) + fibonacci(number -2); //tail recursion
 }
/*Fibonacci number using loop or Iteration*/
public static void fibonacci2(int number) {
    if (number == 1) {
        System.out.println("1");
    } else if (number == 2) {
        System.out.println("1");
        System.out.println("1");
    } else {
        System.out.println("1");
        System.out.println("1");
        int fibo1 = 1, fibo2 = 1, fibonacci = 1;
        for (int i = 3; i <= number; i++) {
            fibonacci = fibo1 + fibo2;
            fibo1 = fibo2;
            fibo2 = fibonacci;
            System.out.println(fibonacci);
        }
    }
} 


How to find first non repeated character in a String in Java?
a). get character array and loop through it to build a hash table with char and their count.
b). loop through LinkedHashMap to find an entry with value 1, that's your first non-repeated character, as LinkedHashMap maintains insertion order.

public static void getFirstNonRepeatedChar(String inputString) {
    Map counts = new LinkedHashMap(
            inputString.length());
    Character repeatedChar = null;
    for (char c : inputString.toCharArray()) {
        counts.put(c, counts.containsKey(c) ? counts.get(c) + 1 : 1);
    }

    for (Entry entry : counts.entrySet()) {
        if (entry.getValue() == 1) {
            repeatedChar = entry.getKey();
        }
    }
    if (repeatedChar != null) {
        System.out.println("First repeated character is " + repeatedChar);
    } else {
        System.out.println("First repeated character not found");
    }
}

How to find factorial of a number using recursion?
private static long factorial(int num){
if(num==1)
    return 1;
else
    return num*factorial(num-1);
}How to find the sum of digits of a number using recursion?
public static int sum(int n){
    return n==0 ? 0 : n%10+sum(n/10);
}
 -K Himaanshu Shuklaa..