Count Valid Triangle Combinations | Dataford Interview Questions

Upstart Network may evaluate groups of candidate loan attributes or offer signals using algorithms that must efficiently examine combinations. Given a list of integers representing potential triangle side lengths, count how many distinct combinations of three positions can form a valid, non-degenerate triangle.

A combination is valid when the sum of its two shorter sides is strictly greater than its longest side. Equal values at different positions are treated as distinct elements.

Formal Specification

Implement count_valid_triangles(sides).

Input: sides, a list of n positive integers.
Output: An integer equal to the number of index combinations (i, j, k) where i < j < k and sides[i], sides[j], and sides[k] can form a valid triangle.
The result counts combinations, not permutations, so each group of three indices is counted once.

Constraints

3 <= len(sides) <= 2,000
1 <= sides[i] <= 10^6
Each combination is based on distinct indices
A triangle is valid only when the two shorter sides sum to more than the longest side

Function Signature

def count_valid_triangles(sides):

Your question is Count Valid Triangle Combinations. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem