Scribd
Upload
5 views33 pages

Problem Solving Techniques for Coding

The document outlines post-bootcamp strategies for improving problem-solving skills in competitive programming, emphasizing the importance of practice, contests, and perseverance. It introduces various problem-solving techniques such as two pointers, pre-computation, and prefix sums, along with example problems to illustrate their application. Additionally, it highlights the significance of optimizing brute force methods to enhance efficiency in coding challenges.

Uploaded by

akilan.tmlzs
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
5 views33 pages

Problem Solving Techniques for Coding

The document outlines post-bootcamp strategies for improving problem-solving skills in competitive programming, emphasizing the importance of practice, contests, and perseverance. It introduces various problem-solving techniques such as two pointers, pre-computation, and prefix sums, along with example problems to illustrate their application. Additionally, it highlights the significance of optimizing brute force methods to enhance efficiency in coding challenges.

Uploaded by

akilan.tmlzs
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

Contents

 What after BOOTCAMP?


 Problem solving techniques such as two
pointer, pre-computation techniques,
hashing, prefix sum
 Practice problems
What after BOOTCAMP?

Practice
Contests
Up solve
Repeat
Contest
Platforms:

Practice
Platforms:
It might not be easy for everyone but
what matters is:
Consistency
Perseverance
Problem Solving Techniques

 There are various problem solving methods to


optimize brute force codes. Some of these are
extensively used in competitive programming.
 You will come across more and more techniques as
you solve more and more problems.
Given two sorted arrays merge
them into one single array
Two pointers

 Uses more than one, typically two, pointers to iterate through


various data structures and process data effectively.
 In many cases it reduces time complexity from O(n^2) to O(n).
 Practice Question :
Given a string s, reverse the order of characters in each
word within a sentence while preserving whitespaces and initial
word order.
Example : Input = “Consistency is the key”
Output = “ycnetsisnoC si eht yek”
Practice Question

 Given an integer array nums, move all the even


integers at the beginning of the array followed by all
the odd integers.
Input: nums = [3,1,2,4]
Output: [2,4,3,1]
Explanation: The outputs [4,2,3,1], [2,4,1,3], and
[4,2,1,3] would also be accepted.
Pre-Computation Techniques

 Sometimes constraints of a problem are such


that one needs to pre-compute values in
advance such that they can be looked up in
O(1) time.
 These are extremely necessary in CP where
calculations can be done without knowing
actual details of the queries.
 Apart from these advantages, previously
acquired results can be reused(very similar to
dynamic programming).
 Example 1:
Number of test cases = t; maximum t=10^6
Find factorial of a number for each test case. Maximum n =25
Example:
Input 3
3
8
15
Output: 6
40320
1307674368000
Sieve of Eratosthenes

 It
is the most efficient way to find all primes
smaller than n when n is smaller than 10
million or so.
 Time complexity is O(Nlog(log(N)))
 Itis generally used in number theory
problems.
Tryto implement it
yourself
 Given array a of N integers. Given Q queries
and in each query given L and R print sum
of array elements from index L and R(L,R
included)

 Constraints
 1<= N <= 10^5
 1<= a[i] <= 10^9
 1<= Q <= 10^5
 1<= L,R <= N
Brute force Optimized
Prefix sum

 A prefix sum is a concept in computer science and


mathematics that refers to the cumulative sum of
elements in an array up to a certain index.
 This is another pre-computation techniques.
 Used extensively for cumulative range based
queries.
THANK YOU

You might also like