TCS NQT Question Solve | 12 Sep | Slot 2 (V) | Codewindow.in

 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 &gt;&gt; n;
    int arr[n];
    for(int i = 0; i &gt; arr[i];
    }
    for(int i = 0; i &lt; 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 &lt; n; i++)
    {
        cout &lt;&lt; arr[i] &lt;&lt; &quot; &quot;;
    }
}

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-&gt;size = 0;
    minHeap-&gt;capacity = capacity;
    minHeap-&gt;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
    &amp;&amp; minHeap-&gt;harr[left] harr[smallest])
    smallest = left;
    if (right size
    &amp;&amp; minHeap-&gt;harr[right] harr[smallest])
    smallest = right;
    if (smallest != idx) {
    swapMinHeapNode(&amp;minHeap-&gt;harr[smallest], &amp;minHeap-&gt;harr[idx]);
    minHeapify(minHeap, smallest);
    }
}
int isSizeOne(struct MinHeap* minHeap)
{
    return (minHeap-&gt;size == 1);
}
int extractMin(struct MinHeap* minHeap)
{
    int temp = minHeap-&gt;harr[0];
    minHeap-&gt;harr[0] = minHeap-&gt;harr[minHeap-&gt;size - 1];
    --minHeap-&gt;size;
    minHeapify(minHeap, 0);
    return temp;
}
void insertMinHeap(struct MinHeap* minHeap, int val)
{
    ++minHeap-&gt;size;
    int i = minHeap-&gt;size - 1;
    while (i &amp;&amp; (val harr[(i - 1) / 2])) {
    minHeap-&gt;harr[i] = minHeap-&gt;harr[(i - 1) / 2];
    i = (i - 1) / 2;
}
minHeap-&gt;harr[i] = val;
}
void buildMinHeap(struct MinHeap* minHeap)
{
    int n = minHeap-&gt;size - 1;
    int i;
    for (i = (n - 1) / 2; i &gt;= 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-&gt;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 &gt;&gt; n;
    int arr[n];
    for(int i = 0; i &gt; arr[i];
    int size = sizeof(arr) / sizeof(arr[0]);
    cout &lt;&lt; minCost(arr, size);
    return 0;
}

Also Checkout

Recent Posts

Leave a Comment

Your email address will not be published. Required fields are marked *