Forem: Manish Reddy Nandineni

Day #8: Number Of Unival Trees Using Python

Manish Reddy Nandineni — Fri, 19 Jun 2020 16:58:29 +0000

Hello everyone.
Today is the Day 8 of the #100DaysOfCodeChallenge.
Received a problem previously asked by Google with an easy tag to it.

The Question On Day #8:

A unival tree (which stands for "universal value") is a tree where all nodes under it have the same value.

Given the root to a binary tree, count the number of unival subtrees.

For example, the following tree has 5 unival subtrees:

Approach

Before moving on to the main logic, let's discuss about the Brute Force way to solve this:
- Starting from the root, we check if the immediate children have the same value as the root node, and then the children of the immediate nodes and so on.
- We repeat this process for every subtree ending up in time taking process.

Optimal Way

The optimal way to solve this problem is by using the bottom-up approach. We first start from the leaf nodes, and move to the upper levels and use the unary value of the child subtree to decide if the main tree is a unary tree or not.

Python Code

Output

No. of unival subtrees= 5

Visualiser

To understand the recursion behind this code, please click here

Feel free to reach out for any query clearance.

Thanks and cheers:)

Day #7: Number of possible decodable messages

Manish Reddy Nandineni — Wed, 17 Jun 2020 15:31:23 +0000

Hello everyone.
Today is the Day 7 of the #100DaysOfCodeChallenge.
And it's a week!!!!
Received a problem previously asked by Facebook with a hard tag to it.

The Question On Day #6:

Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded.

For example, the message '111' would give 3, since it could be decoded as 'aaa', 'ka', and 'ak'.

You can assume that the messages are decodable. For example, '001' is not allowed.

Algorithm

The algorithm is similar to the concept behind fibonacci series. For every increase in the value of n is fibonacci we added it to the n-1 sum.
Similarly, for every increase in the length of the message, we add a particular value to the number of possible ways, based on certain conditions.
Points to check:
- a 1-digit number is considered a message only if it is greater than 0, because a is represented by 1 according to the question.
- a 2-digit number is considered a message only if it has 2 in the ten's place and digit<7 in the one's place or 1 in ten's place and any digit in one's place.

Python Code

Output
Number Of Ways: 3

Visualiser

You can look into the visualiser to understand the BTS of the logic here.

Feel free to reach out for any query clearance.

Thanks and cheers:)

Day #6: XOR Doubly Linked List

Manish Reddy Nandineni — Tue, 16 Jun 2020 12:49:39 +0000

Hello.
Today is the Day 6 of the #100DaysOfCodeChallenge. Received a problem previously asked by Google with a hard tag to it.

The Question On Day #6:

An XOR linked list is a more memory efficient doubly linked list. Instead of each node holding next and prev fields, it holds a field named both, which is an XOR of the next node and the previous node. Implement an XOR linked list; it has an add(element) which adds the element to the end, and a get(index) which returns the node at index.

Doing it on C++, since pointer implementation on Python is messy and not efficient.

Algorithm

The main logic behind the question is to understand the properties of XOR.
Refer wiki.

C++ Code

Output

Nodes: 

40 30 20 10

Explanation

Not getting much into the details of the logic, the wikipedia reference speaks it all.

You can look into the visualiser to understand the BTS of the logic here.

Feel free to reach out for any query clearance.

Thanks and cheers:)

Day #5: Functional Programming with Python.

Manish Reddy Nandineni — Mon, 15 Jun 2020 14:16:53 +0000

Hey. Hope you have been enjoying the series so far.
Today is the Day 5 of the #100DaysOfCodeChallenge. Received a problem previously asked by Jane Street (refer the hyperlink for the company details) with a medium tag to it. This question is a true puzzle and can be solved in a minute if your functional programming understanding is strong.

You may get confused with the question, just like the way I did. I will try my best in putting the solution in the simplest way possible. You can always reach out to me if you need help.

The Question On Day #5:

cons(a, b) constructs a pair, and car(pair) and cdr(pair) returns the first and last element of that pair. For example, car(cons(3, 4)) returns 3, and cdr(cons(3, 4)) returns 4.

Given this implementation of cons:

def cons(a, b):
    def pair(f):
        return f(a, b)
    return pair

Implement car and cdr.

Explanation

The question is a bit confusing but let us try to understand it clearly.

cons is a function which takes two inputs (consider integers). It returns a value which is an function defined inside itself, i.e. pair.
pair is a function which takes a function f as input and returns the return value of its input function, i.e. the return value of the function f is returned by pair.
Now f is a function which will return a value.
f is the key to all our solution.

Algorithm

The end value obtained on calling the function cons is a function pointer pointing to the pair function.
The required implementation goes as follows:

Python Code

Output
3
4

Explanation

When car(cons(3,4)) is called,

