17 hours ago

admin 1.8k

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.