Microsoft Software Engineer I interview questions

They asked me to solve the Word Search problem from LeetCode, where you check if a word can be formed in a 2D grid of letters using backtracking search.

You are given an integer array arr of length n, and three integers x, y, and z. You may select non-overlapping subarrays from arr. Each chosen subarray must be of length 1, length 2, or length 3. You can choose at most x subarrays of length 1. You can choose at most y subarrays of length 2. You can choose at most z subarrays of length 3. Your goal is to maximize the total sum of all elements in the selected subarrays. Return the maximum possible sum you can obtain under these constraints. Input: arr (list of integers), x, y, z (non-negative integers) Output: An integer representing the maximum total sum.