Coding interview

December 11, 2022 7:00 PM PST

---

This document summarizes the coding interview process, including the questions discussed, approaches to solving them, and coding strategies employed during the interview.

---

Interview Structure

• Format: 1 phone interview question (easier) + 1 onsite interview question (harder)

Questions Discussed

Question 1: Length of Longest Subarray

• Concept: Identify the length of the longest contiguous subarray.
• Example: Given an array [7, 2, 3, 1, 5, 8, 9, 6].
• Approach:
  • Use a linear scan from left to right.
  • Maintain a variable for the current length of the subarray and a maximum length variable.
  • Time Complexity: O(N)

Alternative Solutions

• Naive Solution: Use two nested loops to check all subarrays.

  • Time Complexity: O(N^3)

• Dynamic Programming Approach:

  • Use historical results to compute the current subarray length.
  • Define M[i] as the length of the current subarray.
  • Global maximum to track the longest subarray found.

Example Code

public static int solution(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    int max = 0;
    int len = 1;
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > arr[i - 1]) {
            len++;
        } else {
            max = Math.max(max, len);
            len = 1;
        }
    }
    max = Math.max(max, len);
    return max;
}

Question 2: Maximum Number of Envelopes (Russian Doll Problem)

• Concept: Determine the maximum number of envelopes that can fit into each other based on width and height.
• Input Definition: Input can be an array of arrays or an array of objects with width and height fields.

Approach

• Sorting: Sort envelopes based on width, and then by height in reverse to avoid issues with equal widths.
• Dynamic Programming: Find the longest increasing subsequence based on height after sorting by width.

Key Points

• Use binary search to find the maximum element smaller than the current height.
• Maintain a global maximum for the longest subsequence.

Example Strategy

• Base case: M[0] = 1
• Induction rule: M[i] represents the length of the longest ascending subsequence that ends at a[i].
• If no previous element is smaller, return 1; otherwise, find the maximum of M[j] for all j where a[j] < a[i].

Conclusion

• The interview covered dynamic programming concepts and efficient coding strategies for solving problems related to subarrays and subsequences.
• Emphasis on understanding the problem, defining inputs and outputs, and optimizing solutions using historical results.