시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
n 개의 요소를 포함하는 배열 또는 집합이 주어집니다. 여기서 요소는 고유하거나 반복이 없습니다. 셔플 정렬중복이없는 숫자 (또는 세트).
차례
예
// 세트 2, 4, 3 및 1로 배열을 초기화합니다.
int [] nums = {2, 4, 3, 1};
Shuffle 객체 = new Shuffle (nums);
// 배열 [2, 4, 3, 1]을 섞고 그 결과를 반환합니다. [2, 4, 3, 1]의 모든 순열은 반환 될 가능성이 동일해야합니다 (예 : [4, 2, 1, 3] object.shuffle ();
// 배열을 원래 배열 구성 (예 : [2, 4, 3, 1])으로 재설정합니다.
solution.reset ();
두 개의 해시 맵을 사용하여 O (n) 시간 복잡도를 사용하여이를 수행 할 수 있습니다.
배열 셔플에 사용되는 데이터 구조
M (저장 값, 인덱스 쌍) 매핑
맵 K (값 저장, 인덱스 변경)
배열에있는 현재 요소를 저장하는 벡터 arr.
예 :
생성자 함수 알고리즘
- 주어진 배열 번호에있는 모든 요소에 대해 :
- arr [i] = nums [i]
- K에 키 값 쌍 (nums [i], i)을 삽입합니다.
- M에 키 값 쌍 (nums [i], i)을 삽입합니다.
reset () 알고리즘
- 맵 M (iterator it)에있는 모든 항목에 대해 :
- arr [it.second] = arr [it.first], 벡터를 원래 값으로 업데이트합니다.
- 반환 arr.
shuffle () 알고리즘
- n에서 0까지 루프 실행 :
- 범위 (0, n)에서 임의의 인덱스 (인덱스)를 선택합니다.
- 인덱스에있는 요소를 가져 와서 배열에있는 마지막 요소로 바꿉니다.
- 인덱스 요소와 맵 K의 마지막 요소에 대한 해시 값을 업데이트합니다.
- 반환 arr.
실시
배열 셔플을위한 C ++ 프로그램
#include<bits/stdc++.h>
using namespace std;
class Shuffle {
public:
vector<int> arr;
unordered_map<int,int> m;
unordered_map<int,int> k;
Shuffle(vector<int>& nums) {
for(int i=0;i<nums.size();i++){
arr.push_back(nums[i]);
m.insert({nums[i],i});
k.insert({nums[i],i});
}
}
/** Resets the array to its original configuration and return it. */
vector<int> reset() {
for(auto it:m){
arr[it.second]=it.first;
}
return arr;
}
/** Returns a random shuffling of the array. */
vector<int> shuffle() {
int n=arr.size();
while(n){
int in=rand()%n;
int index= k[arr[n-1]];
k[arr[n-1]]=k[arr[in]];
k[arr[in]]=index;
swap(arr[in],arr[n-1]);
n--;
}
return arr;
}
};
int main()
{
vector<int> nums = {2,3,4,1,5,6};
Shuffle* obj = new Shuffle(nums);
cout<<"Original array:\n";
for(int i=0;i<nums.size();i++){
cout<<nums[i]<<" ";
}
vector<int> _shuffle = obj->shuffle();
cout<<"\nArray after shuffle:\n";
for(int i=0;i<_shuffle.size();i++){
cout<<_shuffle[i]<<" ";
}
vector<int> _reset = obj->reset();
cout<<"\nArray after reset:\n";
for(int i=0;i<_reset.size();i++){
cout<<_reset[i]<<" ";
}
return 0;
}
Original array: 2 3 4 1 5 6 Array after shuffle: 2 4 1 5 6 3 Array after reset: 2 3 4 1 5 6
Shuffle an Array를위한 JAVA 프로그램
import java.util.*;
class Shuffle {
HashMap<Integer, Integer> m,k;
int[] arr;
public Shuffle(int[] nums) {
m = new HashMap<>();
k = new HashMap<>();
int n=nums.length;
arr = new int[n];
for(int i=0;i<n;i++){
arr[i]=nums[i];
m.put(nums[i],i);
k.put(nums[i],i);
}
}
/** Resets the array to its original configuration and return it. */
public int[] reset() {
for(Map.Entry<Integer, Integer> it : m.entrySet()){
arr[it.getValue()]=it.getKey();
}
return arr;
}
/** Returns a random shuffling of the array. */
public int[] shuffle() {
int n=arr.length;
Random rand = new Random();
while(n>0){
int in=rand.nextInt(n);
int index = k.get(arr[n-1]);
k.put(arr[n-1],k.get(arr[in]));
k.put(arr[in],index);
int temp = arr[in];
arr[in] = arr[n-1];
arr[n-1] = temp;
n--;
}
return arr;
}
}
public class Main
{
public static void main(String[] args) {
int[] nums = {2,3,4,6};
Shuffle obj = new Shuffle(nums);
System.out.print("Original array:\n");
for(int i=0;i<nums.length;i++){
System.out.print(nums[i]+" ");
}
int[] _shuffle = obj.shuffle();
System.out.print("\nArray after shuffle:\n");
for(int i=0;i<_shuffle.length;i++){
System.out.print(_shuffle[i]+" ");
}
int[] _reset = obj.reset();
System.out.print("\nArray after reset:\n");
for(int i=0;i<_reset.length;i++){
System.out.print(_reset[i]+" ");
}
}
}
Original array: 2 3 4 6 1 0 1 0 Array after shuffle: 4 6 2 3 Array after reset: 2 3 4 6
배열 셔플을위한 복잡성 분석
시간 복잡성
O (n) 모든 함수 즉, 생성자 함수, shuffle (), reset () 모든 함수는 배열의 순회를 한 번만 필요로합니다. 이것이 우리를 선형 시간 복잡성으로 이끄는 이유입니다.
공간 복잡성
O (n), 값 인덱스 쌍을 저장하려면 n 크기의 보조 해시 맵 2 개가 필요합니다.
