Reverse a LinkedList in Java?

Java has a built in functionality to reverse Linked List. This function is available in Collections class and the method name is reverse(). It is a static function so you can simply call it using Collections.reverse(yourLinkedList);

Code :

import java.util.LinkedList;
/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 11/20/13
 * Time: 5:20 PM
 */
public class LinkedListReversal {
    public static void main(String args[]){
        LinkedList<String> myLList = new LinkedList<String>();
        myLList.add("A");
        myLList.add("B");
        myLList.add("C");
        myLList.add("D");
        System.out.println("Original LL : " + myLList);
        Collections.reverse(myLList);
        System.out.println("Revered LL : " + myLList);
    }
}

Output :

Original LL : [A, B, C, D]

Revered LL : [D, C, B, A]

This shows you are aware of Java APIs but ultimately interviewer will get to the logic part as of how this is exactly done. or to put it in other words how is the method Collections.reverse() exactly implemented?

You can view the source code to know the exact method but as far as our LinkedList reversal problem is concerned we do the following -

Code : 

import java.util.LinkedList;
import java.util.ListIterator;
/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 11/20/13
 * Time: 5:20 PM
 */
public class LinkedListReversal {
    public static void reverse(LinkedList<String> linkedList) {
        ListIterator<String> forwardIterator = linkedList.listIterator();
        ListIterator<String> backwardIterator = linkedList.listIterator(linkedList.size());
        for(int i = 1;i<=(linkedList.size()/2);i++){
            String tempString = forwardIterator.next();
            forwardIterator.set(backwardIterator.previous());
            backwardIterator.set(tempString);
        }
    }
    public static void main(String args[]){
        LinkedList<String> myLList = new LinkedList<String>();
        myLList.add("A");
        myLList.add("B");
        myLList.add("C");
        myLList.add("D");
        System.out.println("Original LL : " + myLList);
        LinkedListReversal.reverse(myLList);
        System.out.println("Revered LL : " + myLList);
    }
}

Output : 

Original LL : [A, B, C, D]

Revered LL : [D, C, B, A]


Note : LinkedList data structure in Java is in fact a doubly linked list and hence we could use previous() on the list iterator. If you look at the LinkedList class you will find Node structure as follows

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

If you notice we have both next and prev nodes which implies it is a doubly Linked List.

For java code of reversing a linkedlist from very basics(from creating using Node data structure) you can refer to How to reverse a LinkedList in Java? )

Java Program to print all permutation of a String?

Interviewer may start with a very basic question as to what is number of permutations of a string with n characters. In case repetition is not allowed then it would be n!  i.e  [n*(n-1)*(n-2*....*!)]  . if repetition is allowed it would be n^n i.e [n*n*...n times].

Next would be to code it actually. Generally language is not a concern. What interviewer looks is how candidate thinks(his solving ability) and whether he is able to complete error free and working code. Following is a Java code that will print permutations of a given String along with the number of permutations possible.

Example :

Code : 

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 11/19/13
 * Time: 3:16 PM
 */
public class PermutationsPrinter {
    private int noOfPermutation;
    public void permute(char[] line,int start, int end){
        int j;
        if(start == end){
            noOfPermutation++;
            System.out.println(line);
        }
        else {
            for(j=start;j<=end;j++){
                char[] newLine = getSwappedString(line, start, j);
                permute(newLine,start+1,end);
            }
        }
    }


    private char[] getSwappedString(char[] characters,int i,int j ){
        String newLine = String.valueOf(swap(characters,i,j));//Create New String
        swap(characters,i,j);//restore original String
        return newLine.toCharArray();
    }


    private char[] swap(char[] characters,int i,int j){
        char temp = characters[i];
        characters[i] = characters[j];
        characters[j] = temp;
        return characters;
    }


    public int getNoOfPermutation() {
        return noOfPermutation;
    }


    public static void main(String args[]){
        String line = "ABC";
        PermutationsPrinter permuter = new PermutationsPrinter();
        permuter.permute(line.toCharArray(), 0, line.length() - 1);
        System.out.println("Number Of Permutations made : " + permuter.getNoOfPermutation());
    }
}

Output  : 

ABC

ACB

BAC

BCA

CBA

CAB

Number Of Permutations made : 6

(3! = 6 as expected)

More better example where you don't have to swap again to restore string is provided in the Interview questions git repo -

• Print All String Permuatation

Program to reverse a stack "in place" using recursion?

Code :

import java.util.Stack;
/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 11/15/13
 * Time: 3:30 PM
 */

public class InPlaceStackReversal {
    public static void reverse(Stack<String> stack){
        String element = stack.pop();
        if(stack.size() != 1) {
            reverse(stack);
        }
        pushToBottomOfStack(element,stack);
    }


    private static void pushToBottomOfStack(String data, Stack<String> stack){
        String element = stack.pop();
        if(stack.size() != 0){
            pushToBottomOfStack(data, stack);
        }
        else {
            stack.push(data);
        }
        stack.push(element);
    }

    public static void main(String args[]) {
        Stack<String> myStack = new Stack<String>();
        myStack.push("A");
        myStack.push("B");
        myStack.push("C");
        myStack.push("D");
        System.out.println("Original Stack : " + myStack);
        InPlaceStackReversal.reverse(myStack);
        System.out.println("Revered Stack : " + myStack);

    }
}

Output :

Original Stack : [A, B, C, D]

Revered Stack : [D, C, B, A]

Troubleshooting steps when Android device is detected but not recognized by Eclipse ADT.

If your device is not detected at all by Eclipse ADT then go though the article on Troubleshooting steps when Eclipse ADT does not recognizing your Android device.

Sometimes it does happen when your device is detected but is not recognized by your Eclipse ADT.  Each Android device has a Development Device ID which is used to uniquely identify your android device. You can view this ID by going to

System settings -> Developer options -> Development Device ID

(It is right below option to enable USB debugging)

Screenshot for the same is provided below(It is of my device running Android 4.0.4/ICS).

Now coming back to our main problem.Whenever it occurs you will see your prompt asking for device as follows -

You will see something like ???? which means your device is detected but is not recognized. You can check this issue by going to adt-bundle-windows-x86\sdk\platform-tools and typing the following command

adb.exe devices (Windows)

./adb devices   (Linux)

 In both cases you will see an entry in list of devices but again some ????? with no permissions . All you need to do to get things to work again is restart your server. Detailed steps to do so and it's effect before and after is provided in a snapshot below.

Note that the device is now listed properly. Another interesting thing to note here is when you kill the server a reconnect thread is started in your Eclipse ADT. It will continuously try to reconnect to the server and will stop once server is up. Screenshot for the same is given below.

After this you are all set. Your USB debugging will work perfectly.

Related Links

• How to enable developers option in your android device?
• Troubleshooting steps when Eclipse ADT does not recognize your Android device. 
• Installing Google Nexus 5 USB Drivers (for ADB) 

How to take screenshots in Android 4.0 in above.

If you have a shiny new phone with Ice Cream Sandwich(4.0) or above, screenshots are built right into your phone! Just press the Volume Down and Power buttons at the same time, hold them for a second, and your phone will take a screenshot. It'll show up in your Gallery app for you to share with whomever you wish!

It is slightly different for Samsung devices. You need to press and hold

Power Button + Home Button