시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
n 크기의 배열 a []가 주어집니다. 의 모든 요소 정렬 1을 제외하고 두 번 존재합니다. 한 번만 나타나는 요소를 찾으십시오. 즉, 단일 숫자를 찾는다고 말합니다.
차례
예
입력 : a [] = {1, 3, 5, 5, 2, 1, 3}
출력 : 2
입력 : a [] = {1, 3, 5, 5, 1}
출력 : 3
간단한 방법
다른 모든 요소로 각 요소를 확인하십시오. 단일 요소를 반환합니다.
암호알고리즘
- n 크기의 배열 a []를 초기화합니다.
- 배열에 단일 요소를 저장하는 정수 변수를 만들고 플래그 변수를 0으로 초기화합니다.
- 배열을 순회하고 플래그 변수를 0으로 업데이트하고 단일 요소에 대한 변수를 배열 a []의 현재 인덱스에 저장된 값으로 업데이트합니다.
- 0에서 n-1까지 내부 루프를 만들고 배열 a []의 현재 인덱스에 저장된 값이 단일 요소의 변수와 같고 내부 루프의 현재 인덱스가 현재 인덱스와 같지 않은지 확인합니다. 외부 루프에서 플래그 변수를 1로 업데이트합니다.
- 플래그 변수가 0이면 단일 요소에 대한 변수를 반환합니다.
단일 숫자를 찾는 C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
int singleElement(int a[], int n){
int single,flag=0;
for(int i=0; i<n; i++){
flag = 0;
single = a[i];
for(int j=0; j<n; j++){
if((a[j]==single)&&(j!=i)){
flag=1;
}
}
if(flag==0)
return single;
}
}
int main() {
int a[] = {1, 3, 5, 5, 2, 1, 3};
int n = sizeof(a)/sizeof(a[0]);
cout<<singleElement(a, n);
return 0;
}
2
단일 번호를 찾는 Java 프로그램
class unique{
static int singleElement(int[] a, int n){
int single=0,flag=0;
for(int i=0; i<n; i++){
flag = 0;
single = a[i];
for(int j=0; j<n; j++){
if((a[j]==single)&&(j!=i)){
flag=1;
}
}
if(flag==0){
return single;
}
}
return single;
}
public static void main (String[] args){
int a[] = {1, 3, 5, 5, 2, 1, 3};
int n = a.length;
System.out.println(singleElement(a, n));
}
}
2
복잡성 분석
시간 복잡성 : 의 위에2) 여기서 n은 주어진 배열 a []의 요소 수입니다.
보조 공간 : O (1) 우리는 일정한 추가 공간을 사용했기 때문입니다.
Xor 사용
xor의 속성 사용 –
a xor a = 0
0 xor a = a
암호알고리즘
- n 크기의 배열 a []를 초기화합니다.
- 정수 배열과 정수 배열의 크기를 매개 변수로 받아들이는 주어진 배열 a []에서 단일 요소를 찾는 함수를 만듭니다.
- 변수 single을 초기화하고 주어진 배열의 첫 번째 요소를 그 안에 저장합니다.
- 배열을 1에서 n-1까지 순회하고 변수 single 자체의 xor와 주어진 배열의 현재 인덱스에있는 값으로 변수 single을 업데이트합니다.
- 변수 single을 반환합니다.
단일 숫자를 찾는 C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
int singleElement(int a[], int n){
int single = a[0];
for(int i=1; i<n; i++)
single = single ^ a[i];
return single;
}
int main() {
int a[] = {1, 3, 5, 5, 2, 1, 3};
int n = sizeof(a)/sizeof(a[0]);
cout<<singleElement(a, n);
return 0;
}
2
단일 번호를 찾는 Java 프로그램
class unique{
static int singleElement(int[] a, int n){
int single = a[0];
for(int i=1; i<n; i++)
single = single ^ a[i];
return single;
}
public static void main (String[] args){
int a[] = {1, 3, 5, 5, 2, 1, 3};
int n = a.length;
System.out.println(singleElement(a, n));
}
}
2
복잡성 분석
시간 복잡성 : O (n) 여기서 n은 주어진 배열 a []의 요소 수입니다.
보조 공간 : O (1) 우리는 일정한 추가 공간을 사용했기 때문입니다.
