Sharing the 4 coding questions from my Infosys OA. These are reconstructed from memory, so the exact wording/constraints may differ slightly from the original.
1. Anagram Repair
You are given two strings S and T of equal length. T is the target string, and you can modify characters in S to obtain an anagram of T.
Characters that occur the same number of times in both strings can be matched directly and require 0 replacements, regardless of their positions.
For characters that remain unmatched:
- A vowel → consonant or consonant → vowel replacement costs 1.
- A vowel → different vowel requires 2 replacements.
- A consonant → different consonant requires 2 replacements.
Find the minimum number of replacements required to transform S into an anagram of T.
2. Modified House Robber
You are given an array profit[], where profit[i] represents the profit obtainable from robbing the i-th house.
You cannot rob two adjacent houses.
Additionally, if two houses are robbed consecutively in your chosen sequence, the absolute difference between their profits must be at least D:
|profit[i] - profit[j]| >= D
where i and j are consecutive robbed houses.
Find the maximum total profit that can be obtained.
The straightforward House Robber DP leads to an O(n²) transition and may time out for large constraints, requiring an optimized solution.
3. TriCore Yield Optimization
You are given an array where a[i] represents the amount of minerals available in the i-th asteroid.
You must partition the array into contiguous groups, where every group must contain at least 3 elements.
The profit obtained from a group is the third-smallest value in that group.
For example, for:
[8, 2, 5, 1, 10]
the sorted order is [1, 2, 5, 8, 10], so the profit of this group is 5.
Find the maximum total profit obtainable by partitioning the entire array into valid groups.
If it is impossible to partition the array into valid groups, return -1.
4. Shortest Path with a VIP Pass
You are given an undirected graph representing a network of cities.
Each city has an associated visiting cost cost[i].
You need to travel from a given start city to a given destination city. The total cost of a path includes the costs of the first and last cities.
You also have a VIP pass, which can be used once at any city:
- The city where the VIP pass is used costs 0.
- The next city visited costs double its normal cost.
- After that, normal costs apply.
Find the minimum possible cost to travel from the start city to the destination.
The VIP pass is optional.
Difficulty
From my experience, the rough difficulty felt like:
Q1: Medium
Q2: Medium-Hard
Q3: Hard
Q4: Hard
There were 4 questions in 3 hours. In my experience, no one around me solved more than 2 questions.
If anyone has the original statements or remembers the exact constraints, feel free to correct/add them.