## 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 →## Smallest Number With No Adjacent Duplicates - Google Top Interview Questions

You are given a string s containing "1", "2", "3" and "?". Given that you can replace any “?” with "1", "2" or "3", return the smallest number you can make as a string such that no two adjacent digits are the same. Constraints n ≤ 100,000 where n is the length of s Example 1 Input s = "3?2??" Output "31212" Example 2 Input s = "???" Output "121"

View Solution →