inactive

#include <iostream> using namespace std; struct Node { int data; struct Node* left; struct Node* right; }; struct Node* newNode(int data) { struct Node* node = (struct Node*)malloc(sizeof(struct Node)); node->data = data; node->left = NULL; node->right = NULL; return (node); } void NthInorder(struct Node* node, int n) { static int count = 0; if (node == NULL) return; if (count <= n) { NthInorder(node->left, n); count++; if (count == n) cout << node->data << " "; NthInorder(node->right, n); } } int main() { struct Node* root = newNode(10); root->left = newNode(20); root->right = newNode(30); root->left->left = newNode(40); root->right->right = newNode(50); int n; cin >> n; //awasthi NthInorder(root, n); return 0; }

Imagine you are a computer scientist working on a cutting-edge project involving binary trees. As part of your research, you are analyzing the in-order traversal of a specific binary tree. Your task is to determine the value of the node that appears at the nth position in the in-order traversal sequence. To accomplish this, you are given a binary tree with various nodes. Each node has a unique value associated with it. Your goal is to navigate through the tree using the in-order traversal algorithm, which involves visiting the left subtree, then the current node, and finally the right subtree. By implementing an efficient algorithm, you should be able to find the node that appears at the nth position in the in-order traversal sequence of the given binary tree. Input format : The input consists of an integer value, n, which represents the position of the node in the in-order traversal sequence that needs to be found. Output format : The output prints the value of the node that appears at the nth position in the in-order traversal sequence.

#include <iostream> #include <vector> struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; void inorderReverse(TreeNode* root, int& k, int& result) { if (root == nullptr || k == 0) return; inorderReverse(root->right, k, result); k--; if (k == 0) { result = root->val; return; } inorderReverse(root->left, k, result); } int kthLargest(TreeNode* root, int k) { int result = 0; inorderReverse(root, k, result); return result; } int main() { TreeNode* root = nullptr; // Build the BST int val; while (std::cin >> val && val != -1) { TreeNode* newNode = new TreeNode(val); if (root == nullptr) { root = newNode; } else { TreeNode* current = root; while (true) { if (val < current->val) { if (current->left == nullptr) { current->left = newNode; break; } current = current->left; } else { if (current->right == nullptr) { current->right = newNode; break; } current = current->right; } } } } int k; std::cin >> k; // Find the kth largest element int kthLargestElement = kthLargest(root, k); std::cout << kthLargestElement << std::endl; // Clean up memory (optional) // Implement a function to delete the tree if needed //awasthi return 0; }

You are preparing for a technical interview with a well-known tech company. During a mock interview, you are presented with a coding challenge related to Binary Search Trees (BSTs). The challenge is to write a program that finds the kth largest element in a BST, and you are required to implement an efficient solution. Your task is to complete the code and ensure that it correctly identifies the kth largest element for the given input tree. Input format : The first line of input consists of a sequence of integers representing the elements of the BST. The input is terminated by -1. The second line consists of an integer k, representing the position of the desired largest element. Output format : The output prints a single integer, which is the kth largest element in the BST.

#include <stdio.h> #include <stdlib.h> // Definition for a binary tree node struct TreeNode { int val; struct TreeNode* left; struct TreeNode* right; }; // Function to build the binary tree from user input struct TreeNode* buildTree(int arr[], int* index, int n) { if (*index >= n arr[*index] == -1) { (*index)++; return NULL; } struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode)); root->val = arr[(*index)]; (*index)++; root->left = buildTree(arr, index, n); root->right = buildTree(arr, index, n); return root; } // Inorder traversal to get the elements in sorted order void inorder(struct TreeNode* root, int sorted[], int* index) { if (!root) { return; } inorder(root->left, sorted, index); sorted[(*index)++] = root->val; inorder(root->right, sorted, index); } // Function to find the minimum number of swaps to convert BST int minSwapsToBST(struct TreeNode* root) { int sorted[1000]; // Assuming a maximum of 1000 nodes int index = 0; inorder(root, sorted, &index); struct { int value; int index; } arrpos[1000]; // Assuming a maximum of 1000 nodes int n = index; // Number of elements in the tree for (int i = 0; i < n; i++) { arrpos[i].value = sorted[i]; arrpos[i].index = i; } for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arrpos[j].value > arrpos[j + 1].value) { int temp_value = arrpos[j].value; arrpos[j].value = arrpos[j + 1].value; arrpos[j + 1].value = temp_value; int temp_index = arrpos[j].index; arrpos[j].index = arrpos[j + 1].index; arrpos[j + 1].index = temp_index; } } } // Visited array to keep track of visited elements int visited[1000] = {0}; int ans = 0; for (int i = 0; i < n; i++) { if (visited[i] arrpos[i].index == i) { continue; } else { int j = i; int cycle_size = 0; while (!visited[j]) { visited[j] = 1; j = arrpos[j].index; cycle_size++; } if (cycle_size > 0) { ans += (cycle_size - 1); } } } return ans; } int main() { int n; scanf("%d", &n); int arr[100]; for (int i = 0; i < n; i++) { scanf("%d", &arr[i]); } int index = 0; struct TreeNode* root = buildTree(arr, &index, n); int swaps = minSwapsToBST(root); printf("%d\n", swaps); //awasthi return 0; }

