Scribd
Upload
41 views3 pages

Google Coding Problems Solutions

The document outlines common Google interview coding problems along with their solutions. It includes problems such as 'Two Sum', 'Longest Substring Without Repeating Characters', 'Merge Intervals', and 'Maximum Subarray', each with example inputs and Python code solutions. The solutions utilize various data structures and algorithms to efficiently solve the problems.

Uploaded by

Ram K
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
41 views3 pages

Google Coding Problems Solutions

The document outlines common Google interview coding problems along with their solutions. It includes problems such as 'Two Sum', 'Longest Substring Without Repeating Characters', 'Merge Intervals', and 'Maximum Subarray', each with example inputs and Python code solutions. The solutions utilize various data structures and algorithms to efficiently solve the problems.

Uploaded by

Ram K
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Google Interview Coding Problems & Solutions

1. Two Sum
Problem:

Given an array of integers nums and an integer target, return indices of the two numbers such that

they add up to the target.

Example:

Input: nums = [2, 7, 11, 15], target = 9

Output: [0, 1]

Solution:

def two_sum(nums, target):

hashmap = {} # value: index

for i, num in enumerate(nums):

diff = target - num

if diff in hashmap:

return [hashmap[diff], i]

hashmap[num] = i

2. Longest Substring Without Repeating Characters


Problem:

Given a string s, find the length of the longest substring without repeating characters.

Example:

Input: s = 'abcabcbb'

Output: 3

Solution:

def length_of_longest_substring(s):

char_set = set()
left = 0

max_len = 0

for right in range(len(s)):

while s[right] in char_set:

char_set.remove(s[left])

left += 1

char_set.add(s[right])

max_len = max(max_len, right - left + 1)

return max_len

3. Merge Intervals
Problem:

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals.

Example:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]

Output: [[1,6],[8,10],[15,18]]

Solution:

def merge(intervals):

[Link](key=lambda x: x[0])

merged = []

for interval in intervals:

if not merged or merged[-1][1] < interval[0]:

[Link](interval)

else:

merged[-1][1] = max(merged[-1][1], interval[1])

return merged
4. Maximum Subarray (Kadanes Algorithm)
Problem:

Find the contiguous subarray with the largest sum.

Example:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]

Output: 6

Solution:

def max_sub_array(nums):

max_current = max_global = nums[0]

for num in nums[1:]:

max_current = max(num, max_current + num)

if max_current > max_global:

max_global = max_current

return max_global

You might also like