DEV Community: Mridu Bhatnagar

Course Launch 🚀 - Sets and Frozen Sets in Python

Mridu Bhatnagar — Wed, 26 May 2021 18:58:57 +0000

Are you a newbie and is your next Python learning goal is Sets and Frozen Sets?

Preparing for an upcoming interview, want to brush up your knowledge on Sets and Frozen Sets while solving problem alongside?

I recently built and published a self-paced Python course on Linkedin Learning on Sets and Frozen Sets.

Course Features 👇:

📌 The full course is FREE for a month from the date of your sign-up.
📌 3 bite-sized lessons are available for preview (no sign-up needed).
📌 You can download the lesson on Linkedin Learning iOS and android applications and can learn offline.
📌 Hands-on examples, MCQs, challenges
📌 The course is a collection of bite-sized videos.
📌 Course duration - 1 hour 37 min, lesson duration varies between 40 sec to 6 minutes maximum.

NOTE - If your employer or your university has given you access to the Linkedin Learning library. You would be able to access the full course.

Take the course and spread the word among your peers.
If you take the course do let me know your feedback.

Course Link:

https://www.linkedin.com/learning/python-data-structures-sets-and-frozen-sets

Build a Vocabulary Bot for WhatsApp using Twilio and Python

Mridu Bhatnagar — Thu, 02 Jul 2020 13:17:10 +0000

My mother teaches English to visually impaired students. Due to the current situation with the Coronavirus, in-person classes had to be suspended, and now she is teaching through phone conference calls, with all learning material being exchanged on WhatsApp. I saw an opportunity to solve a problem here, so I decided to build a Vocabulary chatbot to assist her in her teaching.

This tutorial will show you how to create a WhatsApp chatbot that can help you in improving your vocabulary using the Twilio API for WhatsApp, Python and Flask. Below, you can see the conversation I had with the bot.

https://www.twilio.com/blog/build-vocabulary-bot-whatsapp-python-twilio

A long pending to-do task - The Portfolio Website!!!

Mridu Bhatnagar — Mon, 15 Jun 2020 15:19:20 +0000

Since a long time I was contemplating on building a portfolio website. But, got stuck with frameworks, languages, tools, static site generators, content management system the list goes on and on... and the downward spiral began.

Procastination, indecisiveness, indecisiveness and the time passed by. What started as a question in 2018, remained a task in my head ever since. Finally, 2020. Check. Task done.

2 years to decide. 2 days to build. Sounds funny, right. This is a classic case of decision paralysis.

In all these 2 years. Time and again the thought of building the website used to strike my mind. I used to check out couple of options available, reach out to more people.
End result - confused.

Non-technical things I learned in the process:

The more people you ask for an advice. The more confusing it gets. Each of us have our own reasons of preferring something over the other.
My main purpose of building this was to showcase information that my resume does not effectively convey and is important. Spending days and nights on deciding the framework was pointless.
Blogging on the same platform was never the idea. Half baked information and using the shiny new framework after thorough research. Would deviate me from the purpose of building the website.
This is just a portfolio website. Thinking about often trending questions, and most talked about topic amongst developers "Scaling". There seems to be no such scenario where the traffic will spike.
Uneccessary load on mind is not worth it. Time is limited.
Person X used Gatsby, Person Y used Jekyll, Person Z used Hugo. Don't be tempted by others choices. Everyone has a different purpose to built. Mine was to put forth information, without missing out on anything.
Animation - Might give a Wow feeling, but when wrongly done results in worst of its kind user experinece.
Don't get lost amongst all the choices that are available. With small tasks like this one not directly affecting anyone. Just get the job done. Should be the first priority.

Technical things I learned while building it from scratch:

Good way to get a hang of fundamentals. Good old HTML/CSS/JS.
Decision making process. From design, frontend, backend, deployment. All throughout you'll have to make decisions at every step.
Deployment.
Integrating GraphQL API.

Website - https://www.mridubhatnagar.in/

Ps: The site is not mobile responsive at the moment.
To get the results open it on laptop, chrome browser.

Mridu Bhatnagar

@mridu__

A long-pending task completed. 🥳
I will be deploying it soon. 🙂

16:12 PM - 03 Jun 2020

1 41

Day-20 Guess Number Higher or Lower 👩‍💻

Mridu Bhatnagar — Sun, 03 May 2020 18:59:53 +0000

