Algoritmik jumboq intervyusida so'radi

Bugun men quyidagi muammolarga duch keldim. Iltimos, iltimos, ba'zi maslahatlar bering, bu bayonot quyidagicha:

A [] hajmining n qatori berilgan. Quyidagi cheklovlar ostida A [i] * A [j] * A [k]

  • i < j < k
  • A[i] < A[j] < A[k]

Men sinab ko'rgan kod quyidagicha:

#include
using namespace std;

int main(){
  int A[]={1,3,6,8,9};int max=A[0]*A[1]*A[2];
  int n=sizeof(A)/sizeof(A[0]);
  for(int i=0;i<
3
Yo'q, lekin men ushbu saytda yangiman, shuning uchun xato qilishim uchun uzr so'rayman.
qo'shib qo'ydi muallif Rahul Choudhary, manba
Yo'q, lekin men ushbu saytda yangiman, shuning uchun xato qilishim uchun uzr so'rayman.
qo'shib qo'ydi muallif Rahul Choudhary, manba
Yo'q, lekin men ushbu saytda yangiman, shuning uchun xato qilishim uchun uzr so'rayman.
qo'shib qo'ydi muallif Rahul Choudhary, manba
Men u (n ^ 3) ni aniqladim, ammo bu samarali emas.
qo'shib qo'ydi muallif Rahul Choudhary, manba
Men u (n ^ 3) ni aniqladim, ammo bu samarali emas.
qo'shib qo'ydi muallif Rahul Choudhary, manba
Men u (n ^ 3) ni aniqladim, ammo bu samarali emas.
qo'shib qo'ydi muallif Rahul Choudhary, manba
Siz tasodifan joylashtirdingizmi?
qo'shib qo'ydi muallif Rakete1111, manba
Siz tasodifan joylashtirdingizmi?
qo'shib qo'ydi muallif Rakete1111, manba
Siz kiritgan yechim kodini kiriting
qo'shib qo'ydi muallif Kewl, manba
Siz kiritgan yechim kodini kiriting
qo'shib qo'ydi muallif Kewl, manba
Siz kiritgan yechim kodini kiriting
qo'shib qo'ydi muallif Kewl, manba
Siz nima qildingiz, hozir?
qo'shib qo'ydi muallif max66, manba
A [0] 2]
qo'shib qo'ydi muallif max66, manba
A [0] 2]
qo'shib qo'ydi muallif max66, manba
A [0] 2]
qo'shib qo'ydi muallif max66, manba
Siz nima qildingiz, hozir?
qo'shib qo'ydi muallif max66, manba
Siz nima qildingiz, hozir?
qo'shib qo'ydi muallif max66, manba
qo'shib qo'ydi muallif EJoshuaS, manba
qo'shib qo'ydi muallif EJoshuaS, manba
qo'shib qo'ydi muallif EJoshuaS, manba

6 javoblar

Oddiy O (N ^ 2) algoritmi mavjud. Bu erda quyidagicha:

  1. For each element y
  2. Search maximum element x which is smaller than y and before y
  3. Search maximum element z which is larger than y and after y

Step 1 is O(N), Step 2 & 3 can be done in same loop which is O(N), in total it is O(N^2)


U (Ngg N) algoritmi ham bor, lekin bu juda murakkab:

We can precompute in O(N) and query in O(1) for finding maximum in range [l,r]. (Original thought is use segment tree or any RMQ structures, thanks for @PetarPetrovic pointing out)

Shuningdek, ketma-ketlikdagi har bir elementni yineleyken, biz tezda to'siq (tartiblangan ro'yxat) yaratamiz. Pseudo kodi quyidagicha:

Array A = []
Set S = {}
Ans = 0

For i = 0 to N//O(N)
 //A[i] is y
  x = binary search S, maximum element in S which is < A[i] //O(lg N)
  z = RMQ(i+1, N)//O(lg N), or O(1) if we precompute in O(N)
  if(x < A[i] && A[i] < z) Ans = Max(Ans, x*A[i]*z)
  Insert A[i] into S//O(lg N)
//Total is O(N lg N)      

A [i] elementini y elementi sifatida ko'rishga harakat qilamiz.

i oldida barcha elementlarni o'z ichiga olgan tartiblangan to'siqqa ega bo'lgani uchun, to'plamdan foydalanib, maksimal x yordamida ikkilik qidiruvni amalga oshirishimiz mumkin. Biz ushbu elementga keyingi elementni qo'shamiz.

