List - DS Algo related questions

-
In programming, the List data structure is widely used in various scenarios, and interview questions often revolve around its practical applications. Here are some examples of programs where a List is used:

1. Basic Operations on Lists

  • Problem: Implement a program to reverse a list

  • Usage: The list is traversed, and its elements are reordered.

  • Core Java:

    import java.util.*;

public class ReverseList {
    public static List<Integer> reverseList(List<Integer> list) {
        Collections.reverse(list);
        return list;
    }
}

  • Java 8:

    import java.util.*;
import java.util.stream.*;

public class ReverseList {
    public static List<Integer> reverseList(List<Integer> list) {
        return IntStream.rangeClosed(1, list.size())
                        .mapToObj(i -> list.get(list.size() - i))
                        .collect(Collectors.toList());
    }
}


  • Problem: Write a program to remove duplicates from a list.

  • Usage: Lists are used to store unique elements.

  • Core Java:

    import java.util.*;

public class RemoveDuplicates {
    public static List<Integer> removeDuplicates(List<Integer> list) {
        return new ArrayList<>(new HashSet<>(list));
    }
}

  • Java 8:

    import java.util.*;
import java.util.stream.*;

public class RemoveDuplicates {
    public static List<Integer> removeDuplicates(List<Integer> list) {
        return list.stream()
                   .distinct()
                   .collect(Collectors.toList());
    }
}

2. Searching and Sorting

  • Problem: Implement a binary search on a sorted list.

  • Usage: Lists are used to perform search operations efficiently.

  • Core Java:

    import java.util.*;

public class BinarySearch {
    public static int binarySearch(List<Integer> list, int target) {
        int left = 0, right = list.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid) == target)
                return mid;
            if (list.get(mid) < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return -1;
    }
}

  • Problem: Sort a list of integers.

  • Usage: Lists are often sorted using algorithms like quicksort, merge sort, or using built-in functions.

  • Core Java:

    import java.util.*;

public class SortList {
    public static List<Integer> sortList(List<Integer> list) {
        Collections.sort(list);
        return list;
    }
}

  • Java 8:

    import java.util.*;
import java.util.stream.*;

public class SortList {
    public static List<Integer> sortList(List<Integer> list) {
        return list.stream()
                   .sorted()
                   .collect(Collectors.toList());
    }
}

3. Two-Pointer Technique

  • Problem: Find two numbers in a list that add up to a specific target.
  • Usage: The two-pointer technique is commonly applied to sorted lists.
  • Core Java:
    import java.util.*;

public class TwoSum {
    public static int[] twoSum(int[] nums, int target) {
        Arrays.sort(nums);
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target)
                return new int[]{nums[left], nums[right]};
            if (sum < target)
                left++;
            else
                right--;
        }
        return new int[]{};
    }
}

4. Dynamic Programming

  • Problem: Find the length of the longest increasing subsequence in a list.
  • Usage: Lists are used to store intermediate results in dynamic programming.

  • Core Java:

    import java.util.*;

public class LongestIncreasingSubsequence {
    public static int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        return Arrays.stream(dp).max().getAsInt();
    }
}

  • Java 8:

    import java.util.*;

public class LongestIncreasingSubsequence {
    public static int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        return Arrays.stream(dp).max().orElse(0);
    }
}

5. Sliding Window Technique

  • Problem: Find the maximum sum of a subarray of size k.
  • Usage: Lists are used to implement the sliding window approach.
  • Core Java:
    public class MaxSumSubarray {
    public static int maxSumSubarray(int[] nums, int k) {
        int n = nums.length;
        if (n < k) return -1;
        int maxSum = 0;
        for (int i = 0; i < k; i++) {
            maxSum += nums[i];
        }
        int windowSum = maxSum;
        for (int i = k; i < n; i++) {
            windowSum += nums[i] - nums[i - k];
            maxSum = Math.max(maxSum, windowSum);
        }
        return maxSum;
    }
}

6. List Manipulation

  • Problem: Rotate a list to the right by k steps.
  • Usage: Lists are rotated or manipulated to solve problems.

  • Core Java:


    import java.util.*;

public class RotateList {
    public static List<Integer> rotateList(List<Integer> list, int k) {
        Collections.rotate(list, k);
        return list;
    }
}

  • Java 8:

    import java.util.*;

public class RotateList {
    public static List<Integer> rotateList(List<Integer> list, int k) {
        int size = list.size();
        k = k % size;
        List<Integer> result = new ArrayList<>();
        result.addAll(list.subList(size - k, size));
        result.addAll(list.subList(0, size - k));
        return result;
    }
}

7. Matrix Problems (List of Lists)

  • Problem: Rotate a 2D matrix by 90 degrees.
  • Usage: Lists of lists are often used to represent matrices.

  • Core Java:

    import java.util.*;

public class RotateMatrix {
    public static int[][] rotateMatrix(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; i++) {
            for (int j = i; j < n - i - 1; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][j];
                matrix[n - i - 1][j] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
        return matrix;
    }
}

  • Java 8:

    import java.util.*;

public class RotateMatrix {
    public static int[][] rotateMatrix(int[][] matrix) {
        int n = matrix.length;
        int[][] result = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                result[j][n - 1 - i] = matrix[i][j];
            }
        }
        return result;
    }
}