For the last 19 days, I am making sure to solve at least a problem a day. I got stuck at optimizing a problem named Rotate Array yesterday. And, as a result, couldn't solve a problem, could not write. I am still stuck at the same problem. Meanwhile, I solved a new one.

Background

This problem statement is a part of LeetCode's learn card titled Binary Search. Under the sub-heading Binary Search Template-I.

Problem Statement

We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I'll tell you whether the number is higher or lower.
You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):

-1 : My number is lower
 1 : My number is higher
 0 : Congrats! You got it!

Example

Input: n = 10, pick = 6
Output: 6

Solution Approach

start = 1, end = n+1. (See the problem statement. Numbers from 1 to n. Hence, make sure both are inclusive).
calculate mid. mid = int((start+end)/2)
Now pass mid as parameter to the guess API.
Divide the list based on the value returned by API.

# The guess API is already defined for you.
# @param num, your guess
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num: int) -> int:

class Solution:
    def guessNumber(self, n: int) -> int:
        start = 1
        end = n+1
        while start < end:
            mid = int((start+end)/2)
            if guess(mid) == -1:
                end = mid
            elif guess(mid) == 1:
                start = mid + 1
            elif guess(mid) == 0:
                return mid
        return -1

Learnings

The time complexity of the above solution is - O(logn).
When in the problem statement it is already mentioned sorted array think binary search.
Time complexity of Binary Search - O(logn). Time complexity of Linear Search - O(n). Binary search is more efficient.

Day-19 Third Maximum Number

Mridu Bhatnagar — Fri, 01 May 2020 06:44:22 +0000

Background

This problem statement is a part of LeetCode's learn card Introduction to Data Structures Fun with Arrays - 101. Under the sub-heading conclusion.

Problem Statement

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example 1

Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.

Example 2

Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

Example 3

Input: [2, 2, 3, 1]

Output: 1

Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

Solution Approach 1

Intuitively initial thought that came was to keep calculating max from the array. But, this would also mean every time the maximum element is found. Then we would have to remove the same element from the array. Then again calculate max from the remaining elements in the array.

Problems with solution approach 1

Built-in remove cannot be used for deleting an element because there can be duplicate elements present in the list. Remove will only delete the first occurrence of the element.

Solution Approach 2

Create a variable maximum and store some arbitrary value in it.
If the length of the list is greater than 3. Then iterate over the list. If the value of the element is greater than the value of the maximum variable. Store the value of the element in maximum.
Store some arbitrary value in variable second_max. Iterate over the list. If element value is not equal to the value of the maximum. Then again compare all element values with the value of second_max. If the value of element is greater than the stored value in second_max. Replace.
The result would be the third max element.
Else if the length of the list is not greater than 3. Then return a max of the array.

import sys
class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        maximum = -sys.maxsize
        if len(nums) >= 3:
            for element in nums:
                if element > maximum:
                    maximum = element
            second_max = -sys.maxsize
            for element in nums:
                if (element != maximum) and (second_max < element):
                    second_max = element
            third_max = -sys.maxsize
            for element in nums:
                if (element != maximum) and (element != second_max) and (third_max < element):
                    third_max = element
            if (maximum != -sys.maxsize) and (second_max != -sys.maxsize) and (third_max != -sys.maxsize):
                result = third_max
            else:
                result = max(nums)
        else:
            result = max(nums)

        return result

Learnings

Time complexity of the above solution is O(n).
The initial value of the maximum, second_max, third_max has to be a number that doesn't exist in the original list. Otherwise, it would lead to unexpected output.

Day-18 Merge Sorted Array

Mridu Bhatnagar — Thu, 30 Apr 2020 18:18:36 +0000

Background

This problem statement is a part of the Introduction to Data Structures Fun with arrays-101 on leetcode. Under the sub-heading Inserting the Items into an Array.

Problem Statement

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

The number of elements initialized in nums1 and nums2 are m and n respectively.
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]

Solution approach 1

Case 1: nums1[i] < nums2[j]

Compare one element each from both the arrays. If element in 1st array is less then the element in 2nd array. Insert the element to array 3. Increment the counter i of array 1 by 1.

Case 2: nums2[j] < nums1[i]

If element in array 2 is less than element in array 1. Then insert the element in array 3. Increment the counter j of array 2 to the next element.

Case 3: nums1[i] == nums2[j]

