Swetha Kannan

Managing Pandemic Fatigue As a Software Engineer

Posted on June 28, 2021 by Swetha Kannan

Remind yourself about why you do what you do

If you are feeling a lack of motivation and purpose at work, it’s important to take a step back and understand why you are doing this in the first place. Is it because you love coding, solving problems, managing projects, or working alongside talented people and learning from them? Or maybe you took it up to support yourself or your family financially.

Once you know why you are at this job, try and find out what parts of it are causing the lack of motivation. Perhaps you are stuck at a boring job, or a project that you don’t enjoy or maybe you are working overtime losing track of hours in front of the computer. Have conversations with your manager on what kind of work you would like to do once you have completed the current project and ask if there are certain parts of it that you can delegate to make space for work that interests you. You might be tempted to slog off without communicating but remember that a lack of motivation can kill productivity and the quality of work that you produce which is a lose-lose situation for your career and the company that you work for. If you tried that and you still feel miserable, see if it’s time to look for opportunities outside your company.

Take care of physical and mental health

Spend a few minutes 3 to 5 days a week to get a quick exercise session in the morning or after work. Establishing a morning/evening routine can help kick start the day in a right way and also make sure that you log off on time after a day’s work. Stretching for few minutes every hour is very helpful to offload the stress from the body from sitting and working in front of a laptop all day. The marinara chrome extension is a super useful tool to schedule focus time with short and long breaks throughout the day.

Have you been waking up and feeling too tired or fatigued to work, more often than before? The pandemic is an enormously difficult time for people around the world. So you are not to be blamed for not feeling up to it. Mental health is as important or in fact more important than physical health. So don’t skimp on taking a couple of sick days off to catch your breath.

If your problems are chronic or are really impacting work, look into ways in which you can get help. You can reach out to your support system or consider therapy to help you navigate the situation. Many companies have been offering various sessions for boosting morale and supporting employees through these difficult times. Try attending them once in a while. Here’s a quick summary of the different ways to care for our health.

Exercise for 30 minutes everyday
Do mindful meditation for 5 to 10 minutes
Stretch every hour or two
Eat food that nourishes your brain and body
Take time to address mental health issues
Spend time outside of work on hobbies
Take breaks when you are fatigued
Reach out to your social circle
Invest in building deeper connections at work

Verbalize the stress

We tend to go through a lot of stress assuming that our colleagues don’t have these problems since they all seem fine externally. It’s mutually helpful to check on your team mates and connect with others around the company who are also dealing with the stressors of the pandemic. This can be a great way for employees to share their stories and exchange helpful tips to move forward through all this. Verbalize your stress by talking about it to others, in coffee chats, or with a licensed therapist. You can also try writing them down, journaling etc which can offload the stress and give you some time to think through it and address them.

Take a vacation

Many of us might save all the vacation leave not wanting to waste them unless we are on an Instagram worthy vacation. On the contrary taking a shorter/ longer break every few months from work is so important to cope with work life let alone with a pandemic thrown into the mix!

Not taking breaks leads to burnout which can take a huge toll on our health and also impact the quality of work seriously. This becomes a vicious cycle as Engineers tend to lose motivation and purpose when we are not able to produce high quality work.

Find meaning outside of work

For many people, work is a huge part of their identity and this makes them ignore other parts of their lives which can have a significant impact on their well-being. Take time everyday to actively strengthen the aspects of your life beyond work. This could be spending time with your family, friends or neighbors, taking time out for your hobbies and interests, pursuing a side hustle that you are passionate about etc.

Another mistake that a lot of Engineers do is to treat work as their major hobby and don’t take time for anything else in life. This results in overworking beyond work hours which can eventually lead to burnout and a lack of focussed work because increased work hours do not lead to an increase in productivity. In fact, it lowers it significantly. People who take time out to do other things have improved creativity in a problem solving environment.

Have short term goals

With no definite end in sight, the pandemic can seem like a never ending drag. So focus on short term goals at work to check off every quarter or month. Work with your manager and write these goals down in a shared document so that you have something to work towards in a shorter span of time. Make sure that these goals are reasonable and attainable with a few stretch goals to try and challenge yourself in case the others have been accomplished.

Hope these tips are helpful to you. Above all, be kind to yourself and understand that the world is going through an intense pandemic and we were not prepared to go through the motions of life without being affected by it. Stay safe!

Better Programming

5 Useful IntelliJ Shortcuts On MacOS

Posted on June 21, 2021June 21, 2021 by Swetha Kannan

1. Cmd + / or ⌘/

This is a shortcut that can be used across several IDEs to comment out a line. You can use it again to uncomment the line as well.

2. Alt + Enter

It can be annoying to see some lines of the code show up in red. This is a super useful command that gives a list of suggestions to fix your code once you place the cursor on that line and click Alt + Enter. IntelliJ also calls this the problem solving shortcut and there’s a detailed article on their blog on how you can use this to accomplish various context actions.

3. Shift Shift

