단조 증가하는 함수가 처음에 양수가되는 지점 찾기

난이도 중급
자주 묻는 질문 아메리칸 익스프레스
이진 검색 분열과 정복 수색조회수 297

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

문제 정책

"단조 증가하는 함수가 처음으로 양수가되는 지점 찾기"에서 함수를 지정했습니다. "int f (unsigned int x)" 어느 것이 걸립니다 음이 아닌 정수 'x'를 입력으로 반환하고 정수 출력으로. 그만큼 기능 x 값에 대해 단조롭게 증가합니다. 즉, f (x + 1)의 값은 모든 입력 x에 대해 f (x)보다 큽니다. f ()가 처음으로 양수가되는 값 'n'을 찾으십시오. f ()는 단조 증가하므로 f (n + 1), f (n + 2),…의 값은 양수 여야하고 f (n-2), f (n-3), ..의 값은 음수 여야합니다. . 우리의 목표는 O (logn) 시간에 n을 찾는 것입니다. f (x)는 모든 입력 x에 대해 O (1) 시간에 평가 될 수 있다고 가정 할 수 있습니다.

입력 형식

함수 f (x)를 포함하는 첫 번째 및 유일한 행.

출력 형식

정수 값을 포함하는 첫 번째 및 유일한 행은 단조 증가하는 함수가 처음으로 양수가되는 지점을 나타냅니다.

x^2 - 4x - 8
6

설명 : f (x)가 양수가되는 x 값은 6입니다.

암호알고리즘

이 방법에서 주요 아이디어는 이진 검색을 적용하는 것이지만 이진 검색의 경우 낮은 값과 높은 값이 필요합니다. 아래 algo는 값을 찾고 이진 검색을 구현하는 방법을 보여줍니다.

1. f (i)가 2보다 클 때까지 i 값을 두 배로 늘립니다. f (i)가 XNUMX보다 크면 i를 고점으로, i / XNUMX를 저점으로 취하십시오.

2. 이제 i / 2와 i 사이에서 f (i)의 첫 번째 양수 값을 검색합니다. 이진 검색

3. 높거나 같을 때까지 중간을 찾으십시오.

  • f (mid)가 1보다 크고 mid가 low와 같거나 f (mid -0)이 1보다 작거나 같은 경우 즉, f (mid> 0) && (mid == low || f (mid-XNUMX ) <= XNUMX), 중간 반환
  • f (mid)가 XNUMX보다 작 으면 오른쪽 절반에서 재귀 적으로 검색합니다.
  • f (mid)가 XNUMX보다 크면 왼쪽 절반에서 재귀 적으로 검색합니다.

실시

단조 증가하는 함수가 처음으로 양수가되는 지점을 찾는 C ++ 프로그램

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

int binarySearch(int low, int high); 
int f(int x) 
{ 
    return (x*x - 10*x - 20); 
} 

int findFirstPositive() 
{ 
  if (f(0) > 0) 
    return 0; 
  int i = 1; 
  while (f(i) <= 0) 
    i = i*2; 
  return binarySearch(i/2, i); 
} 

int binarySearch(int low, int high) 
{ 
  if (high >= low) 
  { 
    int mid = low + (high - low)/2; 
    if (f(mid) > 0 && (mid == low || f(mid-1) <= 0)) 
      return mid; 

    if (f(mid) <= 0) 
      return binarySearch((mid + 1), high); 
    else  
      return binarySearch(low, (mid -1)); 
  } 
  return -1; 
} 

int main() 
{ 
  cout<<findFirstPositive(); 
  return 0; 
}

단조 증가하는 함수가 처음으로 양이되는 지점을 찾는 Java 프로그램

import java.util.ArrayList;
import java.util.Scanner;
class sum
{
    public static int f(int x)  
    { 
        return (x*x - 10*x - 20);
    } 
    public static int findFirstPositive() 
    { 
        if(f(0)>0)
        {
            return 0;
        }
        int i = 1; 
        while(f(i)<=0) 
            i = i * 2; 
        return binarySearch(i / 2, i); 
    } 
    public static int binarySearch(int low, int high) 
    { 
        if (high >= low) 
        {    
            int mid = low + (high - low)/2;  
            if (f(mid) > 0 && (mid == low || f(mid-1) <= 0)) 
                return mid; 
            if (f(mid) <= 0) 
                return binarySearch((mid + 1), high); 
            else 
                return binarySearch(low, (mid -1)); 
        }
        return -1;
    }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        findFirstPositive();
    }
}
x*x - 10*x - 20
12

복잡성 분석

시간 복잡성

O (로그온) : 'high'를 찾는 단계는 O (Logn)입니다. 따라서 O (Logn) 시간에서 '높음'을 찾을 수 있습니다. 바이너리 검색에서 high / 2와 high 사이에 걸리는 시간은 어떻습니까? 'high'값은 2 * n보다 작아야합니다. high / 2와 high 사이의 요소 수는 O (n)이어야합니다. 따라서 Binary Search의 시간 복잡도는 O (Logn)이고 전체 시간 복잡도는 O (Logn) 인 2 * O (Logn)입니다.

공간 복잡성

O (1) 여기에 보조 공간을 만들지 않기 때문입니다.

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