Zscaler

01How Many Sentences?

Given an array of words and an array of sentences, calculate how many sentences can be created by replacing any word with one of its anagrams. Function Description Complete the function countSentences in the editor. countSentences has the following parameters: string wordSet[n]: an array of strings string sentences[m]: an array of strings Returns int[n]: an array of m integers that denote the number of sentences that can be formed from each sentence

Constraints

0 < n ≤ 10⁵
1 ≤ length of each word ≤ 20
1 ≤ m ≤ 1000
3 ≤ words in a sentence ≤ 20

Example 1

Input:

wordSet = ["listen", "silent", "it", "is"]
sentences = ["listen it is silent"]

Output:

[4]

Explanation: Determine that listen is an anagram of silent. Those two words can be replaced with their anagrams. The four sentences that can be created are:

listen it is silent
listen it is listen
silent it is silent
silent it is listen Therefore, the output is an array with one element: [4].

解法

把 wordSet 按"字符排序后的 key"分组，统计每组大小 g。对每个句子拆词，每个词用同样 key 查找其分组大小(不在集合则为 1)，全部相乘即为该句答案。时间 O((n+总词)·20)。

from collections import defaultdict
from typing import List

def count_sentences(word_set: List[str], sentences: List[str]) -> List[int]:
    groups = defaultdict(int)
    for w in word_set:
        groups["".join(sorted(w))] += 1
    out: List[int] = []
    for s in sentences:
        prod = 1
        for w in s.split():
            key = "".join(sorted(w))
            prod *= groups.get(key, 1)
        out.append(prod)
    return out

import java.util.*;

class Solution {
    public int[] countSentences(String[] wordSet, String[] sentences) {
        Map<String, Integer> g = new HashMap<>();
        for (String w : wordSet) {
            char[] cs = w.toCharArray(); Arrays.sort(cs);
            g.merge(new String(cs), 1, Integer::sum);
        }
        int[] out = new int[sentences.length];
        for (int i = 0; i < sentences.length; i++) {
            long p = 1;
            for (String w : sentences[i].split("\\s+")) {
                char[] cs = w.toCharArray(); Arrays.sort(cs);
                p *= g.getOrDefault(new String(cs), 1);
            }
            out[i] = (int) p;
        }
        return out;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> countSentences(vector<string>& wordSet, vector<string>& sentences) {
        unordered_map<string, int> g;
        for (auto& w : wordSet) { string k = w; sort(k.begin(), k.end()); g[k]++; }
        vector<int> out;
        for (auto& s : sentences) {
            long long p = 1;
            stringstream ss(s); string w;
            while (ss >> w) { string k = w; sort(k.begin(), k.end()); p *= (g.count(k) ? g[k] : 1); }
            out.push_back((int) p);
        }
        return out;
    }
};

02Signal Filter

Sometimes it is necessary to filter a signal by frequency, e.g. to reduce noise outside of the expected frequency range. Filters can be stacked, allowing only the frequencies within the range allowed by all filters to get through. For example, three filters with ranges of [10, 17], [13, 15] and [13, 17] will only allow signals between 13 and 15 through. The only range that all filters overlap is [13, 15]. Given n signals' frequencies and a series of m filters that let through frequencies in the range x to y, inclusive, determine the number of signals that will get through the filters. There will be only one range where all the filters overlap. Function Description Complete the function countSignals in the editor. countSignals has the following parameter(s):

int frequencies[n]: the frequencies of the signals sent through the filters
int filterRanges[m][2]: the lower and upper frequency bounds for each filter Returns int: the number of signals that pass through all filters

Constraints

1 ≤ n ≤ 10⁵
1 ≤ m ≤ 10⁵
1 9</

Example 1

Input:

frequencies = [8, 15, 14, 16, 21]
filterRanges = [[10, 17], [13, 15], [13, 17]]

Output:

Explanation: The range that all of the filters allow through is from 13 to 15, inclusive. The 2 frequencies that will pass through all filters have frequencies of 15 and 14. Return 2.

解法

所有 filter 的交集 = [max(low), min(high)]，遍历 frequencies 计数落在其中的元素个数。时间 O(n+m)。

from typing import List

def count_signals(frequencies: List[int], filter_ranges: List[List[int]]) -> int:
    lo = max(r[0] for r in filter_ranges)
    hi = min(r[1] for r in filter_ranges)
    if lo > hi:
        return 0
    return sum(1 for f in frequencies if lo <= f <= hi)

class Solution {
    public int countSignals(int[] frequencies, int[][] filterRanges) {
        int lo = Integer.MIN_VALUE, hi = Integer.MAX_VALUE;
        for (int[] r : filterRanges) { lo = Math.max(lo, r[0]); hi = Math.min(hi, r[1]); }
        if (lo > hi) return 0;
        int cnt = 0;
        for (int f : frequencies) if (f >= lo && f <= hi) cnt++;
        return cnt;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int countSignals(vector<int>& frequencies, vector<vector<int>>& filterRanges) {
        int lo = INT_MIN, hi = INT_MAX;
        for (auto& r : filterRanges) { lo = max(lo, r[0]); hi = min(hi, r[1]); }
        if (lo > hi) return 0;
        int cnt = 0;
        for (int f : frequencies) if (f >= lo && f <= hi) cnt++;
        return cnt;
    }
};