In Java, String objects are immutable, meaning that they cannot be altered after creation, leading to the creation of new separate objects whenever modifications are needed, which can be inefficient for repeated operations. StringBuilder, on the other hand, is mutable, allowing direct modifications of character sequences, making it more performant when concatenating strings or making multiple changes, as it reduces the overhead of creating new objects .

An adjacency list represents a graph as an array of lists, where each list corresponds to a vertex and contains all adjacent vertices, making it space-efficient for sparse graphs, as it only stores existing edges. In contrast, an adjacency matrix uses a 2D array, storing information for all possible edges (dense representation), with a time complexity of O(1) for edge look-up but uses more space, being less efficient for graphs with fewer edges. Choosing between them depends on the graph's sparsity and the frequency of operations like edge existence checks and neighbor enumeration .

Recursion involves a function calling itself to solve smaller instances of the same problem until it reaches a base condition that does not call the function further, preventing infinite recursion. Base conditions ensure that recursion terminates. Without an appropriate base condition, recursion can result in stack overflow due to excessive memory usage from too many active function calls. This is often indicated by problems such as calculating factorial or Fibonacci numbers, where each recursive call requires additional stack memory .

Memoization is a technique where function calls and their results are recorded to avoid redundant calculations, effectively turning exponential time problems into linear ones by storing intermediate results. It resembles top-down recursion with stored results. Tabulation, or dp table, takes the bottom-up approach by filling up a table iteratively based on previously computed values. While both optimize dynamic programming by reducing computational overhead, memoization can be more intuitive due to its recursive nature, whereas tabulation can be more efficient in terms of space complexity .

Greedy algorithms build up a solution piece by piece, choosing the best possible option at each step, which is advantageous for its simplicity and speed when optimal substructure and greedy-choice properties are present, such as in Kruskal's or Prim's algorithms for minimum spanning trees. However, they can be disadvantageous when local optimal choices do not lead to a global optimum. For example, in the "fractional knapsack problem," a greedy strategy works well, but it might fail for the "0/1 knapsack problem" because selecting locally optimal items could prevent achieving the optimal total benefit .

Merge sort is a stable sorting algorithm because it maintains the relative order of equal elements throughout the sorting process. This is achieved through its divide-and-conquer approach, where arrays are divided into subarrays, individually sorted, and then merged back together. Stability is significant when sorting, especially when elements are keyed on more than one criterion, and preserving the initial sequence among equal elements is required for correctness .

The sliding window technique is used for problems involving arrays or lists, allowing efficient analysis by maintaining a subset of elements inside a window and adjusting it as you iterate over the data. This reduces the need to repeatedly loop through the same elements. An example is finding the maximum sum of a contiguous subarray of a fixed size k. By computing the sum of the first k elements, the window slides by 1 index each time, updating the sum by adding the end element of the new window and removing the first element of the previous window, thus avoiding recalculating the sum from scratch .

Linear search scans each element in the array sequentially until the desired element is found or the end is reached, with a time complexity of O(n), making it less efficient for large datasets. Binary search, on the other hand, requires sorted inputs and works by repeatedly dividing the dataset in half, reducing the search area each step, which gives it a time complexity of O(log n), making it more efficient for large, ordered datasets .

Stacks implemented with arrays provide simple and direct access to elements, benefiting from minimal overhead and better cache performance, but are limited by fixed size, potentially wasting memory or causing overflow. Linked list implementations offer dynamic memory usage, allowing stacks to grow as needed, but they incur additional memory and computational overhead due to pointer manipulations and non-contiguous memory allocations, potentially affecting performance .

Time complexity evaluates the amount of time an algorithm takes to complete as a function of the length of the input, expressed in Big O notation (e.g., O(1), O(n)). Space complexity assesses the amount of memory an algorithm uses relative to the input size. Efficient algorithms aim to minimize both time and space complexity, but there might be trade-offs. For example, a more space-efficient algorithm might run slower and vice versa .