Pages

November 24, 2019

Part 2.4: Leet Code Solutions For Java Coding Interview Round

Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word (last word means the last appearing word if we loop from left to right) in the string.
If the last word does not exist, return 0.

Note: A word is defined as a maximal substring consisting of non-space characters only.

Diameter of Binary Tree
Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree
1
/ \
2 3
/ \
4 5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

Algorithm:
1. Replace all the 0's with -1, this will help us to find out the maximum length subarray with sum = 0.
2. Declare a HashMap, this will help us to find the subarray with sum=0 and start index is not 0.
3. Declare three variables sum, maxLength and endIndex. Initialize maxsize with -1 to handle cases where all 1's or 0's. maxsize=-1 means there is no such subarray.
4. Now we will start iterating, and update the sum.
5. If the sum is equal to 0, increment the maxLength and update endIndex.
6. We will check if the sum is present in the HashMap. If not present add the sum as key and value as index.
7. If the value is present, check if the difference of current index and previously stored value in hash (for the sum) is more than maxsize. If yes, update maxsize and endIndex.
8. Replace all the -1's with 0.