Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
697 views
in Interview-Experiences by Expert (30,360 points) | 697 views

1 Answer

0 like 0 dislike
INTERN

1. Consider a binary tree of N vertices such that children of node k are 2*k and 2*k+1. Vertex 1 is the root of the tree and each node has an integer value associated with it.

Such a tree may be represented as an array of N integers by writing down values from consecutive nodes.

The tree can be represented as an array [-1, 7, 0, 7, -8].
A node is said to be at level x if the length of the shortest path between that node and root x-1. So, the root is at level 1, the children of root are at level 2, and so on.

Your task is to find the smallest level number x such that sum of all nodes at level x is maximal.
Examples: Given array A such that: A[0]=-1, A[1]=7, A[2]=0, A[3]=7, A[4]=-8. The function should return 2.

Input : [-1, 7, 0, 7, -8]
Output : 2
 

 

 

#include <iostream>

using namespace std;

int solution(int a[], int n)

{

    int max = -1;

    int temp = 0;

    for (int i = 0; i < n; i = i + 2) {

        if (i == 0)

            temp = a[i];

        else

            temp = a[i] + a[i - 1];

        if (temp > max)

            max = i;

    }

    return max;

}

  

int main()

{

    int a[4];

    a[0] = -1, a[1] = 7, a[2] = 0, a[3] = 7, a[4] = -8;

    int size = 4;

    cout << solution(a, size);

}


2. Imagine you have a special keyboard with all keys in a single row. The layout of characters on a keyboard is denoted by a string S1 of length 26. S1 is indexed from 0 to 25. Initially, your finger is at index 0. To type a character, you have to move your finger to the index of the desired character. The time taken to move your finger from index i to index j is |j-i|, where || denotes absolute value.

Write a function solution(), that given a string S1 that describes the keyboard layout and a string S2, returns an integer denoting the time taken to type string S2.

Examples:

S1 = abcdefghijklmnopqrstuvwxyz

S2 = cba

Input : S1 = abcdefghijklmnopqrstuvwxyz, S2 = cba
Output : 4
 

 

 

#include <bits/stdc++.h>

using namespace std;

  

int solution(string& s1, string& s2)

{

    map<char, int> dict;

    for (int i = 0; i < 26; i++) {

        dict[s1[i]] = i;

    }

    int ans = 0;

    int prev = 0;

    for (int i = 0; i < s2.length(); i++) {

        ans = ans + abs(dict[s2[i]] - prev);

        prev = dict[s2[i]];

    }

    return ans;

}

  

int main()

{

    string s1 = "abcdefghijklmnopqrstuvwxyz";

    string s2 = "cba";

    cout << solution(s1, s2);

}
by Expert (30,360 points)