O (N) ni [i + 1, N-1] oralig'ida maksimal qiymatni topish uchun O (1) qatori va so'rovni prekompirish uchun ishlatamiz. Topilgan raqam z .

Javobni (x, y, z) joriy tuple va joriy javobdan katta bo'lsa yangilab olamiz.

1
qo'shib qo'ydi
@shole bu kabi samarali echimni taklif qilganingiz uchun tashakkur, bu intervyuda ishora qiluvchi aniq yondoshuv, ammo o'sha paytda noto'g'ri tushuna ololmadim ...
qo'shib qo'ydi muallif Rahul Choudhary, manba
Agar siz faqat [i + 1, N - 1] oralig'ida maksimal qiymatni topmoqchi bo'lsangiz, u (n) prepossess va O (1) so'rovlar vaqtida
qo'shib qo'ydi muallif Petar Petrovic, manba
@PetarPetrovic Ha, siz haqsiz, o'yladim, u hali ham O (N lg N) :)
qo'shib qo'ydi muallif shole, manba

Quyidagi eritma O (n ^ 2)

#include 
#include 
#include 

template 
std::stack getStack (T const * a, std::size_t dimA)
 {
   if ( nullptr == a )
      throw std::runtime_error("nullptr in getStack()");

   if ( 0U == dimA )
      throw std::runtime_error("no values in getStack()");

   T              top;
   std::stack  s;
   std::size_t    pos{ 0U };

   s.push(top = a[pos]);

   do
    {
      if ( top < a[pos] )
         s.push(top = a[pos]);
    }
   while ( ++pos < dimA );

   return s;
 }


int main()
 {
   int          a[] { 34, 12, 3, 7, 29, 45 };
   std::size_t  dimA { sizeof(a)/sizeof(a[0]) };
   std::size_t  numMult { 3U };


   std::stack s;

   std::size_t     pos { 0U };

   do
    {
      s = getStack(a+pos, dimA - pos);
    }
   while ( (s.size() < numMult) && (numMult <= (dimA - ++pos)) );

   if ( s.size() < numMult )
      std::cout << "there is no solution" << std::endl;
   else
    {
      int res { s.top() };

      for ( auto ui = 1U ; ui < numMult ; ++ui )
       {
         s.pop();

         res *= s.top(); 
       }

      std::cout << "the solution is " << res << std::endl;
    }

   return 0;
 }
0
qo'shib qo'ydi
bu yondashuv juda qiziqarli ko'rinadi.
qo'shib qo'ydi muallif Rahul Choudhary, manba

Quyidagi eritma O (n ^ 2)

#include 
#include 
#include 

template 
std::stack getStack (T const * a, std::size_t dimA)
 {
   if ( nullptr == a )
      throw std::runtime_error("nullptr in getStack()");

   if ( 0U == dimA )
      throw std::runtime_error("no values in getStack()");

   T              top;
   std::stack  s;
   std::size_t    pos{ 0U };

   s.push(top = a[pos]);

   do
    {
      if ( top < a[pos] )
         s.push(top = a[pos]);
    }
   while ( ++pos < dimA );

   return s;
 }


int main()
 {
   int          a[] { 34, 12, 3, 7, 29, 45 };
   std::size_t  dimA { sizeof(a)/sizeof(a[0]) };
   std::size_t  numMult { 3U };


   std::stack s;

   std::size_t     pos { 0U };

   do
    {
      s = getStack(a+pos, dimA - pos);
    }
   while ( (s.size() < numMult) && (numMult <= (dimA - ++pos)) );

   if ( s.size() < numMult )
      std::cout << "there is no solution" << std::endl;
   else
    {
      int res { s.top() };

      for ( auto ui = 1U ; ui < numMult ; ++ui )
       {
         s.pop();

         res *= s.top(); 
       }

      std::cout << "the solution is " << res << std::endl;
    }

   return 0;
 }
0
qo'shib qo'ydi
bu yondashuv juda qiziqarli ko'rinadi.
qo'shib qo'ydi muallif Rahul Choudhary, manba

Given i < j < k and you wanted to do something with 3 for loops, then you can obviously do

