Introduction

In this blog post, we'll share the most commonly asked coding interview questions at Microstrategy. If you don't have months to study for your interviews, you can use AI tools like Chatmagic to generate solutions quickly and efficiently - helping you pass the interviews and get the job offer!

Problem #1: Zigzag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) P A H N A P L S I I G Y I R And then read line by line: "PAHNAPLSIIGYIR" Write the code that will take a string and make this conversion given a number of rows: string convert(string s, int numRows); Example 1: Input: s = "PAYPALISHIRING", numRows = 3 Output: "PAHNAPLSIIGYIR" Example 2: Input: s = "PAYPALISHIRING", numRows = 4 Output: "PINALSIGYAHRPI" Explanation: P I N A L S I G Y A H R P I Example 3: Input: s = "A", numRows = 1 Output: "A" Constraints: 1 <= s.length <= 1000 s consists of English letters (lower-case and upper-case), ',' and '.'. 1 <= numRows <= 1000

Topics: String

Problem #2: Backspace String Compare

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character. Note that after backspacing an empty text, the text will continue empty. Example 1: Input: s = "ab#c", t = "ad#c" Output: true Explanation: Both s and t become "ac". Example 2: Input: s = "ab##", t = "c#d#" Output: true Explanation: Both s and t become "". Example 3: Input: s = "a#c", t = "b" Output: false Explanation: s becomes "c" while t becomes "b". Constraints: 1 <= s.length, t.length <= 200 s and t only contain lowercase letters and '#' characters. Follow up: Can you solve it in O(n) time and O(1) space?

Topics: Two Pointers, String, Stack, Simulation

Problem #3: Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. Example 1: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Example 2: Input: nums = [1], k = 1 Output: [1] Constraints: 1 <= nums.length <= 105 -104 <= nums[i] <= 104 k is in the range [1, the number of unique elements in the array]. It is guaranteed that the answer is unique. Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

Topics: Array, Hash Table, Divide and Conquer, Sorting, Heap (Priority Queue), Bucket Sort, Counting, Quickselect

Problem #4: Battleships in a Board

Given an m x n matrix board where each cell is a battleship 'X' or empty '.', return the number of the battleships on board. Battleships can only be placed horizontally or vertically on board. In other words, they can only be made of the shape 1 x k (1 row, k columns) or k x 1 (k rows, 1 column), where k can be of any size. At least one horizontal or vertical cell separates between two battleships (i.e., there are no adjacent battleships). Example 1: Input: board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]] Output: 2 Example 2: Input: board = [["."]] Output: 0 Constraints: m == board.length n == board[i].length 1 <= m, n <= 200 board[i][j] is either '.' or 'X'. Follow up: Could you do it in one-pass, using only O(1) extra memory and without modifying the values board?

Topics: Array, Depth-First Search, Matrix

Problem #6: Permutations

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order. Example 1: Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] Example 2: Input: nums = [0,1] Output: [[0,1],[1,0]] Example 3: Input: nums = [1] Output: [[1]] Constraints: 1 <= nums.length <= 6 -10 <= nums[i] <= 10 All the integers of nums are unique.

Topics: Array, Backtracking

Problem #7: Minimum Number of Swaps to Make the String Balanced

You are given a 0-indexed string s of even length n. The string consists of exactly n / 2 opening brackets '[' and n / 2 closing brackets ']'. A string is called balanced if and only if: It is the empty string, or It can be written as AB, where both A and B are balanced strings, or It can be written as [C], where C is a balanced string. You may swap the brackets at any two indices any number of times. Return the minimum number of swaps to make s balanced. Example 1: Input: s = "][][" Output: 1 Explanation: You can make the string balanced by swapping index 0 with index 3. The resulting string is "[[]]". Example 2: Input: s = "]]][[[" Output: 2 Explanation: You can do the following to make the string balanced: - Swap index 0 with index 4. s = "[]][][". - Swap index 1 with index 5. s = "[[][]]". The resulting string is "[[][]]". Example 3: Input: s = "[]" Output: 0 Explanation: The string is already balanced. Constraints: n == s.length 2 <= n <= 106 n is even. s[i] is either '[' or ']'. The number of opening brackets '[' equals n / 2, and the number of closing brackets ']' equals n / 2.

Topics: Two Pointers, String, Stack, Greedy