#include <iostream> #include <vector> struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; void inorderTraversal(TreeNode* root, int k, int& count, int& result) { if (root == nullptr || count >= k) return; inorderTraversal(root->left, k, count, result); count++; if (count == k) { result = root->val; return; } inorderTraversal(root->right, k, count, result); } int kthSmallest(TreeNode* root, int k) { int count = 0; int result = 0; inorderTraversal(root, k, count, result); return result; } //awasthi int main() { TreeNode* root = nullptr; // Build the BST int val; while (std::cin >> val && val != -1) { TreeNode* newNode = new TreeNode(val); if (root == nullptr) { root = newNode; } else { TreeNode* current = root; while (true) { if (val < current->val) { if (current->left == nullptr) { current->left = newNode; break; } current = current->left; } else { if (current->right == nullptr) { current->right = newNode; break; } current = current->right; } } } } int k; std::cin >> k; // Find the kth smallest element int kthSmallestElement = kthSmallest(root, k); std::cout << kthSmallestElement << std::endl; // Clean up memory (optional) // Implement a function to delete the tree if needed return 0; }

#include <iostream> #include <unordered_set> struct TreeNode { int value; TreeNode* left; TreeNode* right; TreeNode(int val) : value(val), left(nullptr), right(nullptr) {} }; bool hasDuplicates(TreeNode* root, std::unordered_set<int>& seen) { if (root == nullptr) return false; if (seen.find(root->value) != seen.end()) return true; seen.insert(root->value); return hasDuplicates(root->left, seen) || hasDuplicates(root->right, seen); } std::string hasDuplicatesWrapper(TreeNode* root) { std::unordered_set<int> seen; return hasDuplicates(root, seen) ? "Yes" : "No"; } // Function to build the binary tree from the input TreeNode* buildTree(int rootVal) { int leftVal, rightVal; std::cin >> leftVal >> rightVal; TreeNode* root = new TreeNode(rootVal); if (leftVal != -1) root->left = buildTree(leftVal); if (rightVal != -1) root->right = buildTree(rightVal); //awasthi return root; } int main() { int rootValue; std::cin >> rootValue; TreeNode* root = buildTree(rootValue); std::cout << hasDuplicatesWrapper(root) << std::endl; // Free dynamically allocated memory (optional, good practice) // Add a function to deallocate the nodes if necessary return 0; }

You are working on a critical customer database system for a large e-commerce platform. The database stores customer information, like their unique customer IDs, in a binary tree structure. Ensuring data integrity is paramount, as duplicate customer IDs can lead to serious data inconsistencies and operational issues. Your task is to develop a program that checks whether the binary tree containing customer IDs has any duplicate values. Detecting duplicates is essential to maintain the accuracy of customer records. Input format : The first line of input consists of an integer representing the value of the root node. For each node in the tree, there are two integers, Left child data: an integer representing the value of the left child node. Use -1 to indicate no left child. Right child data: an integer representing the value of the right child node. Use -1 to indicate no right child. Output format : Print "Yes" if there are any duplicate customer IDs in the binary tree. Otherwise, print "No".

You are given a binary search tree (BST) and an integer k. Your task is to find the kth smallest element in the BST. Implement the function kthSmallest that takes the root of the BST and an integer k as input and returns the kth smallest element in the BST. Input format : The first line of input consists of a sequence of integers representing the elements of the BST. The input is terminated by -1. The second line consists of an integer k, representing the position of the desired smallest element. Output format : The output prints a single integer, which is the kth smallest element in the BST.

