Technical interviews, especially at FAANG companies, require extensive and dedicated preparation. The extent of topics to cover and the complexity of programming concepts can be unnerving even to experienced coders with several years of industry experience. Most technical interviews at Tier-1 companies test candidates in three important areas - problem solving skills, coding skills, and knowledge of computer science fundamentals. In order to crack these fairly tough interviews at the best technology firms in the world, it is imperative to be adept at each of these three areas, and to master even one of them requires significant time, practice, effort and persistence.
In this article, we’ll look at some popular sorting techniques in data structures and their applications, covered in Omkar Deshapande’s (PhD, Stanford University) live session on “sorting techniques in data structures and how to code algorithms using these techniques”
Sorting techniques in data structures are essentially used to rearrange or reorganize a chunk of random data.
Candidates appearing for interviews at FAANG companies can often expect multiple questions that employ sorting to arrive at problem solutions.
Mentioned below are some popular sorting techniques that often find utility in solving complex problems at these interviews:
- Extensions of Merge Sort
- Extensions of Heap Sort and
- Extensions of Quick Sort
While a lot of these concepts are quite straightforward, it is often challenging to find solutions to problems in a time-tested interview environment. Being hard-pressed for time in an interview can often stimulate anxiety, causing fuzzy thinking and incorrect concept application. This is precisely the reason why mugging up a bunch of problems and expecting them to show up at these interviews can prove futile.
In order to beat the scourge of interview anxiety, a proven way is to improve your problem solving skills. Becoming a problem solver will help you identify inherent patterns in problems and amp up your confidence when you encounter problems that you haven’t solved before. The idea is to categorize problems into patterns by solving a cluster of problems and finding patterns that are coherent among them.This way, you don’t treat every single problem individually but rather go through one pattern after another.
Sorting techniques by Omkar Deshpande
The session begins with Omkar explaining why mugging a bunch of problems, as mentioned earlier, isn’t sufficient to go the mile.
Mugging up 1,300 problems on Leetcode and hoping that a few of them show up at these interviews not only places your success on luck, but also leads you to ignore computing fundamentals and patterns that are essential to becoming a successful problem solver. This process is also enormously time consuming.
On the other hand, when you approach problems by identifying coding patterns, you wouldn’t have to write code from scratch as you’d already have coding patterns in your mind. All you have to do is apply patterns that seem relevant and arrive at solutions in a quicker and more efficient fashion.
This is precisely why Omkar Deshpande stresses on the importance of becoming a good problem solver to emerge successful in these interviews.
The different ways to employ popular sorting techniques were explained using a popular problem that often features at technical interviews.
Before moving onto problem statements, the speaker disucssed key take-aways from the pre-class videos.
Mentioned below are the key learnings that were identified:
a. General algorithm design strategies: These include Brute-Force, Divide-and-Conquer, Decrease-and-Conquer, and Transform-and-Conquer.
b. Algorithm analysis to measusre the efficiency of the algorithm: This can be done using Big-oh Notation, Worst-case, Average-case and Best-case methods.
c. Sorting problem as a case study: This part discusses Merge Sort, Quick Sort and Heap Sort in detail.
Problem statement 1: “Given an array of integers, sort the array in ascending order”
Omkar discussed how the problem can be solved using different sorting techniques, and how to use specific sorting techniques in specific situations.
In order to solve similar problems, it is necessary to know how to code up heap sort, merge sort, and quick sort in the language of your choice, in less than 10mins.
After explaining the sorting techniques and their utility in solving specific problems, Omkar went on to explain the mindset involved behind becoming a good problem solver to crack tough technical interviews.
3 ways to be an effective problem solver
In order to be an effective problem solver, here’s what you must seek to achieve:
1. Mental discipline:
Solving problems can often be viewed as a long, wild-goose chase that involves considerable experimentation. As such, you must work towards increasing your time-span of concentration and embrace failure while you find the best possible route to take while solving a problem. This can only be a result of long and patient hours of coding practice.
2. Emotional Attitude:
The speaker talks about how mountaineering and working out a gym lead to different results. He explains how working out a gym regularly cannot enable you to start scaling ambitious mountain peaks immediately - you’ll have to scale easier peaks and figure out how to conserve and expend energy before taking on the more daunting ones. An almost similar logic applies to problem solving - you can only solve the most complex problems through practice and effort.
3. Learning the craft
Omkar advises how to go about becoming an effective problem solver by explaining the initial steps to take. Here’s how students should go about it:
- By becoming thorough with computing fundamentals.
- By learning how others approach solving specific problems.
- By engaging regularly with peers and instructors to advance your coding capabilities
Note that problem solving is a journey. You’ll often feel clueless at the beginning. But by keeping at it, you can grasp subtle techniques in identifying patterns and classifying problems based on inherent patterns to solve them seamlessly.
Problem Statement 2: The "Two Sum" Problem: You have an array of n numbers and a Target number. Determine if the array contains two numbers whose sum is equal to the Target number.
To help students construct patterns and identify the best possible route to take, the speaker goes through different types of sorting techniques to identify the best possible solution to this problem.
If you want to get into your dream company and wish to get started with your technical prep, sign-up for our Webinar today.