OA Question 1: Maximum Subarray Sum
Given a list of integers (positive and negative), find the continuous subarray with the largest sum.
Example
Input:
6
2 -8 3 -2 4 -10
Output: 5
Explanation: The subarray [3, -2, 4] has the maximum sum 5.
Python Solution (Kadane’s Algorithm)
def max_subarray_sum(arr):
max_ending = max_so_far = arr[0]
for x in arr[1:]:
max_ending = max(x, max_ending + x)
max_so_far = max(max_so_far, max_ending)
return max_so_far
# Example usage
print(max_subarray_sum([2, -8, 3, -2, 4, -10])) # 5
OA Question 2: Longest Palindromic Substring
Find the longest substring of the given string that reads the same forwards and backwards. Substring length must be > 1.
- If multiple substrings share the maximum length, return the lexicographically smallest one.
- If no valid palindrome exists, return
"None".
Example 1
Input: YABCCBAZ
Output: ABCCBA
Example 2
Input: ABC
Output: None
Python Solution (Expand Around Center)
def longest_palindrome(s):
if len(s) < 2:
return "None"
best = ""
for i in range(len(s)):
# odd-length
l, r = i, i
while l >= 0 and r < len(s) and s[l] == s[r]:
cand = s[l:r+1]
if len(cand) > len(best) or (len(cand) == len(best) and cand < best):
best = cand
l -= 1; r += 1
# even-length
l, r = i, i+1
while l >= 0 and r < len(s) and s[l] == s[r]:
cand = s[l:r+1]
if len(cand) > len(best) or (len(cand) == len(best) and cand < best):
best = cand
l -= 1; r += 1
return best if best else "None"
# Examples
print(longest_palindrome("YABCCBAZ")) # ABCCBA
print(longest_palindrome("ABC")) # None
References
Contact Us
We provide OA ghostwriting, VO proxy interviews, and interview assistance. For perfect OA scores, contact us now.
正文完
