google-interview-questions

There are two sorted arrays A and B of size n each, write a program to find the median of these two sorted arrays obtained after merging (the new merged array will be an array of length 2n). 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.

Given an array of n integers and a target number, write a program to find whether a pair sum exists in the array or not. In other words, we need to check for a pair of elements in the array that sum exactly to the target value. Assume that all elements are distinct. Note: This is an excellent problem to learn problem solving using two pointers and hash table.

Given two integer arrays, X[] and Y[] of size m and n, write a program to find intersection of these two arrays. The intersection is a list of common elements present in both arrays. Suppose m > n, all array elements are distinct and intersection elements can be in any order. Note: This is an excellent problem to learn problem solving using various approaches.

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. Note: This is an excellent problem to learn problem solving using dynamic programming.

Given an array of n elements, write a program to find the maximum subarray sum. A subarray of array X[] is a contiguous segment from X[i] to X[j], where 0 <= i <= j <= n-1. Note: Max subarray sum is an excellent problem to learn problem-solving using the divide and conquer approach, dynamic programming, and single loop (kadane's algorithm).

Given a node x and the root of a binary search tree, write a program to find the in-order successor of node x. The in-order successor of node x is a node that will be visited just after node x during an in-order traversal. In other words, the in-order successor of a node x is the node with the smallest key greater than x->key.

Quicksort algorithm is often the best choice for sorting because it works efficiently on average O(nlogn) time complexity. It is also one of the best algorithms to learn divide and conquer approach. In this blog, you will learn: 1) How quick sort works? 2) How to choose a good pivot? 3) Best, worst, and average-case analysis 4) Space complexity and properties of quicksort.

Binary search is an efficient algorithm for searching a value in a sorted array using the divide and conquer idea. It compares the target value with the value at the mid-index and repeatedly reduces the search interval by half. The search continues until the value is found or the subarray size gets reduced to 0. The time complexity of the binary search is O(log n).

Given an array of n integers, find the length of the longest consecutive sequence. In other words, we need to find the length of the longest subsequence such that elements in the subsequence are consecutive integers. The consecutive numbers can be in any order. Note: This is an excellent problem to learn problem-solving using sorting and hash table.

Given two strings X[] and Y[] of sizes m and n, design an algorithm to find the length of the longest common subsequence (LCS). There can be many possible common subsequences of two strings, but we need to return the common subsequence of the longest length. Note that this is an excellent problem to learn dynamic programming.

Given a binary search tree and a key value. Write a program to delete the given key from the binary search tree and return the updated root node. This is an excellent problem to learn pointer manipulation in binary trees and problem-solving using both iterative and recursive approaches.

Write a program to convert a sorted array of integers into a balanced binary search tree. Each node in the tree must follow the BST property, and the height of the left and right subtrees should be as close to equal as possible. Note: This is an excellent problem to learn problem-solving using the divide and conquer approach.

Write a program to find the minimum number of operations required to convert string X to string Y. You have the following three operations permitted on a string: 1) Insert a character 2) Delete a character 3) Replace a character. The edit distance between two strings is the minimum number of operations (insertions, deletions, or substitutions of characters) required to transform one string into the other.

Given the head of a linked list, write a program to find if linked list has a cycle or not. Return true if there is a cycle or loop in the linked list. Otherwise, return false. A linked list with cycle causes iteration to fail because the iteration will never reach the end. So, detecting a linked list loop is important before applying an iterative approach.

Given the root of a binary search tree (BST), write a program to find the absolute minimum difference between the values of any two nodes in the tree. Here node values in the tree can be positive, negative, or zero. Note: This is an excellent problem to learn problem-solving using iterative and recursive inorder traversal of a binary tree.

Given the root of a BST and an integer k, write a program to find the kth largest value among all the nodes' values in the binary search tree. Note: This is an excellent problem to learn problem solving using recursive and iterative inorder traversal and data structure augmentation (storing extra information inside BST nodes for solving a problem).

Given an array and a positive integer k, write a program to find the kth smallest element in the array. This is an excellent problem to learn problem-solving using the max and min heap data structures. The quick-select approach (divide and conquer) is also worth exploring because it helps to optimize time complexity to O(n) on average.

There is a staircase with n steps, and you can climb either 1 or 2 steps at a time. Write a program to count and return the number of unique ways to climb the nth stair. The order of steps taken matters. Note: Climbing stairs is an excellent problem to learn the dynamic programming approach and the application of the Fibonacci series in problem-solving.