This opens a search box to search everywhere across the code. You can search across Classes, Files, Symbols and Actions.

4. Cmd/⌘

When you hover the cursor on a certain keyword, it shows a short description of the highlighted entity. If you click on it, IntelliJ displays the definition of the highlighted class, method or keyword. On the other hand holding Cmd/⌘ and clicking on the keyword will take you to the actual definition of that Datatype, Method, Class etc

5. Alt + Command + Arrow Keys

This is one of my super favorite shortcuts. Pressing Alt + Cmd + Left/ Right arrow keys lets you navigate back and forth between lines of code that you just looked at.

I hope this article was helpful and short enough for you to remember the shortcuts and try them out in your IntelliJ IDE!

Arrays and Strings, Data Structures/ Leetcode, Palindromes

Longest Palindromic Substring

Posted on June 7, 2021June 7, 2021 by Swetha Kannan

Problem Statement

Given a string s, we have to return the longest palindromic substring.

Note: Palindromes are words or phrases that read the same backward and forward, letter for letter, number for number, or word for word. Source: Grammarly

Examples

Input: s = “babad”

Output: “bab”

Input: s = “dfgggggkl”

Output: “ggggg”

Input s = “a”

Output: “a”

Thought Process

In any given string, to find the longest palindromic substring, the brute force approach would be to consider every possible substring and then have a helper function to check if it is a palindrome. This results in a cubic complexity for a string of length N. Why O(N³) complexity? To check if a string is a palindrome or not, we will have to traverse through the whole substring. At the worst case, this will be the entire string s. This takes O(N). We will then have to use two for loops to check each possible substring which will be O(N²). Now let’s think of an efficient way of doing this.

There are two types of palindromes.

Palindromes with an even number of letters. Examples: “aa”, “abba”, “cdeedc”
Palindromes with an odd number of letters. Examples: “a”, “aba”, “cdedc”

The speciality of palindromes is that they expand from a central point and mirror each other on the left and right. How to define what is the center? In an even length palindrome, the center is in between two letters. In “abba”, the center is in between the two “b”s. In “aba”, which is an odd length palindrome, the center is “b”.

How many possible centers are there in a given palindrome?

Example 1: “aba”

The possible centers to consider are a, a <-> b, b, b <-> a, a ie., 5 centers

Example 2: “abba”

The possible centers are a, a <-> b, b, b <-> b, b, b <-> a, a ie., 7 centers

For N = 2, possible centers = 3

For N = 3, possible centers = 5

For N = 4, possible centers = 7

For N = 5, possible centers = 9

Let’s look at the possible centers and see by how much does it go up for each value of N.

(5 – 3) = (7 – 5) = (9 – 7) = 2

We can calculate the number sequence by using xn. In this case x = 2, so 2N. We notice that for N = 3, the possible centers are not 2N = 6, we have to subtract 1. So the generalized sequence will be 2N – 1.

To solve the given problem, we can iterate through each character in the string while considering it as a possible center for a palindrome. We can then expand around this center while checking its left and right side for mirroring. Since there can be odd length and even length palindromes, we have to consider the max length between them.

To get the max odd palindrome, we pass the left and right pointers as the current character since the center is a single character. Example: “aba”, when i = 1 (b), the left and right starting points to expand around will both be “b”, i = 1.

To get the max even palindrome, we pass the left and right pointers as the current and next character since the center is in between two characters. Example: “abba”, when i = 1 (b), the left and right starting points to expand around will be “b”, i = 1 and the next “b”, i = 2.

We can then take the string with the max length between these two values.

longest_palindromic_substring = ""

for i in range(len(s)):
    odd_max = check_palindrome(s, i, i)
    even_max = check_palindrome(s, i, i+1)

    longest_palindromic_substring = max(longest_palindromic_substring, odd_max, even_max, key = len)

Now let’s write a helper function to check if the given string is a palindrome.

def check_palindrome(s, left, right):

    while left >= 0 and right < len(s):

        if s[left] == s[right]: # check mirroring
            left -= 1
            right += 1
        else:  # Break the loop if the characters mismatch
            break  

    return s[left+1: right]

Complexity

O(N²) time – O(N) to expand around each center and O(N) to check if the substring is a palindrome

O(1) space

Putting it all together.

Solution

def find_longest_palindromic_substring:
    
    if not s:
        return s
    
    def check_palindrome(s, left, right):

        while left >= 0 and right < len(s):

            if s[left] == s[right]: # check mirroring
                left -= 1
                right += 1
            else:  # Break the loop if the characters mismatch
                break  

        return s[left+1: right]

    longest_palindromic_substring = ""

    for i in range(len(s)):
        odd_max = check_palindrome(s, i, i)
        even_max = check_palindrome(s, i, i+1)

       longest_palindromic_substring = max(longest_palindromic_substring, odd_max, even_max, key = len) # This will return the max value based on string length (key = len)

    return longest_palindromic_substring

Hope you enjoyed this step by step problem solving approach for the longest palindromic substring problem and learnt a thing or two about palindromes!

