Friday, 27 March 2020

How to start with Competitive Programming?

So you want to start with Competitive Programming? Good, you’re at the right place :)

The following are the steps to help you get started.

Pick a language

Language is the most crucial thing for communicating ideas. An ideal language should be the one that can help you pass the time and space constraints. Python may not be the ideal solution here. Sure it involves a lot of built-in functions but one cannot deny it increases your time of execution putting an impact on CPU memory since it uses an interpreter for line by line execution.

So what to choose? As you can see below is a clear comparison between codes written in .py and .cpp. Surely it depends on the programmer’s ability to shorten code but not too much to create such a big difference. 




2 of the best programming languages known for competitive programming are C and C++. We would recommend C++ here. Both of them take less time of execution than Python but one cannot deny how C++ STL makes your life easier.

Start with Basic Problems

Start your journey by solving basic problems like how to find a prime number, the number of factors of a number, factorial of a number, find greatest/lowest among array, insert an integer into an array, string operations using ASCII values, the sum of the digits of a number, etc. You can find a bunch of such problems on SPOJ.

You might not realize the worth of solving these problems but practicing these more frequently could help you shorten the code than earlier which you used to right and help you save time. Additionally, you will learn how to write error-free code.

Learn Data Structures and Algorithms

Data Structures and Algorithms are going to be your biggest friends if you choose to make them! Not only in your Competitive Programming journey but also in your Placement Interviews.

And it’s super fun to learn them. Once you dive into it, you’ll enjoy the essence. You’ll be amazed at the scope of DSA usage from Google’s fastest search to quickest commute in Uber, DSA plays a role everywhere!

Hey, wait! Are you practicing?

Tried HackerRank? CodeChef? HackerEarth? Practice is highly important to understand the types of problems. Also, practice improves your question reading skills which can help you save time. Mathematics is super fun and you’ll be amazed to know how mathematical functions can be used to find solutions to such complex scenario problems.

As you finish the warm-up problems move on to implementations, strings, sorting, search, recursions, debugging and several other sections that’ll help you master the art of solving problems. 

The best part about these platforms is they not only help you prepare but also enhances the spirit of competition, the spirit of winning. One just cannot express the feeling of satisfaction when you get solving problems. The feeling which you get achieving the Gold badge is amazing! Nobody can take it from you, it’s yours!

Why not involve your friends?

In today’s era, nobody can complain of being not aware of current technology trends. If you’re ignoring this, you’re missing out on a lot my friend!

Practice Competitive with a group of friends or a community. Most colleges now have IEEE, CodeChef Chapters in their universities which are non-profit organizations that help increase technical awareness among young students. Even though these opportunities are present in almost all colleges people usually prefer to procrastinate on this. Some students often tell - “I’ll join them next semester” or “I think maybe I can do it much better sitting in my hostel room” and later you find these guys watching Naruto in their hostel rooms. Make sure it’s not you!

Are we practicing?

Practice must never stop! Practice! Practice! Practice!

Even if you don’t get time, make it to just 5 - 7 problems a day. Learn about more algorithms like Greedy, Dynamic Programming, Backtracking, etc. And don’t forget to revise Data Structures and Algorithms regularly.

Competitions Define Us

Take it a positive way. Competitions. Yes, they do help us know where we stand. Even while you began practicing Problem Solving on HackerRank there would have already been over a million people and you’ve practiced daily to get to your favorite badge. True?

The same is with Competitions. Don’t get stressed. You may not want to directly target ICPC. But you can at least get started involved with regular challenges on platforms like CodeChef. There are many competitions that take place in colleges too, keep your eyes open to all. Don’t miss out on any opportunity.

Dedication

Yes, dedication is important because you’re investing a large part of your time here! You have to get serious about your Competitive routine. You have to constantly analyze the problems which you couldn’t solve earlier or the ones which were taking a long time. Don’t get disheartened if you’re not getting a solution. Look out for help. Again solve until you become perfect. Soon you’ll realize it doesn’t take long enough to get to a Star Ranking on CodeChef. 

Wait! Don’t get complacent! Solve tougher problems. Remember during Engineering Exam preparation, some of us used to solve I.E Irodov problems in Physics. Why? Simple because we could differentiate ourselves from others and hence adopt the same here!

