Summary
Infosys OA with 4 coding problems in 3 hours. The questions ranged from medium to hard and from what I saw around me, finishing more than 2 was basically unheard of.
Questions Asked(4)
This one felt manageable at first.
Suggested Approach
Start by computing the character frequency difference between S and T to identify which characters are in surplus and which are in deficit. Then categorize the surplus characters into vowels and consonants, and greedily match cross-category replacements (cost 1) before handling same-category replacements (cost 2). This greedy approach minimizes total cost by always preferring cheaper operations first.
Compute Character Frequency Differences
Build frequency maps for both S and T, then compute the net surplus/deficit for each character (freq[S][c] - freq[T][c]). Positive values indicate characters S has in excess; negative values indicate characters S needs more of.
Separate Surplus by Category
Partition the surplus characters (those with positive difference) into two buckets: surplus vowels and surplus consonants. Similarly, partition the deficit characters into deficit vowels and deficit consonants.
Apply Cross-Category Replacements (Cost 1)
Match surplus vowels against deficit consonants, and surplus consonants against deficit vowels. Each such pairing costs 1 and resolves one unit of imbalance on each side — apply as many of these as possible first.
Apply Same-Category Replacements (Cost 2)
Handle any remaining surplus vowels paired with deficit vowels, and remaining surplus consonants paired with deficit consonants. Each such replacement costs 2 since it stays within the same character category.
Sum and Return Total Cost
Accumulate the costs from both phases and return the total. Verify your solution with edge cases such as strings that are already anagrams (cost 0) or strings composed entirely of vowels or consonants.
Key Points to Mention
Classic house robber DP breaks down here because the extra constraint makes transitions O(n²) and that's too slow.
Suggested Approach
Treat this as a dynamic programming problem where the state must track both the current house index and the last robbed house index (or its profit value) to enforce both the adjacency and profit-difference constraints. Define dp[i][j] as the maximum profit when considering house i with house j being the most recently robbed house, then build transitions carefully. Clearly articulate the state space, transition logic, and how the two constraints interact before coding.
Clarify Constraints & Examples
Confirm input size, whether profits can be negative, and what D represents. Walk through a small example (e.g., [2, 7, 9, 3, 1], D=3) to validate your understanding of both constraints before designing a solution.
Define the DP State
Define dp[i][j] as the maximum profit achievable up to house i where house j was the last robbed house (j < i). This two-dimensional state captures both which house we are at and what the last robbed profit was, enabling enforcement of the |profit[i] - profit[j]| >= D constraint.
Formulate Transitions
For each house i and each valid previous house j (where i - j >= 2 and |profit[i] - profit[j]| >= D), set dp[i][j] = max(dp[i][j], dp[j][k] + profit[i]) for all valid k. Also handle the base case where house i is the first house robbed: dp[i][-1] = profit[i].
Analyze Complexity & Optimize
Identify that the naive approach is O(n³) time and O(n²) space, then discuss whether sorting or pruning can reduce constant factors. Mention that for large n, segment trees or sorted structures could optimize the inner lookup, demonstrating awareness of scalability.
Code, Test & Edge Cases
Implement the solution cleanly, then test against edge cases: all houses skipped (answer is 0 or best single house), D=0 (reduces to classic house robber), negative profits, and arrays of size 1 or 2. Verbally trace through your example to verify correctness.
Key Points to Mention
Hardest one for me.
Suggested Approach
Recognize this as a dynamic programming problem where you build up an optimal solution by deciding where to place partition boundaries. Define dp[i] as the maximum profit achievable from the first i elements, then for each position i, try all valid group endings (groups of size >= 3) and use the third-smallest element of that group as the profit contribution. Sort each candidate group or use a selection algorithm to efficiently find the third-smallest value.
Clarify Constraints & Edge Cases
Ask about array size, value ranges, and confirm what 'third-smallest' means for groups of exactly 3 (it's the maximum of the group). Identify the base case: if the array has fewer than 3 elements, return -1 immediately.
Define the DP State
Let dp[i] represent the maximum total profit using the first i elements with a valid partition, initialized to -infinity (invalid). dp[0] = 0 as the base case (empty array, zero profit).
Transition: Enumerate Valid Groups
For each index i (1-indexed), iterate over all starting points j such that the group [j..i] has at least 3 elements. If dp[j-1] is valid, compute the third-smallest of the subarray and update dp[i] = max(dp[i], dp[j-1] + third_smallest(j, i)).
Efficiently Find Third-Smallest
As you extend the left boundary j leftward from i, maintain a sorted structure (e.g., insertion into a sorted list or a max-heap of size 3) to track the third-smallest incrementally, avoiding a full sort for each subarray.
Return Result & Analyze Complexity
Return dp[n] if it's valid (not -infinity), otherwise return -1. Discuss time complexity: O(n²) for the DP transitions with O(n log n) for sorting per transition in the naive case, and how incremental tracking improves this.
Key Points to Mention
Dijkstra with extended state, basically.
Suggested Approach
Model this as a modified Dijkstra's shortest path problem where the state includes not just the current city but also whether the VIP pass has been used and whether the next city's cost should be doubled. Extend the state space to (city, vip_used, next_doubled) and run Dijkstra over this augmented graph to find the globally optimal cost. This cleanly handles the pass's side effect without requiring exhaustive search.
Clarify the Problem Constraints
Confirm key details: is the graph weighted by node visit costs only (no edge weights), can the VIP pass be used on the start or end city, and is the graph connected? Clarifying these prevents wasted effort on wrong assumptions.
Define the Augmented State Space
Represent each state as a tuple (current_city, vip_used: bool, next_cost_doubled: bool) to capture all relevant information at any point in the traversal. This transforms the problem into a standard shortest path on a larger but well-defined state graph.
Model State Transitions and Costs
For each state, enumerate transitions: moving to a neighbor without using the pass, or using the pass on the current city (making it free but flagging the next city for double cost). Carefully compute the cost of entering each neighbor based on the 'next_cost_doubled' flag.
Run Dijkstra on the Augmented Graph
Apply Dijkstra's algorithm using a min-heap over the augmented states, initializing with the start city's cost (considering pass usage options). Track visited states to avoid reprocessing and extract the minimum cost when the destination is reached.
Analyze Complexity and Edge Cases
State space is O(N × 2 × 2) = O(N), so overall complexity is O(N log N) with a binary heap, which is efficient. Discuss edge cases: using the pass on the last city (no doubling penalty applies), using it on the start city, and graphs with a single node.
Key Points to Mention
Discussion(3)
Sign in to join the discussion.
Your state definition is basically there. The state I'd use is (node, pass_used, is_doubled) where is_doubled means the current node's cost is doubled because the previous node used the VIP pass. Three binary flags, so 4 possible (pass_used, is_doubled) combinations per node. The cost to enter a node is node_cost * 2 if is_doubled, else node_cost. When you move to a neighbor without using the pass, is_doubled becomes false. When you use the pass on the current node (making it free) and move to a neighbor, that neighbor gets is_doubled = true and pass_used = true.
One thing worth being careful about: "using the pass on a city makes that city free" means you're zeroing the current node's cost, not the next one. So the pass affects where you are now, and the doubling hits wherever you go next. Run Dijkstra over the (node, pass_used, is_doubled) state space with a priority queue on accumulated cost. Start state is (start, false, false) with cost = start_cost. The answer is the minimum cost across all states (destination, *, *). State space is O(4n) which is fine.
Your instinct on the greedy ordering is right. The key insight is that a vowel-consonant mismatch pair costs 1 to fix but eliminates two surplus characters simultaneously, so you want to exhaust those before touching same-category pairs. Concretely: compute frequency difference arrays for vowels and consonants separately, sum the absolute surpluses in each group, then pair cross-category surpluses first. Each cross pair costs 1 and reduces both surpluses by 1. Whatever same-category surplus remains after that costs 2 per pair.
The implementation fumble you mentioned is almost always the same bug: people forget that the cross-category pairing quantity is min(vowel_surplus, consonant_surplus), not their sum. I made exactly that mistake on a similar problem and got a wrong answer on a case where one category had way more surplus than the other. The leftover from the larger group still needs same-category swaps at cost 2, and forgetting to add that in is where the count goes wrong. For an Infosys SWE OA under time pressure, getting the frequency counting right and handling that min() boundary cleanly is probably enough to clear whatever partial threshold they set.
The third-smallest detail is actually the key insight that unlocks the DP. For any group of k elements (k >= 3), if you sort those elements, the third-smallest is index 2. Crucially, adding more elements to a group can only keep or lower the third-smallest value, never raise it. So you always want groups of exactly 3 if you're trying to maximize, because larger groups risk burying a high value further down the sorted order.
That means the DP simplifies a lot: dp[i] = best profit partitioning the first i elements, and you only really need to consider groups of size 3, 4, maybe a few more depending on remainder constraints. For each position i, try group sizes g from 3 up to some limit, take the subarray ending at i of length g, find its third-smallest, add dp[i-g]. The "no valid partition" case is just when n < 3 or when no combination of group sizes >= 3 sums to n, which you can precheck.
Finding the third-smallest for each candidate group efficiently: if you're iterating g from 3 upward for a fixed right endpoint, you can maintain a small sorted structure as you extend leftward. Or just accept O(g log g) per transition since g is bounded in practice. The remainder edge case (e.g., n=7 means you could do 3+4 or 4+3 but not 3+3+1) is worth handling explicitly before the main DP loop.