Simli yenidən təşkil edin

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon eBay Facebook google microsoft Kvalifikasiya
Görməmiş Yığın çeşidləyici SimBaxılıb 82

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.

In Simli yenidən təşkil edin problem verdik sim yalnız “az” işarələrindən ibarətdir. Bizim vəzifəmiz bu simvolları elə düzəltməkdir ki, iki eyni simvol bir-birinə bitişik olmasın.

misal

Input

alma

Buraxılış

pelpa

Input

kitab

Buraxılış

obko

Input

aa

Buraxılış

Mümkün deyil

Input

aab

Buraxılış

Mümkün deyil

Yenidən Düzəltmə üçün İzahat

Bu problemi həll etmək üçün ən yüksək tezlik xarakterini birinci yerə qoymalı olduğumuz maksimum yığını istifadə edərək prioritet növbə tətbiq edəcəyik (xəsislik yanaşması). Bundan sonra, bütün simvolları prioritet növbəmizə / maks yığına qoyacağıq və tezliklərinə görə sıralanacağıq (kökündəki ən yüksək tezlik xarakteri). Ən yüksək tezlikli simvol yığından alınacaq və nəticələnən sətrə əlavə olunacaq. Bu xarakterin tezliyi azaldılacaq və həmin prioritet növbədən kənarda qalacaq.

Simli Yenidən Düzəltmə Alqoritmi

  1. Maksimum yığın istifadə edərək prioritet növbəni başladın, “Pq” xarakteri özləri ilə saxlayacaq tezliklərin.
  2. Nəticə sətrində əvvəllər ziyarət edilmiş element kimi işləyəcək müvəqqəti bir açar yaradın. Başlayın {char = '$', freq = -1}
  3. Isə “Pq” boş deyil
    1. Bir element atılacaq və nəticəyə əlavə olunacaq.
    2. Yaranan elementin tezliyini 1-ə endir.
    3. Əvvəlki elementi tezliyi> "0" olduqda yenidən prioritet növbəsinə çəkin.
    4. Mövcud elementi növbəti təkrar üçün əvvəlki element kimi et.
  4. Orijinal simli ilə nəticələnən simlin uzunluğu bərabər deyilsə, "Mümkün deyil" yazdırın. Başqa çap nəticəsi.

Əvvəlcə simvolların tezliyini saxlaya biləcəyimiz bir sinif adı açarı edirik. Bundan sonra, müqayisə metodumuzu müqayisə etmə metodumuzu ləğv edirik ki, bütün xarakterləri tezliklərinə görə sifariş edə bilərik. Sonra prioritet növbə qurduğumuz ipi yenidən düzəltmək üçün bir iş görürük “Pq” içindəki simvolları saxlamaq və tezliklərinə görə xarakter sifariş etmək və sonra növbəmizi keçmək üçün keycomparator () sinifindən istifadə etmək döngə zamanı Beləliklə, simvolları yenidən düzəldə bildik və nəhayət yenidən düzəldilmiş simli əldə etmək üçün orijinal simli və nəticələnən simli ölçüsünü müqayisə edə bildik.

C ++ dilində tətbiq

#include<iostream>
#include<queue>

using namespace std;

const int MAX_CHAR = 26;
struct Key
{
    int freq; // store frequency of character
    char ch;
    // function for priority_queue to store Key
    // according to freq
    bool operator<(const Key &k) const
    {
        return freq < k.freq;
    }
};

// Function to rearrange character of a string
// so that no char repeats twice
string Rearrange_String(string str)
{
    int original_size = str.length();
    // Store frequencies of all characters in string
    int count[MAX_CHAR] = {0};
    for (int i = 0 ; i < original_size; i++)
        count[str[i]-'a']++;
    // Insert all characters with their frequencies
    // into a priority_queue
    priority_queue< Key > pq;

    for (char c = 'a' ; c <= 'z' ; c++)
    {
        if (count[c-'a'])
        {
            pq.push( Key { count[c-'a'], c} );
        }
    }
    // 's' that will store resultant value
    string s = "" ;

    // work as the previous visited element
    // initial value for previous element be. ( '$' and
    // it's freq '-1' )
    Key prev {-1, '$'} ;
    // traversing queue
    while (!pq.empty())
    {
        // pop the top element from queue
        // add it to string 's'.

        Key k = pq.top();
        pq.pop();
        s = s + k.ch;

        // If frequency of previous character < 0
        // we need not to push it
        if (prev.freq > 0)
            pq.push(prev);

        // make current character as the previous character
        // decrease frequency by 1
        (k.freq)--;
        prev = k;
    }
    // If length of the final string and original
    // string is not same then it is not possible to rearrange.
    if (original_size != s.length())
        return "Not Possible";
    else
        // valid string
        return s;
}
// main function to test above function
int main()
{
    string str = "apple" ;
    cout<<Rearrange_String(str);
    return 0;
}
plaep

Java-da tətbiqetmə

/* Java program to Reorganize string in such manner,
there should no same two adjacent string
*/
import java.io.*;
import java.util.*;

class Key {
  int freq; // store frequency of character
  char ch;
  Key(int val, char c) {
    freq = val;
    ch = c;
  }
}

class KeyComparator implements Comparator<Key> {

  // Overriding compare()method of Comparator
  public int compare(Key k1, Key k2) {
    if (k1.freq<k2.freq)
      return 1;
    else if (k1.freq > k2.freq)
      return -1;
    return 0;
  }
}

class reorganize_string {
  static int MAX_CHAR = 26;

  // Function to rearrange character of a string
  // so that no char repeats twice
  static String Rearrange_String(String str) {
    int original_size = str.length();

    // Store frequencies of all characters in string
    int[] count = new int[MAX_CHAR];

    for (int i = 0; i<original_size; i++)
      count[str.charAt(i) - 'a']++;

    // Insert all characters with their frequencies
    // into a priority_queue
    PriorityQueue<Key> pq = new PriorityQueue<>(new KeyComparator());
    for (char c = 'a'; c<= 'z'; c++) {
      int val = c - 'a';
      if (count[val] > 0)
        pq.add(new Key(count[val], c));
    }

    // 's' that will store resultant value
    String s = "";

    // work as the previous visited element
    // initial value for previous element be. ( '$' and
    // it's freq '-1' )
    Key prev = new Key(-1, '$');

    // traversing queue
    while (pq.size() != 0) {

      // pop the top element from queue
      // add it to string 's'.
      Key k = pq.peek();
      pq.poll();
      s = s + k.ch;

      // If frequency of previous character<0
      // we need not to push it
      if (prev.freq > 0)
        pq.add(prev);

      // make current character as the previous character
      // decrease frequency by 1
      (k.freq) --;
      prev = k;
    }

    // If length of the final string and original
    // string is not same then it is not possible to rearrange.
    if (original_size != s.length())
      return "Not Possible";
    else
      return s;
  }

  // main func to test above function
  public static void main(String args[]) {
    String str = "apple";
    System.out.println(Rearrange_String(str));
  }
}
pelpa

Simli Yenidən Düzəltmək üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (n log A) burada n simli uzunluq və A əlifbaların ölçüsüdür

Kosmik Mürəkkəblik

O (A) burada A əlifbaların ölçüsüdür.

References

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