Verify permutation in-place and implement fast power
Overview
This question evaluates in-place array manipulation and permutation detection alongside efficient exponentiation implementation, measuring competency in space-constrained algorithm design, correctness reasoning for duplicates and out-of-range values, numerical computation with negative and extreme exponents, and awareness of stability and overflow issues. Classified under Coding & Algorithms, it is commonly asked because it tests practical application of algorithmic complexity and resource constraints as well as conceptual understanding of edge-case handling and numerical behavior; the item emphasizes practical implementation skills with significant conceptual reasoning about correctness and robustness, English.
Tesla
Sep 6, 2025, 12:00 AM
Software Engineer
Technical Screen
Coding & Algorithms
0
0
- Given an integer list A of length n, determine whether A is a permutation of [0, 1, ..., n-1]. Do it in-place with O(
- extra space (no auxiliary boolean arrays, hash sets, or sorting). Aim for an idiomatic Python solution; prefer expressions like all/any and comprehensions where appropriate. Provide an O(n)-time approach (e.g., XOR-based or index-placement) that detects out-of-range values and duplicates, and justify correctness and edge cases.
- Implement a function power(base: float, exp: int) -> float that computes base^exp without using library exponentiation. Achieve O(log |exp|) time via exponentiation by squaring, handle negative exponents, exp = 0, base = 0, and the minimum 32-bit integer exponent. Use constant extra space (iterative solution preferred) and discuss numerical stability/overflow considerations.