Amazon-Last 30 days

Question 1

Longest substring without repeating characters(Find the longest substring without repeating characters)

https://leetcode.com/problems/longest-substring-without-repeating-characters/solutions/5111376/video-3-ways-to-solve-this-question-sliding-window-set-hashing-and-the-last-position/?envType=company&envId=amazon&favoriteSlug=amazon-thirty-days

Answer 1

from collections import defaultdict
from typing import Dict
def longest_substring_without_repeating_characters(s:str) ->int:
longest = 0
l = 0
counter: Dict[str, int] = defaultdict(int)
for r in range(len(s)):
counter[s[r]] += 1
while counter[s[r]] > 1:
counter[s[l]] -= 1
l += 1
longest = max(longest, r- l + 1)
return longest

if__name__ == “__main__”:
s = input()
res = longest_substring_without_repeating_characters(s)
print(res)

Question 2

**Word Ladder

Question 3

LRU cache

Question 4

Number of islands

Answer 4

class solution:
def numsislands(self, grid):
if not grid:
return 0
num_islands = 0

for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == “1”
self.dfs(grid, i, j)
num_islands += 1

return num_islands

def dfs(self, grid, r, c):
if (
r < 0
or c < 0
or r >= len(grid)
or c >= len(grid[0])
or grid[r][c] != “1”
):
return
grid[r][c] = “0”

      self.dfs(grid, r - 1, c)
			self.dfs(grid, r + 1, c)
			self.dfs(grid, r, c - 1)
			self.dfs(grid, r, c + 1)

Question 5

Reorganise the string

Answer 5

two appraches we can solve this problem
1)counting and priority queue-
a) what is prority queue -priority quueue is always keeping the highest and lowest priority element on the top and allowing to access it in O(1) time
useful in scheduling , gredy algorithms, simulations where you repeatedly need the next most important item
b)advanatges of a priority queue -uses the binary heap for fast iteration and deletion insert - O(log n), remove the element - O(log n)

dynamically manintains the orders sort the elements every time you add or remove - the prority queue keeps the internal structure automaticaly
2)We can also use max heap for the solution. Maxheap does in log n times

Question 6

Top k Frequent Elements

Answer 6

Heap takes k log(n) so we hav eto use the bucket sort to solve the problem

Question 7

Group Anagrams

Question 8

**3Sum

Question 9

Rotting oranges

Question 10

Copy list Random pointer