3 minutes ago

admin 1.9k

Hyderabad

Question 1: Algorithm Optimization

Problem Statement: You are given an implementation of a function which accepts as input a non-empty zero-indexed array A consisting of N integers.

The function works slowly on large input data and the goal is to optimize it so as to achieve better time and/or space complexity. The optimized function should return the same result as the given implementation for every input that satisfies the assumptions.

Examples:

• For example, given array A such that: A[0] = 4, A[1] = 6, A[2] = 2, A[3] = 2, A[4] = 6, A[5] = 6, A[6] = 1, the function returns 4.
• Also, for given array A such that: A[0] = 2, A[1] = 2, ..., A[49999] = 2, A[50000] = 2 (in other words, A[K] = 2 for each K where 0 <= K <= 50,000), the given implementation works too slow.

(Note: Candidates must analyze the hidden provided code and write an optimized version that yields the same mathematical result).

Question 2: Longest Substring with Even Frequencies

Problem Statement: Write a function that, given a string S consisting of N lowercase English letters, returns the length of the longest substring in which every letter occurs an even number of times. A substring is defined as a contiguous segment of a string. If no such substring exists, return 0.

Examples:

• 1. Given S = "bdaaadadb", the function should return 6. Substrings in which every letter occurs an even number of times are "aa", "adad", "daaada" and "aaadad". The length of the longest of them is 6.
• 2. Given S = "abacb", the function should return 0. There is no non-empty substring in which every letter occurs an even number of times.
• 3. Given S = "zthtzh", the function should return 6. Every letter in the whole string occurs an even number of times.

3 minutes ago

admin 1.9k

Hyderabad

Problem 1 Solution:

Algorithm Optimization (Distinct Elements)

Topics Involved / Prerequisites

• Hash Sets / Hash Maps
• Sorting
• Time Complexity Optimization

Overview

Based on the exact inputs and outputs provided (A = [4, 6, 2, 2, 6, 6, 1] returning 4), this is the classic "Count Distinct Elements" problem. The unoptimized hidden code is likely using a nested loop O(N^2) approach to check for duplicates, which is why an array of 50,000 identical elements times out. We need to optimize this to O(N) or O(N \log N).

Approach

We can solve this in two optimal ways:

1. Sorting: Sort the array and iterate through it, counting an element only if it is different from the previous one. This takes O(N \log N) time and O(1) space.
2. Hash Set: Insert all elements into an unordered_set. A set automatically filters out duplicates. The size of the set at the end is the number of distinct elements. This takes O(N) time and O(N) space.

Given that N = 50,000, the O(N) Hash Set approach is extremely fast and the most idiomatic way to solve this in modern C++.

Code Implementation (C++)

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

int getDistinctCount(const vector<int>& a) {
    unordered_set<int> distinct_elements;
    for (int num : a) {
        distinct_elements.insert(num);
    } 
    // The size of the set is the number of unique elements
    return distinct_elements.size();
}

Time and Space Complexity

• Time Complexity: O(N) — We traverse the array exactly once, and inserting into an unordered_set takes O(1) on average.
• Space Complexity: O(N) — In the worst-case scenario (all elements are unique), the set will store N elements.

3 minutes ago

admin 1.9k

Hyderabad

Problem 2 solution

Longest Substring with Even Frequencies

Topics Involved / Prerequisites

• Bitmasking
• Prefix States (Hash Map)
• String Manipulation

Overview

We need to find the longest substring where every character appears an even number of times. Checking every possible substring would take O(N^3) or O(N^2), which is too slow.

Instead, we can track the "parity" (even or odd count) of all 26 lowercase letters using a Bitmask. Since there are 26 letters, we can use a 32-bit integer where each bit represents a letter ('a' is bit 0, 'b' is bit 1, etc.).

• 0 means the letter has appeared an even number of times.
• 1 means the letter has appeared an odd number of times.

Approach

1. Initialize Variables: A mask initialized to 0 (meaning all letters are currently even/zero), and a Hash Map to store the first time we see a specific mask. We seed the map with map[0] = -1 to handle substrings that start from the very first character.
2. Iterate through the string: For each character at index i, toggle its corresponding bit in the mask using the XOR operator (^).
3. Check the Map: * If we have seen this exact same mask before at index j, it means the characters between j + 1 and i have perfectly canceled each other out (switched from odd back to even, or even back to odd). The length of this valid substring is i - j.
   • Update the maximum length if i - j is greater than our current maximum.
   • If we haven't seen the mask before, store it in the map with its index i.

Code Implementation (C++)

#include <iostream>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

int longestEvenSubstring(const string& s) {
    unordered_map<int, int> mask_first_index;
    
    int current_mask = 0;
    int max_length = 0;
    mask_first_index[0] = -1;
    
    for (int i = 0; i < s.length(); ++i) {
        
        int bit_pos = s[i] - 'a';
        
        // Toggle the bit using XOR
        current_mask ^= (1 << bit_pos);
        if (mask_first_index.find(current_mask) != mask_first_index.end()) {
            
            int previous_index = mask_first_index[current_mask];
            max_length = max(max_length, i - previous_index);
        } else {
            
            mask_first_index[current_mask] = i;
        }
    }
    
    return max_length;
}

Time and Space Complexity

• Time Complexity: O(N) — We iterate through the string of length N exactly once. Hash map lookups and insertions are O(1) on average.
• Space Complexity: O(\min(N, 2^{26})) — We store at most N unique bitmasks in the hash map.