cons(3,4) is invoked in the first place.
cons returns the function pair function.
The parameter passed to the car function is the pair function.
car function returns the value returned by calling the pair function.
pair function takes a function as input, so we pass the left function to it.
pair function returns the value obtained by passing a, b to a a function f. So, our left is the function f, which takes a, b as input and returns a as output to the pair function.
Now the same a is returned by pair function to the car function, which will again return the same value of a.
Now a is returned at the end and printed.
Same goes with the function cdr.

The Python visualiser is very much needed to understand this logic more clearly, please refer it here.

I hope you were able to understand this problem.
Feel free to reach out for any query clearance.

Thanks and cheers:)

Day #4: Finding the smallest positive missing integer from an unordered list using Python.

Manish Reddy Nandineni — Sun, 14 Jun 2020 13:50:07 +0000

Hey, today is the Day 4 of the #100DaysOfCodeChallenge. Received a problem previously asked by Stripe with a hard tag to it.

The Question On Day #4:

Given an array of integers, find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well.

For example, the input [3, 4, -1, 1] should give 2. The input [1, 2, 0] should give 3.

Algorithm

Input the given array into a list
Filter out all the non-positive numbers from the list.
Note that after filtering the non positive elements, the maximum number of positive numbers in the array at the best case can be n, i.e. all the numbers from 1 to n, where n is the length of the positive numbers list.
Now we can mark all the numbers greater than n as not required, because the smallest positive number will definitely be in the range of [1,n] or it will be n+1 if all the numbers from 1 to n are in the array.
Coming to the core logic, consider an element v in the array which is not flag, i.e. it is in the range of [1,n]. Now mark the value at index v negative. If the value v is negative, consider its absolute value.
Why does this work?
- When a element is made negative, it means that the index i where it is located, which is a positive integer, exists in the list.
- If the positive integer doesn't exist in the list, that particular index remains positive, so when the array is traversed, we can exit at the first positive number encountered and output that index since that is the missing number.
- If the entire array is negative, it means that all the numbers from 1 to n exist in the array, hence the smallest positive number missing is (n+1).
Point to note: Since index start from 0, it should be kept in mind while negating the numbers and returning the result.

Python Code

Output

Feel free to reach out for any query clearance.
Thanks and cheers:)

Day #3: Serializing and Deserializing a Binary Tree with Python.

Manish Reddy Nandineni — Sat, 13 Jun 2020 09:23:32 +0000

Hello, today is the Day 3 of the #100DaysOfCodeChallenge. Received a problem previously asked by Google with a medium tag to it. This is also listed in the hard set of problems on LeetCode.

The Question On Day #3:

Given the root to a binary tree, implement serialize(root), which serializes the tree into a string, and deserialize(s), which deserializes the string back into the tree.
For example, given the following Node class

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

The following test should pass:

node = Node('root', Node('left', Node('left.left')), Node('right'))
assert deserialize(serialize(node)).left.left.val == 'left.left'

Algorithm

Create the binary tree using the Node class.
Serializing:
- To serialize the tree into a string, I considered the null nodes as #.
- Starting from root, Depth First Search is used to traverse through the tree.
- If a node exists, its value is appended to the string and the left sub tree is traversed.
- This process continues until there are no more children left. Then a '#' is appended to the array and the recursive function is exited.
- Then the right sub tree is traversed and the same process is followed.
- The final resulting is string is returned.
Deserializing:
- To deserialize a string to form a tree, the first word in the space seperated string is considered as the root.
- When a '#' is encountered, it is considered as a empty node and None is returned.
- In the remaining cases, a new node with the value as the word is formed and the remaining string is traversed.
- This function is called recursively until the end of the string is reached.

Python Code

Output

String after serializing node: root left left.left # # # right # # 

Assert: True

Python Visualiser To Understand The Recursion Better

View the visualisation of the above code in the Python Visualiser to understand the recursion better, step by step.

Please drop your queries in the comments section.

Thanks and cheers:)

Day #2: Product of all the elements of the array, except self.

Manish Reddy Nandineni — Fri, 12 Jun 2020 03:34:21 +0000

Hello, today is the Day 2 of the #100DaysOfCodeChallenge. Received a problem previously asked by Uber with a hard tag to it. Tried my best in solving it, looking for better solutions if possible.

But before that, an addition to yesterday's solution. The reason why in operator takes a time of O(1) on average for sets is: in Python, the sets are stored as hash tables. So when we need to check for the membership of a key, python calculates it's hash value which is the index and thus gives the answer if it exists or not. In most cases, the hashes are unique, and the worst case occurs only when the hash value is common for all the elements in the set and that's when all the elements are to be checked leading to a time complexity of O(n).

The Question On Day #2:

Given an array of integers, return a new array such that each element at  
index `i` of the new array is the product of all the numbers in the  
original array except the one at `i`.

For example, if our input was `[1, 2, 3, 4, 5]`, the expected output would  
be `[120, 60, 40, 30, 24]`. If our input was `[3, 2, 1]`, the expected  
output would be `[2, 3, 6]`.

Condition: Division is not allowed.

Naive Approach

