let's say you have a bunch of unsorted date-times
> 2018-02-08 10:23
> 2018-02-08 9:30
> 2018-01-01 12:00
> 2018-02-08 15:10
given one of them, is there an algorithm for finding the one that follows chronologically (without sorting).
e.g. given the 9:30 how to find the 10:23?
Other urls found in this thread:
idk
>(without sorting).
iterate through all the rest of them and keep track of the smallest time past the current time that has been seen so far
>people like OP are the next generation of programmers
I think of it as job security.
thanks, that's what i was thinking as well. what would the big O of this approach be? is sorting with something like bubble sort better? its worst-case performance is O(n^2)
This. Lmao
Why you want me to do your homework OP?
It's a single pass that only compares the current smallest to current index, you should be able to figure it out
O(n)?
That's basically a min(array) algorithm with a custom min(a,b) function.
At least don't post dijkstra when you're posting these stupid questions.
Yes
It's O(n) worst case
Kids these days aren't getting into programming for the passion, they're getting into it because of the money and because Obama said it was cool to do so
grep then subtract and compare
Sup Forums is that way --->
...
he's right desu
temp = first date in list
iterate over all dates, if date < temp && date > given then temp = date
if temp < given (it's the first in list which was also smaller) then return None
else return temp
Convert it all to unix time, then compare.
But sort it, don't be a faggot.
Too many retarded and over complicated answers ITT
just take your dates, run a loop through them that deletes all - and spaces and : characters
you'll be left with 201802081023 for example
proceed to convert them all to integers and sort like you do normally.
>SORRRRRRT
Is it DD-MM or MM-DD?
You can't tell with your examples, you should include a day after the 12th.
???
you don't know how to sort an array of integers?
>given one of them, is there an algorithm for finding the one that follows chronologically (without sorting).
Can it have dates less than a minute apart, causing duplicate dates?
If I find a 9:31 can I stop searching?
You dare post dijkstra next to this retarded post? Shame on you OP.
Cant you ever read OP, also you shit answere is stupid and slow
fucking retard
i don't care if this is bait or not
translate all into (nano)seconds from epoch
>without sorting
find the smallest greater value by iteration then
>get to the h:mm instead of hh:mm
>kernel panic
This is your only option, OP, O(n) in any case. But why wouldn't you want that shit sorted? Is it, like, milliards of entries? Because if it's not - you're retarded, and should use something like bucket/radix sort - this problem is literally a textbook example for it
> bubble sort
are for fucking real?
I seriously hope nobody ever runs your code in production. May god have mercy on the soul of whoever dares
If there's a unique smallest greater date (see ) then an O(1) best case would exist
right, you can optimize it that way if you wish, but it's one comparison more for every check.
Point is, OP seem unable to supply exact requirements even after been asked.
I suspect this might be an homework assignment.
Ok, for each date, add a label for year, month, day and time. Now subtract the year label with each date. Now you will only consider the dates whose subtraction equal to 0 , because all of them will be the same year. Then you do the same for months and days. This way at the end the code will only consider the dates whose year, month and day are the same. Then every hour will be pased to 24 hours. You subtract them in a way that if the number is negative you add a hourdate1beforedatex, if it positive hourdate1afterdatex, that way it easy to compare them (example date1beforedate2, date2beforedate3 ten date1beforedate3). Then the code go back and take another day, if this day its the same than date1, then pass to the next (also add a code for when there is a sigle year, month or day). I am too lazy to keep thinking how would you compare then the days, months and years, but I guess that the same method for hours would work.
No. FUCKING NO. Don't do this retarded thing.
convert to epoch time with build-in method/function.
The answer is right after the date to epoch convertion.
> I am too lazy to keep thinking
Rise your iq to three digits then you can post.
With MY method you will had less dates to work with. Good luck iteratig over thousand and thousand of dates.
lel no.
one pass to put labels : Ω(n) with n the size of the list
putting label : O(1)
iterating throught dates is Ω(1) but O(n) in the worst case.
If you have the whole set of date stored in cache you won't have that many cache-missed in the second pass.
it's O(2n) ~ O(n) and you have unknow duration on the second pass, it's retarded when you can do everything in one pass.
getting epoch time from the system is heavy as you have to change context to get the hardware time but converting date to epoch is trivial and can be done by highschoolers.
usually you sort dates when you store them so you can quick sort (usually some enhanced merge sort which take advantage of caches sizes).
MM-DD
>because of the money and because Obama said it was cool to do so
perfect, they are doing not only for being greedy retards but communists too. What a wonderful world we live in.
I did it because I liked computers. Now that I have my CS degree I realise that I hate computers
>dijkstra.jpg
>this retardation
kys
take a substring of each integer. convert it to a const integer data type. Proceed to compare each value against its counterpart.
let smallest equal infinity
for date in dates do
let timestamp equal date converted to unix timestamp
if timestamp is less than smallest then
assign timestamp to smallest
end
end
I have never coded in my life, but thanks for the explanation.
The rule of thumb is that it's always YYY:MM:DD. It makes sense when you try and sort them by descending, etc. They'll actually be in the correct order chronologically
YYYY-MM-DD **
GNU sort.
...
STRING SEARCH
>It's O(n) worst case
It's redundant to say worst case. O(n) implies worst case.
Hey Ethan, great moves.
var result = datelist.orderby(x => x)
or something
What implies best and average case?
omega for the best case, "average case" is an interesting concept.
Thanks.
No, it's not implied.