Lately, I’ve been involved in lots programming interviews which involves a lot of data structures and algorithm questions. I discovered practice and practice and practice is all I need. I’m using this thread to challenge myself to solve at least two problems per day. Others can join me too.

Key to Success: Strong Background in Data Structure and Algorithm, and Logic Mathematics.

Languages: C++, and sometimes Java. Others can use Python.

Never knew Nigerians were interested in Competitive programming.

Following

Let's start with this

Karleb:
Let's start with this

The question looks weird. Why 5 and not 6. 11-5. Isn't the goal of selling stocks to get profit. Why not gain more profit. If I had this question the first thing I will do is to sort the array. Then I would loop through the array twice for every loop I will subtract the preceding number from the oncoming number and place that in a constant and return the highest number. The only problem with loops is the time complexity o(n).

tensazangetsu20:

The question looks weird. Why 5 and not 6. 11-5. Isn't the goal of selling stocks to get profit. Why not gain more profit. If I had this question the first thing I will do is to sort the array. Then I would loop through the array twice for every loop I will subtract the preceding number from the oncoming number and place that in a constant and return the highest number. The only problem with loops is the time complexity o(n).

I believe your brute force approach will increase the time complexity to O(n2) since you are looping twice.

For those that love the challenge.

Karleb:


I believe your brute force approach will increase the time complexity to O(n2) since you are looping twice.

Oh yes. Thanks for the correction on that.

Karleb:
Let's start with this

This is clearly a DP problem.

i will post the solution when i charge my laptop

tensazangetsu20:

The question looks weird. Why 5 and not 6. 11-5. Isn't the goal of selling stocks to get profit. Why not gain more profit. If I had this question the first thing I will do is to sort the array. Then I would loop through the array twice for every loop I will subtract the preceding number from the oncoming number and place that in a constant and return the highest number. The only problem with loops is the time complexity o(n).

The aim of the problem is to make maximise profit.

You can decide to buy/sell on the day of your choice.

If you buy on the first day at 9 units and sell on the second day, you make a gain of 2 units.

if you buy on the second day and decide to sell on the subsequent days, you make a loss of 3, 6, 4 and 1 unit respectively.

If you buy on the third day at 8 units, you make a loss of 3 and 1 units on the 4th and 5th day and a gain of 2 units on the 6th day.

if you buy on the 4th day at 5 units, you make a gain of 2 and 5 units on the 5th and 6th day respectively.

if you buy on the 5th day at 7 units and sell on the 6th day, you make a gain of 3 units by selling in the 6th day.

As clearly seen, you make the highest gain when you buy on the 4th day at 5 units and sell on the 6th day at 10 units

clockwisereport:


The aim of the problem is to make maximise profit.

You can decide to buy/sell on the day of your choice.

If you buy on the first day at 9 units and sell on the second day, you make a gain of 2 units.

if you buy on the second day and decide to sell on the subsequent days, you make a loss of 3, 6, 4 and 1 unit respectively.

If you buy on the third day at 8 units, you make a loss of 3 and 1 units on the 4th and 5th day and a gain of 2 units on the 6th day.

if you buy on the 4th day at 5 units, you make a gain of 2 and 5 units on the 5th and 6th day respectively.

if you buy on the 5th day at 7 units and sell on the 6th day, you make a gain of 3 units by selling in the 6th day.

As clearly seen, you make the highest gain when you buy on the 4th day at 5 units and sell on the 6th day at 10 units

Amazing way to think about the problem. How would you go about solving it then?

What are the input constraints for the problems?
E.g
1 < The size of the array < 10^6

Having constraints gives an idea of how efficient your algorithm should be. Like for the second question you could go for a brute Force approach that runs in O(n^2) time, but that would be horribly inefficient for an array of size 10^6, so you would have to come up with something more clever. But if the problem is simply just make a function with no regard of its speed, then that makes things much easier.

clockwisereport:


This is clearly a DP problem.

i will post the solution when i charge my laptop

I will be expecting it.

I like the level of engagement on this thread.

I guess I'll post another problem tomorrow.

clockwisereport:


The aim of the problem is to make maximise profit.

You can decide to buy/sell on the day of your choice.

If you buy on the first day at 9 units and sell on the second day, you make a gain of 2 units.

if you buy on the second day and decide to sell on the subsequent days, you make a loss of 3, 6, 4 and 1 unit respectively.

If you buy on the third day at 8 units, you make a loss of 3 and 1 units on the 4th and 5th day and a gain of 2 units on the 6th day.

