Rippling | SDE 1 | OA
- Posted
- 6 Nov 2026
Summary
I completed the online assessment for Rippling SDE 1 which consisted of two algorithmic problems.
How it went
Q1. Given an int array, find max contiguous subsegments such that sorting subsegments sorts the array (may contain duplicates too).
Solution
Sort the array. Iterate over original and sorted array one index at a time. Maintain a frequency map, adding frequency for sorted num and subtracting for original num, whenever all frequencies are 0, we can create a subsegment. To optimize the check instead of iterating over all keys every time, maintain a counter to track how many keys have non‑zero frequencies.
Q2. Given an undirected tree rooted at 0 (each node has a char value) and queries (array). If the path from queries[i] to 0 (root) contains the nodes: queries[i], v1, v2, ..., vn, 0 how many paths queries[i] to vi exist such that the characters in the path can be rearranged to form a palindrome.
Solution
A palindrome can be formed if we have at most 1 odd‑freq character. Use a 26‑bit mask for parity of each character. Palindrome condition is (mask==0 or (mask & (mask-1)) == 0). DFS from root to calculate the prefix mask from root to all nodes. Mask of a path u→v is mask[u] ^ mask[parent[v]]. During DFS also maintain a hashmap to count valid ancestors, counting frequency of prefix masks along the DFS path. For each node, check 27 possible masks (all‑zero and the 26 masks obtained by flipping one bit) and sum them up to answer the query. Remember to decrement the mask‑frequency hashmap before backtracking.
Questions asked (2)
- 01
Maximum Contiguous Subsegments for Sorting
Data Structures & Algorithms
Given an integer array (may contain duplicates), find the maximum number of contiguous subsegments such that if each subsegment is individually sorted, the entire array becomes sorted.
- 02
Palindrome Paths in a Rooted Tree
Data Structures & Algorithms
Given an undirected tree rooted at node 0 where each node holds a character, and an array of query nodes, for each query node i consider the path from that node to the root:
queries[i], v1, v2, ..., vn, 0. Determine how many prefixes of this path (i.e., paths fromqueries[i]to each ancestorvi) can have their characters rearranged to form a palindrome.