PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates time-series data manipulation and vectorized pandas operations for EMA crossovers, numerical methods and error analysis for implementing a square-root approximation, combinatorial reasoning for counting polygon diagonals, and state-space problem-solving for the classic water-jug reachability puzzle.

  • medium
  • Squarepoint
  • Coding & Algorithms
  • Data Scientist

Implement EMA Crossovers and Root Solvers

Company: Squarepoint

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Solve the following coding and algorithmic problem-solving tasks. ### Task 1: Compute exponential moving average crossovers You are given a pandas DataFrame with at least these columns: - `timestamp`: observation time - `price`: asset price Write Python code using pandas to: 1. Compute a short-term exponential moving average using a span of `short_span`. 2. Compute a long-term exponential moving average using a span of `long_span`. 3. Identify timestamps where the short-term EMA crosses above the long-term EMA. 4. Identify timestamps where the short-term EMA crosses below the long-term EMA. Requirements: - Do not use an explicit Python `for` loop. - Do not use Python `min` or `max` to detect crossovers. - Prefer vectorized pandas operations. - You may use pandas exponential weighted moving average functionality. ### Task 2: Implement square root with precision Implement a function `sqrt_approx(x, eps)` that returns an approximation of the square root of a non-negative number `x` such that the absolute error is at most `eps`. Requirements: - Do not call a built-in square root function. - Handle `x = 0`, `x = 1`, and large values of `x`. - Discuss the time complexity of your method. ### Task 3: Count polygon diagonals Given a polygon with `n` vertices, compute the number of diagonals. A diagonal is a line segment connecting two non-adjacent vertices. Edges of the polygon do not count as diagonals. ### Task 4: Measure exactly four gallons You have a 3-gallon jug and a 5-gallon jug. You have unlimited water and can fill, empty, or pour between jugs. Describe a sequence of operations that leaves exactly 4 gallons in one of the jugs.

Quick Answer: This question evaluates time-series data manipulation and vectorized pandas operations for EMA crossovers, numerical methods and error analysis for implementing a square-root approximation, combinatorial reasoning for counting polygon diagonals, and state-space problem-solving for the classic water-jug reachability puzzle.

Part 1: Detect EMA Crossovers

Given two equal-length arrays, timestamps and prices, compute two exponential moving averages: a short EMA with span short_span and a long EMA with span long_span. Use EMA[0] = prices[0] and alpha = 2 / (span + 1). A bullish crossover happens at index i when the short EMA was less than or equal to the long EMA at i - 1 and becomes greater at i. A bearish crossover happens when the short EMA was greater than or equal to the long EMA at i - 1 and becomes smaller at i. Return the timestamps of all bullish and bearish crossovers.

Constraints

  • 0 <= len(timestamps) == len(prices) <= 200000
  • 1 <= short_span, long_span <= 10^6
  • timestamps are already sorted in increasing order
  • If there are fewer than 2 price points, there can be no crossover

Examples

Input: ([1, 2, 3, 4, 5], [10.0, 9.0, 11.0, 8.0, 12.0], 2, 3)

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

Explanation: The short EMA drops below at timestamp 2, rises above at 3, drops below at 4, and rises above again at 5.

Input: ([], [], 2, 3)

Expected Output: [[], []]

Explanation: Empty input has no crossovers.

Input: ([1], [100.0], 2, 5)

Expected Output: [[], []]

Explanation: A single observation cannot create a crossover.

Input: ([1, 2, 3, 4], [1.0, 2.0, 3.0, 4.0], 2, 4)

Expected Output: [[2], []]

Explanation: Both EMAs start equal. The short EMA moves above the long EMA at timestamp 2 and never crosses back.

Input: ([1, 2, 3], [5.0, 5.0, 5.0], 2, 3)

Expected Output: [[], []]

Explanation: Equal prices keep both EMAs equal, so no crossover occurs.

Hints

  1. You do not need to store all EMA values. Each new EMA only depends on the previous EMA and the current price.
  2. Track the sign of short_ema - long_ema. A crossover occurs when that sign changes across consecutive observations.

Part 2: Approximate Square Root with Precision

