4 ms·

I've just finished the 2nd year of my CS degree. In about 3 minutes I came up with: 1) create an empty string, call it "S2" 2) loop over each char in original

I've just finished the 2nd year of my CS degree. In about 3 minutes I came up with: 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.

deleted 7y ago
[deleted]
171243 7y ago
input: "bcabc" 1. "b" 2. "bc" 3. "bca" 4. "bca" 5. "bca" What am I missing?
- MaximumYComb 7y ago
  Nothing. I hadn't fleshed out my idea yet and that's the error I thought could exist. My solution is wrong.
- deleted 7y ago
  [deleted]
- deleted 7y ago
  [deleted]
- kangnkodos 7y ago
  Take all the possible answers with duplicates removed, and return the first one in alphabetical order. input: "bcabc" output: "abc"
- pizza_dave 7y ago
  that is a single line of code in javascript, assuming you just want the value in #5 const foo = [...new Set('bcabc'.split(''))].join('')
thaumasiotes 7y ago
Here's what I came up with after experimenting with handling the leetcode example ("given cbacdcbc, produce acdb") manually: Build a suffix tree ( https://en.wikipedia.org/wiki/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.
- thaumasiotes 7y ago
  After playing with suffix trees a little more, I need to make a correction: 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.
mmierz 7y ago
That solution as written is O(n^3) This is not an easy problem.
- MaximumYComb 7y ago
  You only check each character in the string once. A hashmap can check if the char is used already. 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.
  - thaumasiotes 7y ago
    > 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.
    - MaximumYComb 7y ago
      The algorithm I described was O(n), you said it was O(3). I'm assuming this happened because my algorithm was actually an incorrect solution but you subconsciously added in steps to make it a correct algorithm which changed its complexity. Hence it's semantics because we seem to be discussing two different algorithms.
- thaumasiotes 7y ago
  Can I ask about the suffix tree solution? A one-hour problem is still pretty easy in the grand scheme of things.
deleted 7y ago
[deleted]
deleted 7y ago
[deleted]

deleted 7y ago

[deleted]

171243 7y ago

input: "bcabc" 1. "b" 2. "bc" 3. "bca" 4. "bca" 5. "bca" What am I missing?

MaximumYComb 7y ago
Nothing. I hadn't fleshed out my idea yet and that's the error I thought could exist. My solution is wrong.
deleted 7y ago
[deleted]
deleted 7y ago
[deleted]
kangnkodos 7y ago
Take all the possible answers with duplicates removed, and return the first one in alphabetical order. input: "bcabc" output: "abc"
pizza_dave 7y ago
that is a single line of code in javascript, assuming you just want the value in #5 const foo = [...new Set('bcabc'.split(''))].join('')

thaumasiotes 7y ago

Here's what I came up with after experimenting with handling the leetcode example ("given cbacdcbc, produce acdb") manually: Build a suffix tree ( https://en.wikipedia.org/wiki/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.

thaumasiotes 7y ago
After playing with suffix trees a little more, I need to make a correction: 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.

mmierz 7y ago

That solution as written is O(n^3) This is not an easy problem.

MaximumYComb 7y ago
You only check each character in the string once. A hashmap can check if the char is used already. 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.
- thaumasiotes 7y ago
  > 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.
  - MaximumYComb 7y ago
    The algorithm I described was O(n), you said it was O(3). I'm assuming this happened because my algorithm was actually an incorrect solution but you subconsciously added in steps to make it a correct algorithm which changed its complexity. Hence it's semantics because we seem to be discussing two different algorithms.
thaumasiotes 7y ago
Can I ask about the suffix tree solution? A one-hour problem is still pretty easy in the grand scheme of things.

deleted 7y ago

[deleted]

deleted 7y ago

[deleted]