❔Interview Questions

INTERVIEW QUESTION - PELOTON

Given an array of integers, we define its degree as the number of occurrences of the element that occurs most frequently in the array. You will be given a list of integers and must determine two properties:

The degree of the array

The length of the shortest sub-array that shares that degree

For example, consider the array [1, 2, 1, 3, 2]. It has a degree of 2 based on the elements with values 1 and 2. The subarray of degree 2 based on the 1’s is [1,2,1] and based on 2’s is [2,1,3,2]. Their lengths are 3 and 4, so the shortest is length 3. Property 1 is 2 and property 2 is 3.

Write a function, in Java, which returns the second property, i.e. the length of the shortest subarray that shares the maximum degree.

int shortestSubArray(int[] arr) {

  // Stores first index for each number
  Map<Integer, Integer> left = new HashMap<>();
 
  // Stores last index for each number 
  Map<Integer, Integer> right = new HashMap<>();

  // Stores frequency of each number
  Map<Integer, Integer> count = new HashMap<>();

  for (int i = 0; i < arr.length; i++) {

    int x = arr[i];

    // If first time number is seen, store first index
    if (!left.containsKey(x)) {
      left.put(x, i);
    }

    // Store last index seen
    right.put(x, i);

    // Increment frequency
    count.put(x, count.getOrDefault(x, 0) + 1);

  }
 
  // Find highest frequency
  int degree = Collections.max(count.values());
 
  int ans = arr.length;

  for (int x : count.keySet()) {

    // For numbers with max frequency
    if (count.get(x) == degree) {
     
      // Calculate subarray length
      ans = Math.min(ans, right.get(x) - left.get(x) + 1);
   
    }

  }

  return ans;

  public static void main(String[] args) {
    int[] arr = {1, 2, 1, 3, 2};
    int shortestSubArrayLength = shortestSubArray(arr);
    System.out.println("Length of the shortest sub-array: " + shortestSubArrayLength);
  }
  
}

This function takes an array of integers as input and returns the length of the shortest subarray that shares the maximum degree. It uses three hashmaps: left, right, and count. The left hashmap stores the first occurrence of each element in the array. The right hashmap stores the last occurrence of each element in the array. The count hashmap stores the number of occurrences of each element in the array.

The first for loop iterates over the input array and updates the values in the three hashmaps. The degree variable is then set to the maximum value in the count hashmap, which represents the degree of the input array.

The second for loop iterates over the keys in the count hashmap. If the value of a key is equal to degree, then it updates the value of ans to be the minimum value between its current value and the difference between the corresponding values in the right and left hashmaps plus one.

Finally, the function returns the value of ans, which represents the length of the shortest sub-array that shares the maximum degree.

Sure, here's a step-by-step visualization of the code:

1. Initialize the three hashmaps `left`, `right`, and `count` to store the leftmost index, rightmost index, and frequency of each element in the array.

- `left`: empty hashmap

- `right`: empty hashmap

- `count`: empty hashmap

2. Iterate through the array `arr` using a for loop:

- Get the current element `x` at index `i`.

- Check if `x` is not present in the `left` hashmap. If not, store its index `i` in the `left` hashmap.

- Update the `right` hashmap with the current index `i` for the element `x`.

- Update the `count` hashmap by incrementing the frequency of element `x` by 1 using `count.getOrDefault(x, 0) + 1`.

- At the end of the loop, the hashmaps will contain the following values:

- `left`: `{1=0, 2=1, 3=3}`

- `right`: `{1=2, 2=4, 3=3}`

- `count`: `{1=2, 2=2, 3=1}`

3. Find the maximum degree by getting the maximum value from the `count` hashmap using `Collections.max(count.values())`.

- The maximum degree is `2`.

4. Iterate through the keys of the `count` hashmap using a for-each loop:

- Get the current element `x`.

- Check if the frequency of element `x` is equal to the maximum degree.

- If it is, calculate the length of the sub-array that includes element `x` by subtracting the leftmost index from the rightmost index and adding 1.

- Update the `ans` variable with the minimum length found so far using `Math.min(ans, right.get(x) - left.get(x) + 1)`.

- At the end of the loop, the value of `ans` will be `3`.

5. Return the value of `ans`, which represents the length of the shortest sub-array that shares the maximum degree.

- The value of `ans` is `3`.

6. In the `main` method, create an array `arr` with the values ``.

7. Call the `shortestSubArray` method with `arr` as the argument to find the length of the shortest sub-array.

- The length of the shortest sub-array is `3`.

8. Print the result, which is the length of the shortest sub-array, using `System.out.println`.

- The output will be `Length of the shortest sub-array: 3`.

Visualizer:

Java Visualizercscircles.cemc.uwaterloo.ca

This code is an implementation of finding the shortest subarray with maximum occurrence of a number. It falls under the following topics in data structures and algorithms:

• HashMaps - The code uses HashMaps to keep track of first/last indexes and frequencies.

• Sliding Window - The core logic of tracking a shrinking range (between first and last index) for each number is a sliding window approach.

• Frequency/Occurrence Problems - The code deals with finding maximum occurrences and the range based on it.

More specifically, this problem can be categorized as:

• Finding the shortest subarray with maximum number of occurrences of an element.

• A variation of the maximum/minimum window problem that looks for the shortest window with a desired property.

So in summary, the key concepts used are HashMaps, sliding windows, and frequency/occurrence based problems. And it falls under the umbrella of window-based problems.