Problem:
We have an array arr[0 . . . n-1]. We should be able to
(1) Find the sum of elements from index l to r where 0 <= l <= r <= n-1

(2) Change value of a specified element of the array to a new value x. We need to do arr[i] = x where 0 <= i <= n-1.

Solution:
We can solve this problem using different datastructures. The main purpose of this problem is to introduce some datastructures which are useful to find optimized solutions in many cases.

Prefix Array:
Given an array arr[] of size n, its prefix sum array is another array prefixSum[] of same size such that the value of prefixSum[i] is arr[0] + arr[1] + arr[2] … arr[i].

void precompute(int prefixSum[])
prefixSum[0]=arr[0]

for i=1 to n-1 prefixSum[i]=prefixSum[i-1]+arr[i]

int rangesum(int l,int r,int prefixSum[])
if(l=0)
return prefixSum[r]
else
return prefixSum[r]-prefixSum[l-1]

void update(int i,int x,int prefixSum [],int arr[])
int diff = x-arr[i]
for j=i to n-1
prefixSum[j]=prefixSum[j]+diff
arr[i] = arr[i] + diff

Time complexity of range sum query is O(1)
and update query is O(n)

Binary Indexed Tree:
DETAILS
Binary Indexed tree or Fenwick tree takes O(logn) complexity for both range sum operation and update operation.
Compared with segment tree , binary indexed tree requires less space and is easier to implement.

Segment Tree:
DETAILS
Segment tree also performs both range sum operation and update operation in O(logn) time.

Square Root Decomposition:
DETAILS
The key concept of this technique is to decompose given array into small chunks specifically of size sqrt(n).
The time complexity of range sum query is O(sqrt(n)) in worst case.
The time complexity of update query operation is O(1).

Solve different problems using these datastructures to become proficient in applying them in various competitive programming problems.

For any doubt or correction feel free to contact me:
@saranyanaharoy

Happy Learning

Jump Game

Difficulty level : Medium


Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index.

Example 1:
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Hint / Solution Link :
SOLUTION

Microsoft Interview Problem

Given an array, rotate the array to the right by k steps, where k is non-negative.


Example 1:
Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:
Input: [-1,-100,3,99] and k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]


Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Could you do it in-place with O(1) extra space?


Solution:
SOLUTION

"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