Show HN: Design, data-structure, algorithm problems and their solutions(github.com)

103 pointsby sanguptavor 10 Jahren25 comments

Show HN: Design, data-structure, algorithm problems and their solutions

https://github.com/sangupta/ps

25 comments

In https://github.com/sangupta/ps/blob/master/solutions/2016/fa... the solution for fastest integer sorting is wrong.

    / build the boolean result array
    boolean[] result = new boolean[array.length];
    for(int index = 0; index < array.length; index++) {
      int num = array[index];
      result[num] = true;
    }

The result array is the same size as the original array.

But when you do:

    int num = array[index];
    result[num] = true;

The index being referenced in the result array is dependent on the value of num. So if num is greater than or equal to the length of the array, it throws an ArrayOutOfBoundsException. And what happens when you try sorting an array with elements having the same value?

Eg- try sorting {10,5,9}

Unrelated: HN needs to allow highlighting code inline.

jedimastertvor 10 Jahren

In the prompt, he says we are looking at a "bounded" integer set, so presumably we know the largest possible number before we start

sanguptavor 10 Jahren

My bad - that was a typo when writing. Updating it.

sawmuraivor 10 Jahren

Yep, should be

boolean[] result = new boolean[Math.max(array)];

ploggingdevvor 10 Jahren

That won't be efficient memorywise since the size of the result array is dependant on the largest value in the array of values.

Consider sorting an array of 2 large integers {65000,30000}. To sort this array, the result array will be initialized with 65000 elements. Very inefficient.

EllipticCurvevor 10 Jahren

Yeah, well, now you get an exception. Not much better...

You should look into bucketsort. That allows you to sort in finite universes in Theta(n+k) without allocating huge arrays for large integers.

sanguptavor 10 Jahren

I will read more about bucketsort and update the article as necessary.

EllipticCurvevor 10 Jahren

I have a simple Python implementation of Countingsort, Bucketsort and Radixsort, if it helps: https://github.com/MauriceGit/Advanced_Algorithms

sanguptavor 10 Jahren

Wouldn't using a sparse bit-array be equivalent to using Bucketsort in space-complexity, but more efficient in time-complexity, or am I missing something here.

sanguptavor 10 Jahren

Thanks a bunch for the link.

sanguptavor 10 Jahren

Using a sparse bit-array will reduce the memory space of the problem.

sanguptavor 10 Jahren

I can work up one. Choosing the right bucket will be O(1) as the index is integer. We can store the buckets for lookup in a hash-table or an array-of-arrays, which again will be O(1). Reaching to the actual index should again be O(1) - unless am messing something here.

rhardihvor 10 Jahren

Yes, but do you have an implementation of a sparse array with constant time lookups?

rhardihvor 10 Jahren

This phrase is misleading:

The fastest time to sort an integer array is O(N)

It could be interpreted as generally applicable. The proposed method uses reverse-indexed flagging, an approach which isn't really feasible if element values are very large.

Generally, the lower bound for any comparison based sorting algorithm is Ω( n log( n )).

EllipticCurvevor 10 Jahren

That is true. Just want to add, that the lower bound for sorting is O(n log(n)) for comparison based sorting in infinite universes. The comparison based factor rules out sorting of any element, that can not be reduced to an integer. Infinite universes in sense, that we don't know about the elements/element-range beforehand.

Sorting in θ(n+k) w.c. and a.c. (most of the time this is equal to O(n)) is possible for finite boundaries that allows for countingsort or bucketsort (radixsort uses countingsort internally).

Some implementations of those algorithms in Python: https://github.com/MauriceGit/Advanced_Algorithms

sanguptavor 10 Jahren

Agreed about the phrase thing - updated the phrase accordingly to say:

"Fastest sorting of bounded integers"

vijayrvor 10 Jahren

Is there something like this for designing of databases? software architecture? For example, things like - learning to design a HIPAA compliant user database, designing a micro services architecture for a small but well defined problem etc?

dtauzellvor 10 Jahren

I think that falls more into the "patterns" space as the problem being solved is not so clear cut. Here is a site with microservices patterns: http://microservices.io/patterns/ .

sanguptavor 10 Jahren

None that I know of and thus the inspiration to start this.

I so intend to write on some pieces of software architecture that I have understanding of. For micro-services piece, if you specific sample well-defined problems, please do let me know and I would like to cover it up.

kevasvor 10 Jahren

I don't know if this has HIPAA compliant schema among their collection ~1,500 or so models.

http://www.databaseanswers.org/data_models/

joakleafvor 10 Jahren

A lot of discussion on bucket/pigeon hole sorting and O(n log n), but nobody mentioning(?):

Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space, Yijie Han and Mikkel Thorup, FOCS '02 Proceedings of the 43rd Symposium on Foundations of Computer Science Pages 135-144

http://dl.acm.org/citation.cfm?id=652131

... Just thought I would throw it out there.

sanguptavor 10 Jahren

Thanks a bunch. I mentioned similarities to bucket sort earlier in the day.

I will go over the mentioned paper and also mention it as a reference.

qwertyuiop924vor 10 Jahren

After going back to solve last year's Advent of Code, I realized that I really need to know more about algorithms. So this is handy.

But I still can't solve last years' AoC. Oh well. I guess I'll just have to keep working on it.

sn9vor 10 Jahren

Check out Sedgewick's Algorithms course on Coursera.

qwertyuiop924vor 10 Jahren

Thanks for the suggestion.