Placements '24: Resources & Advice

Competitive Programming & DSA

No suprise, this by far is the most important part that you need to focus on. Don’t start at the last minute, and try to inculcate the habit of solving questions and discussing with your peers early on.

• Give contests regularly! Codeforces is the best platform for upsolving as well as giving contests. Many companies known for difficult tests often give direct restatements of the problems from here. Codeforces blogs on topics are great too!
• In the final month leading to placement OAs, I also started giving LeetCode, AtCoder, and Codechef contests. I absolutely love AtCoder Beginner contests, have grown acustomed to the LeetCode ones, and hate Codechef. But they all have their own charm, and you should try them all to see which one you like the best.
• The CSES problem set is a gold mine that is often overlooked. I personally used it in two manners:
  • Solving it periodically to ensure that I know the basics of a topic. Many questions from the same are used as subproblems in other problems, and the general solving techniques that I picked up from here helped me a lot. There have been many a times when I was unable to solve some LC questions, and then found articles and solutions of the same building on some CSES problems.
  • Resubmitted some of the common problems before the online assessments to ensure that I my brain has not rotted from using all the templates and Co-Pilot suggestions during the regular CP contests.
• CP Algorithms is my go to resource for templates & intial understanding of a topic. The explanations are crystal clear, all accompanied by code snippets, common extensions of the problems as well as recommened problems. I would not recommed using it as a question source, but definitely for the theory and implementation snippets.
• The infamous Dynamic Programming Atcoder List is a must read for all the DP problems. I would recommend solving the problems on your own first, and then looking at the solutions to see if you can improve your code or if there is a better way to solve the problem. It is probably the best curated introductory list of DP problems of the most common types.
• This is a list of Leetcode Problems that I had curated throught my placements. Some of these problems have been directly asked in OAs, and others are my favourite because of the concepts they teach. They are strictly more from a CP point of view and not DSA, so they may not be entirely useful for interview preparation.

Core Computer Science Concepts

These concepts take the most time, and are often the deciding factors in a low-medium difficulty online assesement where a large majority of the students are able to solve the problems. My two cents: don’t skip these topics or keep them for the last. Learn them early on, and maintain conscise notes. Then as the placement or intern season approaches, make a habit of spending 30-45 minutes daily to solve MCQs related to these topics.

GFG is probably the only resource you need for these MCQs. It is very common for the companies to directly pick questions from here, and the explanations are also very good.

Here are also some conscise notes that I started maintainging as I solved these MCQs, as well as from the questions I saw in my online assements and that of my seniors. I have no plans of updating them, and they probably won’t make any sense if you haven’t studied the topic first. But if you have, they might be a good refresher and help you in remembering some important or lesser known points, and getting those ‘tricky’ questions right.

CPP Topics

When preparing for interviews, these are some common topics that I found to be the favourite amoung interviewers, specially for C++ developer roles or low level system roles. Learn CPP is a great resource for these topics and learning C++ nitigrities in general, but it you are short on time (like I was), these are some topics that you should focus on:

• Void Pointers

  • How to figure out if a void * pointer is pointing to an integer or a character array?
  • How to figure out if a void * pointer is allocated on the stack or the heap?