You are given an unordered binary tree, and your task is to determine the minimum number of swaps required to convert it into a binary search tree (BST). A binary search tree is a binary tree in which, for each node: All nodes in its left subtree have values less than the node's value. All nodes in its right subtree have values greater than the node's value. Your task is to find the minimum number of swaps of the nodes in the given binary tree to transform it into a valid BST. Input format : The first line of input consists of an integer N, representing the number of nodes in the binary tree. The second line consists of the values of the N nodes separated by space, representing the unordered binary tree. The input is terminated by entering -1. Output format : The output prints an integer representing the minimum number of swaps required to convert the given binary tree into a binary search tree (BST).

#include <iostream> void swap(int& a, int& b) { int temp = a; a = b; b = temp; } int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] <= pivot) { i++; swap(arr[i], arr[j]); } } swap(arr[i + 1], arr[high]); return i + 1; } void quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } //awasthi int main() { int N; // std::cout << "Enter the number of years: "; std::cin >> N; int years[N]; //std::cout << "Enter the years:\n"; for (int i = 0; i < N; i++) { std::cin >> years[i]; } quickSort(years, 0, N - 1); //std::cout << "Sorted years in chronological order:\n"; for (int i = 0; i < N; i++) { std::cout << years[i] << " "; } std::cout << std::endl; return 0; }

Imagine you are a computer programmer tasked with creating a program to organize a collection of years in ascending order. This program will take a list of years as input and efficiently sort them using the Quick-Sort algorithm, ensuring that the years are arranged chronologically. Input format : The first line of input consists of an integer N, representing the number of years. The second line consists of N space-separated integers, representing the years. Output format : The output prints the sorted dates in chronological order.

// You are using GCC #include <iostream> void swap(int& a, int& b) { int temp = a; a = b; b = temp; } void rearrangeNegativesBeforePositives(int arr[], int n) { int left = 0, right = n - 1; while (left <= right) { if (arr[left] < 0) { left++; } else if (arr[right] >= 0) { right--; } else { swap(arr[left], arr[right]); left++; right--; } } } int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] <= pivot) { i++; swap(arr[i], arr[j]); } } swap(arr[i + 1], arr[high]); return i + 1; } void quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } int main() { int N; // std::cout << "Enter the number of elements: "; std::cin >> N; int arr[N]; // std::cout << "Enter the elements: "; for (int i = 0; i < N; i++) { std::cin >> arr[i]; } //awasthi rearrangeNegativesBeforePositives(arr, N); quickSort(arr, 0, N - 1); // std::cout << "Sorted array (negative elements before positive elements):\n"; for (int i = 0; i < N; i++) { std::cout << arr[i] << " "; } std::cout << std::endl; return 0; }

You are given an array of integers containing both negative and positive numbers. Your task is to rearrange the elements in such a way that all negative numbers come before the positive numbers. After rearranging, you need to sort the numbers in ascending order using the Quick-Sort algorithm. Implement the following functions: rearrangeNegativesBeforePositives(int arr[], int n): This function takes an array of integers arr and its size n as input. It should rearrange the elements so that all negative numbers appear before the positive numbers while maintaining the relative order of negative and positive numbers. quickSort(int arr[], int low, int high): This is the standard QuickSort function that takes an array of integers arr, the starting index low, and the ending index high. It sorts the numbers in ascending order. Input format : The first line of input consists of an integer N, representing the number of elements in the array. The second line consists of N array elements, separated by space. Output format : The output prints the sorted array, such that the negative elements come before the positive elements, separated by space.

#include <iostream> #include <vector> #include <string> void swap(std::string& a, std::string& b) { std::string temp = a; a = b; b = temp; } int partition(std::vector<std::string>& names, int low, int high) { std::string pivot = names[high]; int i = low - 1; for (int j = low; j < high; j++) { if (names[j] < pivot) { i++; swap(names[i], names[j]); } } swap(names[i + 1], names[high]); return i + 1; } void quickSort(std::vector<std::string>& names, int low, int high) { if (low < high) { int pi = partition(names, low, high); quickSort(names, low, pi - 1); quickSort(names, pi + 1, high); } } int main() { int N; // std::cout << "Enter the number of users: "; std::cin >> N; std::vector<std::string> names(N); // std::cout << "Enter the names of the users:\n"; for (int i = 0; i < N; i++) { std::cin >> names[i]; } //awasthi quickSort(names, 0, N - 1); // std::cout << "Sorted list of names in alphabetical order:\n"; for (const auto& name : names) { std::cout << name << "\n"; } return 0; }