Implement a function that approximates the square root of a non-negative number x without using any built-in square root function. The returned value must have absolute error at most eps. For consistent judging, return the result rounded to 6 decimal places. You should correctly handle x = 0, x = 1, values between 0 and 1, and large values.

Constraints

  • 0 <= x <= 10^12
  • 10^-6 <= eps <= 1
  • Do not use math.sqrt or any other built-in square root routine

Examples

Input: (0, 1e-6)

Expected Output: 0.0

Explanation: The square root of 0 is exactly 0.

Input: (1, 1e-6)

Expected Output: 1.0

Explanation: The square root of 1 is exactly 1.

Input: (2, 1e-6)

Expected Output: 1.414214

Explanation: This is the square root of 2 rounded to 6 decimal places.

Input: (0.25, 1e-6)

Expected Output: 0.5

Explanation: This checks a value between 0 and 1.

Input: (1000000, 1e-6)

Expected Output: 1000.0

Explanation: A large perfect square should still be handled correctly.

Hints

  1. On non-negative numbers, the function f(m) = m * m is monotonic, so binary search works.
  2. If x is less than 1, the square root still lies between 0 and 1.

Part 3: Count Polygon Diagonals

A diagonal of a polygon connects two non-adjacent vertices. Given the number of vertices n in a polygon, compute how many diagonals the polygon has.

Constraints

  • 3 <= n <= 10^9
  • Use 64-bit arithmetic in languages with fixed-size integers

Examples

Input: 3

Expected Output: 0

Explanation: A triangle has no diagonals.

Input: 4

Expected Output: 2

Explanation: A quadrilateral has two diagonals.

Input: 5

Expected Output: 5

Explanation: A pentagon has five diagonals.

Input: 10

Expected Output: 35

Explanation: Using the formula n * (n - 3) / 2 gives 10 * 7 / 2 = 35.

Input: 100000

Expected Output: 4999850000

Explanation: This tests large input and the need for 64-bit arithmetic.

Hints

  1. From one vertex, you can connect to n - 3 vertices by diagonals because you must exclude the vertex itself and its two neighbors.
  2. If you count diagonals from every vertex, you count each diagonal twice.

Part 4: Measure an Exact Target with Two Jugs

You have two water jugs with capacities cap_a and cap_b gallons and unlimited water. Starting from (0, 0), you may perform these operations: fill A, fill B, empty A, empty B, pour A into B, or pour B into A. Return the shortest sequence of operations that leaves exactly target gallons in either jug. If multiple shortest solutions exist, break ties by exploring operations in this exact order: fill A, fill B, empty A, empty B, pour A B, pour B A. If it is impossible, return an empty list.

Constraints

  • 1 <= cap_a, cap_b <= 100
  • 0 <= target <= max(cap_a, cap_b)
  • The start state is always (0, 0)

Examples

Input: (3, 5, 4)

Expected Output: ['fill B', 'pour B A', 'empty A', 'pour B A', 'fill B', 'pour B A']

Explanation: This is the classic 3-gallon and 5-gallon puzzle. The final state reached is (3, 4).

Input: (3, 5, 0)

Expected Output: []

Explanation: No action is needed to have 0 gallons.

Input: (2, 4, 3)

Expected Output: []

Explanation: It is impossible because 3 is not divisible by gcd(2, 4).

Input: (3, 5, 5)

Expected Output: ['fill B']

Explanation: The target already matches the capacity of jug B.

Input: (2, 3, 1)

Expected Output: ['fill B', 'pour B A']

Explanation: Filling B and pouring into A leaves exactly 1 gallon in jug B.

Hints

  1. Think of each water state (a, b) as a node in a graph, and each allowed move as an edge.
  2. Breadth-first search gives a shortest sequence of moves. A gcd check can rule out impossible cases early.
Last updated: May 19, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Solve two coding assessment tasks - Squarepoint (hard)
  • Parse payroll file and answer queries - Squarepoint (medium)
  • Maximize revenue from inventory sales - Squarepoint (medium)
  • Maximize profit from one or many stock trades - Squarepoint (hard)