There are a lot of prestigious competitions and tournaments like ACM ICPC, Google’s Kickstart, HashCode, etc. Many of them are sponsored by big tech giants and there are absolutely big prizes!

Additional Readings
All the best!

Contributed by: Dhairya Ostwal

Wednesday, 25 March 2020

What are some basic projects in machine learning?

The best way to learn Machine Learning, or for that matter any skill, is to take-up projects. Projects help you get a realistic perspective of how things work at the ground level. Here are some interesting project ideas in Machine Learning which you may want to work on in order to build a great resume:
  • Handwritten Digit Recognition: this is the standard project that everyone takes-up and you should also do it. The project is about one of the simplest Machine Learning datasets - “the MNIST dataset
    ” which contains a set of handwritten images containing numbers from 0 to 9 and you are asked to train a Machine Learning algorithm that can correctly identify the digits. By taking up this project, you will learn a lot of aspects of Machine Learning - loading and cleaning data, data preprocessing, applying various ML algorithms on a given set of data, finding the right metrics to measure the algorithm performance, etc.
  • House Price PredictionHouse Price Prediction problem
     is another interesting problem that is focused more on applying Regression techniques. Linear Regression is a simple, yet powerful Machine Learning algorithm and knowing how to apply it would be extremely useful to solve a variety of ML problems. Further, if you ever apply for an ML-related job, expect a question or 2 around Linear Regression.
  • COVID-19 Global Forecasting: this is a new problem that has emerged in the recent COVID-19 outbreak. Here is the dataset
    . The world is going through a crisis and any contribution from the Technology community in terms of predictions or helping the society would certainly be beneficial.
  • Iris Flower Prediction DatasetThe Iris dataset
     contains 3 flower classes of 50 rows each containing the data-points like the height of petal, the width of petal, the height of sepal, and width of the sepal. Based on these 4 parameters, you are supposed to classify a new data-point into one of the 3 flower classes.
  • Titanic Survival Prediction: This is the “Hello World! problem on Kaggle
    ”. The idea is to use parameters like age, gender, etc., and predict whether the person survived the Titanic crash or not. There are some interesting observations which you will learn about when you play with the Titanic Dataset.
Some other problems which are of interest to the world:
  • Sentiment Analysis: analyzing sentiment is an old problem. Every day new solutions to this problem are being created to solve this problem.
  • Credit Card Fraud Detection: a relatively well-known problem which is also quite important for the Industry. If you build something around it, Banks would love to purchase.
  • Insurance Fraudulent Claim Detection: Insurance companies spend millions of dollars every year to ensure that they don’t pay out a fraudulent claim. If someone solves this problem, they will make a ton of money.
I would recommend the below resources to learn ML and take-up projects:
Further readings:

Saturday, 8 February 2020

How can I do a startup like Aman Goel did?

The short version - just get started with something that adds value to other people’s life.
The long version
As one of my advisors says,
To be an entrepreneur, you require 3 things - dil (heart), dimaag (brain) and dum (will power)
Most people possess the first 2 but do not have the last one and that’s the reason most people do not start.
When I started my entrepreneurial journey, fortunately, I had the dum to ditch my upcoming job and start my own venture. However, in the beginning, I also got many things wrong:
  • I focused on how to make money rather than focusing on building a great product.
  • I focused on the output of employees rather than helping them get that output.
  • I focused on how can my clients pay me more rather than building great relationships with them
I focused on all the wrong things. The approach to business was totally wrong and no wonder, I faced a lot of challenges during the first 1.5 years of my business. What went wrong?
I focused on the output rather than the input. Output includes things like - how much money the client pays me. Input includes things like - how well I serve them. After 1.5 years of problems, I realized that my focus should be on things that I can control rather than on the outcomes, where I have no control over. For instance,
  • Instead of focusing on how much money a client pays me, I started focusing on how can I maintain a strong relationship with them. To do that, I decided that I should meet them once every week.
  • Instead of focusing on how much output my employees provide, I started focusing on how can I take care of them the best. To do that, I made sure that my office had all the arrangements to keep them happy - relatively relaxed timings, free snacks, office outings, etc.
