## Monotonous String Groups 🎃 - Google Top Interview Questions

You are given a lowercase alphabet string s. Return the minimum numbers of contiguous substrings in which s must be broken into such that each substring is either non-increasing or non-decreasing. For example, "acccf" is a non-decreasing string, and "bbba" is a non-increasing string. Constraints n ≤ 100,000 where n is the length of s Example 1 Input s = "abcdcba" Output 2 Explanation We can break s into "abcd" + "cba" Example 2 Input s = "zzz" Output

## Pair Sums to Power of Two - Google Top Interview Questions

You are given a list of integers nums. Return the number of pairs i < j such that nums[i] + nums[j] is equal to 2 ** k for some 0 ≤ k. Constraints 0 ≤ n ≤ 100,000 where n is the length of nums Example 1 Input nums = [1, 1, 3, 5] Output 4 Explanation We can have the following pairs that sums to power of 2 (1, 1) (1, 3) (1, 3) (3, 5)

## Range Query on a List - Google Top Interview Questions

Implement a data structure with the following methods: RangeSum(int[] nums) constructs a new instance with the given nums. total(int i, int j) returns the sum of integers from nums between [i, j). That is, nums[i] + nums[i + 1] + ... + nums[j - 1]. Constraints n ≤ 100,000 where n is the length of nums k ≤ 100,000 where k is the number of calls to total Example 1 Input methods = ["constructor", "total", "total"] arguments = [[[1, 2, 5, 0, 3, 7]], [0, 3], [1, 5]]` O

## Removing Triple Successive Duplicates - Google Top Interview Questions

Given a string s containing "0"s and "1"s, consider an operation where you pick a character and toggle its value from "0" to "1" or from "1" to "0". Return the minimum number of operations required to obtain a string containing no instances of three identical consecutive characters. Constraints 0 ≤ n ≤ 100,000 where n is the length of s Example 1 Input s = "1100011" Output 1 Explanation We can toggle the middle "0" to a "1". Example 2 Input s = "0001000"

## Run-Length Decoded String Iterator - Google Top Interview Questions

Given a run-length encoded lowercase alphabet string s, implement an iterator which is the decoded version of s: next() polls the next element in the iterator hasnext() which returns whether the next element exists Constraints n ≤ 100,000 where n is the number of calls to next and hasnext Example 1 Input methods = ["constructor", "next", "hasnext", "next", "next", "hasnext"] arguments = [["2a1b"], [], [], [], [], []]` Output [None, "a", True, "a", "b", False]