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]
View Solution →Run-Length Decoding- Google Top Interview Questions
Given a string s, consisting of digits and lowercase alphabet characters, that's a run-length encoded string, return its decoded version. Note: The original string is guaranteed not to have numbers in it. Constraints 0 ≤ n ≤ 100,000 where n is the length of s Example 1 Input s = "4a3b2c1d2a" Output "aaaabbbccdaa"
View Solution →Search in a Virtually Complete Binary Tree- Google Top Interview Questions
Consider a complete binary tree of n nodes whose values are 1 to n. The root has value of 1, its left child is 2 and its right child is 3. In general, nodes' values are labelled 1 to n in level order traversal. You are given a binary tree root and an integer target. Given that the root was originally a complete binary tree whose values were labelled as described above, and that some of the subtrees were deleted, return whether target exists in root. Bonus: solve in \mathcal{O}(h)O(h) time
View Solution →Set - Google Top Interview Questions
Implement a set data structure with the following methods: CustomSet() constructs a new instance of a set add(int val) adds val to the set exists(int val) returns whether val exists in the set remove(int val) removes the val in the set This should be implemented without using built-in set. Constraints n ≤ 100,000 where n is the number of calls to add, exists and remove Example 1 Input methods = ["constructor", "add", "exists", "remove", "exists"] arguments =
View Solution →Shortest Sublist to Sort - Google Top Interview Questions
Given a list of integers nums, return the length of the shortest sublist in nums which if sorted would make nums sorted in ascending order. Constraints n ≤ 100,000 where n is the length of nums Example 1 Input nums = [0, 1, 4, 3, 8, 9] Output 2 Explanation Sorting the sublist [4, 3] would get us [0, 1, 3, 4, 8, 9] Example 2 Input nums = [5, 4, 3, 2, 8, 9] Output 4 Explanation Sorting the sublist [5, 4, 3, 2] would get us [2, 3, 4, 5, 8, 9]
View Solution →