Solutions to programming interview questions at some of the top companies in the world: cppcodingzen.com

Given an array of integers, find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well.

For example, the input `[3, 4, -1, 1]`

should give `2`

. The input `[1, 2, 0]`

should give `3`

.

You can modify the input array in-place.

This problem is interesting for several reasons:

- It doesn’t fit in any of the standard-bucket algorithmic techniques, like hashing, graph traversal, etc.
- The simplest/inefficient solutions can be easily found and coded, but…

*This short post is going to explore how Graph theory algorithms appear in seemingly unrelated problems during coding interviews.*

*Feel free to explore **previous** **posts** to read more problems (and their solutions) involving Graph algorithms.*

You are given a circular lock with three wheels, each of which display the numbers `0`

through `9`

in order. Each of these wheels rotate clockwise and counterclockwise.

In addition, the lock has a certain number of “dead ends”, meaning that if you turn the wheels to one of these combinations, the lock becomes stuck in that state and cannot be opened.

Let us consider…

Regular expression matching provides quick and efficient solution to many interview problems. In this short post, we are going to explore how a regular expression can decide whether a string represents a valid number.

This interview question was asked by LinkedIn.

Given a string, return whether it represents a number. Here are the different kinds of numbers:

- “10”, a positive integer
- “-10”, a negative integer
- “10.1”, a positive real number
- “-10.1”, a negative real number
- “1e5”, a number in scientific notation

And here are examples of non-numbers:

- “a”
- “x 1”
- “a -2”
- “-”

Like always, let’s clarify the problem statement…

*This post will tackle a problem of optimally splitting a tree (or removing edges from it), and will discuss how Greedy algorithms result in simple solution to the problem. The whole solution fits within about 40 lines of code.*

*Feel free to read a **few older posts* *to read more on Greedy Algorithms.*

You are given a tree with an even number of nodes. Consider each connection between a parent and child node to be an “edge”. You would like to remove some of these edges, such that the disconnected subtrees that remain each have an even number of nodes.

…

This simple short post illustrates how Graph problems appear at a variety of places during a coding interview. Today’s problem deals with a *Directed Acyclic Graph (DAG), *and *Topological sorting* of a DAG. The problem was asked by Airbnb.

Feel free to look at some of the older graph theory problems and their solutions.

We’re given a hashmap associating each `courseId`

key with a list of `courseIds`

values, which represents that the prerequisites of `courseId`

are `courseIds`

. Return a sorted ordering of courses such that we can finish all courses. Return empty if there is no such ordering.

For example…

*Bit manipulation and bitwise operators are some of the hardest problems in programming interviews. This post discusses an interesting bit manipulation problem. The problem was asked by Salesforce.*

Given an array, find the maximum AND value generated by any pair of element from the array.

Examples:

Input : arr[] = {4, 8, 12, 16}

Output : Maximum AND value = 8 Input : arr[] = {4, 8, 16, 2}

Output : Maximum AND value = 0

(Recall that `&`

is a bitwise AND operator in C++).

Recall the truth table of the logical AND operator

The AND of two bits…

*Data structure manipulation comes up pretty frequently in programming interview questions. This post discusses manipulating a linked list to design stacks. The problem was asked in a programming interview by Microsoft.*

*This post also adds more robustness to the implementation by using C++ language support (iterators and templates). A command over standard language constructs makes your interview stand out, and gives you an extra edge in the hiring process!*

Implement three stacks using one Linked List.

The basic algorithm should be easy after a moment’s thought. Here is the diagram that explains it!

*Some of the most interesting programming interview questions are based on arrays. The inputs of these interview questions are simple arrays of integers or floating point numbers. Your task, as a candidate, is to perform some operations on these numbers (maybe find the most frequently occuring one, or the largest sum among the arrays; or, find the most optimal floating point adjustments to the array, as today’s problem demands).*

*Most array based problems are easy to state and understand. It is also extremely easy and quick to come up with and code the simplest, least efficient solution to these problems…*

Here is the copy of Satoshi’s famous White Paper on bitcoin: https://cppcodingzen.com/bitcoin.pdf. Please read, understand, distribute, upload this paper on your website if you care about open and free internet.

*Graph theory is immensely popular among interviewers in a variety of industries. Here is an interview problem on Graph Theory asked at Jane Street, a FinTech firm.*

*Feel free to take a look at some of our **previous** **Graph** **Theory** problems and their solutions.*

Suppose you are given a table of currency exchange rates, represented as a 2D array. …