Solve Two OA Coding Problems

The online assessment included two coding problems:

1. In-place character run compression

   • You are given an array of characters.
   • Compress consecutive identical characters in place.
   • For each maximal run, write the character once, followed by the decimal count only if the run length is greater than 1.
   • The count must be written as individual digit characters.
   • Return the new length of the compressed array.
   • Example: ['a','a','a','b','b','c'] becomes ['a','3','b','2','c'], and the function returns 5.

2. Minimum operations to reduce an integer to zero

   • You are given a positive integer n.
   • In one operation:
     • if n is even, you may replace it with n / 2;
     • if n is odd, you may replace it with either n + 1 or n - 1.
   • Compute the minimum number of operations required to reduce n to 0.
   • Example: if n = 7, one optimal sequence is 7 -> 8 -> 4 -> 2 -> 1 -> 0, which takes 5 operations.

Part 1: In-Place Character Run Compression

Given a list chars where each element is a one-character string, compress consecutive identical characters in place. For each maximal run, write the character once, followed by the run length only if the length is greater than 1. The count must be written as separate digit characters. Return the new length of the compressed list. For example, ['a','a','a','b','b','c'] becomes ['a','3','b','2','c'], and the function returns 5.

Constraints

• 0 <= len(chars) <= 100000
• Each element of chars is a string of length 1
• The algorithm should run in linear time
• Only constant extra auxiliary space should be used

Examples

Example 1

Input: (['a','a','a','b','b','c'],)
Output: 5

Explanation: The list is compressed to ['a','3','b','2','c'], so the new length is 5.

Example 2

Input: (['a'],)
Output: 1

Explanation: A single character stays unchanged.

Hints

1. Use one pointer to scan runs of equal characters and another pointer to write the compressed result.
2. When a run length is greater than 1, convert the count to a string and write each digit separately.

Part 2: Minimum Operations to Reduce an Integer to Zero

Given a positive integer n, compute the minimum number of operations needed to reduce it to 0. In one operation: if n is even, you may replace it with n / 2; if n is odd, you may replace it with either n + 1 or n - 1.

Constraints

• 1 <= n <= 2147483647
• If n is even, the next value must be n // 2
• If n is odd, you may choose either n + 1 or n - 1
• The solution should be efficient for large values of n

Examples

Example 1

Input: (7,)
Output: 5

Explanation: One optimal sequence is 7 -> 8 -> 4 -> 2 -> 1 -> 0.

Example 2

Input: (1,)
Output: 1

Explanation: The only move is 1 -> 0.

Hints

1. For an odd number, both choices make it even. Usually it is better to pick the one that creates more trailing zeros in binary.
2. There is one important special case: when n == 3, subtracting 1 is better than adding 1.