Entering edit mode

**Coding Round**

There were 3 questions in coding round, 2 DSA and 1 SQL question. The level of question was medium.

**DSA Questions**

**Question 1**

Click here to Practice

Submit Problem to OJ

There are N employees and N chairs. You are given M pair of integers (X,Y) where (X,Y) denotes that employess X cannot sit on seat Y. You have to tell number of arrangements of N employees on N chairs such that all constraints satisfy.

- 1 <= N <= 20
- 1 <= M <= 100
- 1 <= X,Y <= N

**Question 2**

You are given a string s of integer characters.You are also given an integer K and Q queries. Every query contains an integer x. For each query you have tell whether there exists any substring in s lets say s_substr which on divided by integer K gives reminder as x. If s_substr%K = x then print "YES" else "NO".

- 1 <= |s| <= 100000
- 1 <= |K| <= 1e9
- 1 <= |Q| <= 100000
- 0 <= S[i] <= 9

**Interview**

**Case study round:**

This was an pen paper round. We were given 2 DSA questions and were asked to write code and logic for it.

Q1 - LRU cache

Click here to Practice

Submit Problem to OJ

Q2 - Find number of triangles in a graph

**Round 1** - This round was based on the previous case study round and resume. I was asked question from the problem solved in case study round. Next I was asked questions from my resume, recent project and tech stack used, few detailed question on tech stack. I explained them the system design, work of the system and what difficulties I faced while creating that project and how did I overcome them. Overall this round went well and I was shortlisted for next round.

**Round 2** - In this round I was asked questions regarding 2 of my projects in resume. One was my recent internship and one of the course project. Overall I explained everything about these projects i.e. there system design, tech stack used, difficulties faced while creating project and how did I overcome it. Overall this round also went well.

**Verdict - Selected**

**Few tips for the interview**:

- You should know the concept behind the logic of DSA questions. They can ask conditional question like if you are allowed to use set in c++. Then how will you solve it.
- You should know in detail about the your projects and tech stack used to develop them.

Entering edit mode

The constraints hint at a dp with bitmasking solution. Lets iterate on the employees keeping a bitmask for the available chairs (we could do the other way around without affecting the complexity of the solution). Let `dp[i][mask]`

denote the number of ways of arrangements of the first `i`

employees and `mask`

denote the bitmask for the available chairs (the `j-th`

chair is available if the `j-th`

bit in `mask`

is `0`

and unavailable if its `1`

).

We can do the following dp tranisition:

`dp[i+1][mask | (1 < < j)] += dp[i][mask]`

provided the`j-th`

bit is not set in`mask`

and the`j-th`

chair is not restricted for the`i-th`

person.

Thus we can solve the problem in a time complexity of `O(N^2 * 2^N + M)`

and space complexity of `O(2^N + M)`

.

```
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
int n,m; cin > > n > > m;
vector<ll> restricted(n,0);
while(m--)
{
int x,y; cin > > x > > y;
x--,y--;
restricted[x] += 1LL < < y;
}
vector<ll> dp(1 < < n,0);
dp[0] = 1;
for(int employee = 0; employee<n; employee++)
{
for(int mask=0; mask<(1LL < < n); mask++)
{
if(__builtin_popcount(mask) != employee) continue;
for(int chair=0; chair<n; chair++)
{
if((mask > > chair)&1) continue;
if((restricted[employee] > > chair)&1) continue;
dp[mask + (1LL < < chair)] += dp[mask];
}
}
}
cout < < dp.back() < < "\n";
return 0;
}
```

Entering edit mode

The LRU cache is a very standard problem, following is the code with comments which explains everything very nicely

```
class LRUCache{
size_t m_capacity;
unordered_map<int, list<pair<int, int>>::iterator> m_map; //m_map_iter->first: key, m_map_iter->second: list iterator;
list<pair<int, int>> m_list; //m_list_iter->first: key, m_list_iter->second: value;
public:
LRUCache(size_t capacity):m_capacity(capacity) {
}
int get(int key) {
auto found_iter = m_map.find(key);
if (found_iter == m_map.end()) //key doesn't exist
return -1;
m_list.splice(m_list.begin(), m_list, found_iter->second); //move the node corresponding to key to front
return found_iter->second->second; //return value of the node
}
void put(int key, int value) {
auto found_iter = m_map.find(key);
if (found_iter != m_map.end()) //key exists
{
m_list.splice(m_list.begin(), m_list, found_iter->second); //move the node corresponding to key to front
found_iter->second->second = value; //update value of the node
return;
}
if (m_map.size() == m_capacity) //reached capacity
{
int key_to_del = m_list.back().first;
m_list.pop_back(); //remove node in list;
m_map.erase(key_to_del); //remove key in map
}
m_list.emplace_front(key, value); //create new node in list
m_map[key] = m_list.begin(); //create correspondence between key and node
}
};
```

Time complexity : `O(1)`

for Put and Get

Entering edit mode

The LRU cache is a very standard problem, following is the code with comments which explains everything very nicely

```
class LRUCache{
size_t m_capacity;
unordered_map<int, list<pair<int, int>>::iterator> m_map; //m_map_iter->first: key, m_map_iter->second: list iterator;
list<pair<int, int>> m_list; //m_list_iter->first: key, m_list_iter->second: value;
public:
LRUCache(size_t capacity):m_capacity(capacity) {
}
int get(int key) {
auto found_iter = m_map.find(key);
if (found_iter == m_map.end()) //key doesn't exist
return -1;
m_list.splice(m_list.begin(), m_list, found_iter->second); //move the node corresponding to key to front
return found_iter->second->second; //return value of the node
}
void put(int key, int value) {
auto found_iter = m_map.find(key);
if (found_iter != m_map.end()) //key exists
{
m_list.splice(m_list.begin(), m_list, found_iter->second); //move the node corresponding to key to front
found_iter->second->second = value; //update value of the node
return;
}
if (m_map.size() == m_capacity) //reached capacity
{
int key_to_del = m_list.back().first;
m_list.pop_back(); //remove node in list;
m_map.erase(key_to_del); //remove key in map
}
m_list.emplace_front(key, value); //create new node in list
m_map[key] = m_list.begin(); //create correspondence between key and node
}
};
```

Time complexity : `O(1)`

for Put and Get