시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
모든 값에 대해 정수 n을 제공했다고 가정합니다. n 염기 k 좋은 염기 k> = 1 일 때 2입니다. 우리가 현 형식 번호 'n'. 문제 설명은 n의 가장 작은 좋은 밑을 찾아서 반환하도록 요구합니다. 현 형식입니다.
예
String n = “15”
2
설명 : Base 15로 쓰여진 2는 1111입니다.
String n = “20”
19
설명 : Base 20로 쓰여진 19는 11입니다.
가장 작은 좋은 기본 문제에 대한 알고리즘
1. Set y to n-1.
2. Add the n-1 into the List.
3. From the i=2 to i< 63,
1. Find out the val = pow of (y, 1.0 / i).
2. From j=0 to j > - 3 and val + j > 1.
1. Set d = val + j.
2. And check if n % d is equal to 0.
1. Find out this polynomial 1 + d + d ^ 2 + d ^ 3 + ... + d ^ i for d and up the current value of I and store into the sum.
3. Check if this polynomial’s sum is equal to the n.
1. Then add the value of d to the list.
4. Repeat the third process until the loop finishes.
5. Get the last element of the list and return that value.
설명
주어진 숫자 n 끈 체재. 모든 숫자 n 기본의 최대 값이 있습니다. n-1. 값은 3에서 10 ^ 18로 변경 될 수 있으므로 최대 64 자리까지 수용 할 수 있습니다. 가장 작은 밑수는 2이고 63까지 올라갈 수 있습니다. 우리가 계산할 수있는 최대 밑수는 n의 모든 값에 대해 n-1이고 최소값은 2입니다.
결과적으로 우리는 각각의 가장 극단적 인 길이 묘사를 찾기 위해베이스를 줄여야합니다. 각 번호에 대해. 자릿수의 경우, 우리는 동등한 존경을 줄 수있는 기수가 존재하는지 찾으려고 할 것입니다. 주어진 값 = m,이 문제는 만족하는 정수 d와 n을 찾는 것입니다.
m = 1 + d + d ^ 2 + d ^ 3 +… + d ^ i.
with 'i'는 배열을 순회 할 때마다 변경할 수있는 값입니다 (b가 최소화된다는 목표로).
방정식에 따라 우리는 항상 쌍으로 답을 얻습니다. 따라서 d1 = m-1. 따라서 목록에 삽입 한 답변의 가능한 값을 요약합니다. 값 (d1,…, dn)이 목록에 있으며 마지막 값을 가져옵니다. 우리는 1 + b + b ^ 2 + b ^ 3 +… + b ^ base의 다항식을 찾아야합니다.
가능한 모든 숫자의 값을 찾을 함수에 대한 후속 조치를 취합니다. 우리가 취한 루프는 최대 62 자리 숫자로 구성 될 수 있기 때문에 64까지이지만 63을 사용하면 오버플로가 발생합니다. 최소값을 찾을 때까지이 작업을 계속할 것이며 동시에 목록에 추가 할 것입니다. 따라서 우리는 가장 작은 염기를 찾고 마지막 염기를 가져 오기만하면됩니다.
암호
가장 작은 좋은베이스를 찾기위한 C ++ 코드
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
using namespace std;
long getGetPolynomial(long, int);
string getMinGoodBase(string n)
{
long x = stoi(n);
vector<long> listt;
listt.push_back(x-1);
long y = x-1;
for (int i = 2; i < 63; i++)
{
double val = pow(y, 1.0 / i);
long value = (long) val;
for (int j = 0; j > -3 && value + j > 1; j--)
{
long d = value + j;
if (y % d == 0)
{
long poly = getGetPolynomial(d, i);
if (poly == x)
{
listt.push_back(d);
}
}
}
}
long end = listt[listt.size() - 1];
string out = to_string(end);
return out;
}
long getGetPolynomial(long d, int n)
{
long out = 1;
long k = 1;
for (int i = 0; i < n; i++)
{
k *= d;
out += k;
}
return out;
}
int main()
{
string num="15";
cout<<getMinGoodBase(num);
}
2
가장 작은 좋은베이스를 찾는 자바 코드
import java.util.ArrayList;
import java.util.List;
class GoodBase
{
public static String getMinGoodBase(String n)
{
long x = Long.parseLong(n);
List<Long> listt = new ArrayList<>();
listt.add(x-1);
long y = x-1;
for (int i = 2; i < 63; i++)
{
double val = Math.pow(y, 1.0 / i);
long value = (long) val;
for (int j = 0; j > -3 && value + j > 1; j--)
{
long d = value + j;
if (y % d == 0)
{
long poly = getPolynomial(d, i);
if (poly == x)
{
listt.add(d);
}
}
}
}
long end = listt.get(listt.size() - 1);
return end+"";
}
public static long getPolynomial(long d, int n)
{
long out = 1;
long k = 1;
for (int i = 0; i < n; i++)
{
k *= d;
out += k;
}
return out;
}
public static void main(String args[])
{
String num="15";
System.out.println(getMinGoodBase(num));
}
}
2
복잡성 분석
시간 복잡성
의 위에2) 어디에 "엔" 문자열의 길이입니다.
공간 복잡성
O (N) 어디에 "엔" 문자열의 길이입니다.
