tutorialcup

[tutorialcup]

Yatra Interview Experience

Read the full article

[tutorialcup]

MAANG Interview Questions and Preparation

Read the full article

[tutorialcup]

Flipping an Image LeetCode Solution

Problem Statement

Flipping an Image LeetCode Solution - We are given a matrix of size n. We need to perform 2 tasks- - flip the image horizontally: it means each row of the given matrix is reversed - invert the image: make all 0’s to 1’s & vice versa Return the resulting matrix. Given matrix contains only 0 or 1 and size of image is ≤ 20.

Examples & Explanations

Example 1: Input: image = ,,] Output: ,,] Explanation: First reverse each row: ,,]. Then, invert the image: ,,] Example 2: Input: image = ,,,] Output: ,,,] Explanation: First reverse each row: ,,,]. Then invert the image: ,,,]

Approach

After reviewing some examples you will notice the following patterns: 1) Look at the first and last value of the row. If they are the same (1,1 or 0,0), they will be flipped in the output. If they are different (1,0 or 0,1), they do not change. Work your way inward to the middle of the list applying this rule. 2) If the row has an odd number of entries, the middle value always flips. For example if len(row) = 5, then row must change values. Bitwise XOR --> 0^1 = 1, 1^1 =0 Let i be the index at the beginning of the row, and j be the index at the end of the row. If the values at these indices (row and row) are equal, flip their values using XOR ^. If the values are not equal, do nothing and move i and j closer to the middle. When i == j , the code still executes as it should. The question has 2 parts- - Flipping the image: we can simply use another array or vector to store matrix and reverse it for all rows and store the answer in another matrix res - Inverting the image: this is an easy task, simply check the value of res and change the value This approach requires us to declare another matrix of size n x n. Can we do better? We can achieve flipping in place by swapping the elements by pivoting the middle element of every row in the image. For each row, keep the middle element in place and swap the ith element with the (n-1-i)th element. We will use XOR to invert the elements. We know that 1^1 = 0 & 1^0 = 1

Code

C++ code for Flipping an Image class Solution { public: vector flipAndInvertImage(vector& image) { int n = image.size(); for(auto &row: image) { for(int i=0; i Read the full article

[tutorialcup]

Partition Labels LeetCode Solution

Problem Statement

Partition Labels LeetCode Solution - You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part. Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s. Return a list of integers representing the size of these parts.

Examples and Explanation

Example 1: Input: s = "ababcbacadefegdehijhklij" Output: Explanation: The partition is "ababcbaca", "defegde", "hijhklij". This is a partition so that each letter appears in at most one part. A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits s into less parts. Example 2: Input: s = "eccbbbbdec" Output: Explanation: The given string can not partitioned further as the letters will be repeated if partitioned.

Algorithm

Let’s look at example 1, we can notice that if we are including ‘a’ in the first partition then we need to include all the ‘a’s appearing in the string. So, we will include the substring from the first index till the last index of occurrences of ‘a’. In the second partition, "defegde" , we notice that including substring from the first index of ‘d’ till the last index of ‘d’ will not suffice. This means that we need to include all the last indices of all letters appearing between the first and last indices of ‘d’ as well.

Code

C++ program for Partition Labels class Solution { public: vector partitionLabels(string s) { map index; for(int i=0; i Read the full article

[tutorialcup]

Range Sum Query 2D - Immutable Leetcode Solution

Problem Statement

Range Sum Query 2D - Immutable Leetcode Solution - Given a 2D matrix matrix, handle multiple queries of the following type: - Calculate the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2). Implement the NumMatrix class: - NumMatrix(int matrix) Initializes the object with the integer matrix matrix. - int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Example

Input , , , , ]], , , ] Output Explanation NumMatrix numMatrix = new NumMatrix(, , , , ]); numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangle) numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle) numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle)

Constraints

- m == matrix.length - n == matrix.length - 1 Read the full article

[tutorialcup]

Amazon Coding Interview Questions

Read the full article

[tutorialcup]

Longest Palindromic Substring LeetCode Solution

Problem Statement

The Longest Palindromic Substring LeetCode Solution - “Longest Palindromic Substring” states that You are Given a string s, return the longest palindromic substring in s. Note: A palindrome is a word that reads the same backward as forwards, e.g. madam.

Example:

  s = "babad" "bab" Explanation: All the unique palindromic substrings are: "b", "a", "d", "bab", "aba". Out of these, “bab” and “aba” are the longest substrings. s = "cbbd" "bb" Explanation: All the unique palindromic substrings are: "c", "b", "d", "bb". Out of these, “bb” is the longest substring.

Brute Force Solution

