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
SuperComputer Inc. has built a super-fast computer server consisting of `N` hyper-scalar lightning-fast processors. These processors are numbered from `1` to `N` and are used to process independent jobs. Every new incoming job is assigned to an arbitrary processor. Sometimes, a processor may be assigned too many jobs while other processors have a relatively light load (or even wait idly). In that case, the whole system undergoes re-balancing.

Re-balancing proceeds in rounds. In each round, every processor can transfer at most one job to each of its neighbors on the bus. Neighbors of the processor `i` are the processors `i - 1` and `i + 1` (processors `1` and `N` have only one neighbor each, `2` and `N - 1` respectively). The goal of re-balancing is to make all processors have the same number of jobs.

**Given the number of jobs initially assigned to each processor, you are asked to determine the minimal number of rounds needed to achieve the state when every processor has the same number of jobs or to determine that such re-balancing is not possible.**

## Solution: **Greedy approach**
We can apply the Greedy approach to solve this problem. First, we need to find the load that each processor will have. We can find it by summing all the elements of the array and then dividing the sum by the total number of elements. Let us call it `load`.
So at the final state, each processor will have the load = `load`.

Now, we can partition the array and find the amount of load that is to be shared between these two partitions. The answer will be the maximum of all the loads shared between all the partitions.

Let us now move on to the implementation.

# Problem statement
SuperComputer Inc. has built a super-fast computer server consisting of `N` hyper-scalar lightning-fast processors. These processors are numbered from `1` to `N` and are used to process independent jobs. Every new incoming job is assigned to an arbitrary processor. Sometimes, a processor may be assigned too many jobs while other processors have a relatively light load (or even wait idly). In that case, the whole system undergoes re-balancing.

Re-balancing proceeds in rounds. In each round, every processor can transfer at most one job to each of its neighbors on the bus. Neighbors of the processor `i` are the processors `i - 1` and `i + 1` (processors `1` and `N` have only one neighbor each, `2` and `N - 1` respectively). The goal of re-balancing is to make all processors have the same number of jobs.

**Given the number of jobs initially assigned to each processor, you are asked to determine the minimal number of rounds needed to achieve the state when every processor has the same number of jobs or to determine that such re-balancing is not possible.**

# Solution: **Greedy approach**
We can apply the Greedy approach to solve this problem. First, we need to find the load that each processor will have. We can find it by summing all the elements of the array and then dividing the sum by the total number of elements. Let us call it `load`.
So at the final state, each processor will have the load = `load`.

Now, we can partition the array and find the amount of load that is to be shared between these two partitions. The answer will be the maximum of all the loads shared between all the partitions.

Let us now move on to the implementation.

Solve another SPOJ problem based on the Greedy approach.

Overview

Number Theory

Number Theory

Divide and Conquer

Greedy Algorithms

Greedy Algorithms

Recursion and Backtracking

Recursion and Backtracking

Dynamic Programming

Graphs

Bonus Lessons

Load Balancer Problem

Problem statement