Insert nums2[j] in array 3. Increment both counter i and j by 1.

As a result, array 3 would be the final merge sorted array.

Things to observe

We are using an extra array. Array 3, that means extra space. As asked in the question. The solution needs to be an in-place solution.
Notice that the skeleton code below mentions no return type. Hence, even though nums3 is the merged sorted array. It cannot be returned.

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        i = 0
        j = 0 
        nums3 = []
        while i < m and j < n:
            if nums1[i] < nums2[j]:
                nums3.append(nums1[i])
                i += 1
            elif nums1[i] > nums2[j]:
                nums3.append(nums2[j])
                j += 1
            elif nums1[i] == nums2[j]:
                nums3.append(nums1[i])
                i += 1
                nums3.append(nums2[j])
                j += 1

        while i < m:
            nums3.append(nums1[i])
            i += 1

        while j < n:
            nums3.append(nums2[j])
            j += 1

Solution approach 2

Keep the merging logic same.
Instead of returning nums3. We can do item assignment. And, copy all the elements of nums3 to nums1.

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        i = 0
        j = 0 
        nums3 = []
        while i < m and j < n:
            if nums1[i] < nums2[j]:
                nums3.append(nums1[i])
                i += 1
            elif nums1[i] > nums2[j]:
                nums3.append(nums2[j])
                j += 1
            elif nums1[i] == nums2[j]:
                nums3.append(nums1[i])
                i += 1
                nums3.append(nums2[j])
                j += 1

        while i < m:
            nums3.append(nums1[i])
            i += 1

        while j < n:
            nums3.append(nums2[j])
            j += 1


        for i in range(0, len(nums1)):
            nums1[i] = nums3[i]

Learnings

We have been able to merge the two sorted array.
Time complexity - O(n)
Time complexity of append - O(1)
As all values of nums1 itself are changed. So, there is no need to return anything. Hence, the solution is accepted.
List.insert might not be the way out. The reason being it is a built-in function. Secondly, insertion in at defined index adds on to the time complexity.

Things to figure out

The solution needs to be an in-place solution. That is no extra memory needs to be used. How to solve it without using any extra space?
Will optimizing on space complexity lead to increased time complexity?

Day-17 Binary Search

Mridu Bhatnagar — Wed, 29 Apr 2020 19:15:26 +0000

Background

This problem statement is a part of LeetCode's learn card binary search. Under the sub-heading background.

Problem Statement

Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise, return -1.

Example 1

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Note:

You may assume that all elements in nums are unique n will be in the range [1, 10000].
The value of each element in nums will be in the range [-9999, 9999].

Solution Approach

Keep dividing the array into halves.
left = 0, right = len(array)-1. Mid would be left+right/2.
Then determine where the element to be searched lies.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)-1
        while left <= right:
            mid = abs(int((left+right)/2))
            if target < nums[mid]:
                right = mid - 1
            elif target > nums[mid]:
                left = mid + 1
            elif nums[mid] == target:
                 return mid
        return -1

Learnings

Time complexity is O(logn).
Take care of the edge conditions.

Day-16 Reverse words in a string III

Mridu Bhatnagar — Tue, 28 Apr 2020 19:43:44 +0000

Background

This problem statement is a part of LeetCode's learn card titled Arrays and Strings. Under the sub-heading conclusion.

Problem Statement

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1

Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

Note: In the string, each word is separated by single space and there will not be any extra space in the string.

Solution Approach 1

Convert the entire string into a list. Split the string based on whitespaces.
Iterate over the list. Reverse each word. For reverse using slicing.
Reconstruct the entire string. This time every word would be reversed.

class Solution:
    def reverseWords(self, s: str) -> str:
        s = s.split()
        s1 = ''
        for x in range(0, len(s)):
            if x == len(s) - 1:
                s1 += s[x][::-1]
            else:
                s1 += s[x][::-1] + ' '
        return s1

Things to notice

We are already using a for loop to iterate over list. Time complexity - O(n).
We are reversing the string using slicing.
Extra space is used here as well. As a new string is being constructed instead of making changes in-place.

Solution approach 2

This is probably the longer route to reach the solution.

Split the string into words. Split using whitespaces.
Iterate over the list. Convert each word into letters.
Then do a reverse based on two-pointer approach. Once, the reverse is done to join those letters to form string again.
Then again convert the list of reversed words to form the output string.

