모든 요소가 이전의 두 배 이상인 주어진 길이의 시퀀스

난이도 쉽게
자주 묻는 질문 Accenture 아마존 코드네이션 Facebook 구글 페이팔 퀄컴
분열과 정복 동적 프로그래밍조회수 69

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

"모든 요소가 이전의 두 배 이상인 주어진 길이의 시퀀스"문제는 두 개의 정수 m과 n을 제공합니다. 여기 m 시퀀스에 존재할 수있는 가장 큰 숫자이며 필수 시퀀스에 있어야하는 요소의 수입니다. 시퀀스에 부과되는 조건이 하나 더 있습니다. 즉, 각 요소는 이전 요소보다 두 배 이상이어야합니다. 모든 조건이 충족되는 총 시퀀스 수를 찾으십시오.

n = 3, m = 6
4

설명

주어진 조건에서 만들 수있는 4 개의 시퀀스가 ​​있습니다 : (1, 2, 4), (1, 2, 5), (1, 2, 6), (1, 3, 6).

접근

문제는 모든 요소가 이전의 두 배 이상인 주어진 길이의 총 시퀀스 수를 찾도록 요청합니다. 시간 복잡도가 높은 순진한 솔루션은 모든 길이 시퀀스를 생성 할 수 있습니다. n. 요소는 오름차순을 따라야하며 최대 수는 m. 그러나 각 요소가 이전 요소보다 두 배 이상이어야한다는 사실을 통합하면 더 효율적인 솔루션이 될 수 있습니다. 따라서 우리는 재귀 공식을 작성할 수 있습니다. 우리가 선택하면 길이가있는 시퀀스를 찾아야합니다. n-1 및 최대 요소 m / xnumx. 그렇지 않으면 길이가있는 시퀀스를 찾아야합니다. 및 최대 요소 m-1. 이 접근 방식은 이전에 논의한 접근 방식보다 약간 더 효율적이지만. 이것은 또한 시간이 많이 걸립니다.

모든 요소가 이전의 두 배 이상인 주어진 길이의 시퀀스

재귀 공식이있는 경우에는 동적 프로그래밍. 위의 내용을 간단히 메모하겠습니다. 재귀 우리가 논의한 솔루션. 이 경우 두 가지 상태가 있습니다. 첫 번째는 최대 수이고 다른 하나는 시퀀스의 길이입니다.

암호

모든 요소가 이전의 두 배 이상인 주어진 길이의 시퀀스를 찾는 C ++ 코드

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

int main()
{
    int n = 3, m = 6;
    int dp[m+1][n+1];
    memset(dp, 0, sizeof dp);
    for(int i=0;i<=m;i++)
        dp[i][0] = 1;
    int ans = 0;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            // we pick the current element
            dp[i][j] = dp[i/2][j-1];
            // we ignore the current element
            dp[i][j] += dp[i-1][j];
        }
    }
    cout<<dp[n][m];
}
4

모든 요소가 이전의 두 배 이상인 주어진 길이의 시퀀스를 찾는 Java 코드

import java.util.*;
class Main{
  public static void main(String[] args)
  {
      int n = 3, m = 6;
      int dp[][] = new int[m+1][n+1];
      for(int i=0;i<=n;i++)
      	for(int j=0;j<=m;j++)
      		dp[i][j] = 0;
      for(int i=0;i<=m;i++)
          dp[i][0] = 1;
      for(int i=1;i<=m;i++){
          for(int j=1;j<=n;j++){
              // we pick the current element
              dp[i][j] = dp[i/2][j-1];
              // we ignore the current element
              dp[i][j] += dp[i-1][j];
          }
      };
    System.out.print("dp[n][m]");
  }
}
4

복잡성 분석

시간 복잡성

O (N * M), 문제의 상태는 시퀀스의 길이와 고려할 수있는 최대 수이기 때문입니다. 따라서 시간 복잡도는 다항식입니다.

공간 복잡성

O (N * M), 중간 결과를 저장하기 위해 2D DP 테이블을 만들었 기 때문입니다. 공간 복잡성도 다항식입니다.

균열 시스템 설계 인터뷰
Translate »