Quick Overview

In the Coding & Algorithms domain, this prompt evaluates numerical methods and precision handling for implementing a square-root function without library support, together with in-place array manipulation, partitioning and complexity reasoning for parity-based rearrangement, testing competencies in algorithm design, numerical approximation, and space-efficient data transformations. These problems are commonly asked to assess understanding of numerical stability, error bounds and iterative approximation as well as mastery of in-place ordering/partitioning strategies and time/space complexity analysis, requiring both conceptual understanding of mathematical properties and practical implementation ability.

Implement sqrt and parity-based array rearrangement

Company: Deshaw

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given two independent coding tasks. --- ### Task 1: Implement Square Root Without Math Library Implement a function that computes the square root of a non-negative number **without** using any built-in square root or exponentiation functions from math libraries. - **Input:** A non-negative real number `x`. - **Output:** A real number `y` such that `y * y` approximates `x` within a specified error bound (for example, absolute error < `1e-6`). - **Constraints:** - You may use basic arithmetic operations (`+`, `-`, `*`, `/`) and control flow. - You may not call built-in functions like `sqrt`, `pow`, etc. - **Clarifications to handle in code:** - What should the function return when `x = 0`? - How do you handle very large or very small positive values of `x`? Define the function signature in a language of your choice, document the precision assumption you make (e.g., `1e-6`), and implement the algorithm. --- ### Task 2: Rearrange Array by Index Parity You are given an array of integers. You must rearrange its elements **in-place** (i.e., using O(1) extra space) so that all numbers at **even positions** (using **1-based indexing**) are strictly smaller than all numbers at **odd positions**. - **Input:** An integer array `arr` of length `n`. - **Output:** The same array, modified in place, such that: - If we number positions starting from 1, then every element at an even position (indices `2, 4, 6, ...`) is strictly less than every element at an odd position (indices `1, 3, 5, ...`). - Any arrangement that satisfies this property is acceptable. - **Example:** - Input: `[1, 2, 3, 4, 5]` - One valid output: `[5, 1, 4, 2, 3]` - Odd positions (1, 3, 5) → values `[5, 4, 3]` - Even positions (2, 4) → values `[1, 2]` - Every even-position value (`1, 2`) is less than every odd-position value (`3, 4, 5`). - **Constraints/requirements:** - The rearrangement must be done in-place (only O(1) extra storage). - Aim for an efficient algorithm (e.g., O(n log n) or better time complexity). Describe your algorithm, its time and space complexity, then implement it.

Quick Answer: In the Coding & Algorithms domain, this prompt evaluates numerical methods and precision handling for implementing a square-root function without library support, together with in-place array manipulation, partitioning and complexity reasoning for parity-based rearrangement, testing competencies in algorithm design, numerical approximation, and space-efficient data transformations. These problems are commonly asked to assess understanding of numerical stability, error bounds and iterative approximation as well as mastery of in-place ordering/partitioning strategies and time/space complexity analysis, requiring both conceptual understanding of mathematical properties and practical implementation ability.

Part 1: Square Root Without Math Library

Given a non-negative real number x, compute its square root without using math.sqrt, pow, or the exponentiation operator. Return the answer rounded to 6 decimal places. Your algorithm should correctly handle x = 0, numbers between 0 and 1, and very large positive values.

Constraints

  • 0 <= x <= 10^12
  • Do not use math.sqrt, pow, or **
  • Absolute error before rounding should be at most about 1e-6

Examples

Input: 0.0

Expected Output: 0.0

Explanation: Edge case: the square root of 0 is exactly 0.

Input: 9.0

Expected Output: 3.0

Explanation: Perfect square.

Hints

  1. The function f(y) = y * y is monotonic for y >= 0, so binary search works well.
  2. A safe search interval is [0, max(1, x)] so that both very small and very large inputs are covered.

Part 2: Rearrange Array by Index Parity

Given an integer array arr, rearrange it in-place so that every number at a 1-based even position is strictly smaller than every number at a 1-based odd position. To make the answer deterministic for testing, if a valid rearrangement exists, return the arrangement produced by first sorting the array, then filling odd positions (1, 3, 5, ...) from left to right with the largest remaining values, and filling even positions (2, 4, 6, ...) from left to right with the smallest remaining values. If no valid rearrangement exists, return [].

Constraints

  • 0 <= len(arr) <= 2 * 10^5
  • -10^9 <= arr[i] <= 10^9
  • Use O(1) extra space beyond a few variables
  • Strict inequality is required: every even-position value must be smaller than every odd-position value

Examples

Input: [1, 2, 3, 4, 5]

Expected Output: [5, 1, 4, 2, 3]

Explanation: Largest remaining values go to positions 1, 3, 5 and smallest remaining values go to positions 2, 4.

Input: []

Expected Output: []

Explanation: Edge case: an empty array is already valid.

Hints

  1. After sorting, all values that go to even positions must come from the lower half, and all values that go to odd positions must come from the upper half.
  2. If you want O(1) extra space after sorting, think about encoding both the old and new value inside the same array cell.

Loading coding console...