Sardar Vallabhbhai Patel Institute of Technology, Vasad
Training & Placement Cell, IT Department
Answer Key for Mock Placement
Sem-6 AY: 2024-25
Please Note: The solution for Coding Test is provided here in C, C++, Java, Python language.
CODING TEST
IT-1
(1) Maximum Depth of Binary Tree
Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down
to the farthest leaf node.
Example 1:
Input: root = [3,9,20,null,null,15,7] Output:
3
Example 2:
Input: root = [1,null,2]
Output: 2
Constraints:
The number of nodes in the tree is in the range [0, 104].
-100 <= [Link] <= 100
Solution:
C:
// Function to calculate the maximum depth of the binary tree
int maxDepth(struct TreeNode* root) { if (root == NULL) { return
0;
}
int leftDepth = maxDepth(root->left); int
rightDepth = maxDepth(root->right);
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}
Prepared by Kashish Zaveri, Samarth Joshi, Tarun Ray, Unnati Suryawanshi (T&P Coordinators) 21/03/2025
C++:
// Function to calculate the maximum depth of the binary tree
int maxDepth(TreeNode* root) { if (root == NULL) { return 0;
}
int leftDepth = maxDepth(root->left); int
rightDepth = maxDepth(root->right);
return max(leftDepth, rightDepth) + 1;
}
Java:
// Function to calculate the maximum depth of the binary tree
public static int maxDepth(TreeNode root) { if (root == null)
{ return 0; }
int leftDepth = maxDepth([Link]); int
rightDepth = maxDepth([Link]);
return [Link](leftDepth, rightDepth) + 1; }
Python:
# Function to calculate the maximum depth of the binary tree
def maxDepth(root):
if not root:
return 0
leftDepth = maxDepth([Link]) rightDepth
= maxDepth([Link])
return max(leftDepth, rightDepth) + 1
Prepared by Kashish Zaveri, Samarth Joshi, Tarun Ray, Unnati Suryawanshi (T&P Coordinators) 21/03/2025
(2) Product of Array Except Self
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all
the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in 0(n) time and without using the division operation.
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Constraints:
2 <= [Link] <= 105
-30 <= nums[i] <= 30
The input is generated such that answer[i] is guaranteed to fit in a 32-bit
Solution:
C:
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
int* result = (int*)malloc(numsSize * sizeof(int));
*returnSize = numsSize;
// Initialize result array with 1
for (int i = 0; i < numsSize; i++)
{ result[i] = 1; }
// Calculate prefix products int
prefix = 1; for (int i = 0; i <
numsSize; i++) { result[i] = prefix;
prefix *= nums[i]; }
// Calculate postfix products and multiply with prefix
int postfix = 1; for (int i = numsSize - 1; i >= 0; i-
-) { result[i] *= postfix; postfix *= nums[i];
}
return result;
}
Prepared by Kashish Zaveri, Samarth Joshi, Tarun Ray, Unnati Suryawanshi (T&P Coordinators) 21/03/2025
C++:
vector<int> productExceptSelf(vector<int>& nums) { int
n = [Link]();
vector<int> result(n, 1);
// Calculate prefix products
int prefix = 1; for (int i =
0; i < n; i++) { result[i] =
prefix; prefix *= nums[i];
}
// Calculate postfix products and multiply with
prefix int postfix = 1; for (int i = n - 1; i >= 0;
i--) { result[i] *= postfix; postfix *= nums[i]; }
return result;
}
Java:
// Initialize result array with 1
for (int i = 0; i < n; i++) {
result[i] = 1;
}
// Calculate prefix products
int prefix = 1; for (int i =
0; i < n; i++) { result[i] =
prefix; prefix *= nums[i];
}
// Calculate postfix products and multiply with prefix
int postfix = 1;
for (int i = n - 1; i >= 0; i--) {
result[i] *= postfix; postfix
*= nums[i];
}
return result;
Prepared by Kashish Zaveri, Samarth Joshi, Tarun Ray, Unnati Suryawanshi (T&P Coordinators) 21/03/2025
Python:
def productExceptSelf(nums): def productExceptSelf(nums):
n = len(nums) result
= [1] * n
# Calculate prefix products
prefix = 1 for i in
range(n): result[i] =
prefix prefix *= nums[i]
# Calculate postfix products and multiply with prefix
postfix = 1 for i in range(n - 1, -1, -1):
result[i] *= postfix
postfix *= nums[i]
return result
Prepared by Kashish Zaveri, Samarth Joshi, Tarun Ray, Unnati Suryawanshi (T&P Coordinators) 21/03/2025
IT-2,3
(1) Valid Palindrome
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all
non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters
include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
Example 1:
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.
Example 2:
Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.
Constraints:
1 <= [Link] <= 2 * 105 s consists only of printable
ASCII characters.
Solution:
C:
boolean isPalindrome(char* s)
{ int left = 0;
int right = strlen(s) - 1;
while (left < right) { while (left < right &&
!isalnum(s[left])) { left++;
}
while (left < right && !isalnum(s[right])) {
right--;
} if (tolower(s[left]) != tolower(s[right]))
{ return false;
}
left++;
right--;
}
return true;
}
Prepared by Kashish Zaveri, Samarth Joshi, Tarun Ray, Unnati Suryawanshi (T&P Coordinators) 21/03/2025
C++:
boolean isPalindrome(string s) { int
left = 0;
int right = [Link]() - 1;
while (left < right) { while (left < right &&
!isalnum(s[left])) { left++;
} while (left < right &&
!isalnum(s[right])) { right--;
}
if (tolower(s[left]) != tolower(s[right])) {
return false;
}
left++;
right--;
} return
true;
}
Java:
public static boolean isPalindrome(String s) { int
left = 0;
int right = [Link]() - 1;
while (left < right) { while (left < right &&
)) { left++;
}
while (left < right && )) {
right--;
}
if ([Link]([Link](left)) !=
[Link]([Link](right))) { return
false;
}
left++;
right--;
}
return true;
}
Prepared by Kashish Zaveri, Samarth Joshi, Tarun Ray, Unnati Suryawanshi (T&P Coordinators) 21/03/2025
Python:
def isPalindrome(s): left
= 0
right = len(s) – 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
Prepared by Kashish Zaveri, Samarth Joshi, Tarun Ray, Unnati Suryawanshi (T&P Coordinators) 21/03/2025
(2). Remove Nth Node From End of List
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Example 1:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Example 2:
Input: head = [1], n = 1
Output: []
Constraints:
The number of nodes in the list is sz.
1 <= sz <= 30
0 <= [Link] <= 100
1 <= n <= sz Solution:
C:
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
struct ListNode dummy = {0, head}; struct ListNode *res =
&dummy; struct ListNode *fast = head;
// Move fast pointer n steps ahead for (int i = 0; i < n; i++) {
if (fast == NULL) return head; // Edge case: n > list length fast
= fast->next;
}
// Move both pointers until fast reaches the end
while (fast != NULL) { fast = fast->next; res =
res->next;
}
// Remove the nth node from the end res->next
= res->next->next;
return [Link];
}
Prepared by Kashish Zaveri, Samarth Joshi, Tarun Ray, Unnati Suryawanshi (T&P Coordinators) 21/03/2025
C++:
ListNode* removeNthFromEnd(ListNode* head, int n){
ListNode dummy(0, head);
ListNode *res = &dummy;
ListNode *fast = head;
// Move fast pointer n steps ahead
for (int i = 0; i < n; i++) { fast
= fast->next;
}
// Move both pointers until fast reaches the end
while (fast != nullptr) { fast = fast->next; res
= res->next;
}
// Remove the nth node from the end res->next
= res->next->next;
return [Link];
}
Java:
public static ListNode removeNthFromEnd(ListNode head, int n) {
ListNode res = new ListNode(0,
head); ListNode dummy = res; for
(int i = 0; i < n; i++) { head =
[Link];
} while (head != null)
{ head = [Link];
dummy = [Link];
}
[Link] = [Link]; return
[Link];
}
Prepared by Kashish Zaveri, Samarth Joshi, Tarun Ray, Unnati Suryawanshi (T&P Coordinators) 21/03/2025
Python:
# Function to remove the nth node from the end def
removeNthFromEnd(head, n):
dummy = ListNode(0, head) res
= dummy fast = head
# Move fast pointer n steps ahead
Preparedfor Kashish_ in Zaveri,range Samarth(n):
fast = [Link]
# Move both pointers until fast reaches the end
while fast:
fast = [Link] res
= [Link]
# Remove the nth node from the end [Link]
= [Link]
return [Link]
Prepared by Kashish Zaveri, Samarth Joshi, Tarun Ray, Unnati Suryawanshi (T&P Coordinators) 21/03/2025
