Question

Goldman Sachs | OA | US | 2022 || Set-3

Answer 1

Q1. Break Palindrome

Given a palindrome, you must change 1 character in it such that the string is not a palindrome and is lexicographically smallest.
Output the string if you are able to do so, otherwise return "IMPOSSIBLE"

Sampe Testcase:

• "aaabbaaa" -> "aaaabaaa"
• "aa" -> "IMPOSSIBLE"

Constraint:

• 1 <= N <= 1000
• the palindrome consists of only lowercase English letter

---

Q2. Pairs of Songs

Given a list of songs's durations songs[], such as [30, 60, 180], we have to find the number of pairs (i, j) where j > i such that songs[i] + songs[j] is a multiple of 60.

Constraint

• 1 <= N <= 100000
• 1 <= song[i] <= 1000

 

Answer 2

Q1) Optimized :-

 

// Time Complexity :- O(N)

// Space Complexity :- O(1)

string helper(string str)
{
    int n = str.size();
    
    for(int i = 0; i < n / 2; i++)
    {
        if(str[i] != 'a')
        {
            str[i] = 'a';
            
            return str;
        }
    }
    
    return "IMPOSSIBLE";
}

int main()
{
    cout<<helper("aaabbaaa") << endl;
    
    cout<<helper("aa") << endl;

    return 0;
}

 

 

Q2) Using Hashmap :-

 

// Time Complexity :- O(N)

// Space Complexity :- O(N)

int helper(vector<int> arr)
{
    int n = arr.size();
    
    int count = 0;
    
    unordered_map<int, int> mp;
    
    for(int i = 0; i < n; i++)
    {
        int rem = arr[i] % 60;
        
        int need = 0;
        
        if(rem != 0)
        {
            need = 60 - rem;
        }
        
        count += mp[need];
        
        mp[rem]++;
    }
    
    return count;
}

int main()
{
    cout << helper({30, 60, 180, 30, 1, 90}) << endl;
    
    return 0;
}