The ultimate guide to coding interviews. Developed by FAANG engineers. Boost problem-solving skills with number theory, dynamic programming, and graph theory. Get interview-ready in just a few hours.

Competitive Programming - Crack Your Coding Interview.png

Whether you’re gearing up for online coding challenges, code-a-thons, or interviews, then this course is for you. With this course, you will solidify your problem-solving skills ensuring a swift sail through any problem. 


You will be tasked with solving some of the most frequently asked questions that are brought up in FAANG interviews. You will start with the concepts of Number Theory and Divide and Conquer, and gradually move towards more complex problems like dynamic programming and graph theory.


With each problem you solve, there will be insightful explanations and full implementation details to really hammer home the concepts. By the time you finish this course, you will have the confidence to solve any problem, no matter the difficulty.

Competitive Programming - Crack Your Coding Interview, C++

# Problem statement
We have to paint `n` boards of length {${A_1}$, ${A_2}$, ..., ${A_n}$}. There are `k` painters available and each takes 1 unit of time to paint 1 unit of the board. The problem is to find the minimum time to get this job done under the constraints that any painter will only paint continuous sections of boards, say board `{2, 3, 4}` or only board `{1}` or nothing but not board `{2, 4, 5}`.

Let us look at some examples:
* We have input `k = 2`, `A = {10, 10, 10, 10}`. The output is `20`.
Here, we can divide the boards into `2`
equal-sized partitions, so each painter gets `20` units of the board and the total
time taken is `20`. 

* We have input `k = 2, A = {10, 20, 30, 40}`. The output is `60`. Here, we can divide the first `3` boards for
one painter and the last board for the 
second painter.

We can describe the problem as:

**Given an array `A` of non-negative integers and a positive integer `k`, we have to divide `A` into `k` of fewer partitions such that the maximum sum of the elements in a partition, overall partitions is minimized.**

# Solution: `Divide and conquer approach`

We can see that the highest possible value could be the sum of all the elements in the array and this happens when we allot `1` painter all the sections of the board. The lowest possible value of the problem could be the maximum value of the array `max`, because in this allocation we can allot `max` to one painter and divide the other sections such that the cost of them is less than or equal to `max` and as close as possible to `max`. Now if we consider using `x` painters in the above scenarios, it is obvious that as the value in the range increases, the value of `x` decreases and vice-versa. From this, we can find the target value when `x  = k` and use a helper function to find `x`, the minimum number of painters required when the maximum length of section a painter can paint is given.

Let us see the implementation to understand the concept better.

Solve a famous interview problem based on Binary Search.

Overview

Number Theory

Number Theory

Divide and Conquer

Greedy Algorithms

Greedy Algorithms

Recursion and Backtracking

Recursion and Backtracking

Dynamic Programming

Graphs

Bonus Lessons

Painter's Partition Problem

Problem statement