Implement sqrt and parity-based array rearrangement
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.
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
ysuch thaty * yapproximatesxwithin 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.
-
You may use basic arithmetic operations (
-
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?
-
What should the function return when
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
arrof lengthn. -
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 (indices1, 3, 5, ...). - Any arrangement that satisfies this property is acceptable.
-
If we number positions starting from 1, then every element at an even position (indices
-
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).
-
Odd positions (1, 3, 5) → values
-
Input:
-
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.