We have already discussed several sorting algorithms that can sort n numbers in both O(n²) and O(nlogn) time complexity in the worst case. These algorithms determine the sorted order based only on the comparisons between the input elements. We call such sorting algorithms comparison sort, where we use only comparisons between elements to gain order information about an input sequence A[0], A[1], . . . , A[n-1]. In other words, given two elements A[i] and A[j], we perform one of the tests A[i] <= A[j], A[i] >= A[j], A[i] = A[j] to determine their relative order. …

Difficulty: Medium, Asked-in: Google, Amazon, Uber, Hike

Key takeaways

  • An excellent problem to learn dynamic programming approach. We are using the bottom-up approach to fill the 2-D table in a row-wise fashion. Based on this idea, we can solve a lot of other problems.
  • A wonderful problem to learn space complexity optimization.

Let’s understand the problem

Given two array strings X and Y of size m and n, write a code to find the length of the longest common sequence.

  • A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the…

Millions of users on the internet are generating terabytes of content every day, and the amazing part is: the amount of content is doubling every six months! So we need an effcient search mechanism or new data structures for storing and accessing data with such growth. From another perspective, Many applications require a mechanism that supports only the dictionary operations: Insert, Search, and Delete. For example, a compiler that translates a programming language maintains a symbol table, in which the keys of elements are character strings corresponding to identifiers in the language.

But the critical question is: what is wrong…

Computer science is a field of dream opportunities. All over the world, millions of students are looking forward to pursuing a career in the field of computer science. Though a lot of learning resources are available online, still, most of the students are struggling to become good at it and crack the interview. After working closely with more than 1k students, here I would like to highlight the top 5 learning challenges in computer science.

Solving problems is a practical skill like, let us say, swimming. We acquire any practical skill by imitation and practice. — George Polya

But before…

Why analysis of algorithms is important?

  • Deciding the efficient algorithm among more than one algorithms.
  • Estimating algorithm performance for different sizes of the input.
  • Understanding the nature of the code and finding scope for further optimization.

The critical question would be: How do we measure the time complexity of an algorithm? What are the essential concepts related to the complexity analysis? Let’s dive deep into it and learn step by step.

What is the input size and running time?

The input size is defined as the total number of items present in the input. The time taken by an algorithm grows with the size of the input i.e. If we increase the input size…

Pointers in C++

A pointer is a special kind of variable designed to store the memory address of another variable. Declaring a pointer is as simple as declaring any other variable, but it is tricky to handle. So, here is a question for you: How do you pass a 2D Array in a function if the parameters of the array are not declared globally? Choose your answer from the given options in the image below. Also, suggest in the comment if you have any other approach.

Why the idea of “OOPS” is essential?

Object-Oriented Programming binds together the data and the methods in the form of an object and selectively exposes the data to other objects. It primarily revolves around classes and objects — definition, instantiation, relationship, communication, etc. On the other hand, the building block of procedural programming is procedures or functions that perform data operations. Explore and Think.

Difficulty: Medium

Asked In: Google, Facebook, Microsoft, Amazon, Flipkart, Hike, Morgan Stanley

Discussed Solution Approaches

  • Brute force approach using nested loops
  • Using sorting and binary search
  • Using sorting and two pointers approach
  • Efficient Approach using a Hash Table

Key takeaway from this coding problem

  • A famous searching problem that can be solved using various approaches.
  • The two-pointers and Hash Table solution are worth exploring.
  • One can find variations of this problem asked during a coding interview.

Let’s understand the problem

Given an array of n integers and given a number targetSum, write a program to determines whether there is a pair of elements in the array that sums to exactly targetSum.

  • We assume…

Difficulty: Easy

Asked in: Google, Amazon, Adobe, Oracle, Qualcomm, SAP Labs, Wipro

Let’s understand the Problem

Given a sorted array X[] of n elements, write a program to search a given element key in X[]. If the key exists, then we need to return its index in the sorted array. Otherwise, return -1.

  • All the integers in X[] are unique.
  • X[] is sorted in ascending order.
Input: X[] = [-4,2,4,5,9,12], key = 5
Output: 3
Explanation: 5 exists in X[] and its index is 3.
Input: X[] = [-4,2,4,5,9,12], key = 6
Output: -1
Explanation: 6 does not exist in x[] so return -1

Binary Search Intuition

Asked In: Google, Microsoft, Adobe, SAP Labs, Goldman Sachs, Qualcomm

Why is learning Quicksort important?

Quick Sort is one of the most popular algorithms that uses a divide and conquer problem-solving. Here are some excellent reasons to learn this algorithm —

  • Often the best practical choice for sorting because it is remarkably efficient on average. It is an in-place sorting algorithm that also works best in the virtual memory environment.
  • One of the best algorithms to learn the idea of recursion in programming. Its recursive structure, the flow of recursion, and the base case are intuitive.
  • A good algorithm to learn the worst, best, and…

Shubham Gautam

Founder and CEO www.enjoyalgorithms.com | Super 30 | IIT BHU | Empowering Youth for Success

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store