Blind75

Question 1

Find Duplicate Elements in Array

Answer 1

HashSet: Inset in O(1)
Add the element if it is not present.
If present then duplicate.
Space = Time = O(n)

If we need Time O(1)
a) Brute Force = O(n2)
b) Sort O(nlogn) and Compare beside elements

Question 2

Find if two strings are anagram of each other

Answer 2

1) Take 2 hashmaps -> if count_s1(key) == count_s2(key)

2) sorted(s1) == sorted(s2)

Question 3

TWO SUM in an array

Answer 3

1) Brute Force = O(n2)

2) diff = target - n
if diff is present in PrevHashmap return prevhashmap(dif) and n

Question 4

GROUP ANAGRAMS

Answer 4

Single solution: O(m*n)

finalRes = defaultdict(list)

for s in strings:
count = [0] * 26

 for c in s:
   value = ord[c] - ord["a"]
   count[value] ++   finalRes[count].append(s)

return finRes.values()

Question 5

TOP K Frequent elements

Answer 5

1) O(nlogn) - Traverse + Sort

2)O( K Log n) - Heapify

3) Reverse Bucket sort:

hashmap = {} to count nums
freq[[] for i in len(nums) + 1] to store array of nums with index count

for n,c in hashmap.items():
freq[c] = n // freq[c].append(n)

for i in range(len(freq)-1,0,-1)
for n in freq[i]
res.append(n)

Question 5

Encode and Decode String

Answer 5

encode() -> res = str(len(s)) + “#” + s

decode()-> res,i = [], 0

while i<len(s)
j=i
while s[j] != ‘#’:
j+1
length = int(str[i:j])
res.append(str[j+1 : j+1+length])
i = j+1+length

Question 6

Product of array except self

Answer 6

O(n)

result = [1] * len(nums)

prefix=1
for i in range(len(nums)):
result[i] = prefix
prefix* = nums[i]

postfix=1
for i in range(len(nums)-1 , -1, -1)
result[i]* = postfix
postfix* = nums[i]
return result

Question 7

Longest Sequence in a List

Answer 7

numset = set(nums)

for n in nums:
if (n-1) not in numset:
length = 0
while(n+length) in numset:
length++
longest = max(longest,length)
return longest