Given a sorted array, write a program to remove duplicates from the array. We need to remove repeated elements so that there is a single occurrence of each element and return the length of the array containing unique elements. Note: This is an excellent problem to learn the fast and slow pointers approach. We have discussed two O(n) time in-place solutions.

In an array of size 2N, there are N + 1 unique elements, and exactly one of these elements is repeated n times. Write a program to return the N-repeated element in the given 2N size array. Note: This is an excellent problem to learn optimization using the mathematical approach. Sometimes mathematical insights into the problem can help us to get efficient solutions.

You are given an array X[] of n elements, write a program to find majority element in an array. A majority element is an element that appears more than n/2 times, so there is at most one such element. Assume that array is non-empty and majority element always exists in the array. Note: This is an excellent problem to learn various approaches.

Given an array X[] of integers, find the maximum parity index. The parity index is the maximum index difference between two elements (X[i], X[j]) such that, j > i and X[j] > X[i]. In other words, we need to find maximum j - i such that j > i and X[j] > X[i]. Note: This is an excellent problem to learn problem solving using sorting and two pointers approaches

Given an array X[] of n distinct elements, write a program to find all the unique triplets in the array whose sum is equal to zero. For example, if triplets with zero sum in the array are (X[i], X[j], X[k]), then X[i] + X[j] + X[k] = 0. Hint: This is an excellent problem to learn problem-solving and optimization using hashing and two pointers approach.

Given an array that includes both positive and negative numbers, write a program to find the first missing positive integer. This is one of the best problems for learning step-by-step time complexity optimization using various approaches. An in-place hashing solution uses the same input array to process values and generate output.

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 endpoints of line i is at (i, height[i]) and (i, 0). Find two lines, which together with x-axis form a container, such that container contains the most water. This is an excellent problem to learn two pointers approach.

Given n non-negative integers representing an elevation map where the width of each bar is 1. Write a program to compute how much water it can trap after raining. This is a famous interview problem to learn time and space complexity optimization using various approaches. Two pointers approach provides an efficient solution using O(n) time and O(1) space.

Given an array consisting of 0s, 1s, and 2s, write a program to sort this array of 0, 1, and 2 in ascending order. We need to sort the array in O(n) time complexity without using sorting algorithms or extra space. Note: This is a variation of the Dutch national flag problem and an excellent problem to learn problem solving using three pointers.

Given an integer n, write a program to return string representation of numbers from 1 to n. If number is divisible by 3, we store “Fizz”. If number is divisible by 5, we store “Buzz”. If number is divisible by both 3 and 5, we store “FizzBuzz”. Hint: This is an excellent puzzle to learn coding concepts like conditional statements, loops, etc.

Given two strings, str1 and str2, of size m and n, write a program to check whether two strings are an anagram of each other or not. A string str1 is an anagram of str2 if characters of str1 can be rearranged to form str2. Note: This is an excellent string problem to learn problem-solving and optimization using direct address table.

Given an n x n 2D matrix, write a program to rotate the matrix by 90 degrees in the anticlockwise direction. The program should rotate the matrix 90 degrees without using extra space. In other words, we have to perform the rotation by modifying the 2D matrix directly. Note that this is an excellent problem to learn problem-solving using loops and the transpose of a matrix.

Given an unsorted array of n integers, write a program to sort array into a wave array. There can be many possible waveforms, but we need to return any one of them. An array A[] is sorted in wave arrangement if A[0] >= A[1] <= A[2] >= A[3] <= A[4] >= ....and so on. Note: This is an excellent problem to learn problem-solving using a single loop.

Given an array X[] of n integers, return true 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.

Given the root of a binary tree, write a program to check whether tree is a valid binary search tree (BST) or not. To check valid bst, we verify bst property at each node: All node values in the left subtree are less than node’s value, all node values in the right subtree are greater than node’s value, and both subtrees are also binary search trees.

Given a string S[], write a program to sort string S in decreasing order based on the frequency of characters. The frequency of a character is the number of times it appears in the string. If two characters have the same frequency, whichever occurs earliest in S, must come first. In other words, frequency based sorting must be stable.

We have given the head of a singly linked list, write a program to sort the list using insertion sort, and return the head of the sorted linked list. To implement this algorithm, we need to understand the idea of insertion sort on array. At each step of the iteration, insertion sort adds one element to the sorted output and grows the partially sorted list size by 1.