Sprinklr

Sprinklr – Round 1 | Difficulty: Medium The interviewer started by asking a few basic questions about the projects mentioned on my resume. After that, we moved on to a DSA problem based on Dynamic Programming. Problem Statement: You are given an array of strings "words" and an integer array "type", where "type[i]" is either "0" or "1", corresponding to "words[i]". Find the longest subsequence satisfying the following conditions: Any two adjacent strings in the subsequence must have the same length. Any two adjacent strings must have different types. The relative order of the selected strings must be preserved. Approach and Discussion: I initially started with a recursive solution using memoization. However, since the problem also required outputting the actual subsequence and not just its length, I switched to a tabulation-based DP approach. After implementing the tabulation solution, the interviewer asked me to optimise its space complexity. I reduced the space usage as much as possible while maintaining the ability to reconstruct the subsequence. Fully reducing the solution to just one or two DP arrays was challenging because I also needed to recover the selected strings. The interviewer then gave me some hints about a more space-efficient approach using a chaining or predecessor-pointer technique to reconstruct the subsequence. With those hints, I implemented the final optimised approach. The interviewer provided a test case, and I dry-ran my solution successfully. The interview focused on DP problem-solving, space optimisation, subsequence reconstruction, and the ability to improve an initial solution based on feedback. Result: Rejected after Round 1.