[Summer 2025] Core Engineering Intern Test

Round 1

Questions:

1. Problem 1: Easy

2. Problem 2: Code: TLE 9/14 passed

   #include <bits/stdc++.h>
   using namespace std;
   
   // Function to generate all super bit strings from an integer bit representation
   void generateSuperBitStrings(int bitString, unordered_set<int> &uniqueStrings) {
       uniqueStrings.insert(bitString);  // Insert original bit string
   
       int mask = 0;
       for (int i = 0; i < 18; i++) { // Generate bit mask with all 1s in 'n' bits
           if (!(bitString & (1 << i))) { // Check if bit i is 0
               mask |= (1 << i);
           }
       }
   
       // Generate all possible super bit strings using the mask
       int numFlips = __builtin_popcount(mask);  // Count zeros (possible flips)
       int totalSubsets = 1 << numFlips;  // 2^numFlips possible bit flips
   
       vector<int> zeroPositions;
       for (int i = 0; i < 18; i++) {
           if (mask & (1 << i)) zeroPositions.push_back(i);
       }
   
       for (int subset = 1; subset < totalSubsets; subset++) {
           int newBitString = bitString;
           for (int j = 0; j < zeroPositions.size(); j++) {
               if (subset & (1 << j)) {
                   newBitString |= (1 << zeroPositions[j]);  // Flip 0 to 1
               }
           }
           uniqueStrings.insert(newBitString);
       }
   }
   
   // Main function to compute the number of unique super bit strings
   int superBitstrings(int n, vector<int> &bitStrings) {
       unordered_set<int> uniqueSuperBitStrings;  // Use unordered_set for O(1) insert & lookup
   
       for (int num : bitStrings) {
           generateSuperBitStrings(num, uniqueSuperBitStrings);
       }
   
       return uniqueSuperBitStrings.size();
   }
   
   // Driver function
   int main() {
       int n = 18;  // Bit length
       vector<int> bitStrings = {10, 26, 262143};  // Example input
   
       cout << "Total unique super bit strings: " << superBitstrings(n, bitStrings) << endl;
       return 0;
   }

3. Problem 3: Code: Accepted

   #include <bits/stdc++.h>
   using namespace std;
   
   // Structure to store call details
   struct Call {
       int start, end, volume;
   };
   
   // Binary search function to find the last non-overlapping call
   int findLastNonOverlapping(vector<Call>& calls, int index) {
       int low = 0, high = index - 1, result = -1;
       
       while (low <= high) {
           int mid = (low + high) / 2;
           if (calls[mid].end < calls[index].start) {
               result = mid;
               low = mid + 1;  // Look for a later valid call
           } else {
               high = mid - 1;
           }
       }
       return result;
   }
   
   // Function to calculate the maximum possible order volume
   int phoneCalls(vector<int> start, vector<int> duration, vector<int> volume) {
       int n = start.size();
       vector<Call> calls(n);
   
       // Step 1: Store and sort calls by end time
       for (int i = 0; i < n; i++) {
           calls[i] = {start[i], start[i] + duration[i], volume[i]};
       }
       sort(calls.begin(), calls.end(), [](Call a, Call b) {
           return a.end < b.end;
       });
   
       // Step 2: Dynamic Programming
       vector<int> dp(n, 0);
       dp[0] = calls[0].volume;
   
       for (int i = 1; i < n; i++) {
           // Include current call
           int include = calls[i].volume;
           int lastNonOverlap = findLastNonOverlapping(calls, i);
           if (lastNonOverlap != -1) {
               include += dp[lastNonOverlap];
           }
   
           // Exclude current call
           int exclude = dp[i - 1];
   
           // Take the maximum value
           dp[i] = max(include, exclude);
       }
   
       return dp[n - 1];
   }
   
   // Driver function
   int main() {
       vector<int> start = {10, 5, 15, 18, 30};
       vector<int> duration = {30, 12, 20, 35, 35};
       vector<int> volume = {50, 51, 20, 25, 10};
   
       cout << "Maximum Order Volume: " << phoneCalls(start, duration, volume) << endl;
       return 0;
   }