You are working on a project to implement a feature that displays the list of users in alphabetical order based on their names. To achieve this, you decide to use the Quick-Sort algorithm to efficiently sort the names. The user inputs the number of users and then the name of each user. Once the names are collected, the program must apply the Quick Sort algorithm to sort and display the names in alphabetical order. Note: This kind of question will be helpful in clearing Capgemini recruitment. Input format : The first line of input consists of an integer N, representing the number of users. The following N lines consist of the names of the users (starting with uppercase letters).

#include <iostream> #include <vector> #include <algorithm> struct Athlete { std::string name; int height; }; int partition(std::vector<Athlete>& athletes, int low, int high) { int pivot = athletes[high].height; int i = low - 1; for (int j = low; j < high; j++) { if (athletes[j].height >= pivot) { i++; std::swap(athletes[i], athletes[j]); } } std::swap(athletes[i + 1], athletes[high]); return i + 1; } void quickSort(std::vector<Athlete>& athletes, int low, int high) { if (low < high) { int pi = partition(athletes, low, high); quickSort(athletes, low, pi - 1); quickSort(athletes, pi + 1, high); } } int main() { int N; // std::cout << "Enter the number of athletes: "; std::cin >> N; //awasthi std::vector<Athlete> athletes(N); for (int i = 0; i < N; i++) { std::cin >> athletes[i].name >> athletes[i].height; } quickSort(athletes, 0, N - 1); // std::cout << "Sorted athletes in descending order of height:\n"; for (const auto& athlete : athletes) { std::cout << athlete.name << " "; } std::cout << std::endl; return 0; }

You are working as a program developer at a renowned sports academy. As part of the academy's performance evaluation system, you are tasked with sorting the athletes based on their heights in descending order. Write a program that takes an array of athlete names and their corresponding heights as input. Your program should use the Quick-Sort algorithm to sort the athletes' names in descending order based on their heights. Input format : The first line of input consists of an integer N, representing the number of athletes. The following N lines consist of the athlete's name and height, separated by space. Output format : The output prints the athletes' names sorted in descending order based on their heights.

// You are using GCC #include <iostream> #include <vector> void merge(std::vector<int>& arr, int left, int middle, int right) { int n1 = middle - left + 1; int n2 = right - middle; std::vector<int> leftArr(n1); std::vector<int> rightArr(n2); for (int i = 0; i < n1; ++i) leftArr[i] = arr[left + i]; for (int j = 0; j < n2; ++j) rightArr[j] = arr[middle + 1 + j]; int i = 0, j = 0, k = left; while (i < n1 && j < n2) { if (leftArr[i] <= rightArr[j]) { arr[k++] = leftArr[i++]; } else { arr[k++] = rightArr[j++]; } } while (i < n1) { arr[k++] = leftArr[i++]; } while (j < n2) { arr[k++] = rightArr[j++]; } } void mergeSort(std::vector<int>& arr, int left, int right) { if (left < right) { int middle = left + (right - left) / 2; mergeSort(arr, left, middle); mergeSort(arr, middle + 1, right); merge(arr, left, middle, right); } } int main() { int n; // std::cout << "Enter the number of scores: "; std::cin >> n; std::vector<int> scores(n); // std::cout << "Enter the scores: "; for (int i = 0; i < n; i++) { std::cin >> scores[i]; } // std::cout << "Initial array of scores: "; for (int score : scores) { std::cout << score << " "; } std::cout << std::endl; // Perform merge sort to sort scores mergeSort(scores, 0, n - 1); //awasthi //std::cout << "Sorted array of scores: "; for (int score : scores) { std::cout << score << " "; } std::cout << std::endl; return 0; }

You are developing a leaderboard system for an online game. The scores of the players are stored in an array of integers. To display the leaderboard, you need to sort the scores in ascending order. Write code to implement a recursive merge sort algorithm for sorting the scores. Note: This kind of question will help in clearing Wipro recruitment. Input format : The first line of input consists of an integer n, representing the number of scores in the array. The second line of input consists of n space-separated integers, representing the scores of the players. Output format : The first line of output displays the initial array of scores before sorting. The second line of output displays the sorted array of scores after applying the merge sort algorithm.