• Smart Pointers & Move Semantics in CPP

  Quick Notes

  • How do these work under the hood and why do we need them?

    We need smart pointers because raw pointers are error prone and can lead to memory leaks. Smart pointers are objects that manage the memory of a pointer, and automatically free the memory when the object goes out of scope. They are also exception safe, and can be used in containers and classes.

  • std::unique_ptr

    • Allocated on the stack, and eventually calls delete on the pointer when it goes out of the scope.
    • The copy assignment operator and the copy constructor are deleted, and thus it can’t be copied. You need to use std::move to transfer the ownership of the pointer.
    • Smart enough to differentiate between scalar delete or array delete, but is advised to use with std::vector or std::array instead of raw arrays.
    • Use std::make_unqiue to create a std::unique_ptr instead of using new directly. It calls the constructor of the object and returns a std::unique_ptr to the object. This can lead to better exception safety and is more readable.

  • std::shared_ptr

    • Keeps track of how many std::shared_ptr are pointing to the same object, and deletes the object when the last std::shared_ptr goes out of scope.
    • Always make a copy of an existing std::shared_ptr if you need more than one std::shared_ptr pointing to the same resource, otherwise each of them might think that it the sole owner, and drop the memory when it goes out of scope.
    • std::make_shared is also available, and is recommended to use instead of new for the same reasons as std::make_unique.
    • Internally, it uses a control block to keep track of the number of std::shared_ptr pointing to the same resource, and the resource itself. The control block is allocated on the heap, and the resource is allocated on the heap as well.

  • std::weak_ptr

  • Difference between references and pointers in C++. When to use which and how they affect the safety as well as the usability of the code?

  • Multithreading in C++

    • Write a web-crawler using multithreading in C++ that can crawl multiple pages at the same time. The crwaler should work in a BFS like manner, and we should be able to configure the maximum depth of the crawler.

    We have assumed the existence of a HtmlParser class that has a method getUrls that returns a list of URLs on the page. The crawl method should return a list of all the URLs that the crawler has visited.

    1
    class Solution
    2
    {
    3
    public:
    4
        vector<string> crawl(string startUrl, HtmlParser htmlParser, int maxDepth = 100)
    5
        {
    6
            unordered_set<string> seen{startUrl};
    7
            string hostname = getHostname(startUrl);
    8
    
    9
            // Store the URL and its depth in the queue
    10
            queue<pair<string, int>> q;
    11
            q.push({startUrl, 0});
    12
    
    13
            vector<thread> threads;
    14
            mutex mtx; // Mutex to guard seen and q
    15
            condition_variable cv;
    16
    
    17
            // Worker function which continuously fetches URLs from the queue and processes them
    18
            // Each worker DOES NOT process one complete depth as it may not be optimal
    19
            auto worker = [&]()
    20
            {
    21
                while (true)
    22
                {
    23
                    pair<string, int> current;
    24
    
    25
                    {
    26
                        unique_lock<mutex> lock(mtx); // Need deferred lock to use cv.wait_for
    27
                        // cv.wait_for is used to avoid spurious wakeups
    28
                        cv.wait_for(lock, 30ms, [&]()
    29
                                    { return !q.empty(); });
    30
    
    31
                        // Kill the worker if the queue is empty
    32
                        if (q.empty())
    33
                            return;
    34
    
    35
                        current = q.front();
    36
                        q.pop();
    37
                    }
    38
    
    39
                    // Parse the URL
    40
                    string url = current.first;
    41
                    int depth = current.second;
    42
    
    43
                    if (depth >= maxDepth)
    44
                        continue;
    45
    
    46
                    vector<string> urls = htmlParser.getUrls(url);
    47
    
    48
                    for (const auto &nextUrl : urls)
    49
                    {
    50
                        // Check if URL is within the same domain
    51
                        if (nextUrl.find(hostname) != string::npos)
    52
                        {
    53
                            lock_guard<mutex> lock(mtx);
    54
                            if (seen.insert(nextUrl).second)
    55
                            {
    56
                                q.push({nextUrl, depth + 1});
    57
                                cv.notify_all();
    58
                            }
    59
                        }
    60
                    }
    61
                }
    62
            };
    63
    
    64
            // Get the number of hardware threads and create that many threads
    65
            for (int i = 0; i < thread::hardware_concurrency(); ++i)
    66
                threads.emplace_back(worker);
    67
    
    68
            for (auto &t : threads)
    69
                t.join();
    70
    
    71
            return {seen.begin(), seen.end()};
    72
        }
    73
    
    74
    private:
    75
        // Extract hostname from the URL
    76
        // URL is assumed to be of the form "http://hostname/..."
    77
        string getHostname(const string &url)
    78
        {
    79
            return url.substr(0, url.find('/', 7));
    80
        }
    81
    };

PS

Computer networks in also usually included in CS concepts, but I decided to skip them in the interest of time. A very few companies ask questions from this topic (like Cisco) and for very specific roles (like Network Engineer). You might want to read about them if you are interested in such roles.