Interview Pearls: K Consecutive Bit Flips

This is a cool problem that sounds very hard by becomes easy with two intuition sparks (and a little twinkle).

Description

In an array A containing only 0s and 1s, a K-bit flip consists of choosing a (contiguous) subarray of length K and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.

Return the minimum number of K-bit flips required so that there is no 0 in the array. If it is not possible, return -1.

Example

Input: A = [0,0,0,1,0,1,1,0], K = 3
Output: 3

Interview Pearls: Sliding Window

If the problem talks about continuous subarrays or substrings, the sliding window technique may help solve it in a linear time. Such problems are tricky, though the solution is simple once you get it. No wonder I am seeing such problems in almost every interview!

Here, we will take a look at Subarrays with K Different Integers (LeetCode Hard), which appeared on LeetCode weekly contest #123. You can also master the sliding windows technique with these additional problems:

• Longest Substring Without Repeating Characters
• Longest Substring with At Most Two Distinct Characters
• Longest Substring with At Most K Distinct Characters

Problem Description

Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly K. For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.

Return the number of good subarrays of A.

Example

Input: A = [1,2,1,2,3], K = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

Dynamic Programming: Minimum Travel Cost

The higher is the bar, the more you're expected to use dynamic programming (DP) during an interview. This technique requires a lot of practice to grasp; if you've mastered the recursion, DP is the next level.

This problem appeared on LeetCode weekly contest #121, and it's a good problem to practice the DP thinking.

Problem Description

In a country popular for train travel, you have planned some train travelling one year in advance. The days of the year that you will travel is given as an array days. Each day is an integer from 1 to 365.

Train tickets are sold in 3 different ways:

• 1-day pass is sold for costs[0] dollars;
• 7-day pass is sold for costs[1] dollars;
• 30-day pass is sold for costs[2] dollars.

The passes allow that many days of consecutive travel. For example, if we get a 7-day pass on day 2, then we can travel for 7 days: day 2, 3, 4, 5, 6, 7, and 8.

Return the minimum number of dollars you need to travel every day in the given list of days.

Interview Pearls: Interleave array in-place

I got this problem in the real interview, and I thought it was interesting. I used the divide and conquer paradigm and came up with a linearithmic solution. After the interview, I could not help thinking about potential linear solution. Read on to see what I found with a little help from the number theory.

Problem Statement

"Given array [a₁, a₂, ..., a_n, b₁, b₂, ..., b_n], interleave it in-place to [a₁, b₁, a₂, b₂, ..., a_n, b_n]"

This problem is also known as "in-shuffle". Think about cutting a deck of cards into equal halves, and interleaving them perfectly, like some of poker junkies can do. It's easy to solve this problem in linear time if you can use additional memory, but the point here is to do it in-place.

Interview Pearls: Count Inversions (Expert)

I am collecting problems that start easy and then lead to a deep conversation, touching on multiple aspects of computer science fundamentals. These problems are being asked during interviews in the top technology companies, often with a twist to see if you understand the underlying principles and can adapt your solution.

Part 1: Introduction, coding practice and simple solutions
Part 2: Advanced solutions
Part 3: Expert solutions

Here we have an innocent-looking problem that bled me dry (luckily, it was not in a real interview!). Turned out, there are many interesting ways to solve it, and I thought it could be a good illustration to some fundamental algorithms. If you digested advanced solutions OK, here is the desert menu: segment tree, lazy propagation segment tree, and height-balanced BST with counters.

7. Segment tree

Segment tree has the same purpose as binary indexed tree (BIT) - efficiently sum ranges in a mutating array. Go ahead and review solution #5 in the previous post to see how we combine update and sum operations to count inversions.

I used to confuse segment tree with interval tree, but they are quite different. Interval tree stores arbitrary intervals in binary search tree, so it can find an overlap in a logarithmic time. Segment tree always works with a predefined interval, which is the size of the underlying array, and uses logarithmic segments of that interval to efficiently perform range operations.

Segment tree is an actual binary tree (unlike BIT); leaves represent elements of the array, and parent nodes represent segments of the array, storing the operation result of its children (and therefore all elements in the segment). Because of that, segment tree requires additional memory comparing to BIT, but also supports non-cumulative operations, such as minimum or maximum value in the range.

Interview Pearls: Count Inversions (Advanced)

I am collecting problems that start easy and then lead to a deep conversation, touching on multiple aspects of computer science fundamentals. These problems are being asked during interviews in the top technology companies, often with a twist to see if you understand the underlying principles and can adapt your solution.

Part 1: Introduction, coding practice and simple solutions
Part 2: Advanced solutions
Part 3: Expert solutions

Here we have an innocent-looking problem that bled me dry (luckily, it was not in a real interview!). Turned out, there are many interesting ways to solve it, and I thought it could be a good illustration to some fundamental algorithms. In the previous post, I covered introductions and simple (but not very efficient) solutions. This is the fun part - we will use advanced concepts like self-balancing trees, binary index trees, and the divide and conquer strategy.

4. Self-balancing BST with counters

So, we implemented our very own BST that can efficiently tell us how many elements are smaller than any given value (solution #3 in the previous post). The run-time complexity is O (n * h), where h is the height of the tree. For a balanced tree, the height is log n, so the complexity is linearithmic. In an unbalanced tree the height can grow up to n, resulting in the quadratic time.

To fight the quadratic time, we can balance the tree to keep its height proportional to log n ^[1] by performing tree rotations when inserting new elements. Tree rotations require amortized ^[2] constant time, so the overall run-time will be still linearithmic. We need to extend our previous solution with the rotation operations and track the number of elements in the both left and right subtrees (so that we can efficiently recalculate these numbers after the rotation).

Interview Pearls: Count Inversions

I am collecting problems that start easy and then lead to a deep conversation, touching on multiple aspects of computer science fundamentals. These problems are being asked during interviews in the top technology companies, often with a twist to see if you understand the underlying principles and can adapt your solution.

Part 1: Introduction, coding practice and simple solutions
Part 2: Advanced solutions
Part 3: Expert solutions

Here we have an innocent-looking problem that bled me dry (luckily, it was not in a real interview!). Turned out, there are many interesting ways to solve it, and I thought it could be a good illustration to some fundamental algorithms. In this first post, we will start with three relatively simple (but not very efficient) solutions. In later parts, we fiddle with binary search trees, indexed trees, merge sort, and even segment trees.

Problem Statement

"Given an array of numbers, count pairs where i < j and numbers[i] > numbers[j]"

I saw this problem also referenced as "Reverse Pairs" and "Count of Smaller Numbers After Self". The result indicates how far the array is from being sorted. It's zero if the array is already sorted, and it's maximum (1 + 2 + ... + size - 1, or size * (size - 1) / 2) if it's sorted in the reverse order. Another way to look at this; the result is the number of swap operations required to sort the array using the bubble sort algorithm.