just now

admin 1.9k

Hyderabad

Question 1: First Day of Subsequence

Problem Statement:

Bob has a string S and Alice has a string T. Each day, Bob takes his string S and appends it to the final string K. For example, if S is "ab" then K will also be "ab" (on the first day), then on the second day, K becomes "abab". On the third day, K becomes "ababab" and so on.

Your task is to help Alice find and return an integer value, representing the day when the string K contains T as a subsequence for the first time.

Note:

• A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
• Do not alter the order of the string while choosing a subsequence.

Input Specification:

• input1: A string value S, representing the string Bob has.
• input2: A string value T, representing the string Alice has.

Output Specification:

Return an integer value representing the day when the string K contains T as a subsequence for the first time.

Question 2: Pet Supply Store

Problem Statement:

A pet supply store uses specific unit symbols to represent quantities of different pet items, which are defined as follows:

• 'f' = bags of dog food  ₹800 per unit.
• 't' = liters of fish tank water  ₹50 per unit.
• 'c' = cat toys  ₹200 per unit.
• 'b' = boxes of pet treats  ₹1200 per unit.

You are given a string S that encodes the list of pet items, and your task is to find and return an integer value representing the total cost of all items in S.

Note: If a unit appears without a number before it, it is assumed to represent a single unit (i.e., quantity = 1). If a number is not followed by a valid unit, treat it as a plain number and add it directly to the total cost.

Input Specification:

• input1: A string S consisting of the quantities and units of 'f', 't', 'c', and 'b'.

Output Specification:

• Return an integer value representing the total cost of all items in S.

Question 3: Electric Wire Grid

Problem Statement:

You are given an integer array A of size N, where each element represents the current in a wire segment. You can invert (multiply by -1) up to X segments, but two consecutive segments cannot be inverted together due to stability constraints.

Your task is to find and return an integer value representing the maximum possible net current after applying the best inversions. If no valid inversion can be made, return the sum of the original array.

Input Specification:

• input1: An integer value N representing the number of segments.
• input2: An integer value X representing the maximum inversion segment.
• input3: An integer array A representing the current values.

Output Specification:

• Return an integer value representing the maximum possible net current after applying the best inversions. If no valid inversion can be made, return the sum of the original array.

just now

admin 1.9k

Hyderabad

Problem 1 Solution

First Day of Subsequence

Topics Involved / Prerequisites

• Two Pointers
• String Parsing
• Modular Arithmetic / Wrapping

Overview

Alice wants to know how many times Bob has to repeat his string S (creating string K) until her string T becomes a valid subsequence. Instead of actually building the massive string K in memory (which would cause a Memory Limit Exceeded error), we can simulate the process using two pointers.

Approach

1. Safety Check: First, check if every character in T exists somewhere in S. If T contains a character that S doesn't have, it's impossible to form the subsequence, and we should return -1.
2. Two Pointers Simulation: Use a pointer j to track our current position in S, and a days counter initialized to 1.
3. Iterate through T: For every character c in T, advance j until S[j] == c.
4. Wrap Around: Whenever j reaches the end of S (j == S.length()), it means we need another copy of S. We reset j to 0 and increment the days counter.

C++ Code

#include <iostream>
#include <string>

using namespace std;

int findFirstDay(string s, string t) {
    // Quick check to see if it's impossible
    for (char c : t) {
        if (s.find(c) == string::npos) {
            return -1; 
        }
    }

    int days = 1;
    int j = 0;
    int n = s.length();

    for (char c : t) {
        
        if (j == n) {
            j = 0;
            days++;
        }
        
        // Find the character in S
        while (s[j] != c) {
            j++;
            if (j == n) {
                j = 0;
                days++;
            }
        }
        // Match found, move past it for the next character search
        j++; 
    }

    return days;
}

Time and Space Complexity

• Time Complexity: O(|T| \times |S|) in the absolute worst-case search, but typically closer to O(|T| + |S|).
• Space Complexity: O(1) — No extra strings are created.

just now

admin 1.9k

Hyderabad

Problem2 Solution

Pet Supply Store

Topics Involved / Prerequisites

• String Traversal
• State Machines / Accumulators
• Conditional Logic

Overview

We need to parse a string that contains a mix of digits and specific unit characters (f, t, c, b). The challenge is handling the implicit rules: a letter without a preceding number means a quantity of 1, and numbers without a valid unit trailing them are treated as flat integer additions.

Approach

1. State Tracking: Keep a running total. Track the currently forming number (num) and a boolean flag (has_num) to know if we are currently building a multi-digit number.
2. Digit Processing: If the character is a digit, multiply the current num by 10 and add the new digit. Set has_num = true.
3. Unit Processing: If it's a letter, check our flag. If has_num is true, our quantity is num; otherwise, it's 1. Multiply the quantity by the corresponding item cost and add to total.
4. Invalid/End states: If we hit an invalid letter, we just add the plain number to the total. Finally, after the loop, if there is a leftover number that wasn't followed by any letter, add it to the total.

Code Implementation (C++)

#include <iostream>
#include <string>
#include <cctype>

using namespace std;

long long calculateTotalCost(string s) {
    long long total = 0;
    long long num = 0;
    bool has_num = false;

    for (char ch : s) {
        if (isdigit(ch)) {
            num = num * 10 + (ch - '0');
            has_num = true;
        } else {
            long long qty = has_num ? num : 1;
            
            if (ch == 'f') total += qty * 800;
            else if (ch == 't') total += qty * 50;
            else if (ch == 'c') total += qty * 200;
            else if (ch == 'b') total += qty * 1200;
            else {
                // Invalid unit: Treat previous digits as a plain number
                if (has_num) total += num;
            }
            
            // Reset state after processing a unit
            num = 0;
            has_num = false;
        }
    }
    
    // Catch any trailing plain numbers at the end of the string
    if (has_num) {
        total += num;
    }
    
    return total;
}

Time and Space Complexity

• Time Complexity: O(N) — We traverse the string exactly once.

Space Complexity: O(1) — Only a few primitive variables are used.

just now

admin 1.9k

Hyderabad

Problem 3 Solution

Electric Wire Grid

Topics Involved / Prerequisites

• Dynamic Programming
• State Constraints (No consecutive elements)

Overview

We are allowed to invert up to X values in an array to maximize the sum, but we cannot invert two adjacent items. This is a variation of the "House Robber" problem, but with negative numbers and an exact limit on operations.

Approach

1. DP State: We use two dynamic programming arrays representing the current index and the number of inversions used.
   • prev_not_inv[j] = Max sum up to the previous wire using j inversions, where the previous wire was NOT inverted.
   • prev_inv[j] = Max sum up to the previous wire using j inversions, where the previous wire WAS inverted.
2. Transitions: For each wire segment i and each possible inversion count j up to X:
   • Skip inversion: We take the max of either state from the previous step and add A[i].
   • Apply inversion: We can only transition from prev_not_inv (since no two consecutives are allowed), subtract A[i] (which is adding -A[i]), and we consume 1 inversion (j-1).
3. Result: The maximum value across all valid inversion counts 0 \le j \le X in both final states.

Code Implementation (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long maxNetCurrent(int n, int x, vector<int> a) {
    if (n == 0) return 0;
    
    const long long INF = 1e18; // Use large constant for impossible states
    
  
    vector<long long> prev_not_inv(x + 1, -INF);
    vector<long long> prev_inv(x + 1, -INF);
    
    // Base Cases for the 0th element
    prev_not_inv[0] = a[0];
    if (x >= 1) {
        prev_inv[1] = -a[0];
    }
    
    for (int i = 1; i < n; ++i) {
        vector<long long> curr_not_inv(x + 1, -INF);
        vector<long long> curr_inv(x + 1, -INF);
        
        for (int j = 0; j <= x; ++j) {
            // Option 1: Do not invert a[i]
            if (prev_not_inv[j] != -INF || prev_inv[j] != -INF) {
                curr_not_inv[j] = max(prev_not_inv[j], prev_inv[j]) + a[i];
            }
            
            // Option 2: Invert a[i] (Requires previous to NOT be inverted)
            if (j > 0 && prev_not_inv[j - 1] != -INF) {
                curr_inv[j] = prev_not_inv[j - 1] - a[i];
            }
        }
        // Move to the next wire segment
        prev_not_inv = curr_not_inv;
        prev_inv = curr_inv;
    }
    
    long long max_current = -INF;
    
   
    for (int j = 0; j <= x; ++j) {
        max_current = max({max_current, prev_not_inv[j], prev_inv[j]});
    }
    
    return max_current;
}

Time and Space Complexity

• Time Complexity: O(N . X) — We iterate through all N elements and for each, we iterate up to X allowed inversions.
•  Space Complexity: O(X) — By only keeping the previous step's states in memory, we optimize space significantly compared to an O(N . X) 2D matrix.