When interviewers give Leetcode problems, what kind of solutions are they looking for?
I've used Leetcode personally as a source of problems I can think about at a leisurely pace in my head. I like to have a few such things (algorithm or coding problems, math problems, physics problems, music theory problems, electronics problems) that I can use when I'm lying in bed but not quite falling asleep yet or stuck in a slow line somewhere to pass the time.
For the Leetcode problems I've used for that, usually from the "hard" or "medium" categories, it is almost always the case that I can easily and quickly come up with an algorithm that gives the answer and I could easily code but is O(n^2).
It is getting down to O(n log n) or O(n) that is difficult. (I'll give a couple of examples below for your amusement of problems where O(n^2) was easy but doing better took me weeks or months).
Are most interviewers satisfied with O(n^2) that produces the right answer or are they looking for something better than that?
Now for your amusement two problems that took me ages to get past O(n^2).
1. You are given an array of integers and are to find the smallest positive integer that is not in the array. For example given [1, 9, 4, 7, 2, 5] the answer is 3. Your answer should run in O(n) time and use constant extra space.
2. Find the longest palindrome in a string. No time or space constraints are specified.
For the first missing positive integer problem without the time and space constraints the answer that quickly comes to mind is to sort the array (O(n log n)) then scan for the first i such that the element at the i'th position is not i ((O(n)).
What really threw me was the constant space requirement. I had always assumed the inputs were constant in Leetcode problems and could and so could not think of a way to do this without using O(n) space.
I even ended up spending a while trying to prove that it could not be done in constant space hoping that when I could not prove that seeing why I could not would point me toward what I was missing. But I was able to sort of convince myself that a Turing machine could not do it in constant space--"sort of convince" because I'm rusty enough with Turing machines I could not be sure I was missing something.
It turns out that inputs aren't constant in Leetcode problems. You are allowed to modify input arrays. It was then not too hard to figure out the O(n) time and constant extra space solution.
For the palindrome problem an O(n^2) is quite straightforward. But I've got a couple of other approaches that seem faster.
Let's call the two halves of a palindrome its "arms". So an even palindrome consists of two arms that are mirror images next to each other and an odd palindrome consists of two mirror image arms that are separated by one character.
If you have an even palindrome with arms of length n, and you want to check for an odd palindrome one over to the that is longer than the even palindrome, you can move the right arm over by one and check that it is still a mirror of the left. If it is you have found a longer odd palindrome.
It the shifted arm does not match, you can then shift the left arm over and check for a match. If they match you have an even palindrome of the same length. You can then check to see if the arms can be extended while still matching.
By inching the arms across the string this way, extending them when possible, you can sweep the string finding the longest polynomial. If verifying that the arms are mirror images was O(1) this inching approach would be O(n). But comparing the arms the most obvious way os O(L) where L is the length of the arm, which would be 1/2 the length of the longest palindrome found so far, which would be O(n), so the inching approach with the simplest arm matching is O(n^2).
But can we do better? What if we maintain for each arm some kind of hash. We can compare the hashes of the arms and only if the hashes match do we need to then do a character by character check that the arms really match. But this doesn't seem to buy us anything because hashes are O(L).
But maybe we can take advantage of the fact that we are moving the arms one character at a time through the string. We need a hash H that given a H(S) for some string
S allows as to compute H(S') where S' is S with a single deletion from one end and a single addition at the other end. For example, our hash might simply be the sum of all the characters in the string. Computing that for an arm after sliding it one addition and one subtraction.
I'd rather have a hash where strings that are just permutations of each other hash differently, so spent a while on that. I came up with something that seemed pretty good, then realized that rsync has such a hash and I should use grab that. It turns out though that the one I came up with is the one rsync uses.
I'm now stuck trying to figure out the run time of this. In most cases I think it will be somewhere between O(n) and O(n^2). Where depends on how often the hash gives false positives on arm matching.
The other approach I'm playing with is completely different. Suppose we scan the string and build a frequency table of all the characters. This is O(n). Now look at the least common character and note the constraints that it puts on the possible positions of long palindromes.
For example suppose the string is 1000 characters long and it only has 3 'X's, which are at positions 10, 200, and 700. We can immediately deduce that if the first X is part of a palindrome that does not include the second X it is an odd palindrome of at most length 19. If the first two X's are part of a palindrome it must be odd and up to length 219. We can make similar deductions for the rest of the cases, and we can rule out any palindromes containing all three X's.
We can check each of those cases to find the longest palindrome involving X. That leaves us with the string partitioned into 4 sections where we then need to check for palindromes larger than the largest X-containing palindrome.
We could then do a similar thing with the lest frequent character in each of those regions, and so on.
Or maybe better is to start with the two least frequent characters and consider their distribution in the string together.
In general the idea here is that the distribution of any particular character in the string imposes constraints on where long palindromes might be and maybe we can build up a set of such constraints to cut the number of palindrome checks we have to do sufficiently to get an efficient algorithm.
That's about as far as I've gotten with this approach. I feel there is probably something there but it might take someone way smarter than me to find it.