Question: Capital One, Interview Experience , oncampus
0
Entering edit mode

## Capital One Interview experience

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

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

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:

1. 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.
2. You should know in detail about the your projects and tech stack used to develop them.
0
Entering edit mode

# Solution to Coding Round Question 1

## Analysis

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 &lt; &lt; 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)`.

## Code

``````#include&lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;

int main()
{
int n,m; cin &gt; &gt; n &gt; &gt; m;
vector&lt;ll&gt; restricted(n,0);
while(m--)
{
int x,y; cin &gt; &gt; x &gt; &gt; y;
x--,y--;
restricted[x] += 1LL &lt; &lt; y;
}

vector&lt;ll&gt; dp(1 &lt; &lt; n,0);
dp[0] = 1;

for(int employee = 0; employee&lt;n; employee++)
{
{
for(int chair=0; chair&lt;n; chair++)
{
if((restricted[employee] &gt; &gt; chair)&amp;1) continue;
}
}
}
cout &lt; &lt; dp.back() &lt; &lt; "\n";
return 0;
}
``````
0
Entering edit mode

# Solution to interview Q-1

## Approach and C++ code

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&lt;int,  list&lt;pair&lt;int, int&gt;&gt;::iterator&gt; m_map; //m_map_iter-&gt;first: key, m_map_iter-&gt;second: list iterator;
list&lt;pair&lt;int, int&gt;&gt; m_list;                               //m_list_iter-&gt;first: key, m_list_iter-&gt;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-&gt;second); //move the node corresponding to key to front
return found_iter-&gt;second-&gt;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-&gt;second); //move the node corresponding to key to front
found_iter-&gt;second-&gt;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

0
Entering edit mode

# Solution to interview Q-1

## Approach and C++ code

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&lt;int,  list&lt;pair&lt;int, int&gt;&gt;::iterator&gt; m_map; //m_map_iter-&gt;first: key, m_map_iter-&gt;second: list iterator;
list&lt;pair&lt;int, int&gt;&gt; m_list;                               //m_list_iter-&gt;first: key, m_list_iter-&gt;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-&gt;second); //move the node corresponding to key to front
return found_iter-&gt;second-&gt;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-&gt;second); //move the node corresponding to key to front
found_iter-&gt;second-&gt;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