class Solution:
    def reverseWords(self, s: str) -> str:
        L = []
        string = s.split()
        for word in string:
            y = list(word)
            start = 0
            end = len(y) - 1
            while start < end:
                temp = y[start]
                y[start] = y[end]
                y[end] = temp
                start += 1
                end -= 1
            new_string = ''.join(y)
            L.append(new_string)
        return ' '.join(L)

Things to notice

We are using extra space. As we are creating a new list in the process.
There is a while loop inside of a for loop. This adds on to the time complexity.
That whole reverse logic was written to avoid using list.reverse().

Some follow up questions

What is the time complexity of reversing a string using slicing s[::-1]? (see solution 1)
As we are using slicing inside a for loop. Will the overall time-complexity of code be O(nk)? (refer to solution 1)
In solution approach 2. We are using a while loop inside of a for loop. This would lead to time complexity O(nk) or O(n^2)?

Day-15 Reverse words in a string

Mridu Bhatnagar — Mon, 27 Apr 2020 10:24:02 +0000

Background

This problem statement is a part of LeetCode's card Arrays and Strings. Under the sub-heading Conclusion.

Problem Statement

Given an input string, reverse the string word by word.

Example 1

Input: "the sky is blue"
Output: "blue is sky the"

Example 2

Input: "  hello world!  "
Output: "world! hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3

Input: "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Note:

A word is defined as a sequence of non-space characters.
Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
You need to reduce multiple spaces between two words to a single space in the reversed string.

Solution Approach 1

Replace double space with single space.
Remove leading and trailing spaces.
Reverse.

class Solution:
    def reverseWords(self, s: str) -> str:
        s.replace("  ", " ").rstrip().lstrip()
        string = s.split()
        string.reverse()
        return ' '.join(string)

Learnings and takeaways from the above snippet

We have hardcoded 2 spaces. Hardcoding in programming should never be done.
If count of consecutive spaces is increased. The code would fail.
Using built-in method reverse() could appear as a shortcut.

Updated solution overcoming the shortcomings listed above.

s.lstrip().rstrip().split(). Takes care of multiple spaces, leading spaces, trailing space.
replace reverse() with implementation of reverse.

class Solution:
    def reverseWords(self, s: str) -> str:
        string = s.lstrip().rstrip().split()
        start = 0
        end = len(string) - 1
        while start < end:
            temp = string[start]
            string[start] = string[end]
            string[end] = temp
            start += 1
            end -= 1

        return ' '.join(string)

Ps:
Last section of the post. Which starts from learnings from the shortcomings of the above snippet is updated after seeing the first comment.

Day-15 Array Partition I

Mridu Bhatnagar — Mon, 27 Apr 2020 05:37:58 +0000

Background

This problem statement was a part of LeetCode's learn card: Array and Strings. Under the sub-heading Two pointer technique.

Problem Statement

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Example 1

Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

Note:

n is a positive integer, which is in the range of [1, 10000].
All the integers in the array will be in the range of [-10000, 10000].

Solution Approach 1

Pick some random examples. And, try calculating the sum of pairs manually for different combination of integers to see if there is some pattern.
Based on step 1. One conclusion that can be drawn is pairing consecutive small numbers together, followed by pairing large numbers. Leads to maximum sum.
Now, 2 achieve step 2. We can sort the given array.
Once the array is sorted. We can have 2 variables. One variable points to the current element. Another element points to the next element.
The current element and the next element form a pair.
Size of array is 2n. Number of pairs are n is mentioned in the problem statement. Based on this we can break the loop.

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        current=0
        next_element = current+1
        total = 0
        counter = 0     
        nums.sort()
        while current < next_element:
            total += min(nums[current], nums[next_element])
            current  = next_element + 1
            next_element = current+ 1
            counter += 1
            if counter == int(len(nums)/2):
                break
        return total

Learnings and obervation from solution approach 1

Time complexity of list.sort() is O(nlogn). Then we are iterating over the list. And calling built-in method min. Min has its own complexity. This in turn would increase the overall time complexity.
We are already sorting the array. And then forming pairs. So, always the minimum element would be the current element. Hence, no need to again call built-in min method to find the minimum of the two numbers.

Updated code based on takeaways from solution approach 1

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        current=0
        next_element = current+1
        total = 0
        counter = 0
        nums.sort()
        while current < next_element:
            total += nums[current]
            current  = next_element + 1
            next_element = current+ 1
            counter += 1
            if counter == int(len(nums)/2):
                break
        return total