Arrays and Strings, Data Structures/ Leetcode, Sliding Window Technique

Longest Substring Without Repeating Characters

Posted on June 1, 2021 by Swetha Kannan

Problem Statement

In a string s, find the length of the longest substring without repeating characters.

Example

Input: s = “abcabcbb”
Output: 3 (“abc”)

Note: Substring means that the letters in the string should be continuous.

Thought Process

The brute force approach to this problem is to construct every possible substring from the given string and keep track of the longest seen substring so far without any repeating characters. This is highly inefficient.

Whenever we want to optimize array or string problems which have some kind of order in them, in this case the continuity of a substring, it’s good to pause and consider whether we can apply the two pointer technique or the sliding window approach. Think about using two pointers in the following situations.

Using two pointers starting at the beginning and end of the array to shrink our search space while comparing the specific elements at start and end pointers
Two pointers starting at the beginning of the array and one moving at a faster speed than the other

Think of sliding window approach in the following situation.

This technique can be used when we need to solve contiguous subarray/ substring problems to solve the overall problem. The window size may be fixed or variable. The window size is variable when we need to find the subarray or the substring in the given problem that meets a certain criteria which is the scenario in this current problem.

Let’s use two pointers called start and end to shrink and expand our sliding window accordingly.

Expand the window when there are no repeated characters in the sliding window
Shrink it when we see a repeated character

Now that we are certain about how we will be using the pointers, the next step is to think about how to formulate shrinking and expansion.

How do we keep track of characters already seen?

As we expand our sliding window considering each additional character added to the substring, let’s store a mapping of a character and the last index where it was seen in a hash map.

lastSeenIndexes = {a: 0, b: 1} etc.

To expand:

We can use the end pointer to traverse the string from left to right for every iteration from i = 0 to i = n-1.

To shrink:

Shrinking the sliding window means determining the position of the start pointer.

The start pointer may have already advanced past the last repeated character
Or we need to move it to the index right after the index of the last seen character

start = max(start, lastSeenIndexes[c] + 1)

Complexity

O(N) time complexity and O(N) space

Solution

def lengthOfLongestSubstring(self, s):
     """
     :type s: str
     :rtype: int
     """
     if not s:
        return 0
        
     start, maxLen = 0, 0
     lastSeenIndexes = {}
        
     for end in range(len(s)):
         c = s[end]
            
         if c in lastSeenIndexes:
             start = max(start, lastSeenIndexes[c] + 1)
                
         lastSeenIndexes[c] = end
            
         maxLen = max(maxLen, end - start + 1)
            
    return maxLen

Hope you enjoyed this step by step problem solving approach for the longest substring without any repeating characters problem!

Professional Improvement

10 Best Practices For Software Engineers To Ensure a Successful Onboarding

Posted on May 24, 2021 by Swetha Kannan

1. Version Control Systems

Learning and mastering the basics as well as frequently used version control concepts are crucial for Engineers to make onboarding easier. It also helps to set oneself up for productive future work. If your company uses a graphical UI for source control, there is a temptation to never learn the Command Line Interface (CLI) but you will eventually have to work at companies who extensively use the CLI. If you are going to be using the Git Version Control System, then here’s my article on some of the Git commands that I have used the most in my career. This should get you through 90% of your Git encounters.

2. Befriend Your IDEs

As soon as you meet your team, find out about IDE(s) they prefer to use. If there’s a clear majority, spend some time learning the basics of using it, including but not limited to cloning repositories, automatic deployment and syncing code changes with a remote host, debugging workflows, automatic refactoring – For example, IntelliJ offers a way to refactor a constructor and replace it with with either a Factory or Builder pattern in Java which can come very handy. Learn shortcuts to search for files, keywords, classes, functions etc. in any code base.

3. Searching For Information

Some companies do a great job of documenting their code, processes and knowledge base and some don’t. Wherever you are, it helps to understand how to search for documentation, previous conversations or issues around a certain topic, code search, ticket search if you’re using a tool like JIRA to manage tasks. The ability to know where and how to search for information facilitates a natural curiosity to indulge in problem solving time before deciding to give up too early and reach out for help. Eventually you might enjoy helping out other Engineers as well with their questions which solidifies the knowledge gained.

4. Regular 1:1s With Manager/ Mentors

One aspect of my current job that I enjoy the most are the 1:1s I have with my manager, mentors and mentees every week. These are some ideas to help you get started with 1:1s with your manager.

How did you feel about last week’s work? How was your weekend?
What did you most enjoy working on?
What exhausted you and is there some help that you need?
Feedback on team members/ projects
Any areas where you struggle with or need more information on
Suggestions for team improvements
Any feedback you have for your manager

An important thing to remember here is to be candid in your 1:1s which will make it easier for others to help or guide you in the right direction. If you are bored working on something, voice it!

5. Do Code Reviews

