Google is the Only Company to Ask this Coding Question! | 1st Letter to Appear Twice - Leetcode 2351

Subscribe to get daily coding videos in your feed!

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[AlphabetAYT]

You can have an array instead and each time we find a letter mark the corresponding index in the array as 1. Boolean array can also be used.

[villandoom]

26 bit can fit inside of a integer. In C++ you can do this with uint32_t, set to 0. When a character is noticed it will look it up and if it finds that it's already set to 1 return that index (perhaps convert to the corresponding letter as uint8_t) if not set the bit to 1. With this you can take advtnsge of fact it does not need to be in memory which is alot slower as it can simply fit inside of a Register instead of memory. And another thing is that this code uses dynamic memory which is even slower

[andrewhamel]

Like all tech bros we miss the important point here: the answer is entirely irrelevant in an interview, it's the explanation you offer. If you have a really interesting reason why you think the hashset is better, I want to hear it!

[dominobuilder]

Also, worst case you would have to look through 27 letters in the string before a repetition has to come. So the time complexity of the entire solution is O(1). Meaning it doesn’t even grow with the length of the string.

[undergroundmonorail]

i feel like you could defend a set here. it won't be faster but it's not clear that this is a performance-critical function, and it's arguably clearer what the intention is

[MrEliteXXL]

It could be made using a bitmask of 26 bits initialized at 0, flipping each bit when finding the corresponding letter and if it is already flipped that is the first letter that appear twice

[Rickyuhh]

i’ve been using youtube shorts a lot and you popped up on my feed and have been showing up recently and you have been giving me the confidence i need to continue on my internship journey🙏

[orterves]

Need to use a bit array (aka 1 32-bit integer)

[SilverSuperGamer]

C++:
26 byte array, index at the character - 'a'
Or a 256 byte array and index at the character for efficiency, since it will be stack allocated after all meaning it doesn't really matter how much memory is used, assuming you have enough memory on the stack (quite likely)

[parthon]

There's a ZERO memory use solution where you can just use the part of the strong you have already checked AS THE SET itself, and it will be faster.

[eliberkowitz]

A set is fine, and it's a bit more readable and extensible if the character set changes in the future. It's also around 7% faster than a list in Python from a test I just ran with 10k iterations. It really doesn't matter which you use unless you have more information (if we're in python I doubt it matters)...

[SufficientElevator]

Set is implemented with a hashmap, that's how it checks if a[] contains x. The reason you shouldn't use that is because you can easily construct a perfect hash function for this set of well-known data. the hash-function built into set is a good default for average data, but it (probably) isn't as good as just setting one bit out of 26.
A more difficult follow-up question would be how would you return all values that appear more than k times -> Misra–Gries heavy hitters algorithm

[HrHaakon]

You could use a hashset, an array, a bitfield on an integer (IF the alphabet is 32 or fewer characters, they did NOT specify the English subset of latin characters after all), or something else, but if the string isn't long, is it really worth your time?

[ivanchu]

These kinds of questions were specific as follow up to get to know if the person they're interviewing is actually thinking about the set of data they're using, and I think it leads to a lot of quality answers, good style of questioning compared to some random drag on to do something in a specific way, may as well get the experience of the person to answer how they would've done it

[TehIdiotOne]

I'm actually pretty happy that i came to the same conclusions and reasonings that you did before even watching the video

[extrams]

This vid ignores the pigeonhole principle.

"at most 26 items in the list, so it's a very fast lookup", ignores that the loop, at most, runs 27 times.
Opimisation on that level ... 26 checks instead of one is HUUUGE!!!!

Obvious, using a bitmask is the right answer, but one could argue that's a specialized form of hashing

char => (1 << char -'a' )

And write it in assembler instead of python, for good measure

[Eikenhorst]

Why would you look it up?? You know there are 26 options at most. So basically you initialize an array of 26 booleans at the start, they are all false by default. You find the next char in the string, you get the unicode integer by just typecasting it, subtract 97 such that 'a' becomes 0. That gives you the index in the array for that character, so you check if that index hold a true, if yes, return character, if no, set to true and continue with next character.
Doing a lookup is just way too slow!

[bkubicek]

The first n characters of the string already _are_ th seen letters.
One only needs to create an uint8_t array, with len of string, that is used for counting.
To go through the string, for checking if previously occured is faster than to go through a linked list.

[quickdry]

the problem only says 'lowercase english', it doesn't say what character encoding, but so many responses assume ascii or whatever. The follow up question to super clever bit based answers could be "now what if this was the character encoding" and then nothing works. Those assumptions about chars made for a LOT of work when databases and their applications suddenly had to jump up to handle different character sets, and numbers of bytes per character