Amazon SDE1 OA very hard

I have joined 3 OA's before and i passed all test cases and problems were simple today i encounted those :

Q1: Amazon's fulfillment centers handle packages of various weights, and they need to optimize their sorting process.

Given an array weight which denotes the weights of n packages, the goal is to create the lexicographically maximal resulting array sorted by non-increasing order of weight using the following operations:

1. Discard the first package from the current weight array

2. Add the first element to the resulting array, then remove it along with the next k (a fixed constant) elements from the current array

Note that Operation 2 can also be applied when fewer than k elements remain after the current element; In that case, the entire remaining array is removed.

The resulting array must have packages arranged in non-Increasing weight order.

Given an array weight of size n and an integer k, find the lexicographically maximal resulting array sorted in non-Increasing order of weight that can be obtained.

Note: An array x is lexicographically greater than an array y If:

x[i] >y[i], where i is the first position where x and y differ, or

/x/ > /y/ and y is a prefix of x (where /x/ denotes the size of array x)

Example

k=1

n=5 weight = [4, 3, 5, 5, 3)

To obtain the lexicographically maximal resulting array sorted in non-increasing order, we will perform the following operations: Sample Input 0

STDIN

Function

2 → k = 2

5 → weight[] size n = 5

10

5

9

2

5

→

weight = [10, 5, 9, 2, 5]

Sample Output 0

10

5 ▼Sample Case 1

Sample Input 1

STDIN

Function

→ k = 0

1 → weight[] size n = 1

3 → weight = [3]

Sample Output 1

3

Explanation

In this case since there is only 1 element, we apply Operation 2, adding weight[0] = 3 to the resulting array, which gives the lexicographically maximal array sorted in non-increasing order of weight.

Thus, the answer is [3].

Question2 : same one here , this my solution and i got time limit exceed passed 9/15 https://leetcode.com/discuss/post/6679050/amazon-online-assessment-by-anonymous_us-dyun/ def max_score(data): n = len(data) if n == 1: return 1

def calculate_score(s):
    total = len(s)
    current_length = 1
    for i in range(1, len(s)):
        if abs(ord(s[i]) - ord(s[i-1])) <= 1:
            current_length += 1
        else:
            total += current_length * (current_length - 1) // 2
            current_length = 1
    total += current_length * (current_length - 1) // 2
    return total

max_score = calculate_score(data)

for i in range(n):
    original_char = data[i]
    # Determine the best possible replacement for the current character
    best_char = None
    best_score = max_score
    # Check left and right neighbors to find the best replacement
    left = data[i-1] if i > 0 else None
    right = data[i+1] if i < n - 1 else None
    # Try replacing with characters that would make it adjacent to neighbors
    for c in 'abcdefghijklmnopqrstuvwxyz':
        if c == original_char:
            continue
        # Check if replacing with 'c' would make it adjacent to left neighbor
        if left is not None and abs(ord(c) - ord(left)) <= 1:
            new_data = data[:i] + c + data[i+1:]
            current_score = calculate_score(new_data)
            if current_score > best_score:
                best_score = current_score
                best_char = c
        # Check if replacing with 'c' would make it adjacent to right neighbor
        if right is not None and abs(ord(c) - ord(right)) <= 1:
            new_data = data[:i] + c + data[i+1:]
            current_score = calculate_score(new_data)
            if current_score > best_score:
                best_score = current_score
                best_char = c
    # If no better replacement found, try replacing with any character
    if best_char is None:
        for c in 'abcdefghijklmnopqrstuvwxyz':
            if c == original_char:
                continue
            new_data = data[:i] + c + data[i+1:]
            current_score = calculate_score(new_data)
            if current_score > best_score:
                best_score = current_score
                best_char = c
    # Update the max_score if a better replacement was found
    if best_score > max_score:
        max_score = best_score
    # Early termination if the maximum possible score is achieved
    if max_score == n + (n * (n - 1)) // 2:
        break
return max_score