In the above solution, we are breaking the loop when count of pairs is equal to half the length of the array. Another approach could be to scrap this whole part off. Instead, put this condition. The index of current element should always be less the length of array.

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        current=0
        next_element = current+1
        total = 0
        nums.sort()
        while current < next_element and current < len(nums)-1:
            total += nums[current]
            current  = next_element + 1
            next_element = current+ 1
        return total

Learnings

Time complexity - O(nlogn).
Got rid of unnecessary min() built-in function.
Two pointer technique.
List.sort() method is an in-place sort. Using sorted() for sorting would have returned a new list. That, however, was not needed.

Day-14 Reverse String

Mridu Bhatnagar — Sun, 26 Apr 2020 12:00:35 +0000

Background

This problem statement is a part of Leetcode's learning card Array and Strings. Under the sub-heading two pointer technique.

Problem Statement

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

You may assume all the characters consist of printable ASCII characters.

Example 1

Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2

Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

Solution Approach 1

Use python built-in methods. There are two ways of doing the same. Suppose s in the initial list. Then s.reverse() could be done or s[::-1] can be done.

Had reaching the solution by using the built-in methods been the aim. Probably the whole exercise would not have been worth the effort.

Solution Approach 2

Iterate over the list.
Swap the first element with the last element.
The list would be completely reversed when we are at the mid of the list.
When the index of the current element is equal to mid of the list. Break.

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        for x in range(0, len(s)):
            if x == int(len(s)/2):
                break
            else:
                temp = s[x]
                s[x] = s[len(s)-x-1]
                s[len(s)-x-1]=temp

Learnings

Time complexity - O(n), Space complexity - O(1).

A more elegant approach

Solution approach 3

Keep two variables. One at the starting of the list at index 0. Another at the end of the list. Index len(L)-1.
Keep swapping the elements until both the variables reach the mid of the list.

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        start = 0
        end = len(s) - 1
        while start < end:
            temp = s[start]
            s[start] = s[end]
            s[end] = temp
            start += 1
            end -= 1

Learnings

The solution is still time complexity O(n) and space complexity O(1).
Two pointer technique. Though in python there is no concept of pointer as such.
Built-in reverse method is also implemented the same way.

Day-13 Find Pivot Index

Mridu Bhatnagar — Fri, 24 Apr 2020 19:42:23 +0000

Background

This problem statement is a part of Leetcode's learning card Arrays and Strings. Under the sub-heading Introduction to Array.

Problem Statement

Input: 
nums = [1, 7, 3, 6, 5, 6]
Output: 3
Explanation: 
The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3.
Also, 3 is the first index where this occurs.

Input: 
nums = [1, 2, 3]
Output: -1
Explanation: 
There is no index that satisfies the conditions in the problem statement.

Note:

The length of nums will be in the range [0, 10000].
Each element nums[i] will be an integer in the range [-1000, 1000].

Solution Approach 1

Reading the problem statement intuitive method that struck was to slice the list. And keep calculating the sum of those sliced sub-lists. When sum of the elements to the left-hand side of the element and right-hand side of the element matches. Return the index.

Problems with Approach 1

This would result in an unoptimized solution. Slicing has its own time complexity depending on the length of the sublist. Overall complexity would have become quadratic.

Solution Approach 2

Take a pen and paper and mathematically try observing the pattern.
Calculate the total of all elements present in the list.
Then compute the sum of all elements to the left-hand side of the current index. Store this sum for each element in a new list.
Sum of right-hand side would be. right_hand_side = Total - value of element at current index - sum of left hand side elements at same index.

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        total = 0
        result = -1
        for x in range(0, len(nums)):
            total += nums[x]

        element_sum = 0
        left_side_sum = [0] # Sum of elements to the left of value
        for i in range(1, len(nums)):
            element_sum += nums[i-1]
            left_side_sum.append(element_sum)

        for index in range(0, len(nums)):
            right_side_sum = total - nums[index] - left_side_sum[index]
            if right_side_sum == left_side_sum[index]:
                result = index
                break

        return result

Learnings and Takeaways

Time complexity - O(n), Space complexity - O(n)
Time complexity of append - O(1)
The first element of left_side_sum is initialized to 0 because there is no value to the left-hand side of leftmost element present in the list.