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

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

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

차례

문제 정책

"단조 증가하는 함수가 처음으로 양수가되는 지점 찾기"에서 함수를 지정했습니다. "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

설명 : 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

복잡성 분석

시간 복잡성

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) 여기에 보조 공간을 만들지 않기 때문입니다.

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