Рубрики

Расшифруйте заданный шаблон двумя способами (вопрос об интервью Flipkart)

Отправитель отправляет двоичную строку получателю, в то время как он шифрует цифры. Вам предоставляется зашифрованная форма строки. Теперь получателю необходимо декодировать строку, и при декодировании было 2 подхода.

Пусть зашифрованная двоичная строка будет P [], а фактическая строка будет S [].

First, receiver starts with first character as 0; 
S[0] = 0 // First decoded bit is 1
Remaining bits or S[i]s are decoded using following formulas.
P[1] = S[1] + S[0] 
P[2] = S[2] + S[1] + S[0] 
P[3] = S[3] + S[2] + S[1] 
and so on ...

Second, Receiver starts with first character as 1; 
S[0] = 1 // First decoded bit is 1
Remaining bits or S[i]s are decoded using following formulas.
P[1] = S[1] + S[0]  
P[2] = S[2] + S[1] + S[0] 
P[3] = S[3] + S[2] + S[1] 
and so on ... 

Вам нужно напечатать две строки, сгенерированные с использованием двух разных после оценки из первого и второго метода. Если какая-либо строка содержит другие двоичные числа, вам нужно напечатать NONE.

Input1; 0123210
Output: 0111000, NONE

Explanation for first output
S[0] = 0, 
P[1] = S[1] + S[0], S[1] = 1
P[2] = S[2] + S[1] + S[0], S[2] = 1
P[3] = S[3] + S[2] + S[1], S[3] = 1
P[4] = S[4] + S[3] + S[2], S[4] = 0 
P[5] = S[5] + S[4] + S[3], S[5] = 0
P[6] = S[6] + S[5] + S[4], S[6] = 0

Explanation for second output 
S[0] = 1,
P[1] = S[1] + S[0], S[1] = 0
P[2] = s[2] + S[1] + S[0], S[2] = 1
P[3] = S[3] + S[2] + S[1], S[3] = 2, not a binary character so NONE.

Источник: Flipkart Интервью | Комплект 9 (в кампусе)

Идея решения этой проблемы проста, мы отслеживаем последние два декодированных бита. Текущий бит S [i] всегда можно рассчитать, вычитая последние два декодированных бита из P [i].

Ниже приводится реализация вышеуказанной идеи. Мы храним последние два декодированных бита в 'first' и 'second'.

C ++

#include<iostream>

using namespace std;

  
// Эта функция печатает декодирование P [] с первым декодированным
// номер как «первый». Если декодированные числа содержат что-нибудь
// кроме 0, выводится NONE

void decodeUtil(int P[], int n, int first)

{

    int S[n];  // массив для хранения декодированного битового паттерна

    S[0] = first;  // Первое число всегда является заданным числом

  

    int second = 0;  // Инициализация второго

  

    // рассчитать все биты, начиная со второго

    for (int i = 1; i < n; i++)

    {

        S[i] = P[i] -  first - second;

        if (S[i] != 1 && S[i] != 0)

        {

            cout << "NONE\n";

            return;

        }

        second = first;

        first = S[i];

    }

  

    // Распечатать выходной массив

    for (int i = 0; i < n; i++)

       cout << S[i];

    cout << endl;

}

  
// Эта функция декодирует P [] с использованием двух методов
// 1) начинается с 0 в качестве первого числа 2) начинается с 1 в качестве первого числа

void decode(int P[], int n)

{

    decodeUtil(P, n, 0);

    decodeUtil(P, n, 1);

}

  

int main()

{

    int P[] = {0, 1, 2, 3, 2, 1, 0};

    int n = sizeof(P)/sizeof(P[0]);

    decode(P, n);

    return 0;

}

python3

# Python3 программа для декодирования заданного
# шаблон двумя способами

  
# Эта функция печатает декодирование P [] с
# первый расшифрованный номер как «первый». Если
# декодированные числа содержат что-либо другое
# 0, то печатается «NONE»

def decodeUtil(P, n, first):

    S = [0 for i in range(n)]

      

    # массив для хранения декодированного битового паттерна

    S[0] = first # Первый номер

                 # всегда заданный номер

  

    second = 0

      

    # Инициализировать второй

  

    # Рассчитать все биты, начиная со второго

    for i in range(1, n, 1):

        S[i] = P[i] - first - second

        if (S[i] != 1 and S[i] != 0):

            print("NONE")

            return

      

        second = first

        first = S[i]

  

    # Распечатать выходной массив

    for i in range(0, n, 1):

        print(S[i], end = "")

    print("\n", end = "")

  
# Эта функция декодирует P [], используя
# две техники
# 1) начинается с 0 в качестве первого числа
# 2) Начинается 1 как первый номер

def decode(P, n):

    decodeUtil(P, n, 0)

    decodeUtil(P, n, 1)

  
Код водителя

if __name__ == '__main__':

    P = [0, 1, 2, 3, 2, 1, 0]

    n = len(P)

    decode(P, n)

      
# Этот код предоставлен
# Shashank_Sharma

PHP

<?php
// PHP программа для декодирования
// данный шаблон двумя способами

  
// Эта функция печатает декодирование
// из P [] с первым декодированным
// номер как «первый». Если
// декодированные числа содержат что-нибудь
// кроме 0, выводится NONE

function decodeUtil($P, $n, $first)

{

      

    // Первый номер всегда

    // данный номер

    $S[0] = $first

  

    // Инициализация второго

    $second = 0; 

  

    // отсчитываем все биты, начиная

    // со второго

    for ($i = 1; $i < $n; $i++)

    {

        $S[$i] = $P[$i] - $first - $second;

        if ($S[$i] != 1 && $S[$i] != 0)

        {

            echo "NONE\n";

            return;

        }

        $second = $first;

        $first = $S[$i];

    }

  

    // Распечатать выходной массив

    for ($i = 0; $i < $n; $i++)

    echo $S[$i];

    echo "\n";

}

  
// Эта функция декодирует P []
// используя два метода
// 1) Начинается с 0 в качестве первого числа
// 2) Начинается с 1 как первое число

function decode($P, $n)

{

    decodeUtil($P, $n, 0);

    decodeUtil($P, $n, 1);

}

  

    // Код драйвера

    $P=array (0, 1, 2, 3, 2, 1, 0);

    $n = sizeof($P);

    decode($P, $n);

  
// Этот код предоставлен ajit
?>


Выход:

0111000
NONE

Сложность времени: O (n)

Эта статья предоставлена Abhishek . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Расшифруйте заданный шаблон двумя способами (вопрос об интервью Flipkart)

0.00 (0%) 0 votes