Compare Strings Google OA 2023 Solution
One string is strictly smaller than another when the frequency of occurrence of the smallest character in the string is less than the frequency of the smallest character in the string is less than the frequency of occurrence of the smallest character in the comparison string.
For example, string “abcd” is smaller than string “aaa” because the smallest character (in lexicographical order) in “abcd” is ‘a’, with a frequency of 1, and the smallest character in “aaa” is also ‘a’, but with a frequency of 3.
In another example, string “a” is smaller than string “bb” because the smallest character in “a” is ‘a’ with a frequency of 1, and the smallest character in “bb” is ‘b’ with a frequency of 2.
Write a function that, given string A (which contains M strings delimited by ‘,’) and string B (which contains N strings delimited by ‘,’), returns an array C of N integers. For 0<= J < N, values of C[J] specify the number of strings in A which are strictly smaller then the comparison Jth string in B (starting from 0).
For example, given strings A and B such that:
Input:
- A= “abcd aabc bd”
- B= “aaa aa”
Output: [3, 2]
the function should return [3, 2], because:
All the strings in the array are strictly smaller than “aaa” on the basis of the given comparison criteria.
Strings “abcd” and “bd” are strictly smaller than “aa”.
Constraints:
- 1 <=N, M <= 10000
- 1 = length of any string contained by A or B <= 10
- All the input strings comprise only lowercase english alphabet letters (a-z)
SOLUTION
Program: Compare Strings Google OA Solution in Python
class Solution:
def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
output, query_count, word_count,c = [], [], [], []
for word in queries :
query_word = [ch for ch in word]
query_word.sort()
f_query_word = query_word.count(query_word[0])
query_count.append(f_query_word)
for word in words :
word = [ch for ch in word]
word.sort()
f_word = word.count(word[0])
word_count.append(f_word)
for q in query_count :
counter = 0
for i in range(len(word_count)) :
if q < word_count[i] :
counter += 1
output.append(counter)
c.append(sum(output[:-1]))
c.append(output[-1])
return cProgram: Compare Strings Google OA Solution in Python
- Create a list word_fs to store the frequency of smallesr char in word in words
- Sort the list : word_fs
- Now for each word in queries : find the freq of smallest char : f
- Now think carefully we have a sorted list : word_fs and a value = f
- we need to find the number of items that are larger than f in the sorted list
- yes this gives the idea to do binary search
class Solution:
def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
def freq(word):
l = len(word)
ans,minn = 1,word[0]
for i in range(1,l):
if word[i] == minn: ans += 1
elif word[i] < minn :
minn = word[i]
ans = 1
return ans
n = len(words)
m = len(queries)
words_fs = []
for i,word in enumerate(words):
words_fs.append(freq(word))
words_fs.sort()
def binarysearch(x):
low ,high = 0,n-1
while low <= high:
mid = (low+high)//2
if words_fs[mid] == x:
low = mid + 1
elif words_fs[mid] < x:
low = mid + 1
else:
high = mid - 1
return high
ans = [0]*m
for i,word in enumerate(queries):
fq = freq(word)
idx = binarysearch(fq)
ans[i] = n - idx - 1
return ansRelated:
- Amazon OA Online Assessment 2022 Questions and Answers
- Microsoft Online Assessment 2021 Questions and Solution
