## Candy Race Taking Square Candies - Microsoft Top Interview Questions

You are given an integer n representing the number of candies. You are playing a game against a friend and in each round a player can take some positive, square number. A player that can't make a move loses. Given that you go first and everyone plays optimally, return whether you will win. Constraints 1 ≤ n ≤ 100,000 Example 1 Input n = 11 Output True Explanation First you can take 9 candies, leaving 2 candies. Then, your friend can only take 1 candy, leaving 1 ca

## Binary Search Tree Typo - Microsoft Top Interview Questions

You are given a binary tree root which is almost a binary search tree except two nodes' values have been swapped. Return the original binary search tree. Constraints n ≤ 100,000 where n is the number of nodes in root Example 1 Input root = [2, [5, null, null], [7, [1, null, null], [8, null, null]]] Output [2, [1, null, null], [7, [5, null, null], [8, null, null]]] Explanation We can swap 1 and 5. Example 2 Input root = [0, [1, null, null], null]

## 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

## 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"

## 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