cswork / libraryOpen practice workspace

Coding questions · Arista

Solve palindrome and missing-number variants

This question evaluates competencies in string processing, array manipulation, binary search, and algorithmic complexity analysis by asking a palindrome check and a missing-number problem that requires both O(n) and O(log n) reasoning, emphasizing edge-case handling and time/space complexity discussion.

You are asked to solve two coding problems and analyze the time and space complexity of each.

  1. Palindrome check Given a string s, determine whether it reads the same forward and backward. Treat the empty string as a valid palindrome. If s is null, return false.

  2. Missing number with arbitrary start Given a sorted array nums of distinct integers, the values should form a consecutive sequence with step size 1, but exactly one number is missing. The sequence does not necessarily start at 0.

    Examples:

    • [4, 5, 6, 8, 9] -> 7
    • [10, 11, 13] -> 12

    First describe an O(n) solution, then improve it to an O(log n) solution using binary search.

For both problems, be prepared to explain your time and space complexity and discuss edge cases.

Palindrome Check

Return whether a string reads the same forward and backward; None returns false and empty string is valid.

Constraints

  • Input is a string or None

Examples

Example 1

Input: ('racecar',)
Output: True

Explanation: Odd palindrome.

Example 2

Input: ('',)
Output: True

Explanation: Empty string.

Hints

  1. Compare characters from both ends.

Missing Number with Arbitrary Start

Given sorted distinct integers from a consecutive sequence with one missing value, return the missing value.

Constraints

  • Exactly one number is missing from the represented consecutive sequence

Examples

Example 1

Input: ([4, 5, 6, 8, 9],)
Output: 7

Explanation: Missing in middle.

Example 2

Input: ([10, 11, 13],)
Output: 12

Explanation: Small example.

Hints

  1. For index i before the gap, nums[i] == nums[0] + i.