Coding
Question 1:
Airport security officials have confiscated several items of the passenger at the security checkpoint. All
the items have been dumped into a huge box(array). Each item possessed a certain amount of risk(0,1,2).
Here is the risk severity of the item representing an array[] of N number of integer values. The risk here is to sort the item based on their level of risk values range from 0 to 2.
Example 1:
Input:
7 ————- Value of N
[1,0,2,0,1,0,2] -> Element of arr[0] to arr[N-1], while input each element is separated by new line
Output:
0 0 0 1 1 2 2 -> Element after sorting based on the risk severity.
Example 2:
Input:
10———— Value of N
[2,1,0,2,1,0,0,1,2,0] -> Element of arr[0] to arr[N-1], while input each element is separated by new line
Output:
0 0 0 0 0 1 1 1 2 2 2 -> Element after sorting based on the risk severity.
Constraints
0<N<=100
0<=arr[i]<=2
Solution: In C++
#include
using namespace std;
int main()
{
int n;
cin >> n;
int arr[n];
for(int i = 0; i > arr[i];
}
for(int i = 0; i < n; i++)
{
for(int j = i+1; j arr[j] )
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
for(int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
}
TCS NQT MOCK TEST / PRACTICE AET
Click Here!
Question 2:
Given N gold wires, each wire has a length associated with it. At a time, only two adjacent small wres
assembled at the end of a large wire and the cost of forming is the sum of their length. Find the minimum
cost when all wires are assembled to form a single wire.
For Example:
Suppose, Arr[] = {7, 6, 8, 6, 1, 1}
{7, 6, 8, 6, 1, 1} – {7, 6, 8, 6, 2}, cost = 2
{7, 6, 8, 6, 2} – {7, 6, 8, 8}, cost = 8
{7, 6, 8, 8} – {13, 8, 8}, cost =13
{13, 8, 8} – {13, 16}, cost = 16
{13, 16} – {29}, cost = 29
2 + 8 + 13 + 16 + 29 = 68
Hence, the minimum cost to assemble all gold wires is : 68
Constraints:
1 <= N <= 30
1<= Arr[] <= 100
Example 1:
Input:
6 -> Value of N, represents size of Arr
7 -> Value of Arr[0], represents length of 1st wire
6 -> Value of Arr[1], represents length of 2nd wire
8 -> Value of Arr[2], represents length of 3rd wire
6 -> Value of Arr[3], represents length of 4th wire
-1 -> Value of Arr[4], represents length of 5th wire
1 -> Value of Arr[5], represents length of 6th wire
Output:
68
Example 2:
Input:
4 -> Value of N, represents size of Arr
12 -> Value of Arr[0], represents length of 1st wire
2 -> Value of Arr[1], represents length of 2nd wire
2 -> Value of Arr[2], represents length of 3rd wire
5 -> Value of Arr[3], represents length of 4th wire
Output:
34
Solution: In c++
#include
using namespace std;
struct MinHeap {
unsigned size;
unsigned capacity;
int* harr;
};
struct MinHeap* createMinHeap(unsigned capacity)
{
struct MinHeap* minHeap = new MinHeap;
minHeap->size = 0;
minHeap->capacity = capacity;
minHeap->harr = new int[capacity];
return minHeap;
}
void swapMinHeapNode(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void minHeapify(struct MinHeap* minHeap, int idx)
{
int smallest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left size
&& minHeap->harr[left] harr[smallest])
smallest = left;
if (right size
&& minHeap->harr[right] harr[smallest])
smallest = right;
if (smallest != idx) {
swapMinHeapNode(&minHeap->harr[smallest], &minHeap->harr[idx]);
minHeapify(minHeap, smallest);
}
}
int isSizeOne(struct MinHeap* minHeap)
{
return (minHeap->size == 1);
}
int extractMin(struct MinHeap* minHeap)
{
int temp = minHeap->harr[0];
minHeap->harr[0] = minHeap->harr[minHeap->size - 1];
--minHeap->size;
minHeapify(minHeap, 0);
return temp;
}
void insertMinHeap(struct MinHeap* minHeap, int val)
{
++minHeap->size;
int i = minHeap->size - 1;
while (i && (val harr[(i - 1) / 2])) {
minHeap->harr[i] = minHeap->harr[(i - 1) / 2];
i = (i - 1) / 2;
}
minHeap->harr[i] = val;
}
void buildMinHeap(struct MinHeap* minHeap)
{
int n = minHeap->size - 1;
int i;
for (i = (n - 1) / 2; i >= 0; --i)
minHeapify(minHeap, i);
}
struct MinHeap* createAndBuildMinHeap(int len[], int size)
{
struct MinHeap* minHeap = createMinHeap(size);
for (int i = 0; i harr[i] = len[i];
minHeap->size = size;
buildMinHeap(minHeap);
return minHeap;
}
int minCost(int len[], int n)
{
int cost = 0;
struct MinHeap* minHeap = createAndBuildMinHeap(len, n);
while (!isSizeOne(minHeap)) {
int min = extractMin(minHeap);
int sec_min = extractMin(minHeap);
cost += (min + sec_min);
insertMinHeap(minHeap, min + sec_min);
}
return cost;
}
int main()
{
int n;
cin >> n;
int arr[n];
for(int i = 0; i > arr[i];
int size = sizeof(arr) / sizeof(arr[0]);
cout << minCost(arr, size);
return 0;
}
Also Checkout