K Tələbə arasında bərabər paylanacaq maksimum şokolad sayı

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Accenture Çiy kərpic Amazon Facebook Fourkites
Geyim SükutBaxılıb 87

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.

“K tələbələr arasında bərabər paylanacaq şokoladların maksimum sayı”, içərisində bəzi şokoladlar olan n qutu verildiyini bildirir. Tutaq ki, k tələbə var. Tapşırıq, ardıcıl qutuları seçərək k tələbələri arasında maksimum şokolad sayını bərabər paylamaqdır. Kassaların 1-dən n-ə qədər rəqəmlərdən ibarət bir sıra olduğunu düşünə bilərik. tapşırıq, k şagirdlərə ən çox şokolad paylaya bilən bir qrup qutu seçməkdir. Verilən qutular bir sıra kimi qəbul edilə bilər və arr [i] içindəki şokolad sayını i'th index mövqeyində təmsil edə bilər.

misal

arr[] = {1, 5, 3, 6, 10, 1}

k = 3
8

Explanation: 5, 3, 6, 10 alt sıra nömrələri k tələbələr arasında paylana biləcək 24 şokolad təşkil edir. Bu, hər şagird üçün 8 şokolad deməkdir ki, bu da verilən dəyərlərin maksimumudur.

Alqoritm

1. Declare a map.
2. Declare an array ‘sum’ of size n (length of the given array).
3. Set resultant to 0 and copy the value of arr[0] to sum[0].
4. Add all the values of arr[i] and sum[i-1] and store each value at sum[i].
5. Traverse the array, while i < n (length of the array).
  1. Set temp to sum[i]%k and check if the temp is equal to 0.
    1. If true then check for if resultant is less than sum[i], if true, then update resultant = sum[i].
  2. Check if the temp is present in a map, if present, then, push this value and the current index into the map.
  3. Else get the number which is related with the temp in a map, let x= map[temp], check if resultant is less than the sum[i] –sum[x].
    1. If true then update the value of resultant=sum[i]-sum[x], where x is map[temp].
6. Return the (resultant / k ).

Izahat

Maksimum şokaladın k tələbələri arasında bərabər paylanması üçün bir tapşırıq verdik. Qutusu əsasən şokolad sayını əks etdirən bir massivdir. Bir şərt də var, şokolad paylamaq üçün ardıcıl qutuları seçməliyik və paylama maksimum dərəcədə olmalıdır.

İstifadə edəcəyik qarışdırma. Elan edəcəyik xəritə. Ancaq bundan əvvəl verilmiş massivlə eyni ölçüdə boş bir sıra yaradacağıq, yəni n. [0] dəyərini arr [0] olaraq təyin edin, [0] cəminin ilk dəyəri arr [0] ilə eyni olmalıdır deməkdir. Keçərkən array, arr [i] və sum [i-1] əlavə edib dəyəri [i] cəmində saxlayacağıq, bu şəkildə bir sıra və cəmin əvvəlki indeksləri elementinin dəyərlərini əlavə edəcəyik. Bunun cəmi massivində dəyərlərimiz olacaq.

Buna bir nümunə götürək:

misal

arr [] = {1, 5, 3, 6, 10, 1}, k = 3

cəmi [0] = arr [0] = 1.

cəmi [1] = arr [i] + cəmi [i-1] = 6,

cəmi [2] = arr [i] + cəmi [i-1] = 9, onu davam etdirərək cəm massivində aşağıdakı dəyərlərə sahib olacağıq.

cəmi [] = {1, 6, 9, 15, 25, 26}.

Temp [i]% k kimi temp götürərək yenidən serialı keçəcəyik. Tempin 0-a bərabər olub olmadığını yoxlayacağıq, amma bu deyil, buna görə xəritədə bu dəyəri ehtiva etmədiyini yoxlayacağıq, indiki indekslə bir xəritədə yerləşdirəcəyik. Yəni xəritədə indi (1,0) var.

