Question bank › Dynamic Programming
Dsa Dynamic Programming Easy

Data Stream Clustering

You are given a sorted list of N sensor readings. You need to partition them into clusters. The cost of a cluster containing readings from index i to j is calculated as: (Reading[j] - Reading[i])^2 + K, where K is a fixed setup cost for any cluster. Minimize the total cost to cover all readings. Input Format: Line 1: N K Line 2: N sorted integers Output Format: A single integer (min cost). Example: Input: 4 10 1 5 6 10 Output: 31 Explanation: Clusters [1] and [5, 6] and [10]. Costs: (1-1)^2+10=10, (6-5)^2+10=11, (10-10)^2+10=10. Total 31.

Key concepts

dynamic_programmingsegmentation

Practise this out loud — free

Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.

🎙 Practise this question now
Part of InterviewLab's verified interview question bank. We show the prompt and concepts to practise with — never a copy-paste solution.