Find opportunities to do code reviews for your team members. If you are super new to the team, ask to be added to the code reviews of repositories that you will soon be working with. This is a great way to understand what kind of changes are pushed and how the technical material that you’re reading links to actual code. It also exposes the coding standards to adhere to within your team. If you are already familiar with the coding language used by your team, this is a great opportunity to warm up to new code while helping the team with the expertise that you are bringing in.

6. Mix It Up

Onboarding can get boring and overwhelming when you spend all your day reading up on documentation. Try to have a good mix of concrete coding tasks as well as something to read and absorb since you will have to look up all that information later anyway. Take regular breaks and make notes of terms that you want to look up later. Get a breath of information before deciding to dive deeper into a particular topic. If things get too difficult to comprehend, setup a 1:1 with a team member and ask for a quick walkthrough.

7. Get To Know The Team

Setting up 1:1s with all your team mates in the first few weeks of joining a new team will bring a sense of familiarity and comfort as a new Engineer. It’s also the time to discover the expertise and interests of people in the team and you may even find a great mentor.

Another aspect of knowing the team is to learn what you will actually be doing. Think of questions such as this.

Who are your customers?
What products do you build and own?
Where can you find a list of repositories owned by the team?
Any important code that you can take a look at?
How does the team contribute to the company’s growth?
How is your team adding value to other teams across the company?
Get a team member to subject expertise mapping from your manager to understand who would be the best person to help you with certain topics

8. Set Clear Objectives

Having a clear set of objectives makes sure that onboarding does not feel like a never ending process. Your team probably owns a lot of code and processes but it’s important to not get overwhelmed by it and instead focus on a small subset of core topics and tickets to work on. If the ramp up is draining or overwhelming, do reach out to your manager. When you work outside of office hours or withhold from surfacing the challenges that you are facing, you miss out on giving valuable feedback on the onboarding process. This could potentially help out future members joining the team. As you check off items on your ramp up, make sure to keep notes on what’s working and what isn’t, any questions that you have and links that you want to read up on later. This is a great way to build your knowledge base.

9. Look Outside Your Team

One of the first and foremost things that I did when I joined my current company Yelp was to scan for organizations or employee groups that I’d love to connect with outside of my team. For more than a year now, I have absolutely enjoyed participating in various events and programs for Women in Engineering. 1:1s are a great place to express your areas of interests and colleagues almost always remember to point you to some amazing groups that you can be a part of. These are also great opportunities to grow as an Engineer and a leader outside of regular coding tasks. Get to know about some interesting communication channels or emails you can subscribe to.

10. Wrap Up Onboarding The Right Way

Make sure to offer feedback on the onboarding process and mentorship that you have received so far. Highlight the work that interested you most and any challenges that you faced with existing processes, codebases or systems.
Find ways to improve existing code, documentation or processes however small it might be.
Talk to your manager about areas that you felt aligned better with your interests and see if there are existing projects that you can be a part of.
If you think you got the most out of your mentorship, feel free to space out your future sessions or be on a lookout for new mentors in your areas of interest.

A well laid out onboarding process is when you feel slightly uncomfortable and challenged in good ways but not overwhelmed to a point of exhaustion. That’s the sweet spot to find – not too easy, not impossible either like the Goldilocks Effect on Infants! Hope you enjoyed reading this post. If you have more ideas on how to improve onboarding, feel free to leave your comments on this post. Have a great week!

Better Programming

Essential Git Commands To Improve Project Workflow

Posted on May 17, 2021 by Swetha Kannan

1. Convert a repository into a Git repository

This will create a .git sub folder in your project directory.

$ cd <PROJECT_DIRECTORY>
$ git init

2. Clone a repo and pull the latest changes

$ git clone <GIT URL>
$ git pull

3. Create a new branch

$ git checkout -b <DESCRIPTIVE BRANCH NAME>

# View all branches
$ git branch

# Checkout an existing branch
$ git checkout <BRANCH_NAME>

4. Delete a branch

# Delete a local branch
$ git branch -d <BRANCH NAME>

# Delete a remote branch
$ git push origin --delete <BRANCH NAME TO DELETE>

5. Rename a branch

# From the branch to be renamed
$ git branch -m <NEW BRANCH NAME>

# From another branch
$ git branch -m <OLD BRANCH NAME> <NEW BRANCH NAME>

# Steps to rename a remote branch after following the above steps
$ git push origin -u <NEW BRANCH NAME>

# Delete old remote branch
$ git push origin --delete <OLD BRANCH NAME>

6. Pull the latest changes from the master branch

There are two ways to pull the latest changes from master into your branch. Tip: If you are working on a complex change, pull the changes from master often (once or twice everyday depending on how frequently new changes are shipped to master). This will save a lot of time not having to deal with merge conflicts.

Do a merge

Note: In this way, you can checkout master and pull all the latest changes into your branch but will have to solve multiple conflicts that arise from this scenario. Solve any conflicts that come up after executing the following commands.

$ git checkout <YOUR BRANCH>
$ git merge master

Do a rebase

$ git checkout <YOUR BRANCH>
$ git rebase master

