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
**Given a sorted array with possibly duplicate elements, the task is to find indexes of the first and last occurrences of an element `x` in the given array.**

For example, we have input `arr[] = {1, 3, 5, 5, 5, 5, 67, 123, 125}` and `x = 5`. The first occurrence is at index `2` and last occurrence is at index `5`.

Let us look at another example. We have input `arr[] = {1, 3, 5, 5, 5, 5, 7, 123, 125 }` and `x = 7`. The first occurrence is at index `6` and the last occurrence is at index `6`.

# Solution: `naïve approach`
The naïve approach is to run a for loop and check given elements in an array.  
* Run a for loop and for `i = 0` to `n-1`.
* Take `first = -1` and `last = -1`.
* When we find an element for the first time, we update `first = i`. 
* We always update `last = i` whenever we find the element.
* We print first and last.

But the time complexity of this solution is *O(n)*.

# Solution: `divide and conquer`
An efficient solution to this problem is to use a Binary Search. The only condition will be that the array should be sorted, as Binary Search can only be applied on sorted arrays. Let us visualize how `first` and `last` can be calculated using Binary Search. The grey color in the input array denotes the `mid` value while performing a Binary Search.

Use Binary Search to find the first and last occurrence of an element in an array.

Overview

Number Theory

Number Theory

Divide and Conquer

Greedy Algorithms

Greedy Algorithms

Recursion and Backtracking

Recursion and Backtracking

Dynamic Programming

Graphs

Bonus Lessons

First and Last Occurrence of an Element

Problem statement