Microsoft interview questions

Count of binary strings without consecutive 1’s

Given a positive integer N, find the count of distinct binary strings of length N that have no consecutive 1’s. For example, Input: N = 2 Output: 3. Explanation: There are 3 possible strings: 00, 01, 10N=3There are 5 possible strings: 000, 001, 010, 100,101 Thought process to find binary ...
Read More

Spiral traversal of a matrix

Given a 2d matrix of dimension n*m, the task is to print the matrix in spiral order. (To understand what is spiral order please refer to the diagram) For example: Input: 3 3 1 2 3 4 5 6 7 8 9 Output: 1 2 3 6 9 8 7 ...
Read More

Plus One Linked List

Given a number represented by a linked list, add 1 to that number and return a new linked list. For example, if the number is 2345, then it is represented as linked as shown below. When we add one to 2345 represented by the linked list, the resulting linked list ...
Read More

Combination sum problem

Combination sum problem Given an array of integers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. Also, the same candidate can occur in the combination multiple times. For example, Input: candidates = [4,3,5,9], target = 9, a solution set is:[ [9], [3,3,3], ...
Read More

Maximum area rectangle in a histogram

A histogram is a diagram consisting of rectangles whose area is proportional to the frequency of a variable and whose width is equal to the class interval. Below is an example of a histogram. Given a histogram, whose class interval is 1, find maximum area rectangle in it. Let me ...
Read More

Segregate 0s and 1s in an array

Given an array of 0s and 1s, segregate 0s and 1s in such as way that all 0s come before 1s. For example, in the array below, The output will be as shown below. This problem is very similar to Dutch national flag problem Different methods to segregate 0s and 1s in an ...
Read More

Minimum cost of connecting n ropes

Given n ropes of different lengths, connect these ropes in one rope. The cost to connect two ropes is equal to the sum of their lengths. We have to connect these ropes with minimum cost. For example, Input: 5, 2, 3, 9. Output: 34 Explanation: We can connect the ropes ...
Read More

Last occurrence element in array

Finding the last occurrence of an element in a list of numbers is very similar to the First occurrence of an element with binary search. Given a sorted array and an element, find the last occurrence of a given element.  As the array can contain duplicate values, there can be ...
Read More

First occurrence of element with binary search

First occurrence of element in sorted array Given a sorted array and an element, find the first occurrence of key in array.  As array can contain duplicate values, there can be multiple occurrences of same element, problem is to find first index. For example, in given array, first occurrence of ...
Read More

Ceiling in sorted array using binary search

Ceiling in sorted array In last post, binary search algorithm, we discussed basics of algorithm, it's implementation and worst case complexity. Today, we will use binary search algorithm to solve another problem called find ceiling in sorted array. To understand problem, first let's understand what is ceiling? Given an array of ...
Read More