2.8 years ago

Anonymous • 0

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.

12 months ago

Ayush Gangwani 1.3k

New Delhi

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 < < 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<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;
}

2.5 years ago

hardik kapoor 140

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<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

2.5 years ago

hardik kapoor 140

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<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