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 about OOPS 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.

Database Management, SQL, and Operating Systems are a much do if you are from a circuital branch. The questions that are asked are usually basic and standard for the most part, but you need to be aware about them and have a good understanding of the concepts. As usual, MCQS from GFG to test your mettle and YouTube videos of any online educator that you like would be a good start.

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. Many of my friends who just covered some basics topics like TCP/IP, OSI model, and HTTPS, were able to answer “most” of the netwroking questions in the OAs as well as the interviews.

Puzzles & Quant Resouce

Other than the above topics, puzzles and probability questions are also very common in OAs & interviews alike. The good news about them is that they have been more or less standardized, so you can find a lot of resources online to practice them. Brainstellar is a must do if you are aiming for Quant roles or roles in major fin-tech giants (Making a habit of 30 minutes daily practice is a good idea). GeeksforGeeks is also a good resource for these questions, and you can find a lot of them in the Puzzles section of the website.

If you want to dwell even deeper into the same, A Practical Guide To Quantitative Finance Interviews by Xinfeng Zhou, better known as the “Green Book” is the most trusted source. I never managed to read it, but the introduction chapter on puzzles is something that I really enjoyed. Quant Guide (AKA the Leetcode for Quant) and Puzzled Quant are some other resources that I have heard good things about, but never used myself.

CPP Topics

WARNING: This section is probably not for you unless you are aiming for a dedicated C++ developer role or a low level role like system programming. If you are aiming for a general SDE role, you should be fine with the basics of C++ and the topics that are covered in the DSA section.

Learn CPP is a great resource for these topics and learning C++ nitigrities in general. The Modern CPP Tutorial and CMU Databases’s 15445 Bootcamp are also some resources that I found post the placement season that I wish I had known about earlier.

Do spend good time on learning about your language in general (apart from the typical competitive programming), and how it works under the hood. If you are short on time, I would recommend focusing on the following topics:

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