Arrays And String

Question 1

Anagrams given 2 strings see if they are anagrams

Answer 1

Anagrams are string that are different but has same character…
Use character encoding ord (c) -ord(‘a’) and put in index of 26 long array compare 2 arrays with O(n)

Question 2

Two sum problem given a target find if there are 2 unique index sum to target sum

Answer 2

Use hash map to store value as key and index as value iterate and subtract target for each iteration ..
If target-n is value in the map meaning we found our 2 nd value
Return the value and the iterated upon index

Question 3

Top k elements
Find top k elements with decreasing order of frequency

Answer 3

1 way is to store frequency and element in map
2 sort the map in sorted order
3 return top k keys

This can also be done through bucket sort by making frequency as index of bucket and storing array of numbers

Question 4

Product of array except self

Answer 4

This is a simple trick post and prefix product
1 Iterate array in one direction and product the array values in another array
2 iterate in reverse order and store value in an array
3 final output array is product of prefix and postfix product

Question 5

Valid soduku

Answer 5

1. First iterate row wise and check 1-9 save it in set and check if it’s unique
2. Repeat same for columns
3. Last is for square 1-9 where the compute is crucial
   (Square //3 )*3 is row
   (Square %3) *3 is col

Question 6

Group anagrams

Answer 6

For group anagram problem employe the same strategy for checking anagrams then have the key stored as tuple of 26 character and append value with same characters

Question 7

Longest consecutive sequence
Longest sequence in an un sorted array return the sequence which is the max

Answer 7

1 the logic is to identify start of the sequence that can be done by saving the array in a set
2 now iterate the array and keep iterating and checking if -1 of that number is not in unique meaning if value is 4 then 3 is not unique that implies a start of sequence
3 once you find start of any sequence take a streak counter at 1 and run a while loop unless counter +1 is found in the set and increment the counter
4 get the length and save as current max and complete array loop to get final max

Question 8

Array contains duplicate

Answer 8

Save value in a set and check if the length of set is not same as len of array