dpalmasan / competitive-programming Goto Github PK

Chapter 4 examples:

• Bubble sort
• Merge Sort
• Count Sort

Generating permutations example and explanation.

Set up gcov to check coverage.

Seems like doctest will do the trick as it is easy to set up and lightweight.

Given an array of events with their starting and ending times (start, end), return the best schedule (maximum amount of events) selecting events that could be scheduled without overlapping times.

Given a list of weights [w1, w2, ..., wn], determine all sums that can be constructed using the weights. For example, if we have the weights w = [1, 3, 3, 5], in this case all sums between 0 and 12 are possible, except 2 and 10.

Solution for longest increasing subsequence problem.

Examples will be added to "Learn by doing", and also they will be explained.

Implement a function that receives an array as input and returns true if the array has unique elements and false otherwise. Implement an O(n log n) approach (use sorting)

In a restaurant, customers arrive and leave during all the service hours. We'd like to find the maximum amount of customers at a given time window. Suppose we know the arriving and leave time (input), find the maximum amount of customers in the restaurant.

Add a solution for a variation of the coin change problem, in which we are interested in counting the number of ways you can arrange coins to sum a certain amount n.

Example:

coins = {1, 3 , 4}, n = 5, there are 6 ways to arrange the coins to sum 5:

• 1 + 1 + 1 + 1 + 1
• 1 + 1 + 3
• 1 + 3 + 1
• 3 + 1 + 1
• 1 + 4
• 4 + 1

Examples will be written in C++ and Python. We need to define a Makefile to build each of the exercises, and also for testing purposes.

Suppose we have a set of coin values coins = {c1, c2, ..., ck}and a target sum n. We are asked to construct the sum n using as few coins as possible.

Examples:

• coins = {1, 2, 5} and n = 12 an optimal solution would be 5 + 5 + 2, which is 3 coins.
• coins = {1, 3, 4} and n = 6, an optimal solution would be 3 + 3 = 6

Find a path from the upper left corner to the lower right corner of an n x n grid, with the restriction that we can only move down and right. Each path contains and integer and the path should be constructed so that the sum of the values along the path is as large as possible.

Implement algorithms for different time complexities and document explanations.