Bütün anaqramları sözlər ardıcıllığı ilə birlikdə çap edin

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.

Sözlər ardıcıllığını nəzərə alaraq, bütün anaqramları bir yerə yığın.

misal

Giriş: sözlər [] = [“uyğun, var, qulaq, tap, sənət, siçovul”]
Çıxış: apt, tap, are, qulaq, incəsənət, siçovul

Budur, (uyğun, vur), (var, qulaq), (sənət, siçovul) anagramlardır.

Zamanın mürəkkəbliyi: O (NMlogM + MNlogN)

Alqoritm

a. İki köməkçi massiv yaradın.

b. Biri indeksləri saxlamaq üçün indeks massivi (index []), digəri sözləri saxlamaq üçün word array.

c. Hər bir fərdi sözü ardıcıllıqla sıralayın (simvolları çeşidləyin).

d. Massiv sözünü çeşidləyin və indeksləri izləyin (uyğun).

e. Dizələri çap etmək üçün indeks massivindən istifadə edin.

Alqoritm işləyir

Giriş:

İndeks [] = [0, 1, 2, 3, 4, 5]
sözlər [] = [“uyğun, var, qulaq, tap, sənət, siçovul”]
fərdi sözləri sıralamaq,
İndeks [] = [0, 1, 2, 3, 4, 5]
sözlər [] = [“uyğun, aer, aer, uyğun, sənət, sənət”]
array sözünü sıralayın və index arrayını yeniləyin,
İndeks [] = [1, 2, 0, 3, 4, 5]
sözlər [] = [“aer, aer, apt, apt, art, art”]
indeks massivinə əsaslanan çap, Çıxış: apt, tap, are, ear, art, rat

C ++ Proqramı

#include <bits/stdc++.h>

using namespace std;

struct Word
{
    //string is word and index is its index in the array
    char* string;
    int index; 
};
 
//Array of words and its size
struct WordArray
{
    struct Word* array;
    int size;
};
 
int CompareChars(const void* a, const void* b)
{
    return *(char*)a - *(char*)b;
}

int CompareStrings(const void* a, const void* b)
{
    struct Word* a1 = (struct Word *)a;
    struct Word* b1 = (struct Word *)b;
    return strcmp(a1->string, b1->string);
}
 
void AnagramsTogether(char* words[], int size)
{
    //Copy words into word array 
    struct WordArray* wordArray =(struct WordArray*) malloc( sizeof(struct WordArray) );
    wordArray->size = size;
    wordArray->array =(struct Word*) malloc( wordArray->size * sizeof(struct Word) );
    int k;
    for (k = 0; k < size; ++k)
    {
        wordArray->array[k].index = k;
        wordArray->array[k].string = (char*) malloc( strlen(words[k]) + 1 );
        strcpy(wordArray->array[k].string, words[k] );
    }
    //sort each word of the words array
    int i;
    for (i = 0; i < size; ++i)
    {
       qsort(wordArray->array[i].string,strlen(wordArray->array[i].string), sizeof(char), CompareChars);
    }
    //sort words of the word array
    qsort(wordArray->array, size, sizeof(wordArray->array[0]), CompareStrings);
    //print words based on there indexes
    for (i = 0; i < size; ++i)
    {
        cout<<words[wordArray->array[i].index]<<", ";
    }
}
 
//Main function
int main()
{
    char* words[] = {"ear", "pat", "rat", "are", "art", "tap"};
    int size = sizeof(words) / sizeof(words[0]);
    AnagramsTogether(words, size);
    return 0;
}

Yoxla

 

 

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