SDE - 1

This problem is a variation of the "Word Break" problem, where we need to construct a string using given substrings at the minimum cost. We can solve this using Dynamic Programming (DP) + Breadth-First Search (BFS).

Step 1: Preprocessing Substrings
a) Store only those substrings that exist in the main string.
b) Discard any substring not present in the main string, as they cannot contribute to the solution.

Step 2: Graph-based Approach (BFS + DP)
a) Define a DP Array → dp[i] represents the minimum cost to form the prefix main_string[0:i].
b) Initialize dp[0] = 0 (cost of forming an empty string is 0).
c) Iterate over all positions in the main string and try to extend it using available substrings.
d) Use a BFS-like approach, treating each position as a node and substrings as edges.
e) For each valid substring, update the minimum cost required to reach that position.

Step 3: Check for Valid Completion
a) If dp[length_of_main_string] is infinity, print "Impossible" (meaning no valid formation exists).
b) Otherwise, print the minimum cost stored in dp[length_of_main_string].

1. Read the input data:- Extract the list of occupied dates and the required match days.
2. Identify free slots:- Find gaps between the given occupied dates and after the last occupied date.
3. Insert "X" markers:
a) If a gap between two occupied dates is large enough to accommodate required match days, place "X" there.
b) If not enough free slots are found, print "Impossible".
4. Output the updated sequence, marking available match days with "X".

Step 1: Count frequencies of each grade

Create a dictionary or map to store grade counts.

Iterate through the input string once.

Step 2: Find the maximum frequency

Iterate through the frequency counts.

Keep track of the highest count.

Step 3: Find grades with the maximum frequency

Collect all grades that appear the maximum number of times.

Step 4: Apply precedence rules

Among the grades with the same highest frequency,

Return the highest grade according to the precedence rule.

Step 1: I first stored the menu items using a dictionary/list of objects, where each item had an Item Code, Name, and Price.

Step 2: The interviewer asked me to allow users to input multiple items by entering their item names and quantities.

Step 3: Then, I fetched the price of each selected item from the menu and multiplied it by the quantity to calculate the cart total.

Step 4: The interviewer asked me to implement a surge fee. So, I applied a ₹50 charge if the total price was below ₹300.

Step 5: Finally, I displayed the order summary, showing the selected items, total price, and final amount payable.

Step 1: I first defined menus separately for Restaurant A and Restaurant B, storing item details individually.

Step 2: The interviewer asked me to ensure that users select a restaurant before placing an order. So, I added a prompt for Restaurant A or B.

Step 3: Then, I implemented user input handling:
a) Users could only enter item codes from the selected restaurant.
b) If an order contained mixed restaurant items (e.g., A001 and B002), the program would return an error message.

Step 4: Finally, I calculated the cart total and applied a ₹50 surge fee if the total price was below ₹300, ensuring correct pricing.

Step 1: I first defined menus separately for Restaurant A and Restaurant B, storing item details individually.

Step 2: The interviewer asked me to modify the input method, so I implemented a food name-based ordering system instead of using item codes.

Step 3: Then, I handled availability and restaurant assignment:

If an item was available in only one restaurant, it was automatically assigned.
If an item was available in both restaurants, the user was asked to choose the preferred restaurant.
Step 4: Finally, I calculated the cart total and applied a ₹50 surge fee if the total price was below ₹300, ensuring correct pricing.

Step 1: I first stored the menu data in the same format as in the main problem, keeping item details unchanged.

Step 2: The interviewer asked me to implement a time-based surge fee, so I fetched the current system time when the order was placed.

Step 3: Then, I added a time check condition:
a) If the order was placed between 10 PM (22:00) and 6 AM (06:00), a ₹50 surge fee was applied.
b) Otherwise, no surge fee was added.

Step 4: Finally, I calculated the final price and displayed the order summary based on whether the surge fee was applicable or not.

Tip 1: Use a Divide-and-Conquer Strategy
Instead of checking the balls one by one, split them into three groups and use the balance scale strategically.

Tip 2: Stepwise Approach to Solve

First Weighing: Divide the 10 balls into three groups:
a) 3 balls on the left side of the scale
b) 3 balls on the right side of the scale
c) 4 balls left aside (not weighed yet)
d) If the balance is equal → the odd ball is among the 4 left-out balls.
e) If the balance tips → the odd ball is among the 6 balls on the scale.

Second Weighing:
a) If the odd ball is among the 4 left-out balls, take 3 of them and weigh them against 3 normal balls.
b) If the odd ball is among the 6 balls on the scale, select 3 from the heavier/lighter side and weigh them against 3 other balls from the opposite side.

Third Weighing:
By now, you’ll have narrowed it down to one specific ball and can determine whether it is heavier or lighter based on the previous results.

Tip 3: Minimum Weighings Required
This puzzle can be solved in a maximum of three weighings using a logical approach instead of brute force.

Brute Force Approach (Recursive Solution):
1. Initially, I started solving this problem using a recursive approach, where for each item, I had two choices:
a) Include the item (if it fits in the knapsack).
b) Exclude the item and move to the next.
2. This method works but has exponential time complexity O(2^N), making it inefficient for large inputs.

Tip 1: Analyze the entire bill carefully and identify all the details.
Tip 2: Try to divide the schema into segments, such as Customer and Restaurant.

Tip 1: Try explaining a project that is creative and solves a real-world problem.
Tip 2: Explain the entire pipeline clearly.
Tip 3: Describe the challenges you faced and how you tackled them.
Tip 4: Make the conversation engaging and explain your project thoroughly.

Tip 1: Explain everything in detail.
Tip 2: They will provide you with a sheet, so try to explain it by writing examples for everything.

Tip 1: Explain everything in detail.
Tip 2: They will provide you with a sheet, so try to explain each item by writing examples.

Tip 1: You can explain briefly or in detail, depending on the time you have left.
Tip 2: Talk about the tech stack you used during your internship.

Tip 1: Be honest and open-minded.
Tip 2: Provide real-life examples.
Tip 3: Respect different perspectives — acknowledge that every individual brings unique strengths to a team.