All content related to google-interview-questions

Find the Intersection of Two Unsorted Arrays

Given two integer arrays X[] and Y[] of size m and n, respectively, write a program to find the intersection of these two arrays. The intersection of two arrays is a list of distinct numbers which are present in both arrays. The numbers in the intersection can be in any order.

EnjoyAlgorithms

Triplet with zero sum

Given an array X[] of distinct elements, write a program to find all the unique triplets in the array whose sum is equal to zero.

EnjoyAlgorithms

Longest Common Subsequence

The longest common subsequence algorithm is a problem to find the length of the longest subsequence common to all subsequences of two strings. The lcs algorithm differs from the algorithm of the longest common substring problem. Explore and Enjoy!

EnjoyAlgorithms

Minimum number of Jumps to reach End

An array of non-negative integers is given and the aim is to reach the last index in the minimum number of jumps. You are initially positioned at the first index of the array and each element in the array represents your maximum jump length at that position.

EnjoyAlgorithms

Detect Loop in a Linked List

Write a program to detect the loop in a linked list. A linked list with a cycle causes iteration over the list to fail because the iteration will never reach the end of the list. Therefore, it is desirable to be able to detect that a linked list has no cycle before trying an iteration. So, we are going to discuss various algorithms to detect a loop in a singly linked list. This is also one of the best-linked list interview problems.

EnjoyAlgorithms

Median of two sorted arrays of the equal size

There are two sorted arrays A and B of size n each, write a program to find the median of the array obtained after merging both the arrays(i.e., an array of length 2n which is even). The median of a sorted array of size n is defined as the middle element when n is odd and the average of the middle two elements when n is even.

EnjoyAlgorithms

Climbing Stairs Problem

There is a staircase of n steps and you can climb either 1 or 2 steps at a time. You need to count and return the total number of unique ways to climb the staircase. The order of steps taken matters.

EnjoyAlgorithms

First Missing Positive

Given an array that includes both positive and negative numbers, write a program to find the first missing positive integer.

EnjoyAlgorithms

Longest Consecutive Sequence

Given an unsorted array X[] consisting of n integers, we need to write a program to find the length of the longest consecutive sequence of integers in the array. The consecutive numbers can be in any order.

EnjoyAlgorithms

kth smallest element in an array

Given an array and a positive integer k, write a program to find the kth smallest element in the array. One of the famous problems to learn a quick-select approach that helps optimize time complexity to O(n) average.

EnjoyAlgorithms

Majority element in an array

You are given an array X[] consisting of n elements, write a program to find majority element in an array i..e return the number which appears more than n/2 times. You may assume that the array is non-empty and the majority element always exists in the array. A majority element is an element that appears more than n/2 times, so there is at most one such element.

EnjoyAlgorithms

Maximum Subarray Sum

Given an array X[] with n elements, we need to write a program to find the maximum subarray sum among all subarrays. A subarray of array X[] of length n is a contiguous segment from X[i] through X[j] where 0<= i <= j <= n. Kadane algorithm idea is intuitive, using a single loop and few variables to solve the problem. We can use a similar idea to solve other coding problems.

EnjoyAlgorithms

Check for pair in an array with a given sum

Given an array of n integers and a target number, write a program to check whether a pair sum exits in the array or not. In other words, we need to check whether pair of elements in the array sum exactly to the target value.

EnjoyAlgorithms

Rotate a matrix by 90 degrees in an anticlockwise direction

Given an n x n 2D matrix representing an image, rotate the image by 90 degrees in an anticlockwise direction.

EnjoyAlgorithms

n Repeated element in 2n size array

In an array of size 2n, there are n+1 unique elements, and exactly one of these elements is repeated n times. Return the element repeated n times.

EnjoyAlgorithms

Binary Search Algorithm: Fast Searching on Sorted Array!

The binary search is one of the fastest search algorithms, which searches a value in the sorted array in an O(logn) time complexity. Here we search a value using divide and conquer by repeatedly dividing the search interval in half. Moreover, the algorithm for binary search also helps us to solve several coding problems.

EnjoyAlgorithms

Quicksort: one of the fastest sorting algorithms!

Quicksort is often the best practical choice for sorting because it works remarkably efficiently on average O(nlogn) time complexity. It is also one of the best algorithms to learn problem-solving using recursion and divide and conquer approach. In this blog, we have covered: 1) How quick sort works recursively? 2) Choosing a correct pivot value in the partition algorithm 3) Best, worst, and average-case time complexity analysis 4) Space complexity and essential properties of the quick sort. Explore and Enjoy!

EnjoyAlgorithms

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. This is a famous rainwater trapping problem.

EnjoyAlgorithms

Remove duplicates from sorted array

Write a program to remove the duplicates from the sorted array. For this we are given a sorted array, the task is to remove the duplicate elements such that there is a single occurrence of each element in the array.

EnjoyAlgorithms

Container With Most Water

Given an array of n non-negative integers height[n], where each represents a point at coordinate (i, height[i]). n vertical lines are drawn such that the two endpoints of line i is at (i, height[i]) and (i, 0).  Write a program to find two lines, which together with the x-axis forms a container, such that the container contains the most water.

EnjoyAlgorithms

Sort an array of 0s, 1s, and 2s —Dutch national flag problem

Given an array a[] consisting of 0s, 1s, and 2s. Write a program to sort the array of 0’s, 1’s, and 2’s in ascending order. This is a famous coding interview problem asked in facebook, microsoft and amazon.

EnjoyAlgorithms

Valid Mountain Array

Given an array X[] of n integers, return true if and only if it is a valid mountain array. The array X[] is a mountain array if and only if n >= 3 and there exists some i with 0 < i < n - 1 such that: X[0] < X[1] <...X[i-1] < X[i] and X[i] > X[i+1] > ...> X[n - 1]. In other words, we call the array mountain array when the array is strictly increasing and then strictly decreasing.

EnjoyAlgorithms

Sort an array in a waveform

Given an array of integers, sort the array into a wave-like arrangement. In other words, An array A[0..n-1] is sorted in wave form if A[0] >= A[1] <= A[2] >= A[3] <= A[4] >= ….This problem has been asked during google coding interview.

EnjoyAlgorithms

Our Weekly Newsletter

Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops and math.