Sortuj ciąg według innego ciągu

Poziom trudności Łatwo
Często zadawane pytania Accenture Accolita Adobe Amazonka FreeCharge InfoEdge Microsoft Salesforce
Sortowanie sznurodwiedzajacy 327

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Problem Statement

Biorąc pod uwagę dwa ciągi wejściowe, wzorzec i ciąg. Musimy posortować ciąg zgodnie z kolejnością określoną we wzorze. Wzór ciąg nie ma duplikatów i zawiera wszystkie znaki łańcucha.

Format wejściowy

Pierwsza linia zawierająca ciąg znaków, których potrzebujemy rodzaj.

Drugi wiersz zawierający ciąg t, który nie ma duplikatów i zawiera wszystkie znaki łańcucha s.

Format wyjściowy

Wydrukuj posortowany ciąg na podstawie łańcucha t.

ograniczenia

  • 1 <= | s |, | t | <= 10 ^ 6
  • s [i] it [j] muszą być tylko małymi literami.

Przykład

abcedabdceade
ebcda
eeebbccdddaaa

Wyjaśnienie: Tutaj najpierw liczymy częstotliwość każdego znaku obecnego w ciągu s. Tak więc z powyższego przykładu s = „abcedabdceade” możemy łatwo uzyskać, że freq z 'a' to 3, freq of 'b' to 2, freq of 'c' is 2, freq of d is 3, and freq of e wynosi 3. Więc teraz przechodzimy przez ciąg t i sprawdzamy częstotliwość tego znaku i drukujemy go tyle razy i przechodzimy do następnego znaku, którego ciągi t i powtarzamy te same kroki aż do końca. W końcu otrzymujemy posortowany łańcuch s = „eeebbccdddaaa”.

Algorytm

  1. Przechowuj liczbę znaków ciągu wejściowego w pliku freq [] szyk.
  2. Przejdź przez łańcuch t od lewej do prawej, dla każdego znaku t [i] zobacz jego liczbę.
  3. Wydrukuj ten znak wiele razy.
  4. Zrób to do końca łańcucha wzoru.

Implementacja sortowania ciągu według innego ciągu

Program w C ++ służący do sortowania ciągu według innego ciągu

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

Program Java do sortowania ciągu według innego ciągu

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

Analiza złożoności sortowania ciągu według innego ciągu

Złożoność czasowa

NA) gdzie N jest rozmiarem podanej tablicy s. Tutaj przechodzimy przez struny, które prowadzą nas do liniowej złożoności czasowej.

Złożoność przestrzeni

O (1) ponieważ nie używamy tutaj żadnej dodatkowej spacji.

Wywiady dotyczące projektowania systemu pękania
Translate »