Array Google Interview Questions

Google interview questions often focus on algorithmic problem-solving using arrays or slices in Go. Here are a few common types of array-related questions that could be asked:

1. Find the Maximum Subarray Sum (Kadane’s Algorithm)

LeetCode#54

Given an array of integers, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example

Input: [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum = 6.

Approach

Use Kadane’s algorithm, which runs in O(n) time.

Solution

• Golang solutions

2. Rotate Array

LeetCode#189

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]

Approach

One way to do this is to reverse parts of the array in place in O(n) time.

Solution

• Golang solutions

3. Trapping Rain Water

Leetcode#42

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.

Example

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Approach

Use two-pointer technique to calculate trapped water in O(n) time.

Solution

• Golang solutions

4. Find Missing Number

Given an array containing n distinct numbers taken from the range 0 to n, find the one number that is missing from the array.

Example

Input: [3,0,1]
Output: 2

Approach

Use the sum formula or XOR in O(n) time.

Solution

• Golang Solution

5. Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

Example

Input: [1,2,3,4]
Output: [24,12,8,6]

Approach

Use prefix and suffix arrays in O(n) time without using division.

More questions

Arrays

1. Find the missing number in an array of integers from 1 to n.
2. Given an array, find all subarrays that sum to a given value.
3. Rotate an array to the right by k steps.
4. Find the first missing positive integer in an unsorted array.
5. Merge two sorted arrays into one sorted array.
6. Find the maximum product subarray.
7. Determine if a given array can be split into two subarrays with equal sum.
8. Find the element that appears more than n/2 times in an array (Majority Element).
9. Find the kth largest element in an array.
10. Sort an array of 0s, 1s, and 2s in linear time.

Visit https://codeandalgo.com/ for more content.