title-img


Lossy Run-Length Encoding - Microsoft Top Interview Questions

You are given a lowercase alphabet string s and an integer k. Consider an operation where we perform a run-length encoding on a string by representing repeated successive characters as a count and character. For example, the string "aabbbc" would be encoded as "2a3bc". Note that we don't put "1c" for "c" since it only appears once successively. Given that you can first remove any k consecutive characters in s, return the minimum length possible of the resulting run-length encoding.

View Solution →

Longest Strictly Increasing Then Decreasing Sublist - Microsoft Top Interview Questions

You are given a list of integers nums. Return the length of the longest sublist such that its length is at least 3 and its values are strictly increasing and then decreasing. Both the increasing part and the decreasing part must be non-empty. Constraints n ≤ 100,000 where n is the length of nums Example 1 Input nums = [7, 1, 3, 5, 2, 0] Output 5 Explanation The sublist [1, 3, 5, 2, 0] is strictly increasing then decreasing. Example 2 Input nums = [

View Solution →

Largest Kth Value of List - Microsoft Top Interview Questions

You are given integers n, total, and k. Consider a list of length n whose sum is total and where the absolute difference between any two consecutive numbers in the list is at most 1. Return the maximum value at index k of such a list. Constraints 1 ≤ n < 2 ** 31 0 ≤ k < n 0 ≤ total < 2 ** 31 Example 1 Input n = 3 total = 10 k = 1 Output 4 Explanation The largest such list is [3, 4, 3]. Example 2 Input n = 4 total = 10 k = 3 Output

View Solution →

Incrementable Stack - Microsoft Top Interview Questions

Implement a stack with the following methods: IncrementableStack() constructs a new instance of an incrementable stack append(int val) appends val to the stack pop() pops and returns the last element in the stack increment(int inc, inc count) increments the value of bottom count elements by inc Each method should be done in \mathcal{O}(1)O(1) time. You can assume that for pop, the stack is non-empty when it is called. Constraints n ≤ 100,000 where n is the number o

View Solution →

Bus Stop - Microsoft Top Interview Questions

You are given a list of integers nums representing bus stops on a line where nums[i] represents the time a bus must arrive at stop i. Given that buses can only move forward, return the minimum number of buses that are needed to pass through all the stops. Constraints n ≤ 1,000 where n is length of nums. Example 1 Input nums = [1, 2, 7, 9, 3, 4] Output 2 Explanation One bus can take this route [1, 2, 3, 4] and another can do [7, 9]. Example 2 Input nums

View Solution →