I shifted my focus from output to input. I tried doing the best I can and in turn, things automatically started improving.
We all have heard what is written in Geeta - karam karo, fal ki chinta na karo (keep working hard without worrying about results). While I never read Geeta, I started applying the above principle wherever possible. A few things happened:
  • I started getting more control on my life because what I do (karam) was completely in my control.
  • My relationship with clients started improving and I got more business automatically. Some of our clients trust us so much that they want us to work on new solutions rather than purchasing them from specialized solution providers.
  • My business started growing, revenues grew by 4x this year. We started getting more clients onboarded. Seeing the success with clients, investors have started reaching out to us.
The whole equation that most entrepreneurs follow is to first find an investor, then build a product and then find a customer. We changed the equation to first finding a customer, then building a product as per what they wanted and we automatically got the investors.
How can I do a startup like Aman Goel did?
Reverse the value equation and focus on what you bring on the table rather than what you take from the table.
PS: Read the book Atomic Habits by James Clear. I believe that the book gets into the details of what I mentioned above. It talks about building the right habits which will automatically lead to better outcomes.

How did Aman Goel manage studies and extracurricular activities like clubs and events during his time at IIT Bombay?

If you enjoy things, you will be able to get the best out of yourself.
I never joined any random club or society for the sake of it. I was engaged in the following extra-curricular activities during the college days:
  • Convener at Rubik’s Club: that was because I loved solving Rubik’s cube and wanted others to learn the same.
  • Teaching Assistant for Multiple courses: that was because I had some thoughts, ideas, and approaches of looking at things differently and I wanted to convey those ideas to others and possibly get some more suggestions. Being a Teaching Assistant was a great way to achieve the same because I got an opportunity to interact with a bunch of some of the smartest students in the country.
  • Department Academic Mentor: this is because I love interacting with people and sharing my experiences with others.
  • Multiple Freelancing Projects: as an engineer, I love building things and solving problems. Freelancing is a great way to do that. Plus, it never hurts to make some side money while in college.
Time Management in college is fairly simple. The trick is simple - pay attention during the lectures so that you can focus on other things outside of the lectures.
Where most students screw up is that they don’t focus during the lectures. That way, the entire time is wasted and then you have to engage in self-study separately. While self-study is good, it is much better to do it alongside the lectures so that you can save time.
At IIT Bombay, the lecture hours are relatively less as compared to other colleges (at least that’s what I have heard from my friends). For instance, a typical semester at IIT Bombay (CSE) would not involve more than 4 - 5 hours of lectures a day. That way, I used to get plenty of time for other stuff.
The bottom-line is time management. Learn to prioritize things. Learn to build a schedule. Learn to build habits and things would be easy to manage.

Sunday, 28 July 2019

How much time will it take to create Quora?

If you really want to build a product that scales to 100 million users, it will be a real big gun and I am sure you will face many challenges both from a technical and non-technical point of view.
Technical challenges:
  • Advanced machine learning algorithms
  • Scaling
Non-technical challenges:
  • Acquiring customers
  • Keeping the product in line with what customers need
These challenges may sound trivial, but as a tech guy, I can say with confidence that scaling to 100 million people is definitely not a piece of cake. When you have a hundred thousand users, you are all good. When a hundred million users are using your app, things start breaking and you really need some groundbreaking technology to handle this volume of traffic.
However, if you are looking for something simple - a Quora like question and answer website, then that’s really simple and I have done it (with the help of a couple of friends). With some effort, anyone can do it.
Here are the screenshots:
The technology behind it:
The database schema is described below:
  • UserProfile table:
  1. user = models.OneToOneField(User, primary_key=True)
  2. avatar = models.ImageField(null=True, upload_to=generate_filename, default="../default_avatar.png")
  3. bio = models.CharField(max_length=50, null=True)
  4. followers = models.ManyToManyField(User, related_name='following')
  5. following = models.ManyToManyField(User, related_name='followers')
  • Topic table:
  1. name = models.CharField(max_length=50)
  2. url = models.CharField(max_length=100, primary_key=True)
  3. followers = models.ManyToManyField(User, related_name='topic_followers')
  • Questions table:
  1. text = models.CharField(max_length=100)
  2. time = models.DateTimeField(default=timezone.now)
  3. asked_by = models.ForeignKey(UserProfile, on_delete=models.SET_NULL,
  4. null=True, db_index=True)
  5. url = models.CharField(max_length=100, primary_key=True)
  6. details = models.CharField(max_length=200)
  7. topics = models.ManyToManyField(Topic, related_name='topic_questions')
  8. followers = models.ManyToManyField(User, related_name='question_followers')
  • Answers table (yo is the term I used for upvote :P):
  1. question_url = models.ForeignKey(Question, on_delete=models.CASCADE)
  2. answered_by = models.ForeignKey(
  3. UserProfile, db_index=True, on_delete=models.SET_NULL, null=True)
  4. question_text = models.CharField(max_length=100)
  5. text = models.TextField()
  6. time = models.DateTimeField(default=timezone.now)
  7. yoers = models.ManyToManyField(User, related_name='yoers')
  • Comments table (answers have comments):
  1. text = models.CharField(max_length=200)
  2. time = models.DateTimeField(default=timezone.now)
  3. commented_by = models.ForeignKey(
  4. User, on_delete=models.SET_NULL, null=True)
  5. answer = models.ForeignKey(Answer, on_delete=models.CASCADE, db_index=True, related_name='comments')
