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.

Graph databases and rapid prototyping (part 3)

In this last part, I am comparing the development experiences when using SQL Server and Neo4j graph database. There is also an overview of Neo4j tools and functionality, and how they accelerate web development and prototyping.

Part 1: How I got hooked on graph databases

Part 2: What is a graph database
Part 3: Rapid prototyping

"Java and Javascript are similar like Car and Carpet are similar" - fun fact

Now when I think about it, a graph database feels like a dynamically-typed language, and a SQL database - like a statically-typed one. As you would consider a dynamically-typed language, such as JavaScript, for the web development and prototyping, a graph database is also a good option for these cases.

"If all you have is a hammer, everything looks like a nail" - the law of the instrument

We have successfully used SQL Server on many projects, and it was our default database choice. For our recent web application, it required a good amount of design and plumbing before we can expose data through Web API. As requirements refined, our initial design underwent many changes. Even with good tools and automated steps, it was painful and time-consuming making changes to the data schema, and, despite 2 abstraction layers, the app was often broken afterwards.

Graph databases and rapid prototyping (part 2)

In this part, I am providing a brief explanation of what a graph database is, with some examples on the data modeling and querying. I am also talking about the schema-less nature of the graph databases, and what advantages it provides when you just start your project.

Part 1: How I got hooked on graph databases
Part 2: What is a graph database
Part 3: Rapid prototyping

"Fool tidies up, a genius rules over chaos" - Albert Einstein

A graph database looks like a bunch of nodes with properties (key-value pairs) and relationships between them. Imagine you gathered data from multiple sources about people, their tweets, posts, likes, friend and followers. Each node may have some unique properties, and there could be similarities.

Rihanna is a friend with the monster, and she likes his posts

Similar nodes can be categorized using labels, such as "person", "monster" and "post". Relationships can have labels too, like "friend", "likes" and "publishes".

Blog ideas

I planned to make a to-do list, or a Kanban board or something, but having it as a blog post provides an important advantage - an extra blog post. Plus, I can see it one place, and give the opportunity for my mom (who does not speak English) and my wife (who does not care about programming) to see what's hopefully coming.

1. Schema-less graph databases
   How I got hooked, and how it changed my approach to design software.
2. Algorithms - Dynamic Programming - Buy/Sell Stock I, II, III, IV, V, and VI.
   Great problem - it starts easy and gradually gets very complex, showing the power of dynamic programming. It's described in a few books and blog posts, and I think there is a value in bringing it all together and build more complex solutions on top of easier ones, like an elephant pyramid.
3. NUTR 200
   I just finished this course in University of Washington, and I had few insights worth sharing, like why a fat-burning exercise has to be more than 20 minutes long.
4. Programming interview from the other side
   I helped interviewing college and industry candidates for my company. I thought I'd describe my approach to evaluate candidates, and criteria we used to compare their performance.
5. Programming Interview Pearls
   These algorithms are being asked during the interviews. They may seem easy, but they can get very deep. With many of them, there is often an 'aha' moment, leading to an elegant and simple solution. 

Upcoming posts and pages: