Question: Sprinklr | SDE-1 | On Campus | 28th November 2020
3
Entering edit mode
Absolutely love TJO! Its super helpful. Hardest question was repeated as it is from TJO.
Here is contribution from my side, please do upvote and I'll keep posting =)
This round just ended now.

Format

  • 90 minutes
  • 6 MCQ with negative marks (+6/-2)
  • 3 Coding problems

Coding Problem 1

You start at (1, 1). You need to tell if you can reach to cell (x, y).
The only step that you can take is this: If you are at (a, b) you can move to either (a+b, b) or (a, a+b).

Coding Problem 2

You are given N shops numbered 1 to N.
There are M people who numbered 1 to M.
ith person visits [Li, Ri] inclusively.

Print out number of three shops that were most frequently visited. If two shops had same number of visitors then print the shop with lower number.

Coding Problem 3

You are given N x M grid. In each cell either it has tower of height = 1, denoted by '*' character or it is plain denoted by '.'
It rains heavily, you need to find out number of cells which have water trapped in it.


MCQs

  1. Another simple recursion for Power Question. answer is O(N)
  2. Another Linked list implementation, asked which data structure is coded? Answer was "Stack"

ADD COMMENTlink 4.1 years ago utopia • 140
4
Entering edit mode
Even though time for test was 90 minutes, I finished complete test in 20minutes :D
Two of 3 coding problems were directly from TJO and AlgoUniversity classes, while 3rd was variation of AlgoUniversity assignment problem. MCQs were easy too, except Q1 which wasn't clear.

Coding Problem 1

I saw this exact question previously on TJO premium, thank god! Wouldn't have solved this hard problem by myself otherwise.
Maybe @Admin User-1 can link the relevant link containing detailed explanation.Accepted
#include 
using namespace std;
int TestCases, L, R;
int main() {
	cin >> TestCases;
	while (TestCases--) {
		cin >> L >> R;
		cout << (__gcd(L, R)==1?"Yes":"No") << "\n";
	}
}

Coding Problem 2

A very cool trick +1, -1, with one line code as taught in AlgoUniversity class of Range Query. I will add code later tonight. Simple idea was to increase A[L]++ and A[R+1]++. Then precompute from left to right just like prefix sum and you get at each A[i] number of visitors at ith shop.Accepted
int n, m, shops[3000003], L, R;
int main() {
	cin >> TestCases;
	while (TestCases--) {
		cin >> n >> m;
		for (int i = 0; i <= n; i++) shops[i] = 0;
		for (int i = 0; i < m; i++) cin >> L >> R, shops[L]++, shops[++R]++;
		for (int i = 1; i <= n; i++) shops[i] += shops[i-1], ord.pb(mp(-shops[i],i));
		sort(shops.begin(), shops.end());
		for (int i = 0; i < 3; i++) reord.insert(shops[i].second);
		for (auto c: reord) cout << c << " ";cout << endl;
	}
	return 0;
}

Coding Problem 3

Got it Accepted with simple DFS.Accepted
#include 

using namespace std;

vector g[1000010];
vector vis[1000010];
int n, m, area, ans = 0;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
bool dry = false;

bool check(int x, int y) {
	if (min(x, y) < 0 or x >= n or y >= m) return false;
	return true;
}

void dfs(int x, int y) {
	vis[x][y] = true;
	++area;
	for (int i = 0; i < 4; i++) {
		int a = x+dx[i], b = y+dy[i];
		if (check(a, b) == false) {
			dry = true;
		} else {
			if (vis[a][b] == false and g[a][b]=='.') dfs(a, b);
		}
	}
}

int main() {
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			g[i].push_back('.');
			vis[i].push_back(false);
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> g[i][j];
			vis[i][j] = false;
		}
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (vis[i][j] == false) {
				dry = false;
				area = 0;
				if (vis[i][j] == false and g[i][j] == '.') dfs(i, j);
				if (dry == false) ans += area;
			}
		}
	}
	cout << ans << "\n";
}
ADD COMMENTlink 4.1 years ago utopia • 140
Entering edit mode
1
Thats correct. Q1 was previously asked in Cure.fit. Detailed solution why GCD solution works is given this link.
http://thejoboverflow.com/p/p49/#p61
ADD REPLYlink 4.0 years ago
admin
1.6k

Login before adding your answer.

Similar Posts
Loading Similar Posts