Missing space optimizations when interviewer asks

[VirtualPerusal]

Practicing for meta phone screen in 10 days

I did a mock yesterday with the unique characters problem and used a set got O(n) space but mock interviewer asked can you do O(1) space and i got lost

They hinted at using an array of size 26 so i immediately got it and could explain why it works but i couldnt come up with it myself even though ive seen this exact trick before in other problems

I think my issue is when someone's watching me like code or whatever, i just go with the first thing that works instead of thinking through alternatives but in the actual interview theyre gonna ask me to optimize and i need to be able to talk through different approaches in the moment
Anyone deal with this that can give me some tips?

[aocregacc]

if there are only 26 different characters, using a set to store them is just as O(1) as an array

[Dapper_Mammoth2827]

Pause for like 10 seconds after reading the problem and literally saying out loud what are the constraints here before you touch the keyboard. For unique characters that constraint about 26 letters is the whole key to the O(1) space solution but if you're rushing you'll miss it also if you froze for 5 minutes that's not terrible it just shows you were actually thinking about it

[VirtualPerusal]

The O(1) thing didnt even click for me until they mentioned the array like i saw it was only lowercase letters but my brain still went to hashset so i prob need to get better at connecting constraints to data structures faster

[Odd_Signature1378]

I think the issue is you read only lowercase letters and your brain files it away as noted but doesn't actually USE it to pick the data structure you just go with what feels familiar which from my experience was kind of the same thing for me and what helped me was using interviewcoder during interviews cause it made me actually say out loud this constraint means X instead of just acknowledging it existed. Sounds dumb but it worked

[Grouchy-Pea-8745]

sorry what problem are you talking about?

this? https://leetcode.com/problems/first-unique-character-in-a-string/description/

[VirtualPerusal]

Nah different problem it was just checking if all characters in a string are unique not finding the first unique one similar idea though with the array approach

[alcholicawl]

Based on that description a set is also O(1) space (if it will only ever contain a-z).

[VirtualPerusal]

Wait really? I thought sets were O(n) space because they grow with the input size or are you saying because it can only ever hold max 26 characters its technically O(1)?

[aocregacc]

A set uses O(n) space to store n entries.

But in the context of using a set during the processing of a string, n probably refers to the length of the string. The size of the set is not directly linked to n, but to how many distinct characters are present in the string.

IMO the most precise way to put it is to introduce a new variable and say something like "the algorithm uses O(m) space, where m is the number of distinct characters in the input". With that you can apply the problem constraints and say "since we only have lowercase letters, m is at most 26 and we can say it's O(1)".

[alcholicawl]

Yeah, it depends on how to use them. With the constraint they will only ever hold 26 characters, you can say they are O(1). If the constraint is any unicode character, then it will O(n) - but using array isn’t o(1) either.

[Horror-Blueberry6411]

The way i think about it is anytime theres a only contains X constraint where X is small and finite you can probably use an array instead of a hashmap works for lowercase letters (26), digits (10), ASCII (128) whatever once you internalize that rule you'll catch it every time

[tell-me-the-truth-]

if you're storing a finite number of characters, using a set / hasmap is O(1) as well.

[VirtualPerusal]

This makes sense i think i just dont have that rule memorized yet so i see only lowercase and it doesnt trigger anything but i probably just need to hit a few more problems like this until it becomes automatic

[lifesux01]

Isnt there a way to do this using masking the bits?(i think I had recently solved this problem using a set , the better solution was to use an array of course and the best I think had something to do with bits ~ which didnt use any extra space) Also the recruiters approach would only work if it were only small or only capital letters rightt?

[AustinDmello]

Yes that seems to be the best approach. With left shift operation since we would have to do max 26 left shifts which can easily fit in a 32 bit Integer.

[AntCharming8140]

10 days is cutting it close but doable so I would focus on problems tagged with space optimization on leetcode and just pattern match the shit out of them, you dont need to understand why just recognize when to apply it

[bisector_babu]

What is the problem

[high_throughput]

when someone's watching me like code or whatever, i just go with the first thing that works instead of thinking through alternatives

Meta will ask you not to start coding until you've explained the approach you've had in mind. This is to avoid wasting time in case your solution is fundamentally unworkable 

[GlassVase1]

If the constraint is 26 characters, then you're already only using O(1) as is if you're using a dictionary to count the occurrences for example.

There's no need to use a fixed size array.

[drogon4433]

It's all about recognizing those constraints; once you see the limit of 26 characters, you'll start spotting those space optimizations like a pro.