Unique String Frequencies - Microsoft Top Interview Questions
Given a lowercase alphabet string s, return the minimum number of characters that we need to delete such that the frequency of each character occurs a unique number of times. Constraints n ≤ 100,000 where n is the length of s Example 1 Input s = "aabb" Output 1 Explanation Both "a" and "b" occur twice, so we can remove say "a" once to make the frequencies unique. Example 2 Input s = "abbccc" Output 0 Explanation The string already has unique fr
View Solution →Three-Way String Split with Equal Ones - Microsoft Top Interview Questions
You are given a binary string s containing "1"s and "0"s. Return the number of ways to split the string into three non-empty parts a, b and c such that a + b + c = s and the number of "1"s in each string is the same. Mod the result by 10 ** 9 + 7. Constraints 3 < n ≤ 100,000 where n is the length of s Example 1 Input s = "11001111" Output 3 Explanation We can have "11" + "0011" + "11" "110" + "011" + "11" "1100" + "11" + "11"
View Solution →Number of Substrings with Single Character Difference - Microsoft Top Interview Questions
You are given two lowercase alphabet strings s and t. Return the number of pairs of substrings across s and t such that if we replace a single character to a different character, it becomes a substring of t. Constraints 0 ≤ n ≤ 100 where n is the length of s 0 ≤ m ≤ 100 where m is the length of t Example 1 Input s = "ab" t = "db" Output 4 Explanation We can have the following substrings: "a" changed to "d" "a" changed to "b" "b" changed to "d" "ab
View Solution →Number of Fractions that Sum to 1 - Microsoft Top Interview Questions
You are given a list of lists fractions where each list contains [numerator, denominator] which represents the number numerator / denominator. Return the number of pairs of fractions there are that sums to 1. Constraints n ≤ 100,000 where n is the length of fractions Example 1 Input fractions = [ [1, 4], [2, 5], [3, 4], [3, 5], [5, 10], [1, 2], [1, 2] ] Output 5 Explanation 1/4 + 3/4, 2/5 + 3/5, 5/10 + 1/2, 5/10 +
View Solution →Minimum Updates to Make Bitwise OR Equal to Target - Microsoft Top Interview Questions
You are given three positive integers a, b and target. Consider an operation where you take either a or b and update one of the bits to 1 or to 0. Return the minimum number of operations required to make a | b = target. Constraints 1 ≤ a, b, target < 2 ** 31 Example 1 Input a = 2 b = 4 target = 8 Output 3 Explanation 10 = a 100 = b 1000 = target We need to first unset a and bs 1 bits to make them zero. Then we can set a directly to 8.
View Solution →