#4. Contains duplicates

Posted by

0

https://leetcode.com/problems/contains-duplicate/

This one always tricks me – even though the problem is really straightforward, I have spent a lot of time trying to find a solution better than O(n) time.

But given the constraint -> -109 <= nums[i] <= 109 – optimal solution cannot be better than O(n) time. Also, the optimal solution ends up being O(n) space as well, since we have to use a Set or a Map data structure to record previously seen numbers.

If we can’t allocate O(n) space: there are two possible solutions. One approach could be to use two loops -> select a number and check if that numbers appears again in the rest of the array -> this would be a O(n^2) solution.

The other solution first sorts the input (which would take O(n logn) time) and then iterates over the sorted array to detect equal neighbors. Swift uses Timsort -> which takes O(n) space, but we could implement selection sort which runs in O(1) space – however I would not expect that in an interview (hopefully).

If we relax the constraint to:

  • Only allow positive numbers with a known upper bound (m)
  • We are allowed to modify the input

In this case, we could solve the problem in O(n) time and O(1) space -> this approach works by moving numbers to their ‘correct’ indexes (e.g. moving the number 2 to index 2 -> which would need moving the number at index 2 to its correct position). If we ever find a number already at its correct position – we know that we have found a duplicate.

#3 Merge Two Sorted Lists

Posted by

0

https://leetcode.com/problems/merge-two-sorted-lists/

This is fairly straightforward problem – the only tricky part being the pointer manipulation associated with any LinkedList related question – but that gets better over time with practice.

Optimal solution takes O(N) time (where N = m + n i.e. addition of the two lists) and O(1) space.

Since the two lists are sorted, we need to pick the smaller element in each iteration and move the pointer ahead for the associated list. At the end, we should not forget to pick off the remaining items from the longer list.

With Swift, using the while let loop operator does make the code a lot easier to reason about.

Valid Parentheses

Posted by

0

https://leetcode.com/problems/valid-parentheses/submissions/

The optimal solution for this one cannot be better than O(n) space – unless you are willing-to/allowed-to modify the input. Also, should that solution be considered O(1) space if you are reusing the space allocated for input?

Instead, the O(n) space optimal solution can be achieved using a stack/array to keep a record of open brackets. When we see a closed bracket – we should return false if the last open bracket is ‘nil’ or not the matching ‘type’. At the end of the loop – we should also not have any dangling open brackets – if we do, that means the sequence of brackets was not balanced – and we should return false.

