🚀 MoEngage Interview DSA Questions

Sharing a couple of interesting problems asked in my interview with MoEngage 👇

🧩 1. Valid Parenthesis String

Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.

The following rules define a valid string:

• Any left parenthesis '(' must have a corresponding right parenthesis ')'.

• Any right parenthesis ')' must have a corresponding left parenthesis '('.

• Left parenthesis '(' must go before the corresponding right parenthesis ')'.

• '*' could be treated as:

  • a single right parenthesis ')', or
  • a single left parenthesis '(', or
  • an empty string "".

Example 1:
Input: s = "()"
Output: true

Example 2:
Input: s = "((*)"
Output: true

🚗 2. Car Fleet

There are n cars at given miles away from the starting mile 0, traveling to reach the mile target.

You are given two integer arrays position and speed, both of length n, where:

• position[i] is the starting mile of the i-th car.
• speed[i] is the speed of the i-th car in miles per hour.

A car cannot pass another car, but it can catch up and then travel next to it at the speed of the slower car.

A car fleet is a single car or a group of cars driving together at the same speed.

If a car catches up to a fleet at the destination point, it is still considered part of the fleet.

Return the number of car fleets that will arrive at the destination.

Example:
Input:
target = 12
position = [10,8,0,5,3]
speed = [2,4,2,1,3]

Output: 3

🔥 Good mix of greedy + stack thinking. Try solving without brute force!

Let me know your approach 👇