← Cohesity Interview Insights

Cohesity·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026

Summary

Interviewed for a software engineer role at Cohesity and got a classic backtracking problem. Nothing too wild but it required getting the recursion right under pressure.

Questions Asked (1)

Q1

Given an array of distinct positive integers and a target value, find all unique combinations of numbers from the array that sum to the target. A number can be used more than once, and combinations that contain the same numbers in different orders count as duplicates.

Algorithms & Data Structures
Author's notes

Knew it was backtracking pretty fast but then spent way too long second-guessing how to avoid duplicate combinations.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a backtracking algorithm to explore all possible combinations, starting from each element and allowing reuse of the same element. Sort the array first to handle duplicates and ensure combinations are generated in a consistent order, avoiding permutations. At each step, recursively add numbers to the current combination, subtract from the remaining target, and backtrack when the target is reached or exceeded.

Pro tip: Emphasize that sorting the input and using a start index in recursion prevents duplicate combinations, which is crucial for efficiency. Also, mention that pruning branches when the remaining target is less than the current number can significantly reduce unnecessary recursive calls.

1. Clarify and Sort

Confirm that the array has distinct positive integers and that numbers can be reused. Sort the array to enable pruning and consistent combination generation.

2. Define Recursive Backtracking

Write a recursive function that takes the current combination, remaining target, and a start index to avoid permutations. At each call, iterate through the array from the start index.

3. Explore and Prune

For each number, if it equals the remaining target, add the combination to results. If it is less, recurse with the updated target and same index (to allow reuse). If greater, break due to sorting.

4. Backtrack and Collect

After exploring a number, remove it from the current combination to backtrack. Continue until all possibilities are exhausted, ensuring no duplicate combinations are added.

5. Analyze Complexity

Discuss time complexity: O(N^(T/M)) where N is number of elements, T is target, M is minimal element, and space complexity for recursion stack and output.

Key Points to Mention

  • Backtracking as the core algorithmic technique
  • Sorting the array to handle duplicates and enable pruning
  • Using a start index to avoid generating permutations
  • Allowing reuse of the same element by not incrementing the index in recursive calls
  • Pruning branches when the remaining target is less than the current candidate
  • Time and space complexity analysis, including the impact of sorting

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.