News for hackers. Stuff that matters.
Re:How necessary are the programming fundamentals? by jasonpeacock on Wednesday May 19, 2021 @10:00AM (#27208727)
IMO, there's a difference between people who are very good at connecting frameworks together and have a strong knowledge of many frameworks and platforms, and people are who are actually building those frameworks/services for others to use. It's the latter who are hard to find & hire, as most people (esp. coding bootcamps and self-taught courses) focus on the former because you can quickly create working mobile and web applications.

One question that I ask during interviews is to write a method to find the intersection of two lists of integers in better than O(n^2) time - basically, any solution that is not two nested `for` loops.

    intersect([1, 2, 3, 4], [2, 4, 6, 8]) => [2, 4]
Half the people I talk to cannot do that in 30 minutes. (no, you cannot use the built-in set operators)
Re:How necessary are the programming fundamentals? by marlowe221 on Thursday May 20, 2021 @09:56AM (#27221140)
I'm a self taught programmer who got his first full time job in tech in June 2020 after 13 years of practicing law. Here's how I would do it:

const intersect = arr1.filter(value => arr2.includes(value))

I don't know much about Big O notation yet, so I don't know if my solution would meet your speed requirements or not, but I'd be interested in your feedback.

You could also turn the two arrays into sets and then compare them. But I'm not sure what impact that would have on performance, if any, in your example.

Re:How necessary are the programming fundamentals? by jasonpeacock on Thursday May 20, 2021 @12:03PM (#27222925)
`arr1.filter()` says "apply a filtering function to every value in arr1". This is O(n) because as the size of arr1 (n) grows larger, the work grows at the same rate (linearly).

`arr2.includes()` says "check if value is in arr2", and most languages implement this method as a linear search (esp. if arr2 is an array). This is also O(m) because as the size of arr2 (m) grows larger, the work (linear search) grows at the same rate.

Taken together, the algorithm is doing "for every value of arr1, apply a filter function which linearly searches for the value in arr2". If arr1 is size 5 (n), and arr2 is size 10 (m), then the total work being done is 5*10 (n*m). Thus the overall performance is O(n*m), though it is commonly simplified to the worst case where both sizes are the same: O(n*n), or O(n^2).

This is the same as using nested for loops, just more elegant (and functional):

    intersection = list()
    for i in arr1:
        for j in arr2:
            if i == j:
                intersection.append(1)
    return intersection

---- SOLUTION ----

One approach is to convert one list into a Set, O(n) because you have to traverse the list once. Then iterate the second list and check if it exists in the Set. Checking if something exists in a Set is constant time, O(1), so you only have the cost of traversing the second list once O(m).

The overall performance is O(n + m * 1), or O(2n) because we assume worst case of both lists being the same size. That is usually simplified to O(n) as we're usually only concerned about the performance behavior, e.g. "how does it change as it gets bigger?" and not directly comparing say two algorithms of O(3n) and O(5n + 1).

There's still a lot of unhandled edge cases and other issues that need addressing in the solution described above, and there are other valid solutions as well. The goal is only to be better than O(n^2), not optimal.

Re:How necessary are the programming fundamentals? by marlowe221 on Thursday May 20, 2021 @02:07PM (#27224822)
Thanks! I appreciate you taking the time to explain and critique my solution.

I've been slowly trying to go back and learn some computer science topics that I missed out on self-teaching and I still have a long way to go.

Re:How necessary are the programming fundamentals? by jasonpeacock on Thursday May 20, 2021 @02:57PM (#27225524)
No problem, even if you had it in school it takes some practice thinking this way to become fluent.

A fun exercise to give reality to the theoretical is to run some benchmarks for your solution, providing inputs of size 10, 100, 1K, 10K, 100K, 1M, etc. and seeing how the performance changes. You can also (with some benchmarking tools) look at the memory usage as well.

When talking about algorithm performance, there's usually considerations for both time and space (memory or disk) that need to be considered.

One thing you'll notice is that most solutions, even the O(n^2), are "fast enough" at small sizes that it doesn't matter what approach you take. In those situations, readability/clarity usually wins such as with your proposed solution.

If I knew my lists would never get larger than 100 elements (or even 1K), I would totally do what you did. The secret is in knowing the problem you're solving.

Re:How necessary are the programming fundamentals? by sireat on Thursday May 20, 2021 @03:17PM (#27225746)
Question is if you allow using prebuilt Map type data structures.

Then it is easy just bucket count with keys being integers in the list and iterate afterwards filtering for value >= 2

Now if no Maps are allowed it is a bit trickier... you might need your own hashing function or as someone else suggested write your own nlogn sort..

Re:How necessary are the programming fundamentals? by commandlinefan on Wednesday May 19, 2021 @11:49AM (#27210303)
Sorted or unsorted?
Re:How necessary are the programming fundamentals? by kubb on Wednesday May 19, 2021 @11:53AM (#27210361)
You can sort yourself, it's only O(n*logn), so it's still gonna be better than O(n^2), even when you include the linear scan to get the intersection.
Re:How necessary are the programming fundamentals? by LorenPechtel on Wednesday May 19, 2021 @10:17PM (#27216608)
And this is why the fundamentals matter.