0 like 1 dislike
2,051 views
| 2,051 views

0 like 0 dislike
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
by Expert (107,880 points)
0 like 0 dislike

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';
}```
by Expert (107,880 points)
0 like 0 dislike
```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 << " ";
}```
by Expert (107,880 points)
0 like 0 dislike
```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;
}```
by Expert (107,880 points)
edited