Not sure whether to do a merge or rebase? Checkout this tutorial on merging vs rebasing.

7. Commit and push changes

# Check the changes you have made
$ git diff

# Stage all the changes
$ git add .

# Stage only a single file
$ git add <FILE NAME>

# Commit the changes
$ git commit -m "Commit message"

# Stage changes and commit one-liner
$ git commit -am "Commit message"

# Check if everything looks okay
$ git status 

# Push changes to remote
$ git push origin master

8. Save changes locally without committing

# Save uncommitted changes in a stack where you can get it back later
$ git stash 

# To retrieve the stash and apply it on top of your branch
$ git stash apply 

# Save stash with a name
$ git stash push -m "Name of the stash"

# To view list of all stashes
$ git stash list 

# Apply a stash with index n
$ git stash apply stash@{n}

# Apply a stash and pop it from stack
$ git stash pop stash@{n}

9. Pull the latest changes into a branch

This can result in change conflicts which have to be resolved.

$ git pull

10. Check commit history

This will display an entire scrollable commit history of your repository.

$ git log

11. Merge branch with master

# Squash and merge if there are too many noisy commits
$ git checkout master
$ git merge --squash <BRANCH TO MERGE>
$ git commit

# Regular merge
$ git checkout master
$ git merge <BRANCH TO MERGE>
$ git push origin master

12. Something’s on fire! Revert!

# Revert a single commit
$ git revert <COMMIT SHA>

# Revert Multiple commits
# Note: Works well only if there are no merge commits done
$ git revert <OLDEST COMMIT SHA>..<LATEST COMMIT SHA>

# Revert multiple commits and retain commit history
# Note: Works with merge commits
$ git checkout -f <TARGET COMMIT SHA> -- .
$ git commit -m 'revert to <TARGET COMMIT SHA>'
$ git diff HEAD # To check

These commands have helped me get 90% of my work done during all these years. Special scenarios have been pretty rare and they definitely warrant a deeper understanding before diving into them. Good luck!

Arrays and Strings, Data Structures/ Leetcode, Two Pointer Technique

[Problem Solving] Three Sum – Using Two Sum

Posted on May 12, 2021 by Swetha Kannan

To understand the following problem, we will be using what we learnt in the two sum problem. If you haven’t read it yet, do make sure to understand it before proceeding. Here’s the link.

Problem Statement

We have an array of integers called nums. We need to return three numbers let’s call it nums[i] = x, nums[j] = y and nums[k] = z that add up to 0. The indices of the returned numbers should all be unique ie., i != j != k

Assumptions

Solution set should not contain duplicate triplets
Empty array results in an empty set
If there are less than three numbers in the input array, return an empty set

Examples

Input: nums = [-1,0,1,2,-1,-4]

Output: [[-1,-1,2],[-1,0,1]]

Thought process

The brute force way to do this would be to loop using three for loops to search for three numbers in the array that sum up to 0. But this would have an O(n³) time complexity. So we need to be slightly better than that. The next best in time is an O(n²) solution. Remember that we should not return duplicate indices.

Let’s say nums[i] + nums[j] + nums[k] = 0

Then nums[i] + nums[j] = – nums[k]

This now resembles a two sum problem where we need to look for nums[i] and nums[j] such that they add up to a target = – nums[k]

To condense the problem, what we can do is loop through the array from k = 0 to k = n-1 and for every nums[k], find two numbers nums[i] and nums[j] that add up to a target = – nums[k].

How can we avoid adding duplicate triplets to the results list? A naive solution is to add all the duplicates to the result list and in the end return the set(result) to remove duplicates. This way we still do unnecessary work on finding the same two numbers that add up to a target value -nums[k].

To avoid executing a two sum loop on duplicates, let’s reuse our solution from the two sum problem where the input array was sorted and contained duplicates. We can sort the nums list and skip searching for two sum values whenever the current nums[k] = nums[k-1]. Sorting makes it easier to club duplicate values together. For ex:

Input: [-1,0,1,2,-1,-4]

Sorted List: [-4, -1, -1, 0 ,1,2]

One of the solutions here that adds up to 0 will be [-1, 0,1]. Now if we did not skip for target = nums[2] = -1, we will again get a solution set of [-1, 0, 1] in the result.

Complexity

O(N²) time complexity and O(1) extra space

Solution

def three_sum(nums):
    """
    :type nums: List[int]
    :rtype: List[List[int]]
    """
    # Edge case when the array is empty
    if not nums:
       return []
    
    n = len(nums)
    # Another edge case when the input array does not have 3 elements
    if len(nums) < 3:
       return []
        
    results = []

    # Sorting helps to club duplicate values together
    nums.sort()
        
    for k in range(0, n):
        # If the current num is equal to the previous value, then skip execution because we will be getting a duplicate solution set
        if k > 0 and nums[k] == nums[k-1]:
            continue
                
            target = -1 * nums[k]
            start = k + 1
            end = n - 1
            
            two_sum(nums, target, results, start, end)
    return results

