Question: Amazon, Recent Online Assessments Questions ( 14th August 2023) | Farewell party for Interns | Password Policy
2
Entering edit mode

ADD COMMENTlink 16 months ago PoGo 2.4k
1
Entering edit mode

question 2 Solution

void solve()
{
  int n;
  cin>>n;
  vector<string> newpass(n);
  vector<string> old(n);
  f(i,n)
  cin>>newpass[i];
  f(i,n)
  cin>>old[i];
  for(int i=0;i<n;i++)
  {
    string np=newpass[i];
    string oldpass=old[i];
    int sz1=np.size();
    int sz2=oldpass.size();
int j=0;
int k=0;
while(j<sz1 && k<sz2)
{
    char comp=np[j];
    char next=comp;
    if(comp=='z')
    {
        next='a';
    }
    else
        next++;
    if(comp==oldpass[k] || oldpass[k]==next)
        k++;
    j++;
  }
  if(k==sz2)
    cout<<"YES"<<" ";
else
    cout<<"NO"<<" ";
}
cout<<endl;



}
int32_t main()
{
 solve();        
}

 

ADD COMMENTlink 16 months ago suryansh jaiswal • 370
Entering edit mode
0

is it correct ,100%?

ADD REPLYlink 16 months ago
ImGroot
• 0
Entering edit mode
0

Yes Suryansh's solution looks correct indeed. I have added my code + explanation to make it super clear.

ADD REPLYlink 16 months ago
slime
• 350
0
Entering edit mode

Problem 1

It is too trivial, simply track number of '+' and '-' signs as you process each event and report the maximum amongst it


Problem 2

Proble in Brief
Determine if an old password can be a subsequence of a new password after applying cyclic changes to a subset of indices in the new password.
 

Core Idea

The essence of the solution lies in the observation that we don't need to generate all possible combinations of cyclic changes in the new password. Instead, we can use a two-pointer approach to simulate this. By comparing characters of the old password with either the original or the cyclically changed character of the new password, we can determine if the old password can be a subsequence of the new password with some cyclic changes.
 

Approach:

  1. For each pair of old and new passwords:
    1. Use two pointers, one for the old password and one for the new password.
    2. If the characters at the current pointers match or the next cyclic character of the new password's current character matches the old password's current character, move the pointer of the old password.
    3. If only the next cyclic character matches, mark that index.
    4. If neither matches, move the pointer of the new password.
    5. If we traverse the entire old password, return true, otherwise return false.

C++ Code:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

char nextCyclicChar(char ch) {
    if (ch == 'z') return 'a';
    return ch + 1;
}

bool isPossibleSubsequence(const string& oldPass, const string& newPass) {
    int i = 0, j = 0;
    while (i < oldPass.size() && j < newPass.size()) {
        if (oldPass[i] == newPass[j] || oldPass[i] == nextCyclicChar(newPass[j])) {
            i++;
        }
        j++;
    }
    return i == oldPass.size();
}

void arePasswordsSimilar(const vector<string>& oldPasswords, const vector<string>& newPasswords) {
    for (int k = 0; k < oldPasswords.size(); k++) {
        if (isPossibleSubsequence(oldPasswords[k], newPasswords[k])) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
}

int main() {
    vector<string> oldPasswords = {"abdbc", "accdb", "abc"};
    vector<string> newPasswords = {"baacbab", "ach", "abc"};
    arePasswordsSimilar(oldPasswords, newPasswords);
    return 0;
}

 

ADD COMMENTlink 16 months ago slime • 350

Login before adding your answer.

Similar Posts
Loading Similar Posts