Verilmiş bir sətrin maksimum çəki çevrilməsi

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon BlackRock ByteDance Kod milləti DE Şou Expedia JP Morgan Ola Cabs
Dinamik proqramlaşdırma SimBaxılıb 72

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Müəyyən bir simli problemin maksimum çəki çevrilməsində, yalnız 'A' və 'B' iki simvoldan ibarət bir simli verildiyi bildirilir. Hər hansı bir işarəni dəyişdirərək sətri başqa sətirə çevirə biləcəyimiz bir əməliyyat var. Beləliklə bir çox transformasiya mümkündür. Bütün mümkün transformasiyalardan maksimum çəki çevrilməsinin ağırlığını tapın.

Alqoritm

Weight of string = weight of total pairs + weight of single characters - total number of toggles.
Two different consecutive characters are considered as pairs.
Weight of single pair (both characters are different) = 2
Weight of single character = 1
(These values are just some random values and can be taken as input)

misalVerilmiş bir sətrin maksimum çəki çevrilməsiPin

BA
2

Explanation:

“AA” simli üçün dörd imkan var ki, bunlara çevrilə bilər:

AB → 2 - 1 = 1

BA → 2 - 1 = 1

AA → 2

BB → 2

Bütün bu transformasiyalar eyni ağırlığa malik olduğundan, mümkün dəyişikliklərdən birini seçə bilərik.

BAA
3

İzahat: Cəmi 8 transformasiya var, bunlardan bir cüt və bir simvollu transformasiyaların maksimum dəyəri var.

 

Verilmiş bir sətrin maksimum çəki çevrilməsinə yanaşma

Sadəlövh yanaşma

Hər bir xarakteri dəyişdirərək mümkün olan bütün dəyişiklikləri edirik. Bütün çevrilmələri etdikdən sonra hər çevrilmənin dəyərini tapırıq və sonra hər çevrilmənin dəyərini hesablayaraq maksimum dəyəri tapırıq.

Səmərəli yanaşma

Hesablamaları azaltmaq üçün budamadan istifadə edərək, müəyyən bir sətrin maksimum çəki çevrilməsini tapmaq üçün rekursiyadan istifadə edəcəyik. Mövcud xarakter və ikinci xarakter fərqli olsa, bu bir cütdür. Bu vəziyyətdə ya ilk simvolu dəyişdirib irəliləməyimiz, ya da simvolları dəyişdirib irəliləməməyimiz üçün iki seçimimiz var. Digər şərt cari xarakter və ikinci simvol eyni olduqda olacaqdır. Bu vəziyyətdə, xarakteri dəyişdirib bir cüt halına gətirəcəyik, yoxsa eləmirik və irəliləyirik.

İlkin (və ya orijinal) problem daha kiçik alt problemlərə çevrilə bildiyindən istifadə edəcəyik dinamik proqramlaşdırma alt problemləri saxlamaq və daha da istifadə etmək.

Kodu

Müəyyən bir simli problemin maksimum çəki çevrilməsi üçün C ++ kodu

#include<bits/stdc++.h>
using namespace std;

int pairCost, toggleCost;

int maxWeightOfTransformation(string s, vector<int> &dp, int i, int stringLength){
    //base case
    if(i>=stringLength)
        return 0;
    if(dp[i]!=-1)
        return dp[i];

    // consider current character as a single character(not a pair)
    int answer = 1 + maxWeightOfTransformation(s, dp, i+1, stringLength);
    if(i+1<stringLength){
        if(s[i]!=s[i+1])
            answer = max(pairCost + maxWeightOfTransformation(s, dp, i+2, stringLength), answer);
        else
            answer = max(pairCost-toggleCost + maxWeightOfTransformation(s, dp, i+2, stringLength), answer);
    }
    return dp[i] = answer;
}

int main()
{
    string s;cin>>s;
    cout<<"Enter pairCost and toggleCost"<<endl;
    cin>>pairCost>>toggleCost;
    int stringLength = s.size();
    vector<int> dp(stringLength, -1);
    cout << "Maximum weight of a transformation of "<<s<<" is " <<maxWeightOfTransformation(s, dp, 0, stringLength);
    return 0;
}
AB
Enter pairCost and toggleCost
2 1
Maximum weight of a transformation of AB is 2

Verilən bir sətrin maksimum çəki çevrilməsi üçün Java Kodu

import java.util.*;

class Main{
    static int pairCost, toggleCost;
    
    static int maxWeightOfTransformation(String s, int[] dp, int i, int stringLength){
        //base case
        if(i>=stringLength)
            return 0;
        if(dp[i]!=-1)
            return dp[i];
    
        // consider current character as a single character(not a pair)
        int answer = 1 + maxWeightOfTransformation(s, dp, i+1, stringLength);
        if(i+1<stringLength){
            if(s.charAt(i)!=s.charAt(i+1))
                answer = Math.max(pairCost + maxWeightOfTransformation(s, dp, i+2, stringLength), answer);
            else
                answer = Math.max(pairCost-toggleCost + maxWeightOfTransformation(s, dp, i+2, stringLength), answer);
        }
        return dp[i] = answer;
    }
    
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        System.out.println("Enter pairCost and toggleCost");
        pairCost=sc.nextInt();
        toggleCost=sc.nextInt();
        int stringLength = s.length();
        int dp[] = new int[stringLength];
        for(int i = 0;i<stringLength;i++)dp[i]=-1;
        int answer = maxWeightOfTransformation(s, dp, 0, stringLength);
        System.out.println("Maximum weight of a transformation of "+s+" is "+answer);
    }
}
AB 
Enter pairCost and toggleCost 
2 1
Maximum weight of a transformation of AB is 2

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (N)

1D DP istifadə edən bir alqoritm istifadə etdiyimizdən və vəziyyətlər arasında keçid də O (1). Bu, alqoritmi O (N) ümumi zaman mürəkkəbliyində işlədir.

Kosmik Mürəkkəblik: O (N)

Burada DP üçün 1D massivi istifadə etdik, beləliklə alqoritm O (N) kosmik mürəkkəbliyə malikdir.

Crack Sistemi Dizayn Müsahibələri
Translate »