# Same as the two sum solution that we coded in the previous article
def two_sum(nums, target, results, s, e): 

    while s < e:
            
        if nums[s] + nums[e] == target:
            results.append([nums[s], nums[e], -target])
            s += 1 # Advance the starting pointer to continue to look for other solutions

            # Skip duplicate solutions in two sum
            while s < e and nums[s] == nums[s-1]:
                s += 1
            
        elif nums[s] + nums[e] < target:
           s += 1
        else:
           e -= 1

Arrays and Strings, Data Structures/ Leetcode, Two Pointer Technique

[Problem Solving] Two Sum – Unsorted and Sorted Array, With and Without Duplicates

Posted on May 3, 2021May 3, 2021 by Swetha Kannan

Two Sum – Problem Statement

We have an array of integers called nums and a target value. We need to return the indices of two numbers, say x and y that add up to target.

Assumptions

Each given input will have exactly one solution
Same element cannot be used twice
Order of indices does not matter

Examples

Input: nums = [2, 7, 11, 15], target = 9

Output: [0, 1] where x = 2 and y = 7

Input: nums = [4, 4], target = 8

Output: [0, 1] where x = 4 and y = 4

Thought process

What’s the brute force way to check if two numbers add up to a target value in an array?

For each value nums[i] where i = 0 initially, we traverse the list from nums[i+1] and see which two indices add up to a target value. The complexity of this will be O(n²) since we loop through the remaining n-i elements for each i. So the first optimization here would be to try and see if we can reduce the traversal to just once.

For a value x, to check if there is another value y = target – x present in the array, we need a way to do a fast lookup without going through the whole array. A dictionary is the data structure that comes to mind in that case. How to design this data structure? What will our keys and values be?

To search for a value y = target – x, we have to store the values in nums as the keys in dictionary to search for. The value for each key can then be its index in the nums array so that we can directly return the indices as our result.

Complexity

O(N) time to traverse the array once, O(1) to look up values.

O(N) space for the look up dictionary

Solution

def two_sum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
        
    look_up = {}
        
    for i, x in enumerate(nums):
       y = target - x

       # Additional condition to make sure we don't return the same index twice
       if y in look_up and look_up[y] != i:
           return [i, look_up[y]]
           look_up[x] = i
            
     return []

Two Sum with Sorted Array – Problem Statement

This is a slight variation of the problem above where the input array nums is sorted in ascending order and we need to find two numbers that add up to a target value.

Assumptions

Each input will have exactly one solution
Same element cannot be used twice to add up to a target

Examples

Input: nums[2, 7, 11, 15], target = 9

Output: [0, 1]

Thought Process

Again, the brute force way of solving this problem would be to traverse the array using two for loops to find two numbers that add up to a target. This way we are not using the added benefit that the array is sorted in ascending order.

This means we can apply the two pointer technique here. This works great in many scenarios especially when the input array is sorted. We can use two pointers starting at two ends of the array. If the numbers they are pointing to do not add up to our target value, there are two decisions that can be made from then on. If the sum is greater than target, this means we have to move the end pointer to the left, otherwise move the start pointer to the right. See below.

Complexity

O(N) time since we traverse the array at most once in case the two elements are at the center of the array.

O(1) space since no additional space is used except for a couple of variables.

Solution

