시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
이 문제에서 우리는 각 요소가 (start + 2 * i)와 같은 크기 n의 배열에서 XOR 연산을해야합니다.
배열의 모든 요소의 비트 별 XOR을 반환해야합니다.
예
n = 4, start = 3
8
설명 :
배열 번호는 [3, 5, 7, 9]와 같습니다. 여기서 (3 ^ 5 ^ 7 ^ 9) = 8입니다.
여기서“^”는 비트 XOR 연산자에 해당합니다.
n = 1, start = 7
7
설명 :
배열 nums는 [7]이므로 xor = 7입니다.
접근 (Brute Force)
i = 0에서 i = n-1까지 for 루프를 n 번 실행하면됩니다. for 루프에서 우리는 변수 res에 저장할 현재 xor로 (start + 2 * i)의 비트 xor를 수행 할 것입니다.
암호알고리즘
1. 배열 요소의 인덱스를 나타내는 변수 ind를 만들고 0으로 초기화합니다.
2. for 루프 동안 현재 xor를 저장할 변수 res를 만들고 0으로 초기화합니다.
3. ind = 0에서 ind = n-1까지 for 루프를 실행합니다.
4. (start + 2 * i) 즉, 인덱스 ind의 요소로 res의 비트 xor를 수행하고 결과를 res에 저장합니다.
5. res를 반환합니다.
어레이 Leetcode 솔루션에서 XOR 작동을위한 구현
C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
int xorOperation(int n, int start) {
int ind=0;
int res=0;
for(ind=0;ind<n;ind++) res=res^(start+2*ind);
return res;
}
int main()
{
int n=4;
int start=3;
cout<<xorOperation(n,start)<<endl;
return 0;
}
8
자바 프로그램
import java.lang.*;
class XorOperation
{
public static int xorOperation(int n, int start)
{
int ind=0;
int res=0;
for(ind=0;ind<n;ind++) res=res^(start+2*ind);
return res;
}
public static void main(String args[])
{
int n=4;
int start=3;
System.out.println(xorOperation(n,start));
}
}
8
어레이 Leetcode 솔루션에서 XOR 연산을위한 복잡성 분석
시간 복잡성
의 위에): 여기서 N은 주어진 배열 크기입니다. N 개의 요소에 대해 단일 for 루프에서 배열을 순회하고 있습니다. 따라서 시간 복잡도는 O (N)입니다.
공간 복잡성
O (1) : 일부 변수 이외의 추가 메모리를 사용하지 않기 때문입니다. 따라서 사용되는 추가 공간은 일정합니다.
접근하다 (비트 조작)
위의 문제에서 우리는 각 다음 요소의 차이가 2임을 알 수 있습니다. 이는 모든 요소가 짝수이거나 모두 홀수임을 의미합니다. 그것은 일종의 범위를 만들지 만 연속적이지는 않습니다. 즉 대체 값을 가지고 있습니다.
비트 조작을 사용하여 일정한 시간에 연속 요소가있는 범위의 비트 xor를 찾을 수 있습니다. 방법을 살펴본 다음 위의 문제를 아래 문제로 변환 해 보겠습니다.
범위 = [3,4,5,6,7,8,9,10]을 가정하고 첫 번째 요소와 마지막 요소 사이의 범위에 xor를 적용해야합니다.
x는 짝수이고 y는 xie y = x + 1 옆의 숫자라고합시다. x와 y의 xor는 항상 1이된다는 것을 쉽게 분석 할 수 있습니다. 또는 모든 짝수와 그 옆의 홀수의 xor는 항상 1입니다. 1.
i.e. 4^5=1, 6^7=1, 8^9=1
이제 그 쌍의 수가 홀수이면 첫 번째 짝수와 마지막 홀수 사이의 요소 xor는 1 또는 1이됩니다.
즉 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 = 1 ^ 1 ^ 1 = 1
이제 3과 10 인 끝 위치에 숫자 만 남았습니다. 따라서 아래 그림과 같이 답은 3 ^ 1 ^ 10 = 8이됩니다.
문제를 연속 범위 XOR로 변환
위의 문제에서 우리는 각 요소 사이의 거리를 2에서 1로 줄일 수 있습니다. 비트 단위로 오른쪽 시프트 각 요소는 1로 나눈다 (2로 나누는 것과 동일). 이렇게하면 요소의 마지막 부분에만 영향을줍니다. 따라서 먼저 다음과 같은 경우에 따라 ans의 마지막 비트를 저장합니다.
1. 배열의 모든 요소가 홀수이고 총 요소 수도 홀수이면 lastbit = 1입니다.
2. 그렇지 않으면 lastbit = 0.
이제 각 요소를 1만큼 오른쪽으로 이동하면 범위는 다음과 같습니다.
시작 / 2, 시작 / 2 +1, 시작 / 2 +2,. . . . , 시작 / 2 + (n-1).
여기서 처음은 시작 / 2이고 마지막은 시작 / 2 + (n-1)입니다.
이제 우리는 끝 요소의 비트 xor와 그 사이의 모든 짝수-홀수 쌍을 일정한 시간에 찾아이 범위의 xor를 쉽게 찾을 수 있습니다.
xor를 찾은 후에는 비트 왼쪽 시프트 최종 답변에서 비트의 원래 위치를 얻기 위해 결과를 1만큼 얻습니다. 마지막으로 결과에 lastbit를 추가하고 반환합니다.
어레이 Leetcode 솔루션에서 XOR 작동을위한 구현
C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
int xorOperation(int n, int start) {
int lastbit;
if(n%2==1 && start%2==1) lastbit=1;
else lastbit=0;
//after 1 right shift
int first= start/2;
int last= start/2+ n-1;
int res=0;
if(first%2==1)
{
res^=first;
first++;
}
if(last%2==0)
{
res^=last;
last--;
}
int pairs=0; //in between pairs
if(first<last) pairs= (last-first+1)/2;
if(pairs%2==1) res^=1;
res<<=1; // back to 1 left shift
res+=lastbit; // attaching last bit
return res;
}
int main()
{
int n=4;
int start=3;
cout<<xorOperation(n,start)<<endl;
return 0;
}
8
자바 프로그램
import java.lang.*;
class Rextester
{
public static int xorOperation(int n, int start)
{
int lastbit;
if(n%2==1 && start%2==1) lastbit=1;
else lastbit=0;
//after 1 right shift
int first= start/2;
int last= start/2+ n-1;
int res=0;
if(first%2==1)
{
res^=first;
first++;
}
if(last%2==0)
{
res^=last;
last--;
}
int pairs=0; //in between pairs
if(first<last) pairs= (last-first+1)/2;
if(pairs%2==1) res^=1;
res<<=1; // back to 1 left shift
res+=lastbit; // attaching last bit
return res;
}
public static void main(String args[])
{
int n=4;
int start=3;
System.out.println(xorOperation(n,start));
}
}
8
어레이 Leetcode 솔루션에서 XOR 연산을위한 복잡성 분석
시간 복잡성
O (1) : 배열의 모든 요소를 순회하지 않기 때문에 비트 조작을 사용하여 일정한 시간에 수행했습니다.
공간 복잡성
O (1) : 여기서도 사용되는 추가 메모리는 일정합니다.
