시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
“Contiguous Array Leetcode”문제는 사용자에게 정렬 크기 n의 a []는 1과 0으로 만 구성됩니다. 찾기 가장 긴 부분 배열 여기서 1의 수는 0의 수와 같습니다.
예
a[ ] = {1, 0, 1, 1, 1, 0, 0}
1 to 6
설명 : 인덱스 1에서 6까지의 하위 배열을 선택하면 길이 6의 최상의 결과를 얻을 수 있습니다. 1에서 6까지의 연속 배열에는 3 개의 3과 0 개의 XNUMX이 있습니다. 여기서는 XNUMX 기반 인덱싱을 고려했습니다.
a[ ] = {1, 1}
No such subarray
접근
순진한 방법
가능한 모든 하위 배열을 생성합니다. 1의 수가 0의 수와 같은 하위 배열이 있는지 확인합니다. 하위 배열의 왼쪽과 오른쪽 경계에 두 개의 포인터 i와 j를 사용합니다. 그런 다음 0을 -0로 바꾼 후 i에서 j까지의 부분 배열 합계가 합계 = 1인지 확인합니다. 그것이 사실이라면 조건을 만족하는 하위 배열을 찾은 것입니다. 이제 답변을 업데이트합니다.
연속 배열 leetcode 문제에 대한 알고리즘
1. Initialize a binary array a[] of size n and three variables sum, max=-1, and start. 2. Traverse through the array and update sum as -1 if a[i] is 0 else 1. 3. Traverse the inner loop and add -1 in sum if a[i] is 0 else 1. 4. Check if the sum is 0 and max is less than j-i+1, update max as j-i+1 and start as i. 5. Outside the loops check if max is -1 print "No such subarray" else print starting and ending index.
암호
연속 배열 Leetcode 문제를 해결하는 C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
int subArray(int a[], int n){
int sum = 0;
int max = -1, start;
for(int i=0; i<n-1; i++){
sum = (a[i]==0) ? -1 : 1;
for(int j=i+1; j<n; j++){
(a[j]==0) ? (sum+=-1) : (sum+=1);
if(sum == 0 && max < j-i+1){
max = j-i+1;
start = i;
}
}
}
if(max == -1)
cout<<"No such subarray";
else
cout<<start<<" to "<<start+max-1;
return max;
}
int main(){
int a[] = { 1, 0, 1, 1, 1, 0, 0 };
int n = sizeof(a) / sizeof(a[0]);
subArray(a, n);
return 0;
}
1 to 6
Contiguous Array Leetcode 문제를 해결하는 Java 프로그램
class LongestSubArray{
int subArray(int a[], int n){
int sum = 0;
int max = -1, start=0,end=0;
for(int i=0; i<n-1; i++){
sum = (a[i]==0) ? -1 : 1;
for(int j=i+1; j<n; j++){
if(a[j] == 0)
sum += -1;
else
sum += 1;
if(sum == 0 && max < j-i+1){
max = j-i+1;
start = i;
}
}
}
if(max == -1)
System.out.println("No such subarray");
else
end = start+max-1;
System.out.println(start+" to "+end);
return max;
}
public static void main(String[] args){
LongestSubArray s = new LongestSubArray();
int a[] = { 1, 0, 1, 1, 1, 0, 0 };
int n = a.length;
s.subArray(a, n);
}
}
1 to 6
복잡성 분석
시간 복잡성
여기서부터 우리는 포인터를 고정한 상태로 배열을 순회하고있었습니다. 우리는 다음과 같은 다항식 시간 복잡도를 얻었습니다. 의 위에2) 여기서 n은 주어진 배열 a []에있는 요소의 수입니다.
공간 복잡성
O (1) 일정한 여유 공간을 사용했기 때문입니다. 우리는 일정한 수의 변수 만 만들었습니다. 그러나 초기 입력 배열 이외의 배열을 사용하지 않았습니다. 그러나 입력 요소를 저장하기 위해 배열을 사용했기 때문에 프로그램 전체는 O (N) 공간 복잡성이 있습니다.
해시 맵 사용
연속 배열 leetcode 문제에 대한 알고리즘
1. Initialize a binary array a[] of size n. 2. Initialize an unordered map. 3. Traverse through the array and update the array value of the current index as -1 if current value if 0 else 1. 4. Traverse through the array and add the elements. 5. If the sum is 0, update max as i+1 and end as i. 6. Else Traverse map and update max as i - map(sum+n) and end as i if max is less than i - map(sum+n) else update map(sum+n) as i. 7. Traverse through the array and update the array value of the current index as 0 if current value is -1 else 1. 8. If the end is greater than -1 print starting and ending index. 9. Else print "No such subarray".
여기서 우리가 한 것은 합계가 0 인 가장 큰 하위 배열을 찾을 때마다 간단히 수행합니다. 우리가하는 일은 접두사 합계를 가져 와서 동일한 합계를 찾을 수있는 곳이있는 경우 맵을 체크인하는 것입니다. 그러면 맵 +1에 저장된 값에서 현재 인덱스까지의 하위 배열의 합계는 0입니다. 여기서는 (sum + n)을 키로 사용합니다. 그러나 합계를 직접 사용할 수도 있습니다. 그러나 (sum + n)을 키로 사용하면 HashMap 대신 배열을 사용할 수도 있습니다. 그러면 (sum + n)> = 0이고 배열 인덱싱이 0부터 시작하도록 보장 할 수 있기 때문입니다.
암호
연속 배열 Leetcode 문제를 해결하는 C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
int subArray(int a[], int n){
unordered_map<int, int> hM;
int sum = 0, max = 0, end = -1;
for(int i=0; i<n; i++)
a[i] = (a[i] == 0) ? -1 : 1;
for(int i=0; i<n; i++){
sum += a[i];
if(sum == 0){
max = i + 1;
end = i;
}
if(hM.find(sum + n) != hM.end()){
if(max < i - hM[sum + n]){
max = i - hM[sum + n];
end = i;
}
}
else
hM[sum + n] = i;
}
for(int i=0; i<n; i++)
a[i] = (a[i] == -1) ? 0 : 1;
if(end>-1)
cout<<end - max + 1<<" to "<<end;
else
cout<<"No such subarray";
return max;
}
int main(){
int a[] = {1, 0, 1, 1, 1, 0, 0};
int n = sizeof(a) / sizeof(a[0]);
subArray(a, n);
return 0;
}
1 to 6
Contiguous Array Leetcode 문제를 해결하는 Java 프로그램
import java.util.HashMap;
class LongestSubArray{
int subArray(int a[], int n){
HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();
int sum = 0, max = 0, end = -1, start = 0;
for(int i=0; i<n; i++){
a[i]=(a[i]==0) ? -1 : 1;
}
for(int i=0; i<n; i++){
sum += a[i];
if(sum == 0){
max = i + 1;
end = i;
}
if(hM.containsKey(sum + n)){
if(max < i - hM.get(sum + n)){
max = i - hM.get(sum + n);
end = i;
}
}
else
hM.put(sum + n, i);
}
for(int i=0; i<n; i++) {
a[i] = (a[i] == -1) ? 0 : 1;
}
int index = end - max + 1;
if(end>-1)
System.out.println(index + " to " + end);
else
System.out.println("No such subarray");
return max;
}
public static void main(String[] args){
LongestSubArray s = new LongestSubArray();
int a[] = { 1, 0, 1, 1, 1, 0, 0 };
int n = a.length;
s.subArray(a, n);
}
}
1 to 6
복잡성 분석
시간 복잡성
의 위에) 여기서 n은 주어진 배열 a []에있는 요소의 수입니다. e가 unorder_map / HashMap을 사용했기 때문에 HashMap은 O (1) 시간이 삽입 검색, 삭제를 수행 할 수 있도록 허용하기 때문에 O (N) 시간을 달성 할 수있었습니다.
공간 복잡성
의 위에) N 개의 추가 공간을 사용했기 때문입니다. HashMap 광고를 사용했기 때문에 N 요소에 대한 정보가 저장되었으므로 최악의 경우 N 요소를 가질 수 있습니다.
