Sliding Window

Question 1

What are the various approaches of Sliding Window ?

Answer 1

1. Sliding Window with fixed Size 2. Sliding window with variable size 3. Sliding window with hashmap. 4. Sliding window with tracking of maxValue .
2. Window with a substring function
3. Window stored ina dequeue

Question 2

1. How can we detect sliding window ?

Answer 2

1. Whenever we have Sequential Values
2. Substring problems which is again sequential values.
3. Longest sub array type of problems
4. Contiguous elements in a linkedlist

Question 3

1. How to get the number of elements between 2 index

Answer 3

highindex - lowIndex +1

Question 4

1. What is the general format ?

Answer 4

Question 5

Common errors in 2 pointer method ?

Answer 5

1. While iterating you might miss an element when you do it while(left<right>
   </right><li>last pointer should be in arr.length-1 not arr.length</li>

</right>

Question 6

Whats the gotcha for sort in js ?

Answer 6

The sort is alphabetic , so we need to pass the function to make it sort properly

Question 7

What does in-place replacement and constant space signify ?

Answer 7

It should immediately indicate swapping

Question 8

Whenever we need to generate integer from strings , add (sum), multiply or have any integer operations. What is a potential pitfall

Answer 8

1. 1. Always think of max bytes .
2. it could be individual numbers are integers but when you sum them , you get the bytes overflow

Question 9

What are the properties of XOR ?

Answer 9

1. taking XOR of a number with itself returns 0, e.g.,

1 ^ 1 = 0

29 ^ 29 = 0

Taking XOR of a number with 0 returns the same number, e.g.,

1 ^ 0 = 1

31 ^ 0 = 31

XOR is Associative & Commutative, which means:

(a ^ b) ^ c = a ^ (b ^ c)

a ^ b = b ^ a

Question 10

How to invert bytes of a number ?

Answer 10

number ^ complement = all_bits_set

number ^ number ^ complement = number ^ all_bits_set

0 ^ complement = number ^ all_bits_set

complement = number ^ all_bits_set

Question 11

How to store a binary tree ?

Answer 11

If parent is at i

LeftChild 2i

RIghtChild2i+1

Level order traversal , keep missing rows blank

Question 12

If the height of the binary tree is h , how many element in full bionary tree ?

Answer 12

2^(h+1)-1

Question 13

Whats hieght of a binary tree ?

Answer 13

log N

Question 14

What should immeditaley come to mind when you see hash map and charachetrs

Answer 14

Hashmap of 26 charachters

Do you need repetitions ?

Question 15

During DFS , whats the complexity?

Answer 15

, it is the size of the tree

Question 16

What are the 2 key terms of tree traversal ?

Answer 16

1. Visiting a vertex - landing on a vertex
2. Exploration of a Vertex - Visting all its adjacent vertices

Question 17

Difefrence between BFS and DFS

Answer 17

• In BFS we will explore a vertex then go to next vertex for exploration
• In DFS , once visited the new vertex , we suspend the vertex and start explorarion
• Use a Queue - DFS
  
  • Push root into the que , start exploring its children and push them to the queue till nothing is left
  • Pop and follow the same approach
  • Level Order Traversal
• Use a stack - DFS
  
  • preorder traversal
• print when you visit

Question 18

What is the complexity of inserting into the a sorted array ?

Answer 18

Inserting a number in a sorted list will take O(N) time if there are ‘N’ numbers in the list. This insertion will be similar to the Insertion sort.

Question 19

What are the functions a heap ?

Answer 19

Push()

pop()

length

peek()

Question 20

What is a balanced binary search tree ?

Answer 20

If the depth of 2 subtrees of any node differ no more than 1

Question 21

Whats the time complexity of knapsack

Answer 21

1. brute force 2^n - (2^​n​​)+(2^​n​​)−1
2. DP - O(NC)

Question 22

DP , when to pass count , and when to return count ?

Answer 22

1. If the count needs to be reset as Longest common substring , its best to pass the count. as well as return it . Because count from parent culd be reset.
2. If the count stays same and does not need to be reset , we should be able to return count and add the current parets count to the child .

Question 23

What should we remember while passing values into recursion ?

Answer 23

1. See if we can pass values which are function of index rarther than the value itself .
2. instead of sending prev values , can you send the prev index ?

Question 24

What are the steps for topological sort ?

Answer 24

1. Make an adjecancy list
2. reate an indegrees array ( index ->count of in edges)
3. Find sources, for in degrees which are 0 and push them tinto queue
4. Start the top sort process
   
   1. Keep running till queue is empty
   2. Dequeue an element and put it into sorted array
   3. Get all the child vertex from the adjacanecy list for that element
   4. For each of child vertex
      
      1. Decrease indegress by 1
      2. if indegrees of any child drops to 0 , enqueue it.
5. The sorted list is topologically sorted.
6. if length of sorted list is less than vertex , there is a cycle

Question 25

1. Whats the difference between Sliding Window and 2 pointer

Answer 25

1. 2 pointer works on sorted numbers
2. Sliding window works on a contibuous sequence
3. 2 pointer works on 2 numbers independently , it does not care what is inside the 2 pointers .
4. Sliding window cares about what is inside the window

Question 26

How do we solve the 3 sum ?

Answer 26

1. First choice should be to use the 2 pointers approach as it does not require extra space .
2. THink of duplicate cases
   
   1. Duplicate while starting the looking for sum()
   2. Duplicate while finding the 2pointers

Question 27

For an array with distinct elements, finding all of its contiguous subarrays . Whats the space complexity ?

Answer 27

It is not all the Combinations of all elements of the array!

For an array with distinct elements, finding all of its contiguous subarrays is like finding the number of ways to choose two indices i and j in the array such that i <= j.

If there are a total of n elements in the array, here is how we can count all the contiguous subarrays:

When i = 0, j can have any value from ‘0’ to ‘n-1’, giving a total of ‘n’ choices.

When i = 1, j can have any value from ‘1’ to ‘n-1’, giving a total of ‘n-1’ choices.

Similarly, when i = 2, j can have ‘n-2’ choices.
…
…

When i = n-1, j can only have ‘1’ choice.

Let’s combine all the choices:

n + (n-1) + (n-2) + … 3 + 2 + 1

Which gives us a total of: n*(n+1)/2n∗(n+1)/2

So, at the most, we need a space of O(n^2) for all the output lists.

Question 28

Print all subarrays of a given array

1. int [] a = {1, 2, 3}; Output: Possible subarrays – {1}, {2}, {3}, {1, 2} , {2, 3}, {1, 2, 3}
2. ordering of number is not important.
3. Element need to be Contiguous.

Answer 28

1. O(n^3) - Time complexity
2. OUterloop - window size
3. Inner loop start point
4. most inner - iterate and print - or clone and push

https://www.geeksforgeeks.org/subarraysubstring-vs-subsequence-and-programs-to-generate-them/

Question 29

1. Print all possible combinations of a given array
2. Input: [1, 5, 3] Output: [], [1], [5], [3], [1,5], [1,3], [5,3], [1,5,3]

Answer 29

Time complexity #

Since, in each step, the number of subsets doubles as we add each element to all the existing subsets, the time complexity of the above algorithm is O(2^N)O(2​N​​), where ‘N’ is the total number of elements in the input set. This also means that, in the end, we will have a total of O(2^N)O(2​N​​) subsets.

Space complexity #

All the additional space used by our algorithm is for the output list. Since we will have a total of O(2^N)O(2​N​​) subsets, the space complexity of our algorithm is also O(2^N)O(2​N​​).

Question 30

Suppose we have an array 1,2,3,4,5,6

window 2,3,4

Then window expands to include 5 .

HOw many sub arrays can we make that include the last element ?

Answer 30

right - left + 1

For every right, we update left and prod to maintain this invariant. Then, the number of intervals with subarray product less than k and with right-most coordinate right, is right - left + 1. We’ll count all of these for each value of right.

https://leetcode.com/problems/subarray-product-less-than-k/solution/

Question 31

Whats the difference betwen shift and unshift ?

Answer 31

Shift remove from the first beginning

Unshift - insert into the beginning

Question 32

1. Given a set of numbers that might contain duplicates, find all of its distinct subsets.
2. Whats the special duplicate handling ?

Answer 32

1. We sort the numbers
2. Instead of adding the dup num to all the sets generated , we aonly add the dup num to the sets generated by the previous iteration
3. Keep track of the end index (length of array) fromthe previous iteraton

Question 33

How many permutations possible ?

Input: [1,3,5] Output: [1,3,5], [1,5,3], [3,1,5], [3,5,1], [5,1,3], [5,3,1]

Answer 33

If a set has ‘n’ distinct elements it will have n!n! permutations.

Question 34

How do you get bit count of a number ?

Answer 34

while (n > 0) {

bit_count++;

n = n >> 1;

}

Question 35

How do you get a number with all bts set ?

Answer 35

let all_bits_set = Math.pow(2, bit_count) - 1;