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

3 months ago

Ayush Gangwani 1.2k

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

21 months ago

hardik kapoor 130

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

21 months ago

hardik kapoor 130

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