Növbəti 6 sayını götürərək və müvəqqəti olaraq [i]% k məbləğinin yoxlanılması indi 0 olduğu aşkar olunduğundan nəticəni indi yeniləyəcəyik. Nəticə 6 olardı.

Növbəti element 9 və 15 olardı, bu modeldə hər ikisinin modulu 3-ə bərabərdir, beləliklə 0-ə qədər, nəticə 15-ə bərabər olar. Növbəti rəqəm 15-dir, indi 25 kimi bir temp var. başqa şərtə. Ancaq xəritədə artıq 1 var. Beləliklə, bunun dəyərini alacağıq və bu, 1-a bərabərdir, çünki 0 və 1-u xəritədə saxladıq. Sonra [i] -sum [0] cəmini öyrənəcəyik və bu, 0 olacaqdır, nəticədə bu rəqəmlə nəticələnəcəkdir.

Daha bir nömrəni ziyarət etdikdən sonra cavabımız 24 olduğu kimi qalır. Nəhayət, 24/3/8-ə qayıdacağıq. Bu, son cavabımız olacaq.

K Tələbə arasında bərabər paylanacaq maksimum şokolad sayıPin

Həyata keçirilməsi

K tələbələr arasında bərabər paylanacaq maksimum şokolad sayı üçün C ++ proqramı

#include<iostream>
#include<unordered_map>

using namespace std;

int getChocolateNumbers(int arr[], int n, int k)
{
    unordered_map<int, int> MAP;

    int sum[n];

    int resultant = 0;

    sum[0] = arr[0];
    for (int i = 1; i < n; i++)
        sum[i] = sum[i - 1] + arr[i];

    for (int i = 0; i < n; i++)
    {
        int temp = sum[i] % k;

        if (temp == 0)
        {
            if (resultant < sum[i])
                resultant = sum[i];
        }
        else if (MAP.find(temp) == MAP.end())
            MAP[temp] = i;

        else if (resultant < (sum[i] - sum[MAP[temp]]))
            resultant = sum[i] - sum[MAP[temp]];
    }
    return (resultant / k);
}
int main()
{
    int arr[] = {1, 5, 3, 6, 10, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout << "Number of chocolates which can be equally distributed:  "<< getChocolateNumbers(arr, n, k);
    return 0;
}
Number of chocolates which can be equally distributed:  8

K Tələbələr arasında bərabər paylanacaq Maksimum Şokolad sayı üçün Java proqramı

import java.util.HashMap;

class distributionOfChocolates
{
    public static int getChocolateNumbers(int arr[], int n, int k)
    {
        HashMap <Integer,Integer> MAP = new HashMap<Integer,Integer>();

        int sum[]=new int[n];

        int resultant = 0;

        sum[0] = arr[0];
        for (int i = 1; i < n; i++)
        {
            sum[i] = sum[i - 1] + arr[i];
        }
        for (int i = 0; i < n; i++)
        {
            int temp = sum[i] % k;

            if (temp == 0)
            {
                if (resultant < sum[i])
                    resultant = sum[i];
            }

            else if (!MAP.containsKey(temp) )
                MAP.put(temp, i);

            else if (resultant < (sum[i] - sum[MAP.get(temp)]))
                resultant = sum[i] - sum[MAP.get(temp)];
        }

        return (resultant / k);
    }
    public static void main(String[] args)
    {
        int arr[] = { 1,5,3,6,10,1 };
        int n = arr.length;
        int k = 3;
        System.out.println("Number of chocolates which can be equally distributed: "+ getChocolateNumbers(arr, n, k));
    }
}
Number of chocolates which can be equally distributed: 8

K Tələbələr arasında bərabər paylanacaq maksimum şokolad sayı üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n) hara "N" massivdəki elementlərin sayıdır.

Kosmik Mürəkkəblik

O (n) hara "N" massivdəki elementlərin sayıdır.

arayış

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