1. They asked me to implement Stack with
a). Push,
b). Pop
c). add K to bottom e elements
I don't want to use in-built Stack that Java provides. Hence I wrote a class Stack and defined the functionalities for each of the above operations.
I used an array here to maintain stack. Basically it's a Stack using Array.
For a). TC - O(1). Just add to the current free position (top) in the array and increment top.
b). TC - O(1). Decrement top and remove the element.
c). TC - O(e). Iterate bottom e elements (from 0 -> e) and increment by K.
2. Given n integers and value k, print total number of pairs such that,
for all pairs -> (a, b)
a) a < b
b) a + k == b
c) (a, b) should be unique.
For eq., for integers 1 1 2 2 2 and k = 1
You can have only 1 pair = (1, 2).
Because,
a). 1 < 2
b). 1 + k (1) == 2
I used Set to eliminate duplicates and gave the answer in <= O(n) solution.
Basically the tc is O(non-duplicates)
3. Given N integers (which contains duplicates ) in an array, make the array unique.
Constraints,.
1. You can only increment the values and you cannot decrement.
2. Make array unique in minimal number of increments such that the sum of total elements in the array has to be minimum.