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

Click here to Practice

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

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 mask=0; mask&lt;(1LL &lt; &lt; n); mask++)
        {
            if(__builtin_popcount(mask) != employee) continue;
            for(int chair=0; chair&lt;n; chair++)
            {
                if((mask &gt; &gt; chair)&amp;1) continue;
                if((restricted[employee] &gt; &gt; chair)&amp;1) continue;
                dp[mask + (1LL &lt; &lt; chair)] += dp[mask];
            }
        }
    }
    cout &lt; &lt; dp.back() &lt; &lt; "\n";
    return 0;
}
ADD COMMENTlink 16 months ago Ayush Gangwani 1.1k
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

ADD COMMENTlink 16 months ago hardik kapoor 130
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

ADD COMMENTlink 16 months ago hardik kapoor 130

Login before adding your answer.

APPLY NOWSimilar Posts
Loading Similar Posts