Check Digits and Combine Ranges
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are asked to solve two independent coding tasks.
### Task 1: Check Whether an Integer Reads the Same Backward
Given an integer `x`, return `true` if its decimal representation reads the same from left to right and from right to left; otherwise return `false`.
Requirements and edge cases:
- Negative integers should return `false` because of the leading minus sign.
- You may assume `x` fits in a signed 32-bit integer.
- Try to solve it without converting the integer to a string.
Example:
```text
Input: x = 121
Output: true
```
```text
Input: x = -121
Output: false
```
```text
Input: x = 10
Output: false
```
### Task 2: Combine Overlapping Ranges
Given an array of intervals `intervals`, where each interval is represented as `[start, end]`, combine all overlapping intervals and return an array of non-overlapping intervals that covers exactly the same ranges.
Requirements and edge cases:
- Intervals may be provided in any order.
- Two intervals overlap if they share at least one point. For example, `[1, 4]` and `[4, 5]` should be combined into `[1, 5]`.
- Return the intervals in increasing order by start value.
Example:
```text
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
```
```text
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
```
Quick Answer: This two-part question evaluates numeric digit-manipulation and interval-merging competencies, specifically integer palindrome detection (accounting for sign and integer limits) and combining overlapping ranges via sorting and range aggregation in the Coding & Algorithms domain.
Part 1: Check Whether an Integer Reads the Same Backward
Given an integer x, return True if its decimal representation reads the same from left to right and from right to left. Otherwise, return False. Negative integers are not palindromes because of the leading minus sign. Try to solve the problem using arithmetic operations instead of converting the integer to a string.
Constraints
- -2^31 <= x <= 2^31 - 1
- Negative integers must return False
- An arithmetic-based solution is preferred over string conversion
Examples
Input: 121
Expected Output: True
Explanation: 121 reads the same forward and backward.
Input: -121
Expected Output: False
Explanation: Negative numbers are not palindromes.
Hints
- A negative number can never be a palindrome because the minus sign only appears on the left.
- Try reversing only the second half of the digits instead of the whole number.
Part 2: Combine Overlapping Ranges
Given a list of intervals, where each interval is represented as [start, end], merge all overlapping intervals and return a new list of non-overlapping intervals that covers exactly the same ranges. Intervals may appear in any order. Two intervals overlap if they share at least one point, so [1, 4] and [4, 5] should be merged into [1, 5]. Return the result sorted by starting value.
Constraints
- 0 <= len(intervals) <= 10^4
- -10^9 <= start <= end <= 10^9
- Intervals may be unsorted
Examples
Input: [[1, 3], [2, 6], [8, 10], [15, 18]]
Expected Output: [[1, 6], [8, 10], [15, 18]]
Explanation: The first two intervals overlap and merge into [1, 6].
Input: [[1, 4], [4, 5]]
Expected Output: [[1, 5]]
Explanation: The intervals share the point 4, so they overlap.
Hints
- Sort the intervals by their start value before trying to merge them.
- Keep track of the last interval in the output. If the next interval overlaps, extend the end; otherwise, start a new interval.