Verilən Nümunədən bütün Binary Strings yaradın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon google microsoft
SimBaxılıb 414

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

"Verilən Nümunədən Bütün İkili Sətrlər Yaradın" problemində biz məlumat verdik sim “S” 0, 1-dən və? (wildcard char). Əvəz edərək bütün mümkün ikili sətirləri yaratmalıyıq? '0' və '1' ilə.

Giriş Formatı

"S" simli olan ilk və yalnız bir sətir.

Çıxış formatı

Sətri olan hər sətrin a-nı təmsil etdiyi 2 ^ n sətri çap edin ikili simli. Burada n “?” Sayıdır verilmiş “s” sətrində char.

Məhdudiyyətlər

  • 1 <= | s | <= 15
  • s [i] rəqəmi (0-9) və ya “?” olmalıdır

misal

1?1
101
111

Explanation: N-nin dəyəri (sətirdə '?' No) burada 1-dir. Beləliklə, 101 və 111 saylı iki simli var.

1?0?1?1
1000101
1000111
1001101
1001111
1100101
1100111
1101101
1101111

Explanation: N-nin dəyəri (sətirdəki '?' No) burada 3-dür. Beləliklə, 8 simli mümkündür 1000101, 1000111, 1001101, 1001111, 1100101, 1100111, 1101101, 1101111.

Verilən Nümunədən bütün İkili Sətirləri Yaratma Alqoritmi

Təkrarlamadan istifadə edərək buna nail ola bilərik. Fikir istifadə etməkdir queue. Giriş simvolunda ilk dəfə joker karakterin baş vermə vəziyyətini tapırıq və onu '0', sonra '1' ilə əvəzləyirik və hər iki simli də növbəyə basırıq. Sonra növbədən növbəti sətri açırıq və növbə boş olana qədər prosesi təkrarlayırıq. Xeyr joker simvol qaldı, sadəcə simli çap edirik.

  • "S" sətrini daxil edin.
  • Verilmiş simli növbəyə basdırın.
  • Növbə boş olmayana qədər təkrarlayın:

1. İndi növbənin ön dəyərini bir sətirdə saxlayın.

2. “?” -Nin ilk baş vermə vəziyyətini tapın.

3. Heç bir uyğunluq tapılmadıqda return string :: npos tapın.

3.1 '?' Dəyişdirin '0' ilə və sətri sıraya daxil edin.

3.2 '?' Dəyişdirin '1' ilə və sətri sıraya daxil edin.

4. Heç bir joker simvol qalmayıbsa, simli çap edin.

5. Sıranı növbədən çıxarın.

Həyata keçirilməsi

Verilən Nümunədən bütün ikili simləri yaratmaq üçün C ++ proqramı

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

int main() 
{ 
  string s;
  cin>>s;
  queue<string> q; 
  q.push(s); 
  while (!q.empty()) 
  { 
    string temp = q.front(); 
    size_t index = temp.find('?'); 
    if(index != string::npos) 
    { 
      temp[index] = '0'; 
      q.push(temp); 
      temp[index] = '1'; 
      q.push(temp); 
    } 
    else
    {
      cout<<temp<<endl; 
        }
    q.pop(); 
  } 
  return 0; 
} 

Verilən Nümunədən bütün İkili Sətirləri Yaratmaq üçün Java Proqramı

import java.util.Scanner;
import java.util.Stack;

class sum
{
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        String s = sr.next();
        Stack<String> stack = new Stack();
        stack.push(s);        
        int index;
        while(!stack.empty())
        {
            String curr = stack.pop();
            if((index = curr.indexOf('?')) != -1)
            {
                for (char ch = '0'; ch <= '1'; ch++)
                {
                    curr = curr.substring(0, index) + ch +
                            curr.substring(index + 1);
                    stack.push(curr);
                }
            }
            else
                System.out.println(curr);
        }
    }
}




1?01?
11011
11010
10011
10010

Verilən Nümunədən bütün İkili Sətirləri Yaratmaq üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (2 ^ n) hara n simli üzərində joker nömrələrin sayıdır.

Kosmik Mürəkkəblik

O (m * (2 ^ n)) hara m "s" sətrinin ölçüsüdür və n sətirdə joker işarənin sayıdır.

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