Bir simli başqa bir simliyə görə çeşidləyin

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

İki giriş sətri, naxış və sətir verilmişdir. Sıralamalıyıq sim naxışla müəyyən edilmiş sıraya görə. model sətrin təkrarı yoxdur və sətrin bütün simvolları var.

Giriş Formatı

Bir s sətrini ehtiva edən ilk sətir, ehtiyacımız var cür.

Təkrarlanan olmayan bir sətir t olan və s sətrinin bütün simvollarına sahib ikinci sətir.

Çıxış formatı

T sətri əsasında sıralanmış sətri çap edin.

Məhdudiyyətlər

• 1 <= | s |, | t | <= 10 ^ 6
• s [i] və t [j] yalnız kiçik hərf olmalıdır.

misal

abcedabdceade
ebcda

eeebbccdddaaa

Explanation: Burada əvvəlcə sayırıq tezliyi s sətrində mövcud olan hər bir char. Beləliklə, yuxarıdakı s = “abcedabdceade” nümunəsi ilə asanlıqla 'a' frekansının 3, 'b' nin tezliyinin 2, 'c' nin tezliyinin 2, d-nin frekansının 3 və e-nin frekini asanlıqla əldə edə bilərik. 3-dir. Beləliklə, indi t sətrini keçirik və bu cədvəlin tezliyini yoxlayırıq və dəfələrlə yazdırırıq, sətirlə növbəti sətrə keçirik və t eyni addımları sona qədər təkrarlayırıq, nəhayət, sıralanmış simli əldə edirik. s = “eeebbccdddaaa”.

Alqoritm

1. Giriş sətrinin simvol sayını tez [] serial.
2. T simli soldan sağa keçin, hər bir t [i] işarəsi üçün onun sayına baxın.
3. Bu yazını dəfələrlə çap edin.
4. Bunu naxış ipinin sonuna qədər edin.

Bir simli başqa bir simliyə görə sıralamaq üçün tətbiqetmə

Bir simli başqa bir simliyə görə sıralamaq üçün C ++ proqramı

#include <bits/stdc++.h>
using namespace std;
 
void SortByPattern(string &s, string t)
{
    int freq[26] = {0};
    int n=s.length();
    int m=t.length();
    for(int i=0;i<n;i++)
    {
        freq[s[i]-'a']++;
    }
    int index = 0;
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<freq[t[i]-'a'];j++)
        {
            s[index]=t[i];
            index++;
        }
    }
}

int main()
{
    string s,t;
    cin>>s>>t;
    SortByPattern(s,t);
    cout<<s<<endl;
    return 0;
}

import java.util.Arrays;
import java.util.Scanner;

class sum {
    
    static void SortByPattern(String s, String t)
    {
       int n = s.length();
       int m = t.length();
       char[] s1 = s.toCharArray();
       char[] t1 = t.toCharArray();
       int freq[] = new int[26];
       Arrays.fill(freq, 0);
       for(int i=0;i<n;i++)
       {
           freq[s1[i]-'a']++;
       }
       int index=0;
       for(int i=0;i<m;i++)
       {
           for(int j=0;j<freq[t1[i]-'a'];j++)
           {
               s1[index]=t1[i];
               index++;
           }
       }
       for(int i=0;i<n;i++)
       {
           System.out.print(s1[i]);
       }
    }
    public static void main(String[] args) 
    {
        Scanner sr= new Scanner(System.in);
        String s = sr.next();
        String t = sr.next();
        SortByPattern(s,t);
    } 

abcabcabc
bxyzca

bbbcccaaa

Bir simli başqa bir simliyə görə sıralamaq üçün komplekslik analizi

Zamanın mürəkkəbliyi

O (N) hara N verilən s massivinin ölçüsüdür. Burada bizi xətti zaman mürəkkəbliyinə aparan s cərgələrini keçirik.

Kosmik Mürəkkəblik

O (1) çünki burada heç bir köməkçi yerdən istifadə etmirik.