A good problem gives people with algorithms ability a space to demonstrate that, but it should also give space for demonstrating strengths in design, coding, communication, etc. This one is almost all algorithms, of the "have you seen things like this before" variety, plus a small amount of code.
(Speaking only for myself)
The other important bit is that you often don't need to just find the optimal solution to get good ratings. For the question I used to use, I've had perhaps one person get the optimal solution without any hints. None have solved the extensions without hints. I've given more than one Strong Hire rating.
Can someone explain this? I can't even parse that sentence.
CACB
You can get either CAB or ACB. If you were to order all of the possible results of removing duplicates (in this case only two, but obviously many more for more complex strings) and order them alphabetically, then take the lowest one, that would be the right answer.
In the second example with input cbacdcbc a possible solution would be cbad but acdb is "smaller" (ordered before).
As an engineer, before starting to code, I'd first ask if the customer would prefer "abcd" or "cbad" for the second example, as either would be far cheaper in terms of development and maintenance costs to do. It's somewhat common to discover that they're just taking the "acdb" you're giving them because that's exactly what they asked for, and then they're alphabetizing it to "abcd" afterward on their end, anyway. But sometimes, there is a legit reason for the weirdness, and the customer is willing to pay for the extra effort.
Whenever someone seems intent on aiming at foot and pulling trigger, always ask "Are you sure?" and "Why do you want that?" at least once before helping them do what they want.
The "read hypothetical; code answer" type of test doesn't quite capture that like the interactive interview discussion does.
I sometimes follow a Reddit sub geared for mostly recent CS grads. Every week or two will be a post from someone who got a FAANG job, detailing what he did in order to pass the interview. And some of these are pretty absurd - graduating last semester and since then spending 6 months going through leetcode 6 hours a day, studying algorithms, paying for interview training classes, etc.
And as an older guy who has a decent CS degree but hasn't needed to use 90% of anything related to algorithms in 15 years, I'd have to study a lot, and along with the numerous days of vacation time used for these interviews in California, it doesn't seem worth the effort.
AFAIK they only blacklist you for 6 months and then you can try again. Even that may be relaxed if you're trying for a different department or, especially, geographical location.
> numerous days of vacation time used for these interviews in California, it doesn't seem worth the effort.
In India at least, the big companies handle this better than smaller ones - they have one or two telephonic interviews to begin with and then finish off all the face-to-face interviews in a single day.
12ms w/ 2.1MB memory usage - apparently 25 percentile for speed and lower memory usage than 100% of submissions in ~50 lines of Go.
[1] https://leetcode.com/submissions/detail/292246392/ (Not sure if you can deep link in to leetcode like this?)
[2] I am looking for a job! Hit me up! https://news.ycombinator.com/item?id=21937576
It seems you cannot, 404 error.
1) create an empty string, call it "S2" 2) loop over each char in original string 3) if the char isn't in S2, add it to the end of S2. If the char is already present in S2 then lexicographically compare the prior S2 verse S2 with this char shifted to the end. Keep the lower ordered one.
This took about 3-4 minutes of thinking and is O(n). It might not be optimal, it might not even be a correct solution as I've spent only a few minutes on it. However, I feel it's close and it wouldn't take much to flesh out.
EDIT: This solution is incorrect.
Build a suffix tree ( https://en.wikipedia.org/wiki/Suffix_tree ) of the input with two modifications:
1. When adding a letter to the suffix tree, skip any paths that already contain that letter. (Thus, each path will contain a given letter no more than once.)
2. Include accounting information in each node specifying the length of the longest suffix including that node.
From wikipedia, construction of an ordinary suffix tree takes time and space linear in the length of the input string. At this level of analysis, I'm just hoping that modification #2 doesn't affect that. #1 certainly won't, in that it involves spending less time and less space than otherwise (by bailing out early under some circumstances).
Once the tree is constructed, just walk it, selecting at every point the child that is lexicographically earliest among all children with the maximum suffix length.
Observation: constructing this tree by hand really feels exponential; I suspect that the linear time and space requirements lean on an assumption that the size of the alphabet is finite.
Observation #2: Based on the comment timestamps, this took about 40 minutes of thinking. I think it's a good solution, but it probably wouldn't look great in an interview. (Also, handwaving "construct a suffix tree" is fast, but actually producing the code to do it takes extra time.) :/
Observation #3: assuming your solution is correct, it is essentially a reduction by dynamic programming of this one, only doing the calculations that are necessary to produce the lexicographically earliest string where I produce them all.
This problem asks for subsequences rather than substrings. As a result, when adding a node to the "suffix tree", it will need to be added as the child of more nodes than it would if we were building an actual suffix tree.
This seems like the type of change that might make construction of the tree harder than O(n). In particular, it will violate the constraint that a suffix tree for a string of length n has only n leaves.
This is not an easy problem.
For each char in the original string there is: * 1 check in hashmap (let's assume it was found). This is O(1) * build a new string where we remove that char from the string we are building (string2) and add it to the end. This step may look O(n) initially since we need to find that char in string2 but string2 is capped at 26 characters so it's O(1) * One comparison between the string we are building and the altered version.
How does that make it O(n^3)? I can't see which step inside the initial loop is O(n) or greater.
EDIT: The solution is actually incorrect so this is now semantics.
Interesting use of "semantics".
The question of "how fast does this algorithm run?" is totally independent from the question of "what does this algorithm do?"; the second one is semantic but you're discussing the first here.
1. "b"
2. "bc"
3. "bca"
4. "bca"
5. "bca"
input: "bcabc"
output: "abc"
I'll stick with creating actual solutions for real people with real problems. So much easier. shrug
I have never tried to solve such problems before, but wouldn't it be enough to convert the string into a set of chars, then into an array of chars, sort it, and return it as a string?
No. Please re-read the problem statement. It's way more complicated than that. If you figure out how to do it, try to figure out how to do it in O(N).
An optimal solution would be something like
- create an array of 26 or 52 bytes depending on whether this is case sensitive
- iterate over the string and set the byte corresponding to each letter’s position in the alphabet to 1
- iterate over the byte array and for each 1 you encounter print out the corresponding letter
Consider the input “ba”
This solution will return “ab”, which is not a strong that can be generated by deleting characters from the input.
But that's what "lexicographical" means?
> In mathematics, the lexicographical order is a generalization of the way words are alphabetically ordered based on the alphabetical order of their component letters.
> This generalization consists primarily in defining a total order on the sequences (often called strings in computer science) of elements of a finite totally ordered set, often called an alphabet.
> if you still understand your undergraduate level algorithms course and the corresponding vocabulary, then you know what you need to know
speaking from experience, this would not get you nowhere near the level you have to be for passing the Google interview (or any other FAANG interview for that matter). You need to study long and hard in addition to solving OJ problems and familiarize yourself with different problem patterns. Let me give you and example of what I got at Google: https://leetcode.com/problems/remove-duplicate-letters/ Solving this problem optimally with only what you remember from undergrad algo courses is impossible. You either need to have a knack for these types of challenges or solve enough of them to identify a solution pattern.