Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
1,212 views
in Online Assessments by Expert (46,090 points) | 1,212 views

2 Answers

0 like 0 dislike
Best answer

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

 

by Expert (46,090 points)
0 like 0 dislike

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;
}

 

 

by Expert (46,090 points)

Get best answers to any doubt/query/question related to programming , jobs, gate, internships and tech-companies. Feel free to ask a question and you will receive the best advice/suggestion related to anything you ask about software-engineering , development and programming problems .