"What are the algorithms required to solve all problems (using C++) in any competitive coding contest?"
Answered by Mostafa Saad Ibrahim, ACM ICPC World Finalist, Problem Setter

Here is my helper list. It lists most of needed algorithms/concepts.Some elements are not algorithms (e.g. Fake, States/Concerns) and little repetitions.

But 1 final advice: Initially, Given great attention to thinking skills rather than the knowledge. This is helpful for both competitions and your future. To do so, make sure you are so good in adhocks, where no algorithms are required, just pure thinking.

Asked in Amazon Interview

Find Longest Palindrome in a String : Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

NOTE: Required Time Complexity O(n^2).

Example:
Input:
1
aaaabbaa

Output:
aabbaa

Solution:
https://www.linkedin.com/feed/update/urn:li:activity:6594490601763364864

Problem : Merge Intervals
Given a collection of intervals, merge all overlapping intervals.

Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.


Solution:
SOLUTION

Elevator Problem

A building has floors numbered 0 through n≤10^18. There is a single elevator with four buttons: "go to floor 0", "+a floors", "+b floors", and "+c floors". We have a,b,c≤ 10^6. Compute the number of unreachable floors.


Solution:

This feels like a number theory problem, but trying to solve it by GCDs and casework will not lead to success. Instead, treat it as a graph theory problem. First, note that if you can reach floor x, you can reach all floors of the form x+k*a. Hence, for each remainder modulo a all we need is the smallest reachable x with this remainder. These can be found by using Dijkstra’s shortest path algorithm on a graph with a nodes. The nodes are the remainder classes, and from each node there are two edges, corresponding to +b and +c.

The stunning thing about this problem is the asymmetry of the solution: you are treating one button differently from the other two.

Credits : Michal Forišek on Quora, scientist, competitive programmer

Adobe Interview:
Credits : GFG

Problem:
Find Minimum Number of Platforms Required for a Railway/Bus Station

Given arrival and departure times of all trains that reach a railway station, the task is to find the minimum number of platforms required for the railway station so that no train waits.
We are given two arrays which represent arrival and departure times of trains that stop

Examples:
Input: arr[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}
dep[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}
Output: 3
There are at-most three trains at a time (time between 11:00 to 11:20)

Solution:
SOLUTION

Dynamic Programming playlist by Chirayu Jain

https://www.youtube.com/playlist?list=PLtBICreuIvuuVifFHcHvIUR6elWTy1K5v

Some links for Competitive Programming Resources :

1. https://github.com/kothariji/competitive-programming

2. https://github.com/kunal-kushwaha/Competitive-Programming-Resources

List of awesome learning resources :


https://www.topcoder.com/thrive/articles/List%20of%20awesome%20learning%20resources

The Ultimate Topic List (with Resources, Problems and Templates) - Codeforces
https://codeforces.com/blog/entry/95106