8. String Manipulation Using Lists

  • Problem: Reverse the words in a string.
  • Usage: Strings are split into a list of words for manipulation.

  • Core Java:

    public class ReverseWords {
    public static String reverseWords(String s) {
        String[] words = s.split(" ");
        StringBuilder reversed = new StringBuilder();
        for (int i = words.length - 1; i >= 0; i--) {
            reversed.append(words[i]).append(" ");
        }
        return reversed.toString().trim();
    }
}

  • Java 8:

    import java.util.*;
import java.util.stream.*;

public class ReverseWords {
    public static String reverseWords(String s) {
        return Arrays.stream(s.split(" "))
                     .reduce((word1, word2) -> word2 + " " + word1)
                     .orElse("");
    }
}

9. List as a Stack/Queue

  • Problem: Implement a stack using a list.

  • Usage: Lists can be used to simulate stack operations.

  • Core Java:

    import java.util.*;

public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);  // Push
        stack.pop();    // Pop
    }
}

10. Graph Algorithms Using Lists

  • Problem: Implement a graph using an adjacency list.
  • Usage: Lists are used to represent the adjacency list in graph problems.

Problem: Implement a Graph Using an Adjacency List

Core Java Implementation

In Core Java, you would typically use a HashMap to represent the adjacency list, where the keys are the nodes (vertices) and the values are lists of adjacent nodes (edges).

import java.util.*;

public class Graph {
    private Map<Integer, List<Integer>> adjList;

    public Graph() {
        adjList = new HashMap<>();
    }

    // Method to add an edge to the graph
    public void addEdge(int u, int v) {
        adjList.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
        adjList.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
    }

    // Method to print the adjacency list of the graph
    public void printGraph() {
        for (Map.Entry<Integer, List<Integer>> entry : adjList.entrySet()) {
            System.out.println("Vertex " + entry.getKey() + ": " + entry.getValue());
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addEdge(0, 1);
        graph.addEdge(0, 4);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);
        
        graph.printGraph();
    }
}

Java 8 Implementation

In Java 8, you can take advantage of the computeIfAbsent method (as shown in the Core Java example) and also use streams if you want to perform operations on the graph's adjacency list.

import java.util.*;
import java.util.stream.Collectors;

public class Graph {
    private Map<Integer, List<Integer>> adjList;

    public Graph() {
        adjList = new HashMap<>();
    }

    // Method to add an edge to the graph
    public void addEdge(int u, int v) {
        adjList.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
        adjList.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
    }

    // Method to print the adjacency list of the graph
    public void printGraph() {
        adjList.forEach((vertex, edges) -> 
            System.out.println("Vertex " + vertex + ": " + 
                edges.stream()
                     .map(String::valueOf)
                     .collect(Collectors.joining(", "))
            )
        );
    }

    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addEdge(0, 1);
        graph.addEdge(0, 4);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);
        
        graph.printGraph();
    }
}

Explanation:

  • addEdge(int u, int v): This method adds an edge between nodes u and v. If the nodes are not already in the adjacency list, computeIfAbsent creates a new entry for them.
  • printGraph(): This method prints the adjacency list of the graph. In the Java 8 version, streams are used to format the output.

This setup is straightforward and efficient for representing and working with undirected graphs using an adjacency list.

Comments

Post a Comment

Popular posts from this blog

Full Stack Java Developer - FAQ

-
PROJECT Explain project architecture & technologies stack used in current project?   Your current project deployment process, If its Microservices then explain its CI/CD process?   How do you scale up and down your application if its support microservice architecture?   If you worked on Jenkins then explain it job/pipeline?   What all approach you will take to track slow running application from end to end, Explain step by step?   How do you deal the difficult customer with adhoc requirement?   How will you handle pressure situation within team?   All achievements in IT career?   Anything you have learned during COVID situation last year? CORE JAVA Static method can be overloaded? Static method can be override...
Read more

DSA Interview Coding Questions

-
1] Arrays 1] Find first and second best score Example Given an array, write a function to get first, second best scores from the array and return it in new array. Array may contain duplicates. Example myArray = { 84 , 85 , 86 , 87 , 85 , 90 , 85 , 83 , 23 , 45 , 84 , 1 , 2 , 0 } firstSecond ( myArray ) // {90, 87} Solution: import java . util . Arrays ; import java . util . Collections ; public class Exercise { public static int [] findTopTwoScores ( int [] array ) { int firstHighest = Integer . MIN_VALUE ; int secondHighest = Integer . MIN_VALUE ;   for ( int score : array ) { if ( score > firstHighest ) { secondHighest = firstHighest ; firstHighest = score ; } else if ( score > secondHighest && score < firstHighest ) { secondHighest = score ; } }   return new int []{ firstHighest , secondHighest }...
Read more

Java Interview Question - New FAQs

-
1. Performance Testing & Setting up benchmarks Performance testing evaluate how a system performs under load & to setup benchmarks below steps to be noted down. Steps are: Define KPIs: Response time, throughput, CPU/memory usage etc. Identify Critical Scenarios: like login, search, submit form Use Tools: Gatling, Apache Bench, JMeter (Use to simulate 1000 concurrent users hitting a Rest API and measure the response time Baseline Measurement: Run tests under normal load to establish a baseline Load Testing: Gradually increase users to find system limits Stress Testing: Push beyond limits to see how the system fails Bench marking: Compare results against industry standards or previous releases 2. ACID properties in database It ensure the reliable transaction Atomicity : All operations in a transaction succeed or none do Consistency : DB remains in a valid state before and after the transaction Isolation : Concurrent transactions don't interfere Durability : Once commited...
Read more