def two_sum(nums, target):
        """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
        
    s = 0
    e = len(nums) - 1
        
    while s < e:
            
        if nums[s] + nums[e] == target:
           return [s, e]
            
        elif nums[s] + nums[e] < target:
           s += 1
        else:
           e -= 1
                
     return []

Two Sum with Sorted Array and Duplicates

Let’s consider the exact same problem as above but now our result can have multiple solutions that add up to the same target value but it cannot contain duplicates.

Instead of returning the indices, let’s return the numbers to make it easier for understanding.

Assumptions

Each input will have multiple solutions
Same element cannot be used twice to add up to a target
The solution cannot contain duplicate sets

Examples

Input: nums = [2, 2, 4, 4, 5, 7, 7, 9, 11, 15], target = 9

Output: [[2, 7], [4, 5]]

Thought Process

In order to return multiple solutions, once we find nums[s] + nums[e] = target, we have to advance our start s pointer and continue to look for other solutions. We can collect the solutions inside a result list. If we don’t account for duplicate solutions, this is how our code will look. For the given input above, this code will return all solutions including the duplicates [[2, 7], [2, 7], [4, 5], [4, 5]].

def two_sum(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
        
    s = 0
    e = len(nums) - 1
    result = []
    
    while s < e:
            
        if nums[s] + nums[e] == target:
            result.append([nums[s], nums[e]])
            s += 1 # Advance the starting pointer to continue to look for other solutions
            
        elif nums[s] + nums[e] < target:
           s += 1
        else:
           e -= 1
                
    return result

In order to avoid duplicate solutions since our array is already sorted, we can compare the current value with the previous value. If they are the same, we are about to build the exact same solution that was found in the previous run, so we can skip it. For example, in [2, 2, 4, 4, 5, 7, 7, 9, 11, 15], when i = 1, nums[i] = 2 = nums[i-1] = 2, which will again yield [2, 7] as a duplicate solution, so let’s skip it and advance the starting s pointer. Then our solution can be slightly modified as shown below.

Complexity

O(N) time

O(1) space since we don’t usually include result as additional space

Solution

def two_sum(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
        
    s = 0
    e = len(nums) - 1
    result = []
    
    while s < e:
            
        if nums[s] + nums[e] == target:
            result.append([nums[s], nums[e]])
            s += 1 # Advance the starting pointer to continue to look for other solutions

            # Skip duplicate solutions
            while s < e and nums[s] == nums[s-1]:
                s += 1
            
        elif nums[s] + nums[e] < target:
           s += 1
        else:
           e -= 1
                
    return result

Data Structures/ Leetcode, Trees

Part 1: Tree Concepts – Four Different Tree Traversals

Posted on July 20, 2020July 20, 2020 by Swetha Kannan

Pre-order: root, left, right – F, B, A, D, C, E, G, I, H

Recursive Implementation:

The recursive implementation is quite simple and intuitive. We process the root and then its left and right children until there are no nodes left, recursively.

def preorderTraversal(self, root: TreeNode) -> List[int]:
    
    nodes = []

    def preorder(root):
        if root:
            nodes.append(root.val)
            preorder(root.left)
            preorder(root.right)

    preorder(root)
    return nodes

Iterative Implementation:

What happens beneath recursion is the use of stack space to store nodes. In the iterative implementation, we can explicitly mimic the use of stack. Note that we need to process the root, the left child and then the right child. In stacks, the rule is Last In First Out (LIFO) or First In Last Out (FILO). This means, to process the left node before the right node in pre-order, we have to add the right node to the stack before adding the left node. See the code below.

def preorderTraversal(self, root: TreeNode) -> List[int]:
    if not root:
        return []

    nodes, stack = [], [root]

    while stack:
        curr = stack.pop()
        nodes.append(curr.val)

        if curr.right:
            stack.append(curr.right)
        if curr.left:
            stack.append(curr.left)

    return nodes

In-order: left, root, right – A, B, C, D, E, F, G, H, I

Recursive Implementation:

This is very similar to pre-order traversal except that we process the left node before the root and then the right child.

def inorderTraversal(self, root: TreeNode) -> List[int]:

    nodes = []

    def inorder(root):
        if root:
            inorder(root.left)
            nodes.append(root.val)
            inorder(root.right)

    inorder(root)
    return nodes

Iterative Implementation:

The iterative implementation of in-order traversal is a little tricky. In in-order, we have to process the left node first and then the root followed by the right child. For this, we have to get to the left most node in the tree first which is the leftmost leaf node if it is present.

Do this by using a pointer called curr which points to the root at first.
Traverse the left subtree while adding nodes to the stack, setting curr = curr.left until there are no more nodes left which means until curr is NULL. This will capture the entire left subtree of a node.
Once curr is NULL, start traversing the right subtree. Before traversing the right subtree, pop the stack and add the top most element to the nodes list.
To traverse the right subtree, set curr = curr.right

Basically we keep going as left as possible from a given node until there are no more nodes left. We then pop the stack, add to the results and start traversing the right subtree of the node that we just processed. We keep repeating this process as long as curr is not NULL or the stack is not empty. I recommend that you hand simulate a simple example to understand how the algorithm works.

def inorderTraversal(self, root: TreeNode) -> List[int]:

    if not root:
        return []

    nodes, stack = [], []
    curr = root

    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        nodes.append(curr.val)
        curr = curr.right
    return nodes

Post-order: left, right, root – A, C, E, D, B, H, I, G, F

Recursive Implementation:

In post order, we process the left and right child before the root node, recursively.

def postorderTraversal(self, root: TreeNode) -> List[int]:

    nodes = []

    def postorder(root):
        if root:
            postorder(root.left)
            postorder(root.right)
            nodes.append(root.val)

    postorder(root)
    return nodes

Iterative Implementation:

In the post-order traversal implementation, we will take a simple approach where our stack contains the reverse of post order sequence. Once we are done processing, we will return the results by reversing the stack.

Note that in post-order, we need to return left, right and then root. The reverse of this is root, right and then left. This is the order in which we will be processing the nodes.

To begin with, add the root to the stack.
Pop the stack and add the top most element to nodes list.
Add the left child of this node and then the right child to the stack. This will make sure that we pop and process the right child first and then the left child.
Notice that the order of processing/ popping is root, right and then the left child which is the reverse of post-order traversal.
Upon processing the whole tree, return the reverse of nodes list.

def postorderTraversal(self, root: TreeNode) -> List[int]:

    if not root:
        return []

    stack = [root]
    nodes = []

    while stack:
        node = stack.pop()
        nodes.append(node.val)

        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)

    return nodes[::-1]

Level-order: F, B, G, A, D, I, C, E, H

Level-order traversal is also known as Breadth First Search of a tree. For this we can use a queue usually but the code below uses a simple Python List to mimic the same functionality. Here level indicates the height of the tree. We go from root to the leaves level by level.

Add root to a list/ queue called level.
Add all the nodes at the top most level to the nodes list.
Create a temp list and add the left and right child of each node in this level from left to right.
Set level to this temp list to process the next level.
Continue processing each level as long as there are nodes left.

Implementation:

def levelOrder(self, root: TreeNode) -> List[List[int]]:

        if not root:
            return []

        level = [root]
        result = []

        while level:
            result.append([node.val for node in level])

            temp = []
            for node in level:
                if node.left:
                    temp.append(node.left)
                if node.right:
                    temp.append(node.right)

            level = [node for node in temp]

        return result

Time Complexity: The processing time for different traversals is O(N) where N is the number of nodes in the tree and we have to process all N nodes.

Space Complexity: O(N) for the use of stack/ queue space where N is the number of nodes in the tree.

Hope you enjoyed learning the implementations for different types of tree traversals.

coding interview preparation, Professional Improvement

The different types of interviewers whom you may have to work with.

Posted on July 13, 2020July 13, 2020 by Swetha Kannan

The future co-worker

This is an interviewer who can put themselves in your shoes the minute they walk-in. They understand what an important day this is for you and the nervousness you carry. They know that you have done incredible amounts of hard work and won’t try to belittle you in any way. They are here because they want to solve the problem with you. As you go through your interview, whether you aced it or not, you will come out of it feeling like you had a good conversation where you learnt something. This is the kind of interviewer who is great to work with during and after the interview. Although you might think that you are the only one being evaluated, it is a great opportunity for you to evaluate whether you can see yourself working with this person in the future.

Now that we’ve gotten the best package, let’s look at some of the not-so-good scenarios that can happen.

The one who wouldn’t look at you

Sometimes interviewers have been told to type every little conversation that goes on in the room. Although there are some great note-takers who aren’t constantly distracted, most of them in this category don’t care to look at you much. The typing is distracting, there is no eye contact, mostly they aren’t listening nor trying to have an organic conversation with you.

If you had to interview with someone like that, don’t be afraid to take up space in the room. If you start feeling stressed or the interview feels too cold, politely let them know that the typing is a little distracting to your thought process. You can also pause a few times and wait to get their attention before proceeding so that they don’t miss out on the key points that you are mentioning during your interview. It is important for you to stay assured that you are not responsible for their distracted state no matter how boring the question is, so go about it confidently because this day is more important to you than it is for them.

The one who wants you to be a mind-reader

Some interviewers do not let you solve a problem using your own methods. This could be because they aren’t aware of more than one way of solving a problem or they aren’t able to understand how you’re trying to solve it.

Let us always assume the latter because if you are standing there judging the interviewer for not knowing multiple ways of solving a problem, it won’t benefit you in any way. This can create a communication barrier between the both of you. This is when you can take a step back and try to best explain your algorithm with a few examples. Place emphasis on why your approach might work. Pay attention when the interviewer counters it. In some cases, they might expect you to go for the most efficient solution right away. You have probably only come up with a brute force one and can’t really think of how it can be improved. When you feel stuck in this state, explain that you haven’t quite gotten there but you are hoping to get started with a basic solution and iteratively improve upon it once you see the caveats. Most interviewers will be fine with this approach.

The one with the unnecessary arrogance

An interviewer’s job is to make a case for someone who exhibits potential to be a good developer and fit for the company and its culture. Unfortunately, some of them try to check if you are as smart as them, or pick a super difficult problem. This might mostly be a junior developer whose idea of Software Development hasn’t grown beyond solving difficult Leetcode questions yet.

Such an interview scenario can be extremely stressful and the worst outcome is you experiencing a mental block. Try to pick a few easy example cases and manually solve the problem. See if you can turn that into a brute force algorithm that can work for the most common cases. You can then discuss edge cases and improve your algorithm. At any point, an interviewer should not try to trick you or turn it into a stress interview. If that starts to happen, take a few deep breaths and start over. Remember that it’s okay to sometimes not solve it at all. There are thousands of different problems out there and it’s completely okay to be clueless when an overly difficult problem gets presented to you. It was just one of those unlucky days.

The silence of the lambs

This type of interviewer can make you feel nervous throughout the interview by being silent. You may feel stuck at various points on whether your approach is right, waiting for cues to proceed or step back. A good interviewer will make sure to guide you and let you know when you are going in the wrong direction, but sometimes they might not. If this happens, calm yourselves and give it your best shot. Start explaining how you plan on solving the problem and once you are done, stop and explicitly ask whether you can go ahead and code it up. Get to this point as quickly as possible so that you have enough time to brainstorm an alternate approach if your first one doesn’t work out. Be aware of time and allocate a comfortable chunk of time to code the solution.

Hope this post helped you to mentally prepare yourselves to interview with any type of interviewer whom you might encounter. Good luck with your upcoming interviews 🙂