DSA - Interview Bit

Question 1

Bubble sort

Answer 1

Keep comparing two elements and keep the higher element to the right. Keep shifting to the end of the array.

Result: The biggest element is put to the end of the array, followed by the next biggest and so on..

Question 2

Insertion sort

Answer 2

Pick an element and keep swapping (shifting the array) with the adjacent element until it reaches its correct position.

Result: The left half of the array is sorted at any point in time. And the right half contains the unsorted array.

Question 3

Selection sort

Answer 3

Find/select the min element from the array and place it at the beginning of the array. Select the next smallest element and place it in the second position and so on..

Result: The left half contains the sorted array at any point in time.

Question 4

Check if the tree is a valid BST

Answer 4

Define a range on each node and check if its value lies in that range

Question 5

Zig-zag level order tree traversal

Answer 5

Use 2 stacks

Question 6

SUBSET-SUM PROBLEM

Find a subset of an array which equals sum = k

Answer 6

DP: Element of choice = the number is included in the subset or not

Question 7

Longest contiguous subarray with equal number of 0s and 1s

Answer 7

Replace all 0s with -1.
Compute and store prefix sum.
If the prefix sum value at any two indices is equal, it means the number of 0s and 1s between those numbers is equal, and which is why they added up to zero.

Use hashmap {sum: min_index} to store the prefix sum as you traverse the array and maintain a maxlen variable.

REMEMBER: hashmap[0] = -1
The prefix sum is 0 at the start. We need to store this because if at any later index the prefix sum is 0, and we want to match with the min_index where we encountered 0 previously using the hashmap, that will be -1th index (where the sum was 0).

Question 8

Max element in every k elements of an array

Answer 8

Double-ended queue

Question 9

Merge overlapping intervals

Answer 9

https://leetcode.com/problems/merge-intervals/submissions/

Question 10

Given a sorted array of integers, find the number of occurrences of a given target value.
If the target is not found in the array, return 0

Answer 10

Linear scan - O(n)
BINARY SEARCH - O (log n)

https://www.interviewbit.com/problems/count-element-occurence/

Question 11

DP solving techniques

CodeCamp + Scaler academy

Answer 11

Questions will be like:

1. In how many ways can you … ? Find number of substrings/arrays/sets … such that … ?
2. Maximize/Minimize x

• Optimal substructure: Express the bigger problem into smaller problems. Look for the solution to smaller problems and see how to build the solution for the bigger problem = RECURSION.
• Overlapping subproblem: Reuse the previous states by storing them = DYNAMIC PROGRAMMING

1. What does each state represent?
2. What parameters are required to describe each state?
3. Element of choice

ANS: Create a recursive equation f(n) and use memorization.
Use top-down approach to create the base cases and recursive equation.

In case 1) . ‘n’ will be some target value given in the question.
eg: In how many ways can you create the sum (= n) from an array (subset problem),
In how many ways can you travel from the starting point to n.

In case 2) ‘n’ will not be given explicitly in the question. You will take ‘n’ as the length of the given problem (array, matrix etc.)
eg: Maximize robber sum from the given houses. Here n will become the number of given houses

Question 12

DP problems:

1. Stairs problem
2. Coin change
3. Number of ways to reach (n,m) in a matrix
4. Min cost path in matrix
5. Party pairs problem
6. Subset problem (and its variants)

Answer 12

https://www.scaler.com/academy/mentee-dashboard/classes

Question 13

Find the kth smallest element in an array
Constraints: No extra space, cannot modify the array

More specific: Find median of an array
(Here, k = N/2)

Answer 13

1. Sort array and return the middle element
2. Use modified Binary search

The median will have exactly N/2 elements lesser than it.

Count the number of elements lesser than mid (lt) and number of elements equal to mid (eq).

Question 14

Binary Search Main Idea

Answer 14

Given a random number x, can I decide if my answer will definitely be >x or

Question 15

Find the missing number in an array of given range [1,n]

Answer 15

1. Sum of first n natural numbers - Sum of array
   = n(n+1) / 2 - sum(arr)
2. XOR
   a = Element wise XOR all elements of array
   b = Element wise XOR of numbers between [1,n]
   Missing number = a^b

https://www.geeksforgeeks.org/find-the-missing-number/

Question 16

Trapping rainwater

Answer 16

1. Create Left max and Right max arrays
   O(n) time, O(2n) space
2. Instead of storing the left max and right max of every element, compute them in the loop.
   O(n) time, O(1) space

Question 17

Rotate an array k times

Answer 17

1. Rotate one element at a time. For each of the k elements, n elements are shifted.
   O(n*k) time, O(1) space
2. Use temp array
   O(n) time, O(k) space
3. Reverse the original array. Reverse arr[:k] and arr[k+1:]
   O(n) time, O(1) space

Question 18

Print tree in vertical order

Answer 18

Leetcode

Question 19

Count Sorted Vowel Strings

Given an integer n, return the number of strings of length n that consist only of vowels (a, e, i, o, u) and are lexicographically sorted.

Answer 19

https://leetcode.com/problems/count-sorted-vowel-strings/discuss/918760/Dynamic-Programming-Python-100-Explanation-%2B-code

Question 20

Perfect Sum Problem (Print all subsets with given sum)

Answer 20

https://www.geeksforgeeks.org/perfect-sum-problem-print-subsets-given-sum/

Question 21

Linked List important points

Answer 21

Most problems require you to maintain 2 pointers: prev, current
prev = None
current = head
And within a while loop current != None, we will maintain nextNode pointer = current.next

Conditions are checked on the current node

1. After deleting a node (prev.next = current.next), prev is not moved/updated (prev = current) in the while loop because we need a reference to the prev of the deleted node in order to link it to the remaining list. Only current is moved/updated (current = current.next), prev stays as it is.
2. Take care of null pointers when accessing node.next
   Use if-else wherever appropriate.
   node.next if node else None

3. Base cases
        # empty list or list with only one node
        if head == None or head.next == None:
            return False

4. Fast and slow pointers - used to find middle element of the list, cycle detection, kth node from end (variant of fast-slow),
5. Double check while loop condition of what you want (while current != None OR while current.next != None)