if you buy on the 4th day at 5 units, you make a gain of 2 and 5 units on the 5th and 6th day respectively.

if you buy on the 5th day at 7 units and sell on the 6th day, you make a gain of 3 units by selling in the 6th day.

As clearly seen, you make the highest gain when you buy on the 4th day at 5 units and sell on the 6th day at 10 units

I duff my hat for you.

You should take up the role of a lecturer!

if I got the question correctly then this should work. I can't guarantee efficiency or speed tho since I don't know algorithms terms like O[n2] or all that stuff

arr = [9, 11, 8, 5, 7, 10]
def buy_and_sell(arr):
	sorted_arr = sorted(arr)
	buyAt = sorted_arr[0]
	slicedArr = arr[arr.index(buyAt): ]
	slicedArr.sort()
	sellAt = slicedArr[-1]
	
	return sellAt - buyAt
	
print(buy_and_sell(arr))

DrLevi:
if I got the question correctly then this should work. I can't guarantee efficiency or speed tho since I don't know algorithms terms like O[n2] or all that stuff

arr = [9, 11, 8, 5, 7, 10]
def buy_and_sell(arr):
	sorted_arr = sorted(arr)
	buyAt = sorted_arr[0]
	slicedArr = arr[arr.index(buyAt): ]
	slicedArr.sort()
	sellAt = slicedArr[-1]
	
	return sellAt - buyAt
	
print(buy_and_sell(arr))

DrLevi:
if I got the question correctly then this should work. I can't guarantee efficiency or speed tho since I don't know algorithms terms like O[n2] or all that stuff

arr = [9, 11, 8, 5, 7, 10]
def buy_and_sell(arr):
	sorted_arr = sorted(arr)
	buyAt = sorted_arr[0]
	slicedArr = arr[arr.index(buyAt): ]
	slicedArr.sort()
	sellAt = slicedArr[-1]
	
	return sellAt - buyAt
	
print(buy_and_sell(arr))

Nice approach. It works for that example but not for some others e.g [2,3,4,1,2] will return 1 and [2,4,5,1] returns 0.

.

Karleb:




Although my python is not that good and I've not ran the code, but I believe this will return a negative value.

Lol... It wouldn't. The code works, just might not efficient

Darivie04:

Nice approach. It works for that example but not for some others e.g [2,3,4,1,2] will return 1 and [2,4,5,1] runs into an error.

now you've mentioned it, it becomes more complex.

back to the drawing board

How about this one?

.

Darivie04:
[right][/right][center][/center]

 prices = [9, 11, 8, 5, 7, 10]

 def buy_and_sell(stock_prices):
  largest_profit = 0
  for i in range(len(stock_prices)):
   for k in stock_prices[i:]:
    if k - stock_prices[i] > largest_profit:
     largest_profit = k - stock_prices[i]
  return largest_profit

 print(buy_and_sell(prices))
 

There should be a more clever way to solve the problem but this works.

This code returns "2" instead of 5

DrLevi:

This code returns "2" instead of 5

Must be nairaland formatting cutting out part of the code, I'm still tryna fix that. It returns 5 over here.

Darivie04:

Must be nairaland formatting cutting out part of the code, I'm still tryna fix that. It returns 5 over here.

Brilliant, it works

https://pastebin.com/vpYL0k7r
Much easier. The formatting on the site was messing up the code.

Karleb:
How about this one?

I have done this before

vheckthor1:
I have done this before

Post your answer here let's learn

Karleb:
Let's start with this

This is a maximum sub array problem, famous Kadane algorithm.
It's an O(n) algorithm, only one for loop is required
Call the first array a with size n,
You create a new array of size n-1, each index i will contain a[i + 1] - a[i], then you find a maximum sub array of the new array.


If I had to study an undergraduate course in Nigeria again, I would have studied Mathematics

Karleb:
For those that love the challenge.

This should be O log (n).
You sort the tuples, you keep adding elements from the tuples (navigating from top to bottom) to a new list, before adding you do this, if the last tuple that was added to the new list, contains the range of the new tuple you want to add, you skip adding this tuple to the list, if the new tuple contains the range of the last tuple added, you remove the last tuple added, and add the new tuple, else you just add the new tuple to the list

Karleb:
Let's start with this

function maxer(arr){
let holder = 0;
for(let i=0; i< arr.length; i++){
let some = arr.slice(arr[i])
let maxima = Math.max(...some)
let subractor=maxima - arr[i]
if(subractor>holder){
holder = subractor
}
}
return holder
}
solved in javascript and the big O(n)=1
a single loop