Idea: We can check all the substrings and check which substrings are palindrome, then take the longest among them. 

Code:

C++ Program of Longest Palindromic Substring LeetCode Solution #include using namespace std; bool check(string &s, int i, int j) { while (i max_len) { max_len = j - i + 1; starting_index = i; } } } } return s.substr(starting_index, max_len); } int main() { string s = "babad"; cout Read the full article

[tutorialcup]

Longest Palindromic Substring LeetCode Solution

Problem Statement

The Longest Palindromic Substring LeetCode Solution - “Longest Palindromic Substring” states that You are Given a string s, return the longest palindromic substring in s. Note: A palindrome is a word that reads the same backward as forwards, e.g. madam.

Example:

  s = "babad" "bab" Explanation: All the unique palindromic substrings are: "b", "a", "d", "bab", "aba". Out of these, “bab” and “aba” are the longest substrings. s = "cbbd" "bb" Explanation: All the unique palindromic substrings are: "c", "b", "d", "bb". Out of these, “bb” is the longest substring.

Brute Force Solution

Idea: We can check all the substrings and check which substrings are palindrome, then take the longest among them. 

Code:

C++ Program of Longest Palindromic Substring LeetCode Solution #include using namespace std; bool check(string &s, int i, int j) { while (i max_len) { max_len = j - i + 1; starting_index = i; } } } } return s.substr(starting_index, max_len); } int main() { string s = "babad"; cout Read the full article

[tutorialcup]

Merge Two Binary Trees LeetCode Solution

Problem Statement

Merge Two Binary Trees LeetCode Solution - You are given two binary trees root1 and root2. Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree. Return the merged tree.

Example

Test Case 1: Input: root1 = root2 = Output:

Explanation

After merging the Binary trees the output tree becomes . Approach Idea We can traverse both the given trees in a preorder fashion. At every step, we check if the current node exists(isn't null) for both the trees. If so, we add the values in the current nodes of both the trees and update the value in the current node of the first tree to reflect this sum obtained. At every step, we also call the original function mergeTrees() with the left children and then with the right children of the current nodes of the two trees. If at any step, one of these children happens to be null, we return the child of the other tree(representing the corresponding child subtree) to be added as a child subtree to the calling parent node in the first tree. At the end, the first tree will represent the required resultant merged binary tree.

Code for Merge Two Binary Trees LeetCode Solution

Java Program class Solution { public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { if (root1 == null) return root2; if (root2 == null) return root1; TreeNode node = new TreeNode(root1.val + root2.val); node.left = mergeTrees(root1.left, root2.left); node.right = mergeTrees(root1.right, root2.right); return node; } } C++ Program class Solution { public: TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) { if (!root1 || !root2) return root1 ? root1 : root2; TreeNode* node = new TreeNode(root1->val + root2->val); node->left = mergeTrees(root1->left, root2->left); node->right = mergeTrees(root1->right, root2->right); return node; } };

Complexity Analysis for Merge Two Binary Trees LeetCode Solution

Time Complexity will be O(m). A total of m nodes need to be traversed. Here, m represents the minimum number of nodes from the two given trees. Space Complexity will be O(m). The depth of the recursion tree can go up to m in the case of a skewed tree. In an average case, depth will be O(logm). Reference: https://en.wikipedia.org/?title=Pre-order_traversal Read the full article

[tutorialcup]

Strobogrammatic Number LeetCode Solution

Problem Statement

Strobogrammatic Number LeetCode Solution - Given a string num which represents an integer, return true if num is a strobogrammatic number. A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Example

Test Case 1: Input: num =  "69" Output: true Test Case 2: Input: num =  "692" Output: false

Explanation

i) For the first test case if we rotate "69" by 180 degrees, it's the same. ii) For the second test case if we rotate "692" by 180 degrees, it's not the same number. Approach Idea We need to determine what each digit becomes when rotated by 180 degrees. There are three possibilities for each digit: - it becomes invalid - it stays the same - it becomes a different digit We'll consider a digit to be rotatable if, and only if, that digit becomes a valid digit when rotated. If we think carefully, we can identify that 0, 1, 6, 8, 9 are rotatable as only these digits are valid when it is rotated upside down by 180 degrees. So if the number contains any digit other than these, we can easily say that it is not a strobogrammatic number. For other digits, we need to check if their rotation is the same as the number at its counterpart.

Code for Strobogrammatic Number LeetCode Solution

Java Program class Solution { public boolean isStrobogrammatic(String num) { Map map = new HashMap(); map.put('6', '9'); map.put('9', '6'); map.put('0', '0'); map.put('1', '1'); map.put('8', '8'); int l = 0, r = num.length() - 1; while (l Read the full article