Input the given n numbers into a list.
Traverse through the list n times and calculate the product each time, by skipping the number at that index.
Store the product in a new answer list.

Python Code

     l=[1,2,3,4,5]  
     a=[0]*len(l)  
     for i in range(len(l)):  
        p=1  
        for j in range(len(l)):
            if(i==j):
                continue
            else:
                p*=l[j]  
            a[i]=p  
     print(a)

Time Complexity Of The Above Solution

The traversal through the list for the outer loop executes at a time of O(n). The inner loop again takes a time of O(n) to traverse through the entire list.

The total time complexity for the solution will result in a time complexity of O(n^2).

Better Approach

I wrote a code satisfying the problem statement but found a better solution than mine in terms of time complexity at LeetCode. ref

Algorithm

Input the given n numbers into a list.
Consider that each element has a left product and a right produt, which mean product of all the elements to the left of the element and product of all the elements to the right of the element respectively.
Store the left and right products of each element in 2 different lists l and r where l has the left product of an element at the index i in list a and r similarly has the right product.
Now store the product of multiplying l[i[4] and r[i] in r[i] itself, which is the final output list.

Python Code

    a=[1,2,3,4,5]  
    length=len(a)  
    l=[0]*length  
    r=[0]*length  

    l[0]=1             #since there is no element to the left of the first element we keep it's left product as 1  

    for i in range(1,length):  
        l[i]=l[i-1]*a[i-1]  

    '''Ex: take i=1 the left product at i=1 is product of all elements  
    to the left of it. Since we have the left product of the   
    previous element already stored in the list l we multiply  
    it with the element at i-1.'''  

    r[length-1]=1       #since there is no element to the right of the last element.  

    for i in reversed(range(length-1)): 
        r[i]=r[i+1]*l[i+1]
        #same logic as above but in reverrse order

    #calculating the individual product
    for i range(length):
        r[i]*=l[i]
    print(r)

Time Complexity Of The Above Solution

The 3 individual loops need 1 traversal each through the entire list and each loop has only one operation in it.

Thus the total time complexity of the above program is O(n)

Thanks and cheers:)

Day #1: My Start With 100 Days Of Code

Manish Reddy Nandineni — Wed, 10 Jun 2020 17:32:13 +0000

Hi! I'm Manish. I was wondering what to do in this COVID-19 pandemic, to stay a bit productive and then the phrase 100 Days Of Code striked me while surfing the internet and I decided to take up the challenge.

To begin with that, I have enolled for the email subscription by Daily Coding Problems. The team at DCP sends us an email with one coding problem a day and I believed that it would be the right thing for the challenge. To add to that, I have decided to share my experience on solving the question too and start writing on dev.

The Question On Day #1:

Given a list of numbers and a number `k`, return whether any two numbers from the list add up to `k`.

For example, given `[10, 15, 3, 7]` and `k` of `17`, return true since `10 + 7` is `17`.

My First Approach

Input the given numbers into a list and and the sum to check in a variable.
Traverse through the list and for each element at index i, check if there exists a complementary number starting from the index i in the list.
If there exists atleast one such number print "pair exists" and exit the loop by marking a flag.
After the cursor exits the loop adn if the flag is still unmarked, print "pair doesn't exist".

Python Code

l=[10,15,3,7]
k=17
flag=0
for i in range(len(l)-1):
    if (k-l[i]) in l[i+1:]:
        #slicing to prevent additional checks
        print("pair exists")
        flag=1
        break
if flag==0:
    print("pair doesn't exist")

Points To Note:

The check for the complementary number is only done for the sliced list from i+1 to len(l), since the previous number pairs are already checked in the iterations before.
The last element of the list is thus skipped from being checked for a complementary number.

Time Complexity Of The Above Solution

The traversal through the list takes a time of O(n) where n is the length of list. For each element, there is an another check with in operator which again takes a time complexity of O(n-i) for a list in python ref.

The total time complexity for the solution will result in a time complexity of O(n^2).

Better Approach

An approach better to the above solution is to convert the list into a set first, does making the in operator efficient to use.

The time complexity of using the in operator on a set is O(1) on average and O(n) in the worst case.

Python Code

l=[10,15,3,7]
k=17
s=set(l) #converting list l into a set and storing it in s
flag=0
for i in s:
    if (k-i) in s:
        print("pair exists")
        flag=1
        break
if flag==0:
    print("pair doesn't exist")

Time Complexity Of The Above Solution

The conversion from list to a set takes a time of O(n) where n is the length of list. Hence, the total time complexity for the above solution is O(n)+O(nx1)
[O(nx1) on average and O(nxn) in the worst case for the loop and condition check using in operator on the set s].

Thus the total time complexity on average results to O(n) and O(n^2) in the worst case scenario.

This question helped me in understanding the time complexities of individual data structure operations in python. I would love to hear from my fellow developers and take suggestions on improving the above logic. I am a pretty newbie to solving such questions, please consider it. I also request you to drop suggestions to improve my article readability or understanding.

Thanks and cheers:)