Duration: 105 mins
Questions: 3 DSA problems
Platform: HackerRank

Q1 - Area of Triangle
Given three sets of distinct coordinates that form a triangle, calculate the area of the triangle. At least one side of the triangle will be parallel to either the x-axis or the y-axis.

Example
x = [0, 3, 0]
y = [0, 5, 2]
Aligned by index, the 3 coordinates are [0,0], [3,5], [0,2]. The base of the triangle is 2, and the height is 3. The area of a triangle is (base * height)/2, so 3*2/2= 3. All resulting areas will be whole numbers.

Constraints
0 <= x[i], y[i] < 10^5

Sample Case 0
Sample Input
x = [0, 3, 6]
y = [0, 3, 0]
Sample Output
9
Explanation
The base has a length of 6, and the height is 3. The area is (6 * 3) / 2 = 9.

Sample Case 1
Sample Input
x = [0, 1, 0]
y = [0, 0, 2]
Sample Output
1
Explanation
The base of the triangle is 1 and the height is 2, so the area is (1 * 2) / 2 = 1.

long long getTriangleArea(vector<int> x, vector<int> y) {
    long long area = abs(
        (long long)x[0] * (y[1] - y[2]) +
        (long long)x[1] * (y[2] - y[0]) +
        (long long)x[2] * (y[0] - y[1])
    );

    return area >> 1;
}

Q2 - Simple Cipher
A simple cipher is built on the alphabet wheel which has uppercase English letters ['A'-'Z'] written on it. Given an encrypted string consisting of English letters ['A'-'Z'] only, decrypt the string by replacing each character with the kth character away on the wheel in the counter-clockwise direction. Counter-clockwise is the opposite direction in which the hands on a clock usually move. Z is 1 unit counter-clockwise from A.

Example
encrypted = 'VTAOG'
k = 2
Looking back 2 from 'V' returns 'T', from 'T' returns 'R', and so on. The decrypted string is 'TRYME'.

Constraints
1 <= |encrypted| <= 10^5
1 <= k <= 10^5
encrypted[i] <- ascii['A'-'Z']

Sample Case 0
Sample Input
encrypted = 'CDEF'
k = 2
Sample Output
ABCD
Explanation
Each character is replaced by the character k = 2 positions away in the counter-clockwise direction. 'C'->'A', 'D'->'B', and so on. The decrypted string is 'ABCD'.

Sample Case 1
Sample Input
encrypted = 'DGEO'
k = 3
Sample Output
ADBL
Explanation
Each character is replaced by the character k = 3 positions away in the counter-clockwise direction. 'D'->'A', 'G'->'D', and so on. The decrypted string is 'ADBL'.

string simpleCipher(string encrypted, int k) {
    int alphabetSize = 26;
    k %= alphabetSize;
    
    string ans;
    for(auto &ch: encrypted) {
        char og = (ch - 'A' - k + alphabetSize) % alphabetSize + 'A';
        ans += og;
    }
    
    return ans;
}

Q3 - Connected Groups
Relationships between people may be represented in a matrix as a series of binary digits. For example, the direct relationships for person 0 with persons 0 through 5 might be shown as 101100. This means that person 0 knows persons 0, 2 and 3, the indices of each of the 1 values. A relationship is transitive. In other words, if person 0 knows person 2 and person 2 knows person 3, then person 0 knows person 3 through person 2. A group is composed of all of the people who know one another, whether directly or transitively. Determine the number of groups represented in a matrix.

Example
Consider the following relationships matrix:
related = ['110', '110', '001']
Persons 0 and 1 are connected, while person 2 is not. There are 2 groups.

Constraints
1 <= n <= 300
0 <= i < n
|related| = n
Each related[i] contains a binary string of n zeros and ones. related is a square matrix.

Sample Case 0
Sample Input
related = ['1100', '1110', '0110', '0001']
Sample Output
2
Explanation
There are n = 4 people numbered related[0] through related[3]. There are 2 pairs who directly know each another: (related[0], related[1]) and (related[1], related[2]). Because a relation is transitive, the set of people {related[0], related[1], related[2]} is considered a single group. The remaining person, related[3], does not know any other people and is a separate group: (related[3]}. There are a total of 2 groups.

Sample Case 1
Sample Input
related = ['10000', '01000', '00100', '00010', '00001']
Sample Output
5
Explanation
No direct relationships are shown so there are 5 groups: {related[0]}, {related[1]}, {related[2]}, {related[3]}, and {related[4]}.

void dfs(int person, vector<string> &related, vector<bool> &visited) {
    visited[person] = 1;
    for(int friendIdx = 0; friendIdx < related.size(); friendIdx++) {
        if(related[person][friendIdx] == '1' and !visited[friendIdx]) {
            dfs(friendIdx, related, visited);
        }
    }
}

int countGroups(vector<string> &related) {
    vector<bool> visited(related.size());
    int ans = 0;

    for(int person = 0; person < related.size(); person++) {
        if(!visited[person]) {
            dfs(person, related, visited);
            ans++;
        }
    }

    return ans;
}