for(i = 0; i < n; ++i) {
    for(j = i + 1; j < n; ++j){
         if (A[i] < A[j]) {
             for(k = j + 1; k < n; ++k){
                 if(A[j] < A[k]) {
                 /*DoSomething with i,j,k*/
                 }
            }
         }
    }
}

Bu, asosan, har qanday narsadan ko'ra ko'proq chuqurlikdagi kabus.

0
qo'shib qo'ydi
@AlexG Ha, lekin biz buni O (nlogn) yoki O (n ^ 2) kabi bir narsada qila olamizmi?
qo'shib qo'ydi muallif Rahul Choudhary, manba
@ max66 bu echimning vaqt murakkabligi O (n ^ 3) o'ng.if ha, keyin bu samarali emas, bir.interviewer yaxshiroq qilishni so'radi.
qo'shib qo'ydi muallif Rahul Choudhary, manba
@Rahul - ha: mening taklifim bilan, O (n ^ 3).
qo'shib qo'ydi muallif max66, manba
Agar A [i] - bu cheklov for (j = i + 1; j < A (j)) for (k = j + 1; k
qo'shib qo'ydi muallif max66, manba
@ max66 Yangilandi, rahmat. Bu eng yomon holatda (i = 0, j = 0, k = 0) faqatgina O (n ^ 3), boshqa hollarda esa bu tezroq bo'ladi.
qo'shib qo'ydi muallif AlexG, manba

Given i < j < k and you wanted to do something with 3 for loops, then you can obviously do

for(i = 0; i < n; ++i) {
    for(j = i + 1; j < n; ++j){
         if (A[i] < A[j]) {
             for(k = j + 1; k < n; ++k){
                 if(A[j] < A[k]) {
                 /*DoSomething with i,j,k*/
                 }
            }
         }
    }
}

Bu, asosan, har qanday narsadan ko'ra ko'proq chuqurlikdagi kabus.

0
qo'shib qo'ydi
@AlexG Ha, lekin biz buni O (nlogn) yoki O (n ^ 2) kabi bir narsada qila olamizmi?
qo'shib qo'ydi muallif Rahul Choudhary, manba
@ max66 bu echimning vaqt murakkabligi O (n ^ 3) o'ng.if ha, keyin bu samarali emas, bir.interviewer yaxshiroq qilishni so'radi.
qo'shib qo'ydi muallif Rahul Choudhary, manba
@Rahul - ha: mening taklifim bilan, O (n ^ 3).
qo'shib qo'ydi muallif max66, manba
Agar A [i] - bu cheklov for (j = i + 1; j < A (j)) for (k = j + 1; k
qo'shib qo'ydi muallif max66, manba
@ max66 Yangilandi, rahmat. Bu eng yomon holatda (i = 0, j = 0, k = 0) faqatgina O (n ^ 3), boshqa hollarda esa bu tezroq bo'ladi.
qo'shib qo'ydi muallif AlexG, manba

Given i < j < k and you wanted to do something with 3 for loops, then you can obviously do

for(i = 0; i < n; ++i) {
    for(j = i + 1; j < n; ++j){
         if (A[i] < A[j]) {
             for(k = j + 1; k < n; ++k){
                 if(A[j] < A[k]) {
                 /*DoSomething with i,j,k*/
                 }
            }
         }
    }
}

Bu, asosan, har qanday narsadan ko'ra ko'proq chuqurlikdagi kabus.

0
qo'shib qo'ydi
@AlexG Ha, lekin biz buni O (nlogn) yoki O (n ^ 2) kabi bir narsada qila olamizmi?
qo'shib qo'ydi muallif Rahul Choudhary, manba
@ max66 bu echimning vaqt murakkabligi O (n ^ 3) o'ng.if ha, keyin bu samarali emas, bir.interviewer yaxshiroq qilishni so'radi.
qo'shib qo'ydi muallif Rahul Choudhary, manba
@Rahul - ha: mening taklifim bilan, O (n ^ 3).
qo'shib qo'ydi muallif max66, manba
Agar A [i] - bu cheklov for (j = i + 1; j < A (j)) for (k = j + 1; k
qo'shib qo'ydi muallif max66, manba
@ max66 Yangilandi, rahmat. Bu eng yomon holatda (i = 0, j = 0, k = 0) faqatgina O (n ^ 3), boshqa hollarda esa bu tezroq bo'ladi.
qo'shib qo'ydi muallif AlexG, manba