까다로운 Google 인터뷰 질문
내 친구가 직업 인터뷰를하고 있습니다. 인터뷰 질문 중 하나가 저를 생각하게 만들었습니다. 피드백을 원했습니다.
음수가 아닌 정수는 i와 j입니다. 다음 방정식이 주어지면 출력이 정렬되는 방식으로 i 및 j를 반복하는 (최적의) 솔루션을 찾으십시오.
2^i * 5^j
처음 몇 라운드는 다음과 같습니다.
2^0 * 5^0 = 1
2^1 * 5^0 = 2
2^2 * 5^0 = 4
2^0 * 5^1 = 5
2^3 * 5^0 = 8
2^1 * 5^1 = 10
2^4 * 5^0 = 16
2^2 * 5^1 = 20
2^0 * 5^2 = 25
내가 시도한대로 패턴을 볼 수 없습니다. 당신의 생각?
Dijkstra는 "A 학문 분야"에서 웅변적인 솔루션을 도출합니다. 그는이 문제를 해밍으로 인한 것이라고 생각합니다. 다음은 Dijkstra 솔루션의 구현입니다.
int main()
{
const int n = 20; // Generate the first n numbers
std::vector<int> v(n);
v[0] = 1;
int i2 = 0; // Index for 2
int i5 = 0; // Index for 5
int x2 = 2 * v[i2]; // Next two candidates
int x5 = 5 * v[i5];
for (int i = 1; i != n; ++i)
{
int m = std::min(x2, x5);
std::cout << m << " ";
v[i] = m;
if (x2 == m)
{
++i2;
x2 = 2 * v[i2];
}
if (x5 == m)
{
++i5;
x5 = 5 * v[i5];
}
}
std::cout << std::endl;
return 0;
}
여기에 더 세련된 방법이 있습니다 (이전 답변보다 더 세련되었습니다).
숫자가 행렬에 있다고 상상해보십시오.
0 1 2 3 4 5 -- this is i
----------------------------------------------
0| 1 2 4 8 16 32
1| 5 10 20 40 80 160
2| 25 50 100 200 400 800
3| 125 250 500 1000 2000 ...
4| 625 1250 2500 5000 ...
j on the vertical
당신이해야 할 일은에서 시작 하여이 행렬을 '걷는 것' (0,0)입니다. 또한 가능한 다음 움직임이 무엇인지 추적해야합니다. 시작할 때 (0,0)두 가지 옵션 만 있습니다 : (0,1)또는 (1,0): 값 (0,1)이 작기 때문에 선택하십시오. 다음 다음 선택에 대한 동일한 작업을 수행 (0,2)하거나 (1,0). 지금까지 다음 목록이 1, 2, 4있습니다.. 다음으로 이동 (1,0)하는 값이보다 작습니다 (0,3). 그러나 이제 다음 이동을 위해 , 또는 , 또는 세 가지 중에서 선택할 수 있습니다 .(0,3)(1,1)(2,0)
목록을 얻기 위해 매트릭스가 필요하지는 않지만 모든 선택 사항을 추적해야합니다 (예 : 125+에 도달하면 4 가지 선택 사항이 있음).
최소 힙을 사용하십시오.
1을 넣습니다.
추출물-최소 x를받는다고 가정 해보십시오.
힙에 2x 및 5x를 밀어 넣습니다.
반복.
x = 2 ^ i * 5 ^ j를 저장하는 대신 (i, j)를 저장하고 사용자 정의 비교 기능을 사용할 수 있습니다.
FIFO 기반 솔루션은 스토리지 용량이 더 적습니다. 파이썬 코드.
F = [[1, 0, 0]] # FIFO [value, i, j]
i2 = -1; n2 = n5 = None # indices, nexts
for i in range(1000): # print the first 1000
last = F[-1][:]
print "%3d. %21d = 2^%d * 5^%d" % tuple([i] + last)
if n2 <= last: i2 += 1; n2 = F[i2][:]; n2[0] *= 2; n2[1] += 1
if n5 <= last: i2 -= 1; n5 = F.pop(0); n5[0] *= 5; n5[2] += 1
F.append(min(n2, n5))
산출:
0. 1 = 2^0 * 5^0
1. 2 = 2^1 * 5^0
2. 4 = 2^2 * 5^0
...
998. 100000000000000000000 = 2^20 * 5^20
999. 102400000000000000000 = 2^27 * 5^17
O(n)기능적인 언어로 하는 것은 매우 쉽습니다 . 목록 l의 2^i*5^j수는 간단하게 정의 할 수 있습니다 1다음 2*l과 5*l합병했다. 하스켈에서의 모습은 다음과 같습니다.
merge :: [Integer] -> [Integer] -> [Integer]
merge (a:as) (b:bs)
| a < b = a : (merge as (b:bs))
| a == b = a : (merge as bs)
| b > a = b : (merge (a:as) bs)
xs :: [Integer]
xs = 1 : merge (map(2*)xs) (map(5*)xs)
이 merge기능은 일정한 시간에 새로운 가치를 제공합니다. 그렇기 map때문에 그렇습니다 l.
개별 지수와 그 합계가 무엇인지 추적해야합니다.
f(0,0) --> 1이제 부터 시작하여 그중 하나를 증가시켜야합니다.
f(1,0) = 2
f(0,1) = 5
그래서 우리는 2가 다음임을 알고 있습니다. 또한 우리는 합이 5를 초과 할 때까지 지수를 증가시킬 수 있다는 것을 알고 있습니다.
당신은 당신이 원하는 라운드 수에 도달 할 때까지 이런 식으로 계속 진행하고 있습니다.
동적 프로그래밍을 사용하면 O (n)에서이를 수행 할 수 있습니다. 사실 i와 j의 값은 우리에게 0을 줄 수 없으며 1을 얻으려면 두 값이 모두 0이어야합니다.
TwoCount[1] = 0
FiveCount[1] = 0
// function returns two values i, and j
FindIJ(x) {
if (TwoCount[x / 2]) {
i = TwoCount[x / 2] + 1
j = FiveCount[x / 2]
}
else if (FiveCount[x / 5]) {
i = TwoCount[x / 2]
j = FiveCount[x / 5] + 1
}
}
이 기능 검사를 호출 할 때마다 i와 j는 그렇지 않은 null의 경우, 다음 채우기, 설정되어있는 경우 TwoCount및FiveCount
C ++ 답변. 나쁜 코딩 스타일로 죄송하지만 서두르고 있습니다 :(
#include <cstdlib>
#include <iostream>
#include <vector>
int * TwoCount;
int * FiveCount;
using namespace std;
void FindIJ(int x, int &i, int &j) {
if (x % 2 == 0 && TwoCount[x / 2] > -1) {
cout << "There's a solution for " << (x/2) << endl;
i = TwoCount[x / 2] + 1;
j = FiveCount[x / 2];
} else if (x % 5 == 0 && TwoCount[x / 5] > -1) {
cout << "There's a solution for " << (x/5) << endl;
i = TwoCount[x / 5];
j = FiveCount[x / 5] + 1;
}
}
int main() {
TwoCount = new int[200];
FiveCount = new int[200];
for (int i = 0; i < 200; ++i) {
TwoCount[i] = -1;
FiveCount[i] = -1;
}
TwoCount[1] = 0;
FiveCount[1] = 0;
for (int output = 2; output < 100; output++) {
int i = -1;
int j = -1;
FindIJ(output, i, j);
if (i > -1 && j > -1) {
cout << "2^" << i << " * " << "5^"
<< j << " = " << output << endl;
TwoCount[output] = i;
FiveCount[output] = j;
}
}
}
분명히 스토리지 이외의 데이터 구조를 사용하여 스토리지 등을 동적으로 늘릴 수 있습니다. 이것은 작동한다는 것을 보여주는 스케치 일뿐입니다.
이것을 다른 방향에서 보지 않겠습니까? 카운터를 사용하여 원래 공식에 대해 가능한 답을 테스트하십시오. 의사 코드가 유감입니다.
for x = 1 to n
{
i=j=0
y=x
while ( y > 1 )
{
z=y
if y divisible by 2 then increment i and divide y by 2
if y divisible by 5 then increment j and divide y by 5
if y=1 then print i,j & x // done calculating for this x
if z=y then exit while loop // didn't divide anything this loop and this x is no good
}
}
이것은 OEIS의 관련 항목입니다.
처음 몇 항을 생성하여 순서가 지정된 순서를 얻는 것이 가능합니다.
12 34
그런 다음 두 번째 항에서 시작하여 4와 5를 곱하여 다음 2를 얻습니다.
1 2 4 5 8 10
1 2 4 5 8 10 16 20
12 5 8 10 16 20 25
등등...
직관적으로 이것은 올바른 것 같지만 물론 증거가 없습니다.
log_2 (5) = 2.32라는 것을 알고 있습니다. 이것으로부터 우리는 2 ^ 2 <5 and 2 ^ 3> 5임을 알 수 있습니다.
이제 가능한 답변의 매트릭스를보십시오.
j/i 0 1 2 3 4 5
0 1 2 4 8 16 32
1 5 10 20 40 80 160
2 25 50 100 200 400 800
3 125 250 500 ...
이제이 예에서는 순서대로 숫자를 선택하십시오. 순서는 다음과 같습니다.
j/i 0 1 2 3 4 5
0 1 2 3 5 7 10
1 4 6 8 11 14 18
2 9 12 15 19 23 27
3 16 20 24...
모든 행은 시작하는 행 뒤에서 2 개의 열을 시작합니다. 예를 들어, i = 0 j = 1은 i = 2j = 0 바로 뒤에옵니다.
따라서이 패턴에서 도출 할 수있는 알고리즘은 (j> i라고 가정)입니다.
int i = 2;
int j = 5;
int k;
int m;
int space = (int)(log((float)j)/log((float)i));
for(k = 0; k < space*10; k++)
{
for(m = 0; m < 10; m++)
{
int newi = k-space*m;
if(newi < 0)
break;
else if(newi > 10)
continue;
int result = pow((float)i,newi) * pow((float)j,m);
printf("%d^%d * %d^%d = %d\n", i, newi, j, m, result);
}
}
참고 : 여기의 코드는 i 및 j의 지수 값을 10보다 작게 제한합니다.이 알고리즘을 다른 임의의 범위에 맞게 쉽게 확장 할 수 있습니다.
참고 :이 알고리즘의 실행 시간은 첫 n 개의 대답에 대한 O (n)입니다.
참고 :이 알고리즘의 공간 복잡도는 O (1)입니다.
내 구현은 다음 아이디어를 기반으로합니다.
- 두 개의 대기열 Q2와 Q5를 모두 1로 초기화합니다. 두 대기열을 정렬 된 순서대로 유지합니다.
- 모든 단계에서 Q2 또는 Q5에서 가장 작은 숫자 MIN을 큐에서 빼서 인쇄하십시오. Q2와 Q5에 동일한 요소가있는 경우 둘 다 제거하십시오. 이 번호를 인쇄하십시오. 이것은 기본적으로 두 개의 정렬 된 배열을 병합하는 것입니다-각 단계에서 가장 작은 요소를 선택하고 진행하십시오.
- MIN * 2 ~ Q2 및 MIN * 5 ~ Q5를 큐에 넣습니다. MIN이 이전 MIN 수보다 높기 때문에이 변경으로 인해 Q2 / Q5의 불변이 정렬되지 않습니다.
예:
Start with 1 and 1 (to handle i=0;j=0 case):
Q2: 1
Q5: 1
Dequeue 1, print it and enqueue 1*2 and 1*5:
Q2: 2
Q5: 5
Pick 2 and add 2*2 and 2*5:
Q2: 4
Q5: 5 10
Pick 4 and add 4*2 and 4*5:
Q2: 8
Q5: 5 10 20
....
자바 코드 :
public void printNumbers(int n) {
Queue<Integer> q2 = new LinkedList<Integer>();
Queue<Integer> q5 = new LinkedList<Integer>();
q2.add(1);
q5.add(1);
for (int i = 0; i < n; i++) {
int a = q2.peek();
int b = q5.peek();
int min = Math.min(a, b);
System.out.println(min);
if (min == a) {
q2.remove();
}
if (min == b) {
q5.remove();
}
q2.add(min * 2);
q5.add(min * 5);
}
}
결과를 계산의 값과 함께 정렬 된 목록에 넣어 i및j
Edsger Dijkstra (http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF)가 user515430에 의해 구현 한 알고리즘은 아마도 최대한 빠른 속도 일 것입니다. 나는 2^i * 5^j"특별 번호" 의 한 형태 인 모든 번호를 부릅니다 . 이제 vlads O(i*j)는 이중 알고리즘을 사용합니다. 하나는 특수 숫자를 생성 O(i*j)하고 하나는 링크 된 기사에 따라 정렬합니다 O(i*j).
그러나 Dijkstra의 알고리즘을 확인하십시오 (아래 참조). 이 경우 n에 우리가 생성하는 특수 숫자의 양은입니다 i*j. 우리는 한 번 반복 1 -> n하며 모든 루프에서 일정한 동작을 수행합니다. 따라서이 알고리즘도 있습니다 O(i*j). 그리고 꽤 빠른 속도로 일정합니다.
GMP (C ++ 래퍼)를 사용하여 C ++에서 구현하고에 의존 boost::lexical_cast하지만 쉽게 제거 할 수는 있지만 (게으르고 Boost를 사용하지 않는 사람은 누구입니까?) 로 컴파일되었습니다 g++ -O3 test.cpp -lgmpxx -o test. Q6600에서 Ubuntu 10.10 time ./test 1000000은 1145ms.
#include <iostream>
#include <boost/lexical_cast.hpp>
#include <gmpxx.h>
int main(int argc, char *argv[]) {
mpz_class m, x2, x5, *array, r;
long n, i, i2, i5;
if (argc < 2) return 1;
n = boost::lexical_cast<long>(argv[1]);
array = new mpz_class[n];
array[0] = 1;
x2 = 2;
x5 = 5;
i2 = i5 = 0;
for (i = 1; i != n; ++i) {
m = std::min(x2, x5);
array[i] = m;
if (x2 == m) {
++i2;
x2 = 2 * array[i2];
}
if (x5 == m) {
++i5;
x5 = 5 * array[i5];
}
}
delete [] array;
std::cout << m << std::endl;
return 0;
}
i를 행으로, j를 열로 행렬을 그리면 패턴을 볼 수 있습니다. i = 0으로 시작한 다음 행렬의 맨 위에 도달 할 때까지 (2> 행 0) 오른쪽으로 2 행씩 올라가서 행렬을 순회합니다. 그런 다음 i + 1 등으로 이동하십시오.
따라서 i = 7의 경우 다음과 같이 여행합니다.
7, 0 -> 5, 1 -> 3, 2 -> 1, 3
그리고 i = 8 :
8, 0 -> 6, 1 -> 4, 2 -> 2, 3 -> 0, 4
여기서는 Java에서 i = 9까지 올라갑니다. 행렬 위치 (i, j)와 값을 인쇄합니다.
for(int k = 0; k < 10; k++) {
int j = 0;
for(int i = k; i >= 0; i -= 2) {
int value = (int)(Math.pow(2, i) * Math.pow(5, j));
System.out.println(i + ", " + j + " -> " + value);
j++;
}
}
내 직감 :
초기 값을 1로 i = 0, j = 0으로 설정하면 다음 숫자를 (2 ^ 1) (5 ^ 0), (2 ^ 2) (5 ^ 0), (2 ^ 0)으로 만들 수 있습니다 * (5 ^ 1), ... 즉 2,4,5 ..
어느 시점에서든 내 숫자는 x입니다. 다음과 같은 방법으로 다음 숫자를 만들 수 있습니다.
- x * 2
- x * 4
- x * 5
설명 :
Since new numbers can only be the product with 2 or 5.
But 4 (pow(2,2)) is smaller than 5, and also we have to generate
Numbers in sorted order.Therefore we will consider next numbers
be multiplied with 2,4,5.
Why we have taken x*4 ? Reason is to pace up i, such that it should not
be greater than pace of j(which is 5 to power). It means I will
multiply my number by 2, then by 4(since 4 < 5), and then by 5
to get the next three numbers in sorted order.
시운전
We need to take an Array-list of Integers, let say Arr.
Also put our elements in Array List<Integers> Arr.
Initially it contains Arr : [1]
x = 1로 시작할 수 있습니다.
다음 3 개의 숫자는 1 * 2, 1 * 4, 1 * 5 [2,4,5]입니다. Arr [1,2,4,5]
이제 x = 2
다음 3 개의 숫자는 [4,8,10]입니다. {4가 이미 발생한 이후에는 무시합니다} [8,10]; Arr [1,2,4,5,8,10]
이제 x = 4
다음 3 자리 숫자 [8,16,20] {8 이미 무시했습니다} [16,20] Arr [1,2,4,5,8,10,16,20]
x = 5
다음 3 자리 숫자 [10,20,25] {10,20} 이미 [25]가 추가됨 Arr [1,2,4,5,8,10,16,20,25]
종료 조건
Terminating condition when Arr last number becomes greater
than (5^m1 * 2^m2), where m1,m2 are given by user.
분석
Time Complexity : O(K) : where k is numbers possible between i,j=0 to
i=m1,j=m2.
Space Complexity : O(K)
다음 주에 무엇을 기대해야하는지 궁금해서이 질문을 찾았습니다.
생각은 2 ^ i가 5 ^ j만큼 큰 단계에서 증가하지 않는다고 생각합니다. 따라서 다음 j 단계가 크지 않으면 i를 늘리십시오.
C ++의 예 (Qt는 선택 사항) :
QFile f("out.txt"); //use output method of your choice here
f.open(QIODevice::WriteOnly);
QTextStream ts(&f);
int i=0;
int res=0;
for( int j=0; j<10; ++j )
{
int powI = std::pow(2.0,i );
int powJ = std::pow(5.0,j );
while ( powI <= powJ )
{
res = powI * powJ;
if ( res<0 )
break; //integer range overflow
ts<<i<<"\t"<<j<<"\t"<<res<<"\n";
++i;
powI = std::pow(2.0,i );
}
}
출력 :
i j 2^i * 5^j
0 0 1
1 1 10
2 1 20
3 2 200
4 2 400
5 3 4000
6 3 8000
7 4 80000
8 4 160000
9 4 320000
10 5 3200000
11 5 6400000
12 6 64000000
13 6 128000000
14 7 1280000000
여기 내 해결책이 있습니다
#include <stdio.h>
#include <math.h>
#define N_VALUE 5
#define M_VALUE 5
int n_val_at_m_level[M_VALUE];
int print_lower_level_val(long double val_of_higher_level, int m_level)
{
int n;
long double my_val;
for( n = n_val_at_m_level[m_level]; n <= N_VALUE; n++) {
my_val = powl(2,n) * powl(5,m_level);
if(m_level != M_VALUE && my_val > val_of_higher_level) {
n_val_at_m_level[m_level] = n;
return 0;
}
if( m_level != 0) {
print_lower_level_val(my_val, m_level - 1);
}
if(my_val < val_of_higher_level || m_level == M_VALUE) {
printf(" %Lf n=%d m = %d\n", my_val, n, m_level);
} else {
n_val_at_m_level[m_level] = n;
return 0;
}
}
n_val_at_m_level[m_level] = n;
return 0;
}
main()
{
print_lower_level_val(0, M_VALUE); /* to sort 2^n * 5^m */
}
결과 :
1.000000 n = 0 m = 0
2.000000 n = 1 m = 0
4.000000 n = 2 m = 0
5.000000 n = 0 m = 1
8.000000 n = 3 m = 0
10.000000 n = 1 m = 1
16.000000 n = 4 m = 0
20.000000 n = 2 m = 1
25.000000 n = 0 m = 2
32.000000 n = 5 m = 0
40.000000 n = 3 m = 1
50.000000 n = 1 m = 2
80.000000 n = 4 m = 1
100.000000 n = 2 m = 2
125.000000 n = 0 m = 3
160.000000 n = 5 m = 1
200.000000 n = 3 m = 2
250.000000 n = 1 m = 3
400.000000 n = 4 m = 2
500.000000 n = 2 m = 3
625.000000 n = 0 m = 4
800.000000 n = 5 m = 2
1000.000000 n = 3 m = 3
1250.000000 n = 1 m = 4
2000.000000 n = 4 m = 3
2500.000000 n = 2 m = 4
3125.000000 n = 0 m = 5
4000.000000 n = 5 m = 3
5000.000000 n = 3 m = 4
6250.000000 n = 1 m = 5
10000.000000 n = 4 m = 4
12500.000000 n = 2 m = 5
20000.000000 n = 5 m = 4
25000.000000 n = 3 m = 5
50000.000000 n = 4 m = 5
100000.000000 n = 5 m = 5
나는 내가 틀렸다는 것을 알고 있지만 여기에는 2,3,5와 같은 많은 숫자가 포함되지 않기 때문에 매우 간단한 휴리스틱이 있습니다. i, j 2 ^ i * 5 ^ j에 대해 다음 시퀀스는 2 ^ (i-2) * 5 ^ (j + 1)이됩니다. 구글이기 때문에 간단한 해결책이 있어야합니다.
def func(i, j):
print i, j, (2**i)*(5**j)
imax=i=2
j=0
print "i", "j", "(2**i)*(5**j)"
for k in range(20):
func(i,j)
j=j+1; i=i-2
if(i<0):
i = imax = imax+1
j=0
이것은 다음과 같이 출력을 생성합니다.
i j (2**i)*(5**j)
2 0 4
0 1 5
3 0 8
1 1 10
4 0 16
2 1 20
0 2 25
5 0 32
3 1 40
1 2 50
6 0 64
4 1 80
2 2 100
0 3 125
7 0 128
5 1 160
3 2 200
1 3 250
8 0 256
6 1 320
식에서 i 또는 j를 증가시킬 때 실제로 일어나는 일 2^i * 5^j을 겪으면 다른 2 또는 5를 곱하는 것입니다. i와 j의 특정 값이 주어지면 문제를 다시 언급하면 다음을 어떻게 찾을 수 있습니까? 값이 클수록 솔루션이 명확 해집니다.
직관적으로 열거 할 수있는 규칙은 다음과 같습니다.
i > 1표현식 에 2 쌍 ( ) 이 있으면 다음으로 큰 숫자를 얻으려면 5로 바꿔야합니다. 따라서,i -= 2및j += 1.- 그렇지 않으면 5 (
j > 0)가 있으면 3을 2로 바꿔야합니다. 그래서j -= 1및i += 3. - 그렇지 않으면 값을 최소로 늘리려면 다른 2 개만 제공하면됩니다.
i += 1.
Ruby의 프로그램은 다음과 같습니다.
i = j = 0
20.times do
puts 2**i * 5**j
if i > 1
j += 1
i -= 2
elsif j > 0
j -= 1
i += 3
else
i += 1
end
end
우리가 java Collection을 사용할 수 있다면 O (n ^ 2)로이 숫자를 가질 수 있습니다
public static void main(String[] args) throws Exception {
int powerLimit = 7;
int first = 2;
int second = 5;
SortedSet<Integer> set = new TreeSet<Integer>();
for (int i = 0; i < powerLimit; i++) {
for (int j = 0; j < powerLimit; j++) {
Integer x = (int) (Math.pow(first, i) * Math.pow(second, j));
set.add(x);
}
}
set=set.headSet((int)Math.pow(first, powerLimit));
for (int p : set)
System.out.println(p);
}
여기서 powerLimit는 매우 신중하게 초기화되어야합니다! 원하는 숫자 수에 따라 다릅니다.
스칼라에 대한 나의 시도는 다음과 같습니다.
case class IndexValue(twosIndex: Int, fivesIndex: Int)
case class OutputValues(twos: Int, fives: Int, value: Int) {
def test(): Boolean = {
Math.pow(2, twos) * Math.pow(5, fives) == value
}
}
def run(last: IndexValue = IndexValue(0, 0), list: List[OutputValues] = List(OutputValues(0, 0, 1))): List[OutputValues] = {
if (list.size > 20) {
return list
}
val twosValue = list(last.twosIndex).value * 2
val fivesValue = list(last.fivesIndex).value * 5
if (twosValue == fivesValue) {
val lastIndex = IndexValue(last.twosIndex + 1, last.fivesIndex + 1)
val outputValues = OutputValues(value = twosValue, twos = list(last.twosIndex).twos + 1, fives = list(last.fivesIndex).fives + 1)
run(lastIndex, list :+ outputValues)
} else if (twosValue < fivesValue) {
val lastIndex = IndexValue(last.twosIndex + 1, last.fivesIndex)
val outputValues = OutputValues(value = twosValue, twos = list(last.twosIndex).twos + 1, fives = list(last.twosIndex).fives)
run(lastIndex, list :+ outputValues)
} else {
val lastIndex = IndexValue(last.twosIndex, last.fivesIndex + 1)
val outputValues = OutputValues(value = fivesValue, twos = list(last.fivesIndex).twos, fives = list(last.fivesIndex).fives + 1)
run(lastIndex, list :+ outputValues)
}
}
val initialIndex = IndexValue(0, 0)
run(initialIndex, List(OutputValues(0, 0, 1))) foreach println
산출:
OutputValues(0,0,1)
OutputValues(1,0,2)
OutputValues(2,0,4)
OutputValues(0,1,5)
OutputValues(3,0,8)
OutputValues(1,1,10)
OutputValues(4,0,16)
OutputValues(2,1,20)
OutputValues(0,2,25)
OutputValues(5,0,32)
OutputValues(3,1,40)
OutputValues(1,2,50)
OutputValues(6,0,64)
OutputValues(4,1,80)
OutputValues(2,2,100)
OutputValues(0,3,125)
OutputValues(7,0,128)
OutputValues(5,1,160)
OutputValues(3,2,200)
OutputValues(1,3,250)
OutputValues(8,0,256)
참고 URL : https://stackoverflow.com/questions/5505894/tricky-google-interview-question
'Programing' 카테고리의 다른 글
| STL에서 실제로 deque는 무엇입니까? (0) | 2020.05.28 |
|---|---|
| 디렉토리를 비교하는 도구 (Windows 7) (0) | 2020.05.28 |
| .git / config 파일에서 줄을 주석 처리 할 수 있습니까? (0) | 2020.05.28 |
| sbt에서“자세한 내용은 사용 중단 된 상태로 다시 실행”하는 방법은 무엇입니까? (0) | 2020.05.28 |
| Git-Windows에서 .netrc 파일을 사용하여 사용자 및 비밀번호를 저장하는 방법 (0) | 2020.05.28 |