Edit: Let’s say, that the problem states the input string could only contain one of ‘(‘, ‘[‘, “{” types – in that case we can keep a single integer var openBrackets that we increment when we see a open bracket and decrement when we see a closed one. At any point if openBrackets becomes negative we know that the sequence was unbalanced, similarly, at the end of the loop, openBrackets should be 0 for the string to be balanced. This is O(1) space solution since we do not need a stack/array to keep a track of open brackets.

2 Sum

Posted by

2

https://leetcode.com/problems/two-sum

Probably the first problem you solved when you started leetcoding.

This is a classic problem – I haven’t been asked this problem ever in an interview – but this one brings back a lot of memories and yes there was a time I struggled to solve this problem as well 🙂

Using 2 loops would be the most straightforward but slow way to solve this problem – in an interview, the interviewer will expect a better solution that O(N^2) though.

The optimal solution uses a hashmap to keep the index of previously seen numbers – this increases the space complexity to O(n), but improves the time complexity to O(n).

Variant: Although this problem asks for the index of the two numbers that add up to target – there is a variant of this problem that asks for the actual numbers itself (i.e. find the two numbers that add to target). That variant can be solved in O(n logn) time, if we cannot/do-not want to allocated O(n) space – that solution first sorts the input array and then iterates over the sorted array with two pointers – increasing the left pointer if the sum is smaller and reducing the right pointer if the sum is larger than the target.

If you just solved this problem on your own – welcome to leetcoding, you have an exciting journey ahead of you.

Grind 75

Posted by

0

Although I have done most of the questions from this list while preparing for interviews in the past, I am going to revisit this series again over the next few weeks.

For two reasons:
#1. I want to start making YouTube videos – this series of questions seems like a good idea since I can focus on the video making part and not worry about the content much.
#2. It would be a good prep primer as I start preparing to enter the market again.

Let me know if you have feedback on the content I create – it would good to hear back on what I could improve as I start learning the art of video making.

Struct Vs. Class in Swift

Posted by

0

TLDR:

Classes:

  • Are referenced
  • Can inherit from other classes.
  • Have a de-initializer
  • Have an identity (‘===’).
  • Allocated on the heap – reference maintained on the stack.

Structs:

  • Are copied, not referenced.
  • Can implement protocols
  • Allocated on the stack

Why this question?

This question gets asked a lot in interviews. In fact, I don’t even remember an interview in which this discussion was not bought up in some form.

More than likely, though, this gets asked of you in a telephone interview – I think I should write about the different types of iOS interviews out there – but that is for another post.

Going back to the telephonic interview – the hiring team quickly wants to figure out if you are worth talking to – they want to know if you know the basics and if you would be able to meet the hiring bar if invited for an on-site interview.

And this question is perfect for that.

If you can’t explain the difference between a Struct and Class in a couple of sentences – you have never worked with Swift or you aren’t paying attention to details – in both cases, the company would likely not want to hire you. (sorry, but true).

Basics

First off, Structs are value types, whereas Classes are reference types. That means a new copy of data is created every time you pass a Struct around. Whereas for classes, new references keep pointing to the same location in memory when accessing data.

This makes Structs inherently safer than Classes – with a Struct, another thread will never be able to modify a value you are holding on to. Instead, the thread will get a new copy of the data and can only modify its local copy.

With Classes, on the other hand, you have to be cautious when working with multiple threads – since a different part of code could be pointing to the reference you are holding on to – issues such as data corruption or unintended side effects are more likely.

In a telephonic screen – the interviewer might just stop you at this point and move on to the next question since it is clear you understand the most fundamental difference between a Struct and Class.

Other differences

Classes support inheritance which Structs do not. (Inheritance mostly causes more issues than it resolves, but that’s for another blog post, I guess). But if your specific use case is a good fit for inheritance, you have to choose Classes over Structs for data modeling.

Classes also have a ‘denit’ method which gets called just before the object is released from memory – this could be useful to clean up any resources you might be holding on to in the Class. With Structs, since they are allocated on the stack (and are treated as values), there is no equivalent method.

Immutability difference

A Struct created with a let keyboard is immutable – both the reference and the values inside. That means the reference cannot point to another Struct, and the values cannot be modified in the future.

However, a Class reference created with a let keyboard allows values inside to change, but the reference is immutable.

Which one to use?

Structs should normally be your default choice when modeling state in your app because of the thread safety associated with value types – using Structs also makes your code much easier to reason about since you need to only focus on a method/block of code without worrying about another part of the app modifying state.

However, you would be better off starting with a Class in the following scenarios:

  • You need interoperability with Objective C.
  • Reference-based modeling makes sense for your use – i.e., you want to share state between your apps threads and use the side effects to propagate state changes.
  • You want to use Identity checks (‘===‘) for equality.

How do people get started?

Posted by

0

Obviously I didn’t write. Ha-ha, what a surprise!?

Why is it so hard to build a new habit? I feel like forcing myself to do anything more than the existing routine is super hard.

How do people get started on new behaviors and then stick with them?

Maybe I am aiming too high? Instead of trying to create polished articles or well-made videos, should I focus on just producing content? Perhaps over time, I would get better at it while keeping the barrier to entry low.

Another blog.

Posted by

0

Here is to a new blog.

Just getting started with this whole writing thing – over the last few days I have realized that writing calms me down, there is something about writing that organizes my thoughts, makes my brain churn less.

I plan on writing here just to clear my mind, to talk about my days and life.

This blog may not add any value for someone else – this is because I am not writing for others, this blog is just to keep me sane.