시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
“k 문자를 제거한 후 주어진 문자열에서 문자 수의 최소 제곱합”문제는 현 소문자 만 포함. 나머지 문자열에서 각 문자의 빈도 제곱의 합이 최소가되도록 문자열에서 k 문자를 제거 할 수 있습니다. 그 최소값을 찾아서 인쇄하십시오.
예
str = "aabcd" k = 2
3
str = "aabbcc" k = 2
6
str = "aaaaabbxd" k = 1
22
순진한 접근
제거하는 것이 항상 최적입니다. 문자 최대 주파수로.
- 주어진 원래 문자열에서 모든 문자의 빈도를 세고 freq 배열에 저장하십시오.
- 종류 내림차순의 freq 배열.
- 4 단계를 'k'번 반복합니다.
- freq 배열에서 첫 번째 요소의 주파수를 1만큼 줄이고 freq 배열을 다시 정렬합니다.
- 최소값은 freq 배열에있는 값의 제곱의 합입니다.
시간 복잡성 = O (n + k * c)
공간 복잡성 = O (1)
여기서 c는 문자열의 고유 문자 수와 같은 상수입니다.
k 문자를 제거한 후 주어진 문자열에서 문자 수의 최소 제곱합을 찾는 코드
자바 코드
import java.util.Arrays;
import java.util.Collections;
class MinimumSumOfSquaresOfCharacterCountsInAGivenStringAfterRemovingKCharacters {
private static int minSumSquares(String str, int k) {
char sArr[] = str.toCharArray();
int minSum = 0;
// create a freq array, with initial value as 0
Integer freq[] = new Integer[26];
for (int i = 0; i < 26; i++) {
freq[i] = 0;
}
// traverse in the original string and calculate the frequency of every character
for (int i = 0; i < sArr.length; i++) {
freq[sArr[i] - 'a']++;
}
// sort the array in descending order
Arrays.sort(freq, Collections.reverseOrder());
// remove k characters
for (int i = 0; i < k; i++) {
// remove the character with maximum freq and reduce the freq
freq[0]--;
// sort the array in descending order
Arrays.sort(freq, Collections.reverseOrder());
}
// minSum is the sum of squares of all the elements in freq array
for (int i = 0; i < 26; i++) {
minSum += (freq[i] * freq[i]);
}
return minSum;
}
public static void main(String[] args) {
// Example 1
String str1 = "aabcd";
int k1 = 2;
System.out.println(minSumSquares(str1, k1));
// Example 2
String str2 = "aabbcc";
int k2 = 2;
System.out.println(minSumSquares(str2, k2));
// Example 3
String str3 = "aaaaabbxd";
int k3 = 1;
System.out.println(minSumSquares(str3, k3));
}
}
3 6 22
C ++ 코드
#include<bits/stdc++.h>
using namespace std;
int minSumSquares(string str, int k) {
int minSum = 0;
// create a freq array, with initial value as 0
int freq[26];
for (int i = 0; i < 26; i++) {
freq[i] = 0;
}
// traverse in the original string and calculate the frequency of every character
for (int i = 0; i < str.length(); i++) {
freq[str[i] - 'a']++;
}
// sort the array in descending order
sort(freq, freq + 26, greater<int>());
// remove k characters
for (int i = 0; i < k; i++) {
// remove the character with maximum freq and reduce the freq
freq[0]--;
// sort the array in descending order
sort(freq, freq + 26, greater<int>());
}
// minSum is the sum of squares of all the elements in freq array
for (int i = 0; i < 26; i++) {
minSum += (freq[i] * freq[i]);
}
return minSum;
}
int main() {
// Example 1
string str1 = "aabcd";
int k1 = 2;
cout<<minSumSquares(str1, k1)<<endl;
// Example 2
string str2 = "aabbcc";
int k2 = 2;
cout<<minSumSquares(str2, k2)<<endl;
// Example 3
string str3 = "aaaaabbxd";
int k3 = 1;
cout<<minSumSquares(str3, k3)<<endl;
return 0;
}
3 6 22
최적의 접근 방식
최대 빈도로 캐릭터를 제거하는 목표는 Priority Queue를 사용하여 최적으로 달성 할 수 있습니다.
- 만들기 우선 순위 대기열 q는 최대 힙입니다.
- 원래 문자열에서 모든 문자의 빈도를 세고 우선 순위 대기열을 만듭니다.
- 4 단계를 'k'번 반복합니다.
- 우선 순위 대기열의 맨 위를 제거하고 1만큼 줄이고 XNUMX이 아니면 우선 순위 대기열로 다시 밀어 넣습니다.
- 최소값은 우선 순위 대기열에있는 값의 제곱의 합입니다.
시간 복잡성 = O (n + k * log (c))
공간 복잡성 = O (c)
여기서 c는 문자열의 고유 문자 수와 같은 상수입니다. 우선 순위 대기열에서 k 요소를 제거하고 있기 때문입니다. 우선 순위 대기열에서 삽입 및 제거 O (로그 N) 시각. 그래서 인자 logN이 왔습니다. 공간 복잡성은 주파수 배열을 만들었지 만 주파수 배열의 크기가 입력과 무관하기 때문입니다. 따라서 공간 복잡성은 일정합니다.
k 문자를 제거한 후 주어진 문자열에서 문자 수의 최소 제곱합을 찾는 코드
자바 코드
import java.util.Collections;
import java.util.PriorityQueue;
class MinimumSumOfSquaresOfCharacterCountsInAGivenStringAfterRemovingKCharacters {
private static int minSumSquares(String str, int k) {
char[] sArr = str.toCharArray();
// create a frequency array
int freq[] = new int[26];
// traverse in the original string and count the frequency of each character
for (int i = 0; i < sArr.length; i++) {
freq[sArr[i] - 'a']++;
}
// create a priority queue and store the frequency of each character
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
for (int i = 0; i < 26; i++) {
if (freq[i] != 0)
priorityQueue.add(freq[i]);
}
// remove k characters
for (int i = 0; i < k; i++) {
// remove the character with maximum frequency
int curr = priorityQueue.poll();
// reduce the frequency
curr--;
if (curr != 0)
priorityQueue.add(curr);
}
int minSum = 0;
// min sum is the sum of squares of elements in priority queue
for (Integer i : priorityQueue) {
minSum += (i * i);
}
return minSum;
}
public static void main(String[] args) {
// Example 1
String str1 = "aabcd";
int k1 = 2;
System.out.println(minSumSquares(str1, k1));
// Example 2
String str2 = "aabbcc";
int k2 = 2;
System.out.println(minSumSquares(str2, k2));
// Example 3
String str3 = "aaaaabbxd";
int k3 = 1;
System.out.println(minSumSquares(str3, k3));
}
}
3 6 22
C ++ 코드
#include<bits/stdc++.h>
using namespace std;
int minSumSquares(string str, int k) {
int minSum = 0;
// create a freq array, with initial value as 0
int freq[26];
for (int i = 0; i < 26; i++) {
freq[i] = 0;
}
// traverse in the original string and calculate the frequency of every character
for (int i = 0; i < str.length(); i++) {
freq[str[i] - 'a']++;
}
// create a priority queue and store the frequency of each character
priority_queue<int> pq;
for (int i = 0; i < 26; i++) {
if (freq[i] != 0) {
pq.push(freq[i]);
}
}
// remove k characters
for (int i = 0; i < k; i++) {
// remove the character with maximum frequency
int curr = pq.top();
pq.pop();
// reduce the frequency
curr--;
if (curr != 0) {
pq.push(curr);
}
}
// min sum is the sum of squares of elements in priority queue
while (!pq.empty()) {
minSum += (pq.top() * pq.top());
pq.pop();
}
return minSum;
}
int main() {
// Example 1
string str1 = "aabcd";
int k1 = 2;
cout<<minSumSquares(str1, k1)<<endl;
// Example 2
string str2 = "aabbcc";
int k2 = 2;
cout<<minSumSquares(str2, k2)<<endl;
// Example 3
string str3 = "aaaaabbxd";
int k3 = 1;
cout<<minSumSquares(str3, k3)<<endl;
return 0;
}
3 6 22
