ProgrammerHumor
averageTechJobInterview
Discussion
Yeah just walk out
If that solution takes anything but O(1) time, you're automatically disqualified
Longest common prefix isn't even that hard though. Just iterate through both sequences from the beginning until they don't match. It seems in the same tier as fizzbuzz for a "weed out people who lack basic programming skills" question.
For 2 ordered containers, as you say it's trivial. Literally a one-liner.
For N, not so much.
Why not? It still seems like it could be a one-liner. You just advance until one of the N doesn't match or you've reached the end of one of the strings.
I don't think we're describing the same problem.
Let's do strings.
Blue
Red
Black
Bluegreen
Brown
Orange
Yellow
Periwinkle
Cornflower
Orangered
Pink
Cerulean
Blackpink
Green
Off-white
Cream
Eggshell
What's your algorithm for the longest prefix that appears in multiple strings. Eg, in this case, "Orange".
The longest common prefix of all of these strings is the empty string "" because they do not all share the same first character.
Oh, if it's for every string then that's absolutely trivial.
You'd learn more from "what's an integer" (extra funny if you ask a Javascript dev).
Oh, if it's for every string then that's absolutely trivial.
That's what those words mean, yes.
So what are we thinking here? I'm thinking a tree with each letter as a node with frequency and then see what's the deepest we can traverse where frequency is 2 or more.
It's still easy, just more steps, and I still wouldn't want to hire a developer who couldn't figure it out.
Right, but that's an interesting question. That's testing a skill.
Just getting to "you can very easily do this O(n log(n))" is useful. Can you do it O(n)? My way isn't.
With a trie you can do it in O(n), with n the total number of characters.
A more simple solution with hash maps would give you something like O(n*k) with n the total number of characters, and k the length of the longest word. (Or alternatively, O(m*k2), with m the number of words.)
I'm guessing your O(n log n) solution involves sorting the words first?
I think there's another O(n) approach that involves essentially applying radix sort to the words. Then you can even terminate early once each word is in its own 'bucket', meaning you've exhausted the longest common prefix. Though depending on what data structure you choose for storing the buckets, I think you pretty much reinvent the trie-based solution.
“basic” programming skills that are necessary for the job though?
Yes, knowing to loop through things and compare things to each other is necessary.
Why write it in leetcode? They’re running leetcode on their app servers?
I'm not sure what you mean. Leetcode isn't a programming language or technology, it's just a website with coding challenges, so I don't know how or why you would run it on an app server (unless your app is leetcode itself).
And remember you have to do it inplace no extra space and o(1) and same time proving p=np
Leetcode solves a specific problem companies need solving.
The point of the modern tech interview loop is to take a wide funnel and narrow it down. The first rounds need to narrow down the applicant pool by a factor of 1000, that's how many applicants there are to sort through, the vast majority of whom aren't right for the position.
Your engineers' time is very valuable, so you need an easy, standardized, and self-contained interview format that filters out the unqualified en masse. Only after that can the priority be finding the right candidate with positive signal.
Leetcode format interviews aren't perfect, but companies have found they statistically identify a good candidate, even if they don't identify all good candidates. Because that's the thing: you don't need to identify all good candidates, only one, because only one can take the job anyway. When the data set is highly imbalanced (vastly more unqualified applicants than qualified), and your objective is just finding any true positive, not necessarily all, you want to prioritize precision over recall. Your format might reject 90% of good applicants, but if it rejects 99.99% of bad applicants and with high probability nets you one of the 10% good, that's a good interview strategy.
And as the data has borne out, Leetcode style / DSA coding ability is often correlated with coding aptitude that's good enough on balance to make an informed choice, when taken together with signal from other rounds like systems design and behavioral. It does what it needs to for the company.
Longest common prefix is something that can actually come up irl and is pretty simple tho
DataDog told me the next step was leetcode and I told them they can just take my name off the list
Lol, datadog and Komodo health interviews both absolutely suck. I did 5 rounds with Komodo 4 off which were technical. They messaged me with “good news” then never messaged back. I think they were right that was good news
Mr May