Hashing

Question 1

Largest continuous sequence with 0 sum

Answer 1

Unordered map m
Int presum=0
Maxlen=0
Int left=-1 , right=-1
For i from 0 to n
Presum+=a(i)
If presum==0
  Left=0 right is i
   Maxlen =i+1
If(m.find(presum)!=m.end())
 If(i-m(presum) > maxlen)
 Then left=m(presum)+1
 Right=i
Maxlen=max(maxlen,i-m(presum))
If(m.find(presum))==m end ())
 M insert(presum,i))
If left is -1 and right is -1 return v
Else for i from left to right 
 Add a(i) to v 
And return v

Question 2

Longest subarray length
Given an array of 0s and 1s, find the length of the longest subarray such that the count of 1s is more than the count of 0s

Answer 2

Vector int a
 If v(i) is 0 then push -1 to v else 1
Int sum =1
Unordered map s
 Presum =0, res=0
For i from 0 to n
 Presum+=a(i)
If presum==sum, 
  Res=i+1
If(s.find(presum-sum)!=s.end())
 Res=max(res, i-s(presum-sum))
Else if it is not already in the map
 S.insert(presum,i)
Return res

Question 3

2 sum

Answer 3

Unordered map m
Int second=infi
Int first=infi
 Stores first kccurances of different numbers.
For i from 0 to n
If m.find(b-a(i))!=m.end()
 Auto it=m find(b-a(i))
 Auto prev=it.second
 If (iprev)
   First=prev
If(m.find(a(i)==m.end())
 M.insert(a(i),i)
 If first and second are within bounds
Then push them res and return

Question 4

4 sum
A+b+c+d = target?
Given num array and target

Answer 4

For i from 0 to n
 Int target3 =target-num(i)
 For j from i+1 to n
  Target2=target3 -num(j)
  Int front = j+1
  Int back =n-1
 While (front

Question 5

Valid soduku

Answer 5

Vector > rows, col, grid
Pair:: iterator,bool> ret
For i from 0 to 9
 For j from 0 to 9
 Charc= board(i,j)
 If c is . continue
Int gridIDx= coordtogrididx(i,j)
Ret=row(i).insert(c)
I(!ret.second) return false
Ret=col(j).insert(c)
If(!ret.second) return false
Ret=grids(gridIDx).insert(c)
If(!ret.second) return false

Return true

Coorto grid i/3*3+j/3

Question 6

Pairs with given xors

Answer 6

If a xor b is c , then a xor c is b and b xor c is a. 
Now the problem is similar to finding pair with given sum
Unordered set s
Int count=0
For i from 0 to n
 If (s.find(a(i) xor b)!=s end())
   Count++
S.insert(a(i))

Return count

Question 7

Anagrams

Given an rray of strings, return all groups of strings that are anagrams

Answer 7

Vector> Sol
For i from 0 to n
  Temp=a(i)
  Sort(temp begin(), temp.end())
  M.push_back(i+1)

Auto it=m.begin()
While (i!=m.end())
  Sol.push_back(it.second)
  It++
Return Sol

Question 8

Equal a+b=c+d? Multiple solutions, return lexographically smallest

Answer 8

Map(int, pairs(int,int)) sum
Vector int ans
For i from 0 to n
 For j from i+1 to n
  Auto sumab=a(i)+a(j)
  If(sum.find(sumab)==sum.end())
    Sum(sumab) =make_pair(i,j)
  Else
  Pair p = sum(sumab)
 If (p.first<i>temp(t)
  Ans.clear()
  Ans=temp
  Break

Return ans</i>

Question 9

Check palindrome

Answer 9

Unordered map m
Stores frequencies of elements in map
Int count is 0
 For auto it: m
   If it.second%2 is 1
    Count++
If(n%2 is 1 and count<= 1 )
 Ret 1
Else if (n%2 is 0 and count is 0)
 Ret 1

Ret 0

Question 10

Increment problem

Given a stream of numbers a , on arrival of each number increase the first occurance by 1 and include in the stream

Answer 10

Unordered map m
For i from 0 to n
If a(i) is not already present in the map 
  M(a(i)+1)=m(a(i))
M(a(i))=i

For auto it in m
A(i.second)=i.first

Ret a

Question 11

Subarray with given xor

Answer 11

Long long ans=0
Create xorarr
Unordered map m
Create a prefix xor sum array such that xorarr(i) has value equal to xor of all elements form arr(0,i)
Create a map that stores number of prefix array elements  corresponding to xor value
Xorarr(0)=are(0)
Computing xor array
 For i from 1 to 
 Xorarr(i)= xor(i-1) and a(i)

Calculate answer
For i from 0 to n
 Int temp=m xor xorarr(i)
If above xor exists in map, then there is another prefix with same xor , that is there is subarray ending at i with xor equal to m
Ans+=m(temp)
If this subarray has xor equal to m itself
 If (xorarr(i)==m)
  Ans++
Add xor of this subarray to map
M(xorarr(i))++

Return ans

Question 12

Subarray with b odd numbers

Find the total number of subarrays having exactly b odd number

Answer 12

Change even numbers to 0 and odd numbers to 1
Now problem reduces to finding largest subarray with sum b
Unordered map m
Int count=0
Int presum=0
For i from 0 to n
Presum+=a(i)
If presum==b
 Count++
If(m.find(presum-b)!=m.end())
 Count+=m(presum-b)
M(presum)++
Return count

Question 13

Given a string find the length of the longest substring without any repeating char

Answer 13

Map char, int seen
Used to store last position of occurrence
Int max_len is 0
Int start=0

For end from 0 to n
If (seen.find(s(end))!=seen.end())
 Start=max(start,seen(s(end))+1)
Seen(s(end))=end
Max_len=max(max_len,end-start+1)

Return max_len