시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
상위 K 개 단어 문제에서 우리는 단어 목록과 정수 k를 제공했습니다. 목록에서 가장 자주 사용되는 k 개의 문자열을 인쇄합니다.
차례
예
입력 :
list = { "code", "sky", "pen", "sky", "sky", "blue", "code"}
k = 2
출력 :
하늘
암호
입력 :
목록 = { "예", "아니요", "예", "예"}
k = 1
출력 :
예
상위 K 단어에 대한 설명
주어진 목록 = { "cpp", "java", "java", "cpp", "python", "java", "cpp", "kotlin", "kotlin", "java"} 및 k = 3
각 단어의 총 발생 횟수 –
- cpp는 주어진 목록에서 3 번 발생했습니다.
- java는 주어진 목록에서 4 번 발생했습니다.
- 파이썬은 주어진 목록에서 1 번 발생했습니다.
- kotlin은 주어진 목록에서 2 번 발생했습니다.
각 단어의 발생 횟수 감소 –
자바, cpp, kotlin, python
따라서 주어진 목록에서 자주 사용되는 상위 k 개 (즉 3 개) 단어는 다음과 같습니다.
- 자바
- CPP
- 코 틀린
상위 K 개 빈번한 단어에 대한 알고리즘
- 단어 목록과 정수 k를 초기화합니다.
- 지도 및 우선 순위 초기화 변발.
- 목록을 탐색하고 맵을 증가시킵니다 [list [i]]].
- 맵을 탐색하고 우선 순위 대기열의 크기가 k 미만인지 확인하여 대기열의 현재 요소를 푸시합니다.
- 그렇지 않으면 큐의 최상위 요소가 현재 요소보다 작 으면 최상위 요소를 제거하고 현재 요소를 큐에 삽입합니다.
- 그렇지 않으면 대기열의 최상위 요소가 현재 요소와 같고 최상위 요소의 키가 현재 요소의 키보다 크면 최상위 요소를 제거하고 현재 요소를 대기열에 삽입합니다.
- 빈 목록을 만듭니다.
- 큐를 탐색하고 임시 변수에 최상위 요소를 저장하고 최상위 요소를 삭제 한 다음 새 목록에 키를 저장합니다.
- 새 목록을 되돌리고 반환하십시오.
상위 k 개의 자주 사용되는 단어를 찾는 C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
void frequent(vector<auto> v){
for(int i = 0; i<v.size(); i++){
cout<<v[i]<< endl;
}
}
struct Comparator{
bool operator()(pair <string ,int> a, pair <string, int> b){
if(a.second != b.second)
return !(a.second < b.second);
return !(a.first > b.first);
}
};
class Solution{
public:
static bool cmp(pair <string, int> a, pair <string, int> b){
if(a.second != b.second)
return a.second > b.second;
return a.first < b.first;
}
vector<string> topFrequent(vector<string>& words, int k){
map<string, int> m;
priority_queue < pair <string, int>, vector < pair <string, int> >, Comparator > v;
for(int i = 0; i < words.size(); i++){
m[words[i]]++;
}
map<string, int> :: iterator i = m.begin();
while(i != m.end()){
if(v.size() < k){
v.push(*i);
}
else if(v.top().second < i->second){
v.pop();
v.push(*i);
}
else if(v.top().second == i->second && v.top().first > i->first){
v.pop();
v.push(*i);
}
i++;
}
vector <string> res;
while(!v.empty()){
pair <string, int> temp = v.top();
v.pop();
res.push_back(temp.first);
}
reverse(res.begin(), res.end());
return res;
}
};
int main(){
Solution s;
vector<string> v = {"code", "sky", "pen", "sky", "sky", "blue", "code"};
int k = 2;
frequent(s.topFrequent(v, k));
return 0;
}
sky code
자주 사용되는 상위 k 단어를 찾는 Java 프로그램
import java.util.*;
class text{
public List<String> topKFrequentAlternate(final String[] words, int k) {
final Map<String, Integer> freq = new HashMap<>();
final Queue<WordFreq> queue = new PriorityQueue<>((w1, w2) -> {
if (w1.getFreq() != w2.getFreq()) {
return w1.getFreq() - w2.getFreq();
}
return w2.getWord().compareTo(w1.getWord());
});
final List<String> result = new ArrayList<>();
for (final String word : words) {
if (freq.containsKey(word)) {
final int count = freq.get(word);
freq.put(word, count + 1);
} else {
freq.put(word, 1);
}
}
for (final Map.Entry<String, Integer> entry : freq.entrySet()) {
queue.offer(new WordFreq(entry.getKey(), entry.getValue()));
if (queue.size() > k) {
queue.poll();
}
}
while (k-- > 0) {
result.add(queue.poll().getWord());
}
Collections.reverse(result);
return result;
}
}
class WordFreq {
private final String word;
private final int freq;
WordFreq(final String word, final int freq) {
this.word = word;
this.freq = freq;
}
String getWord() {
return this.word;
}
int getFreq() {
return this.freq;
}
@Override
public String toString() {
return Objects.toString(word) + "->" + Objects.toString(freq);
}
public static void main (String[] args){
text t = new text();
String[] words = {"code", "sky", "pen", "sky", "sky", "blue", "code"};
int k = 2;
List<String> res = new ArrayList<String>();
res = t.topKFrequentAlternate(words,k);
ListIterator<String> lItr = res.listIterator();
while (lItr.hasNext()){
System.out.println(lItr.next());
}
}
}
sky code