An interesting piece remains - newsfeed algorithm:
As can be seen, the newsfeed has 3 parts:
  • Latest Questions/Answers:
  1. user = request.user
  2. latest_questions = Question.objects.all().order_by('-time')[:FEED_COUNT]
  3. latest_answers = Answer.objects.all().order_by(
  4. '-time')[:FEED_COUNT].prefetch_related('question_url')
  5. latest_qa = list(latest_questions) + list(latest_answers)
  6. latest_qa.sort(key=lambda x: x.time, reverse=True)
  7.  
  8. yo_list, yo_count_list = utils_get_yo_info(latest_qa, user)
  9. latest_qa_with_yos = zip(latest_qa, yo_list, yo_count_list)
  10.  
  11. return render(request, 'home/latestqa.html', {
  12. 'latest_qa_with_yos': latest_qa_with_yos,
  13. 'user': user,
  14. 'domain': settings.DOMAIN_NAME})
Here is a brief explanation of the code above:
  1. Generate a list of latest 20 or so questions
  2. Generate a list of latest 20 or so answers
  3. Sort them in the reverse order of time after combining the 2 lists
  4. Show them as the latest Q/A newsfeed
  • Topics you like:
  1. topics = request.user.topic_followers.all()
  2. topic_questions = list(set(Question.objects.filter(
  3. topics__in=topics).order_by('-time')[:FEED_COUNT]))
  4. topic_questions.sort(key=lambda x: x.time, reverse=True)
  5.  
  6. yo_list, yo_count_list = utils_get_yo_info(topic_questions, request.user)
  7. topic_questions_with_yos = zip(topic_questions, yo_list, yo_count_list)
  8.  
  9. return render(request, 'home/topicsyoulike.html',
  10. {'topic_questions_with_yos': topic_questions_with_yos})
This is quite straightforward - a simple database query + some manipulations
  • People you follow:
  1. following = request.user.following.all()
  2. answers = list(set(Answer.objects.filter(
  3. answered_by__in=following).order_by('-time')[:FEED_COUNT]))
  4. answers.sort(key=lambda x: x.time, reverse=True)
  5.  
  6. yo_list, yo_count_list = utils_get_yo_info(answers, request.user)
  7. answers_with_yos = zip(answers, yo_list, yo_count_list)
  8.  
  9. return render(request, 'home/peopleyoufollow.html',
  10. {'answers_with_yos': answers_with_yos})
Again, this is also quite straightforward to understand.
All of these newsfeed ‘algorithms’ were written by me and are in a very raw form. None of them is really ‘intelligent’ and I am sure many of the database queries can be optimized significantly. But again, this wasn’t supposed to be Quora, it was rather supposed to be Quora-like.
Note that the site has been abandoned. It was just an academic project (no commercialization) and the questions and answers you see in the screenshots are because it was tested by my friends a couple of days back. It took a few weeks to complete the web-app.
The name SoclWebApp was randomly chosen (Socl == (Soc)ialize + (L)earn). The site isn’t indexed by search engines and you won’t be able to find it on Google/elsewhere. However, I would be more than happy to answer any questions :)

How to start with Competitive Programming?

So you want to start with Competitive Programming? Good, you’re at the right place :) The following are the steps to help you get start...