Product of Array Except Self

Given an array of \( n \) integers where \( n > 1 \), \( nums \), print an array \( output \) such that \( output[i] \) is equal to the product of all the elements of \( nums \) except \( nums[i] \).

Solve the problem in \( O(N) \) without using division.

[Read More]

Stock Maximize

Solutions A good strategy consists in selling one share only if that increases someday in the future. The best time to sell it corresponds to highest price reached after the day we buy the stock. For instance: 1 2 5 100 The best strategy is: at day 1 we buy the stock and we pay 2 at day 2 we buy the stock and we pay 5 (we don’t sell the stock bought before yet) at day 3 we sell both the stocks by earning 100-2 + 100-5 = 193 In other words, the best strategy consists in buying every stock at price \(p_i\) only if in the future the stock price \(p_i\) is surpassed. [Read More]

Student Sections

The school term starts soon, and the students need to be sorted into their respective sections. There are \( n \) students numbered \( 1 \) to \( n \), and \( m \) sections numbered \( 1 \) to \( m \). Section needs to have exactly \( a_i \) students. To simplify the process, the school has decided to assign students to sections in increasing student number, which means the first \( a_1 \) students will be assigned section \( 1 \), the next \( a_2 \) students will be assigned section \( 2 \), and so on. [Read More]

The Crazy Broker

Solutions This problem seem complicated if you try not using additional data structures. This is a typical case where pre-processing is needed and, in particular, we use two special kind of prefix sums. To answer to the first type of queries, we need to cache the running maximums of the prices: 1 2 3 4 5 6 7 8 vector<int> prefixMax(n); auto runningMax = p.front(); prefixMax[0] = runningMax; for (auto i=1; i<n; ++i) { prefixMax[i] = max(runningMax, p[i]); runningMax = prefixMax[i]; } In C++, we have a very useful standard algorithm to perform the same routine: [Read More]

The Lucky Employee

Summer is over and people at Gugol are sad and unmotivated. They would prefer going back on vacation instead of working - how to blame them? Ted, head of employee happiness department, has got an idea to cheer people up: he will run a lottery among all the employees and will award the luckiest one with two extra weeks of vacation. The lottery will work this way: Ted will raffle off some ranges of employee ids like \( [120, 200] \) and \( [150, 180] \), a sophisticated algorithm will calculate which is the most frequent employee id in all such ranges, if more than one such an id exists, the sophisticated algorithm will select the smallest one - it corresponds to the employee who has been working at Gugol for more time You are a \( \cancel{slave} \) trainee at Gugol and you have to design and write such a sophisticated algorithm. [Read More]

The maximum subarray

Solutions We have two similar tasks: find the maximum sum of any nonempty subarray find the maximum sum of any nonempty subsequence The latter is clearly esier since the elements in a subsequence are not necessarily contiguous. The former is a very classical problem that we’ll deal with in a moment. To solve the first task, we can sum all the positive elements. This works as long as we have at least one positive (or zero) element. [Read More]