Questions
16 of 19
1What is the Prefix Sum technique?
2Why is insertion/deletion in the middle of an array O(n)?
3Explain the concept of Amortized O(1) for Dynamic Array insertion.
4How do you find the second largest element in an unsorted array?
5What is the difference between a String and a Character Array?
6What is the Sliding Window technique? Give a use case.
7What is a Sparse Array? When is it useful?
8Why is string concatenation in a loop O(n²)? How do you fix it? (StringBuilder)
9What is the Two-Pointer technique? Give a use case.
10What is a Dynamic Array (ArrayList/Vector)? How does it grow?
11What are the advantages and disadvantages of Arrays?
12What is an Array? How is it stored in memory?
13Explain Kadane's Algorithm (Maximum Subarray Sum). What is its complexity?
14Why are Strings immutable in Java/C#? What are the benefits?
15What is String Interning?
16Explain how to find the longest palindromic substring.
17Why is accessing an array element O(1)?
18How do you check if two strings are anagrams of each other?
19How do you rotate an array by k positions? (In-place vs extra space)
Data-StructuresData-Structures
Basics
Complexity Analysis
Arrays and Strings
Linked Lists
Stacks and Queues
Hash Tables
16 / 19

Explain how to find the longest palindromic substring.

Longest Palindromic Substring

javascript
  1. 1

    Expand-around-center takes O(n²) time in the worst case.

  2. 2

    Auxiliary space is O(1), excluding the returned substring.

  3. 3

    Dynamic programming can also solve the problem in O(n²) time and O(n²) space.

  4. 4

    Manacher's Algorithm solves the problem in O(n) time but is more complex.

  5. 5

    For production code, I would choose the approach based on input size and maintainability requirements.

Difficulty: 4/10

Follow-up Questions

  • ❓How does Manacher's Algorithm achieve O(n)?
  • ❓How would you solve this using dynamic programming?
  • ❓What is the difference between longest palindromic substring and subsequence?