💼 Mindtickle SDE-1 | DSA Interview Round

This round involved two algorithmic questions designed to assess problem-solving skills, understanding of data structures, and the ability to optimize for time and space complexity.

🧗 Problem 1: Farthest Reachable Hill

📄 Problem Statement:

You're on a hiking expedition across a series of hills, represented by an array elevations, where each element indicates the height of a hill. Starting from hill 0, your objective is to travel as far as possible using a limited number of grappling hooks and a stockpile of climbing gear units.

🔁 Movement Rules:

To move from hill i to hill i + 1:

• If the next hill is at the same height or lower, you can walk without using any equipment.

• If the next hill is higher, you must either:

  • Use one grappling hook, or
  • Spend a number of climbing gear units equal to the elevation gain:
    (elevations[i+1] - elevations[i]).

You may choose when to use grappling hooks or climbing gear. The objective is to plan your resource usage wisely to reach the farthest hill possible.

✅ Function Signature:

int furthestHillIndex(vector<int>& elevations, int climbing_gears, int grappling_hook);

🧪 Sample Inputs & Expected Outputs:

• Input: elevations = [4,2,7,6,9,14,12], climbing_gears = 5, grappling_hook = 1
  Output: 4

• Input: elevations = [14,3,19,3], climbing_gears = 17, grappling_hook = 0
  Output: 3

• Input: elevations = [3,11,7,11,15], climbing_gears = 8, grappling_hook = 1
  Output: 4

⚖️ Problem 2: Balanced Substring Replacement

📄 Problem Statement:

You are given a string S consisting only of the characters 'A', 'B', 'C', and 'D'. The length of the string is always a multiple of 4 (i.e., length = 4 * N for some positive integer N).

A string is considered balanced if every character 'A', 'B', 'C', and 'D' appears exactly N times.

Your task is to find the minimum length of a contiguous substring that can be replaced with any arbitrary sequence (of the same length) such that the entire string becomes balanced.

✅ Function Signature:

int minSubstringToBalance(string s);

🎯 Objective:

Identify the shortest substring to replace, so that the final string has an equal number of each character, i.e., count('A') = count('B') = count('C') = count('D') = N.

🧪 Sample Inputs & Expected Outputs:

• Input: "AAAABBCD"
  Output: 2
  (Replace "AA" with "CD")

• Input: "ABBBADAA"
  Output: 3

• Input: "BACD"
  Output: 0
  (Already balanced)

📌 Notes:

• These problems are on greedy strategies, priority queues, and sliding window techniques.
• Be ready to explain time and space complexities, and discuss trade-offs in different solution approaches.

📌 Update

even after solving both the questions in time and with excepted time and space complexities , I was not shortlisted further and no proper feedback is provided as well.