Wednesday, August 12, 2020

How to reverse an ArrayList in place in Java - Coding Interview Questions

You can reverse an ArrayList in place in Java by using the same algorithm we have used to reverse an array in place in Java. If you have already solved that problem then It's a no-brainer because ArrayList is nothing but a dynamic array, which can resize itself. All elements of an array are stored in the internal array itself. By the way, if you need to reverse an ArrayList then you should be using the Collections.reverse() method provided by the Java Collection framework. It's a generic method, so you can not only reverse an ArrayList but also Vector, LinkedList, CopyOnWriteArrayList, or any other List implementation.

Though, worth noting is that this method internally uses a ListIterator for reversing the list, which might not be as efficient as our algorithm.

If this question is asked in an interview, then you can also use recursion to reverse the ArrayList, as shown in this article. The interviewer often tests the candidate with a recursive algorithm just to check if they understand recursion or not.

Also, basic knowledge of essential data structure is also very important and that's why I suggest all Java programmers join a comprehensive Data Structure and Algorithms course like Data Structures and Algorithms: Deep Dive Using Java on Udemy to fill the gaps in your understanding.




How to reverse an ArrayList in place in Java

Here is code to reverse an ArrayList of String in place. The algorithm is generic, so you can also use it to reverse an ArrayList of Integer, Double, or any other object. If you look carefully, we are just iterating over the array and swapping elements from the opposite end until we reach the middle of the list. At this point, our list is completely reversed. This is the same algorithm we have used to reverse an array earlier.

// let's now reverse the list in place in Java
        int size = listOfFood.size();
        for (int i = 0; i < size / 2; i++) {
            final String food = listOfFood.get(i);
            listOfFood.set(i, listOfFood.get(size - i - 1)); // swap
            listOfFood.set(size - i - 1, food); // swap
        }

Though a couple of things, you need to keep in mind. Since we are using the set() method, you cannot pass an unmodifiable or read-only ArrayList to this method. Using this algorithm with read-only ArrayList will throw java.lang.UnSupportedOperationException.

The time complexity of this algorithm is O(n/2) i.e. O(n) where n is the size of ArrayList, and space complexity is O(1) because we don't need additional list or space required by the recursive algorithm to reverse a list in Java.

One more thing which you should keep in mind this algorithm should only be used with List which supports RandomAccess e.g. ArrayList and Vector. Though you can reverse the LinkedList using this algorithm, it will be of order O(n^2) because the linked list doesn't support index-based access and get() method traverse the linked list to retrieve the desired element.

Since traversal in a linked list is O(n), the time complexity of algorithm rises to O(n^2) for reversing linked list in place using this algorithm.

On the same note, if you came here are part of your programming job interview preparation, you should also check Grokking the Coding Interview: Patterns for Coding Questions course on Educative.

It will teach you essential coding patterns like sliding window, merge intervals, fast and slow points, and other approaches that can help you to solve real coding questions from reputed companies interviews like Facebook, Amazon, Google, and Microsoft.

How to reverse an ArrayList in place in Java - Coding Interview Questions

And, if you find Educative platform and their Grokking courses like Grokking the System Design Interview, Grokking the Object-Oriented Programming interview then consider getting Educative Subscription which provides access to their 100+ courses in just $18 per month. It's very cost-effective and great for preparing for coding interviews.


Java Program to reverse an ArrayList in place

Here is our sample Java program to reverse an ArrayList of String in place. The algorithm is generic, so you can also use it to reverse an ArrayList of Integer, Double, or any other object.

import java.util.ArrayList;
import java.util.List;

/*
 * Java Program to reverse an ArrayList in place.
 * When you reverse ArrayList in place, you are not
 * allowed to use additional buffer e.g. an array
 * or any collection.
 */
public class ReverseArrayListInPlace {

    public static void main(String args[]) {

        // Let's create a list of foods which helps
        // to lose weight, one of the prime concern programmers
        List<String> listOfFood = new ArrayList<>();
        listOfFood.add("Beans");
        listOfFood.add("Soup");
        listOfFood.add("Dark Chocolate");
        listOfFood.add("Yogurt");
        listOfFood.add("Sausage");
        listOfFood.add("Pure Vegetables");
        listOfFood.add("Nuts");

        System.out.println("Original ArrayList: " + listOfFood);

        // let's now reverse the list in place in Java
        int size = listOfFood.size();
        for (int i = 0; i < size / 2; i++) {
            final String food = listOfFood.get(i);
            listOfFood.set(i, listOfFood.get(size - i - 1)); // swap
            listOfFood.set(size - i - 1, food); // swap
        }

        System.out.println("Reversed ArrayList: " + listOfFood);
    }

}

Output:
Original ArrayList: [Beans, Soup, Dark Chocolate, Yogurt, Sausage,
Pure Vegetables, Nuts]
Reversed ArrayList: [Nuts, Pure Vegetables, Sausage, Yogurt, Dark Chocolate,
Soup, Beans]

That's all about how to reverse an ArrayList in place in Java. Just keep in mind that you can use reverse ArrayList of any object e.g. String, Integer, Float, or Double. You can also use this algorithm to reverse Vector or any other List which supports index-based access.

One more requirement of this algorithm is that List should not be unmodifiable i.e. set() method should not throw UnSupportedOperationException. Don't use this algorithm to reverse the linked list in Java because time complexity would be O(n^2), you can see the following courses for more details on calculating time and space complexity.


Further Learning
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Cracking the Coding Interview: 189 Problems and Solutions
Grokking the Coding Interview: Patterns for Coding Questions


Hungry for More?? Here you go
  • How to reverse a String in place in Java? (solution)
  • Top 20 Amazon and Google Interview Questions? (list)
  • How to implement the Quicksort algorithm in Java? [solution]
  • 7 Best courses to learn Data Structure and Algorithms (courses)
  • How to find all permutations of a String in Java? (solution)
  • Write a program to find the top two numbers from an integer array? [solution]
  • How to find duplicate words in Java String? (solution)
  • 10+ Algorithms and Programming Courses to Crack Interviews (courses)
  • How to check if an array contains a number in Java? [solution]
  • How to print the Fibonacci series without recursion? (solution)
  • 10 Free Data Structure and Algorithms Courses for beginners (free courses)
  • How to find the highest and lowest element in the unsorted array? [solution]
  • 10 Books to learn Data Structure and Algorithms (books)
  • How to check if a String is a Palindrome in Java? (solution)
  • 10 Data Structure and Programming Courses to Crack Interviews (courses)
  • How to find duplicate elements in an array? (solution)
  • 20+ binary tree questions from coding interviews (questions)
  • How do you print prime numbers up to a given number? (solution)
  • 25 systems design questions from interviews (questions)
  • How to find the largest prime factor of a number in Java? (solution)
  • How to count the number of words in a given String? (solution)

Thanks for reading this article so far. If you like these dynamic programming coding problems then please share it with your friends and colleagues. If you have any questions or feedback then please drop a note.

P.S. - If you are preparing for Programming Job Interview and you need more such questions, can check the Data Structures and Algorithms Bootcamp by Jonathan Rasmusson course on  Udemy to refresh your knowledge in quick time. 

No comments :

Post a Comment