주어진 네 개의 키를 사용하여 A의 최대 수를 인쇄하는 방법-TutorialCup

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

Twitter Facebook 링크드인 버퍼 레딧 텀블러

차례

문제 정책

주어진 XNUMX 개의 키를 사용하여 A의 최대 수를 인쇄하는 방법,이 문제는 누를 키를 선택할 수있는 옵션이 있음을 나타냅니다. 키는 다음 작업을 수행합니다.

Key1 – 화면에 'A'인쇄
Key2 – 전체 화면을 선택합니다.
Key3 – 선택한 콘텐츠를 복사합니다.
Key4 – 복사 된 내용을 인쇄합니다.

키를 N 번만 누를 수 있으며 인쇄 할 수있는 A의 최대 수를 확인합니다. 만들 수있는 조합을 사용하여 인쇄 할 수있는 A의 최대 수를 찾으십시오.

예

Number of keys that can be pressed = 2

Number of A's that can be printed = 2

설명 : 다른 조합은 더 나은 결과를 찾을 수 없기 때문입니다. 다른 키 누름 조합을 사용하면 더 많은 수의 A를 인쇄 할 수 없습니다. 다른 조합을 시도해 볼 수 있습니다. 하나의 A를 인쇄한다고 가정 해 봅시다. 'A'를 인쇄하지 않으면 'A'를 선택한 다음 인쇄 할 수 없기 때문입니다. 따라서 단일 'A'를 인쇄하는 것이 좋습니다. 그 후에 우리는 선택, 인쇄 및 복사의 세 가지 조합 중 하나를 수행 할 수 있습니다. 그러나 이러한 조합은 더 나은 결과를 제공 할 수 없습니다.

핀

Number of keys that can be pressed = 6

Number of A's that can be printed = 6

설명 : Key6 ( 'A'인쇄), Key1, Key1, Key1 (전체 화면 내용 선택), Key2 (선택 내용 복사), Key3 (복사 내용 인쇄)의 4 가지 키 누름을 사용합니다. 동일한 수의 A를 인쇄 할 수있는 다른 키 누름이있을 수 있습니다.

접근

주어진 3 개의 키를 사용하여 A의 최대 수를 인쇄하는 방법을 찾는 것은 키 누름 횟수 = N-1에서 XNUMX로 시작하여 A의 최대 수를 찾으려면 해결할 수 있습니다.
i 번째 위치는 Key2, Key3을 누른 다음 Key4의 시퀀스를 누르는 지점입니다. 이제 N-3에서 1로 반복하면 그러한 점이 많이있을 수 있습니다.

항상 그렇듯이 문제가 사용하기 때문에 기본 케이스가 필요합니다. 동적 프로그래밍. 여기서 n <= 6이면 단순히 숫자를 인쇄합니다. 왜 우리는 이것을 동적 프로그래밍 코드에서 DP 배열을 사용하지 않더라도? 문제가 하위 문제 중복과 최적 하위 구조라는 두 가지 조건을 충족하기 때문입니다. 각 문제는 더 세분화 될 수 있으며 그 다음 더 나뉩니다.

암호

인쇄 할 수있는 최대 As 수를 찾는 C ++ 코드

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

int maximumNumberOfAsPrinted(int numberOfKeyPresses)
{
  if(numberOfKeyPresses <= 6)
    return numberOfKeyPresses;

  int maxNumberOfAs = 0;
  for(int i = numberOfKeyPresses-3; i>=1;i--) {
    // here we consider that after ith keystroke we are performing only selection, copy once and then paste
    // thus starting from numberOfKeyPresses-3
    int numberOfAs = (numberOfKeyPresses-i-1)*maximumNumberOfAsPrinted(i);
    if (numberOfAs > maxNumberOfAs)
      maxNumberOfAs = numberOfAs;
  }
  return maxNumberOfAs;
}

int main()
{
  int numberOfKeyPresses;cin>>numberOfKeyPresses;
  int numberOfAsPrinted = maximumNumberOfAsPrinted(numberOfKeyPresses);
  cout<<numberOfAsPrinted;
}

인쇄 할 수있는 최대 As 수를 찾는 Java 코드

import java.util.*;

class Main{
    static int maximumNumberOfAsPrinted(int numberOfKeyPresses)
    {
    	if(numberOfKeyPresses <= 6)
    		return numberOfKeyPresses;
    
    	int maxNumberOfAs = 0;
    	for(int i = numberOfKeyPresses-3; i>=1;i--) {
    		// here we consider that after ith keystroke we are performing only selection, copy once and then paste
    		// thus starting from numberOfKeyPresses-3
    		int numberOfAs = (numberOfKeyPresses-i-1)*maximumNumberOfAsPrinted(i);
    		if (numberOfAs > maxNumberOfAs)
    			maxNumberOfAs = numberOfAs;
    	}
    	return maxNumberOfAs;
    }

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
    	int numberOfKeyPresses = sc.nextInt();
    	int numberOfAsPrinted = maximumNumberOfAsPrinted(numberOfKeyPresses);
    	System.out.println(numberOfAsPrinted);
    }
}

복잡성 분석

시간 복잡성: 의 위에)

우리는 단순히 많은 키 누르기에 대해 루프를 실행했기 때문입니다. 알고리즘의 선형 시간 복잡도는 O (N)입니다.

공간 복잡성: O (1)

특정 정수와 요소 만 저장하기 때문입니다. 우리는 일정한 공간 복잡성을 가지고 있습니다.

Twitter Facebook 링크드인 버퍼 레딧 텀블러