Katkat
Back

Implement sqrt and parity-based array rearrangement

DeshawMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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.