DEV Community

Cover image for Are these lists equal?

Are these lists equal?

Carlos Roso on July 09, 2020

This is an entry-level algorithm to get you warmed up for tough interviews like those you get in Amazon, Google, Toptal, and top remote work sites....
Collapse
 
unmultimedio profile image
Julian R Figueroa • Edited

I like a lot these kinds of exercises, very nice diagrams and a way to explain it!

Did you know it can be solved with just one frequency map by adding/removing the key? Same O(n), but two-thirds of the operations and half the memory :)

Check (and run) this snippet: play.golang.org/p/ZR5QHwZPAn8

This is only valid because of:

You can assume that there's no duplicate item in any of the lists.

Very cool articles man! 🚀

Collapse
 
caroso1222 profile image
Carlos Roso

Thanks mate! Your support is always much appreciated 🙏🏼

You got a point, yeah! Much more performant in time and space indeed.

Collapse
 
robdwaller profile image
Rob Waller

This is an interesting post and a great explanation of the problem.

But I must ask what is the point of an interview question where someone can basically Google the answer? This doesn't really tell you a lot about the developer.

It saddens me we see this a lot in the tech industry.

Collapse
 
caroso1222 profile image
Carlos Roso

Good point. There's no absolute answer to this question. This has been and will be a heated discussed topic.

It doesn't sadden me, though. I wouldn't apply to work at such a company if it doesn't align to my values, which would be your case. And that's fine. It's just another type of interviewing.

Truth is, if your goal is work at a FANG company or a top remote company, chances are you'll need to do algorithms. No need to be sad about it, though, just avoid such companies and find those you feel comfortable with.

Collapse
 
robdwaller profile image
Rob Waller

Admittedly algorithms aren't the worst example of "obscure tech question bingo" which a lot of organisations base their interviews around.

It saddens me because I don't think it's a great way to find good developers and will result in plenty of false negatives. So I believe good developers will needlessly miss out on good opportunities. Assessing the way a developer works rather than what they know at a given point in time is a better approach for finding good developers IMHO because the former is harder to teach than the latter.

But as you say this is for FANGs and I have never worked at a FANG and probably never will. And I imagine most of the developers they interview are of a high quality regardless.

Collapse
 
aigoncharov profile image
Andrey Goncharov

A great example of how one can sacrifice memory for CPU time! However, what is the point of counting if by the original condition "You can assume that there's no duplicate item in any of the lists". We might as well use sets here for simplicity.

Collapse
 
caroso1222 profile image
Carlos Roso

Yeah, a set would work perfectly well. That's the kind of realization I wanted from the post. I'd rather write about the general use case to have readers drill down to more optimal solutions.

Collapse
 
jiangh profile image
Hong Jiang

You could build a map with list 1, and then iterate over list 2 to compare each element with its count in the map. The asymptotic complexity is the same, but the code would be more concise and efficient (2 loops instead of 3).

Collapse
 
caroso1222 profile image
Carlos Roso

That's right. That's the kind of response I was expecting from this post. My O(n) solution is clear enough to lay a foundation for non-asymptotic optimizations like yours or that of the first comment. Thanks for contributing!

Collapse
 
alikham profile image
Ali Khan

Thank you Carlos 🥰 this is super helpful 🥳

Collapse
 
trelje profile image
Pelle Trelje

I understand that O(nlong) is a typo, but I like it.

Collapse
 
caroso1222 profile image
Carlos Roso

Good catch! I'll edit, thanks!

Collapse
 
akdeberg profile image
Anik Khan

The way you explained it is really awesome and praiseworthy. Great article 😊

Collapse
 
caroso1222 profile image
Carlos Roso

Thanks Anik! I'm glad it was useful to you :D

Collapse
 
abdisalan_js profile image
Abdisalan

Well done, give some value to the community then come in for the hard sell at the end ;)

Collapse
 
caroso1222 profile image
Carlos Roso

Yep. It's a win-win. Traffic for DEV. Value for readers. Traffic for me.

Collapse
 
mightytechno profile image
Mighty

Nice explanation. Thanks for sharing.

Collapse
 
caroso1222 profile image
Carlos Roso

Thanks! Glad you found it useful!

Collapse
 
lobsterpants66 profile image
Chris Shepherd

Hmmm,
I would employ someone who spent 5 minutes googling for a list compare solution and 2 minutes wrapping some code around it.

Seems more like a real solution to me.

Collapse
 
caroso1222 profile image
Carlos Roso

Fair enough. Both approaches are valid depending on the perspective.