Question

De-Shaw | OA Coding Questions and Solutions | Set - 16 | SDE - 2 | 2022

Answer 1

Round was on Hackerrank platform with WebCam required.
Test Format:
3 Coding questions + 20 MCQs (7 questions based on DS,OS, SQL,Networking and 13 aptitude questions)
Duration: 1 hour 20 minutes in total, but each coding question and each section had different time allocated.
SECTION 1 : 3 Coding questions
Instruction: You cannot revisit previous coding question if you've moved to next question(with or without submitting) or if time allocated to that question is completed.

A fancy statement given for this problem https://leetcode.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k/ . Time given to solve: 15 minutes
Another fancy statement was given but the problem boiled down to:
Given an input matrix of sizen*n filled with integers (not necessarly sorted). From this input matrix, another matrix of same size n*n is generated, which is spirally sorted (input matrix elements are sorted and then elements are inserted in spiral order in matrix). Then you are given Q queries having target values to be searched. Have to search this target in spirally sorted matrix which we created and return the element present in input matrix at the searched index.
Example:
Input matrix:
1 4 5
2 3 9
6 8 7
Input queries: [3 , 6, 7, 8 , 2]
Output: [ 5, 8 , 6, 2 , 4]
Explanation:
Spirally sorted matrix created:
1 2 3
8 9 4
7 6 5
Query1: index of 3 in spirally sorted matrix is [0,2], corresponding element in input matrix is 5.
Query2: index of 6 in spirally sorted matrix is [2,1], corresponding element in input matrix is 8 and so on.
Time given to solve was: 15 min
Long story was given but in short problem was:
Given a string having numbers from 0-9. Let numeric value of this string be "num". Find number of ways to get a string containing all digits from 0-9 by performing following operations at most once.
a) Replace the string with number we get by dividing "num" by power(10 ,k ) for any k.
b) Replace the string with remainder of "num' on division with power(10,k) for any k.
Example input: "121234567890"
Output: 3
Explanation:
way1 : No operation, string already contains all digits from 0-9
way 2: second operation with k=10, remainder with power(10,10) is "1234567890" which contains all digits
way 3: second operation with k=11, remainder with power(10,11) is "121234567890" which contains all digits.
Input string size range: [1,1e5]
Time given to solve : 30 minutes
SECTION 2: DS, OS, Networking, DBMS, CS fundamental MCQs
Time to solve 7 question was 7 minutes.

SECTION 3: Aptitude MCQs
13 minutes for 13 questions

Answer 2

Q3 solution: By keeping track of substrings with all chars

Explanation:

We will check if all characters are present in the string.
If not, return 0, else increment answer by 1 (no modifications
required).

Quotient means removing suffix.
Remainder means removing prefix.
Let us assume a substring s[mini...maxi] with all the characters from 0 to 9
present.

We can remove prefixes in 0 to mini - 1 ways = mini ways
We can remove suffixes in maxi + 1 to n - 1 ways = n - 1 - maxi ways
Both operation can be applied (mini) * (n - 1 - maxi) ways
Repeat same for all disjoint substrings with all the characters. Extra care needs to
be taken for start and end.

#include<bits/stdc++.h>
using namespace std;

// TC: O(n), SC: O(n)
int noOfCombinations(string s) {
    int n = s.length();
    int ret = 0;
    if ((set<char>(s.begin(), s.end())).size() == 10) ++ret; // no modifications reqd
    else return 0;
    vector<array<int, 2>> pos;
    unordered_map<char, int> last;
    for (int i = 0; i < n; ++i) {
        last[s[i]] = i;
        if (last.size() == 10) { // all chars exist
            int mini = n + 1, maxi = -1;
            for (auto x: last) {
                mini = min(x.second, mini);
                maxi = max(x.second, maxi);
            }
            pos.push_back({mini, maxi});
            last.clear();
        }
    }
    int start = 0, end = n - 1;
    if (pos.size() > 1) {
        end = pos[1][0];
    }
    for (int i = 0; i < (int)pos.size(); ++i) {
        auto segment = pos[i];
        // both quotient and remainder
        int prefixLength = segment[0] - start, suffixLength = end - segment[1];
        ret += prefixLength * suffixLength;
        // only remainder
        ret += prefixLength;
        // only quotient
        ret += suffixLength;
        start = segment[0];
        if (i < (int)pos.size() - 1) {
            end = pos[i + 1][0];
        } else {
            end = n - 1;
        }
    }
    return ret;
}

int main() {
    cout << noOfCombinations("121234567890") << '\n';
}

Answer 3

Q2 solution: Using a map

#include<bits/stdc++.h>
using namespace std;

// TC: O(n * n * log(n)), SC: O(n * n)
vector<int> checkElement(vector<vector<int>> nums, vector<int> queries) {
    int n = nums.size();
    vector<int> elems;
    for (auto v: nums) {
        for (auto x: v) {
            elems.push_back(x);
        }
    }
    sort(elems.begin(), elems.end());
    unordered_map<int, array<int, 2>> idx2pos;
    // taken from https://csposts.com/posts/generate-spiral-matrix
    int rowStart = 0, rowEnd = n - 1, columnStart = 0, columnEnd = n - 1;
    int cur = 0;
    while (rowStart <= rowEnd and columnStart <= columnEnd) {
        // traversing from top left to top right (first row in the layer)
        for (int c = columnStart; c <= columnEnd; ++c) {
            idx2pos[elems[cur++]] = {rowStart, c};
        }
        ++rowStart;
        // traversing from top right to bottom right (last column in the layer)
        for (int r = rowStart; r <= rowEnd; ++r) {
            idx2pos[elems[cur++]] = {r, columnEnd};
        }
        --columnEnd;
        // traversing from bottom right to bottom left (last row in the layer)
        for (int c = columnEnd; c >= columnStart; --c) {
            idx2pos[elems[cur++]] = {rowEnd, c};
        }
        --rowEnd;
        // traversing from bottom left to top left (first column in the layer)
        for (int r = rowEnd; r >= rowStart; --r) {
            idx2pos[elems[cur++]] = {r, columnStart};
        }
        ++columnStart;
    }
    vector<int> ret;
    for (int q: queries) {
        // position of q in the spiral matrix
        auto spiralPos = idx2pos[q];
        // element in `spiralPos` in the original matrix
        ret.push_back(nums[spiralPos[0]][spiralPos[1]]);
    }
    return ret;
}

int main() {
    auto ret = checkElement({
        {1, 4, 5},
        {2, 3, 9},
        {6, 8, 7}
    }, {3, 6, 7, 8, 2});
    for (int x: ret) cout << x << " ";
}

Answer 4

Q1 solution: Similar to coin change but the greedy method can be applied for Fibonacci

int findMinFibonacciNumbers(int k) {
        vector<int> fib;
        int a = 1, b = 1;
        fib.push_back(1);
        fib.push_back(1);
        int target = k + 1;
        int c = 0;
        while(c <= target) {
            c = a + b;
            a = b;
            b = c;
            fib.push_back(c);
        }
        int n = (int)fib.size() - 1;
        int ans = 0;
        while(k > 0) {
            ans += k / fib[n];
            k %= fib[n];
            --n;
        }
        return ans;
}