Problem Approach

Question 1

Trapping water

Answer 1

Have two separate arrays for figuring out the maximum heights when you start from the left and if you start from the right.

Now when you iterate through the given array you can find the minimum among the left and right max arrays, say that is X.
X - value of the current index in the given array will give you its capacity.

Add up all the values and thats how many units of water

Question 2

How do you reverse a string? [sort of a linkedlist o(1) space problem]

Answer 2

Can be done with two pointers at the end and exchange as you iterate

Question 3

What is the best approach when there are repetitive actions to be done with just a change of parameters?
For instance, to swap adjacent nodes in a linkedList

Answer 3

When there are repetitive actions to be done with just a change of parameters recursion is a good choice

swapNodes(Node s)
{
  // since we are passing the node next to the second
  first.next = swapNode(second.next);
  second.next = first;

  // in the end return the second 
  return second;
}

Question 4

How do you reverse a linked list

Answer 4

Recursion can be used since only a change of parameters needs to be done with each call.

Question 5

Capacity of water

Answer 5

Since the capacity is determined by both width and height, we can start with the largest width and work our way.

so therefore start with the extremes and calculate the capacity and move either pointer only if there is a line greater than it(this means that there is a possibility of higher capacity). At every point you will keep track of the max capacity

Question 6

Three sum problem

a+b+c =0 given a list of integers

Answer 6

sort the array(nlogn)
then taking one of the elements as a pivot we call twosum method
In this method we calculate the sum of pivot + lo + high
if that sum is > 0 then we need to decrement high
if sum < 0 increment lo
else we have our result

now to avoid having duplicates we can move our lo pointer if two values are repeated (i.e duplicates)

Question 7

give an array of integers find the product of i = product of values at all other indexes than i

Answer 7

generate two new arrays left and right.
Left array is the product of all elements to the left of an index
Right array is the product of all elements to the right of an index

then multiple the values in both arrays to get the result

Question 8

Find the median of two sorted arrays

Answer 8

this is like the last step of merge in merge sort. you compare the first elements and add to an auxiliary array . This would take O(m+n)

In order to do this in O(log(m+n)) you can just consider only the left array of the combined array(so only half of the subset) since all elements to the left of median will be less than median.

consider what is the mid point for the combined array that gives number of elements x in left array
Now assuming all x come from the first array. we start from the middle of the first array and compare that value with the mid+1 of the second array. If its more that indicates that we need to consider more elements from the second array. Similar comparison is done for the second array as well. if neither conditions satisfy then we have found the right partition and just need to confirm by comparing both mid’s

Question 9

Dutch national flag problem. Sort a given array of integers in order where each color represents a number. This must be done in place and going over the array only once
[0,1,0,2]

Answer 9

We use three pointers
one is the current element (curr)
one is the leftmost element ( left)
one is the rightmost element (right)

if the current == 0 we swap curr with left
then we curr++ and left++

if the current == 2 we swap curr with right
then right–;

else we curr++;

all of this is done till curr <= right;

Question 10

Quick Select

Answer 10

Used in problems where kth frequent, kth largest, kth less frequent

similar to doing quick sort but we can make it more effective by considering only one half

while partitioning consider right most element as pivot
pivot = arr[right]
i= left;
j = left till right
compare if the j <= pivot then swap i with j

once you go through all elements then swap i with pivot and return i;
Then compare i with the kth element position. If it isn’t same then consider which side of the array to perform quick select again

Question 11

Given a graph, of street view with time to travel between vertices. Given a start and end location find the time taken to travel.

Answer 11

Similar to Dijakstra

Question 12

What data structure would you use for a LRU Cache(least recently used) that will do insert and delete in constant time and delete the first added value?

Answer 12

There is a structure that combines both hashmap and linked list. in Java LinkedHashMap.
OR
you can use a hashmap of key to value(value: is a doubly linked list so that removal from front is easy)

Question 13

How would you find the longest palindromic substring

Answer 13

an approach is to try expand as you go through the characters of the string. eventually you will reach a point where a possible palindrome can form as you expand from it

Question 14

Some operations whose time complexity is often mistaken

Answer 14

1. Adding or removing (or even changing) just one character anywhere in a string is O(n)O(n), because strings are immutable. The entire string is rebuilt for every change.
2. Adding or removing not from the end of a list, vector, or array is O(n)O(n) because the other items are moved up to make a gap or down to fill in the gap.
3. Checking if an item is in a list, because this requires a linear search. Even if you use binary search, it’ll still be O(\log n)
4. Recall that checking if an item is in a set is O(1)

Question 15

Coin change problem

Given coins [1,2,5] what is the minimum coins to make amount =11

Answer 15

Can use dynamic programming
generate a dp array starting from 0 to the amount.
initialize all values to amount+1;
initialize dp[0] = 0 , since in order to generate amount =0 the minimum coins will always be 0.
keep building this dp array utilizing the previous values

the dp[amount] will have the answer. if its value > amount+1 that means there is no solution

Question 16

How would you return the next lexicographic permutation for a given array of integers

eg: [1,2,3]

the permutations are 123, 132,321 etc
ans: 132

Answer 16

start from the rightmost side and find the first number a[i] < a[i+1]
in this case it is 2
then start again from the right and find the first number > 2, which is 3.
exchange 2 and 3
1 3 2
and reverse all elements after 3

Question 17

How do you group given strings into groups of anagrams?

Answer 17

Method 1:
for every string
sort the string
put it in a map with key(the sorted string) and value the actual string

this way the map with have a list of strings in its values

return a new ArrayList(map.values())

Method 2:
use an array of 26 letters for EACH string.
populate it with the count of characters in that word
example :raat will have [2,0…….1,…..1] where 2 is the count for ‘a’ and 1 for r and t

generate a unique key using these values(can add # before each count to generate a unique string to be used a hash key of a map or add all the counts )

check if that key exists in the map if it does append the string s to the list of values
else add it to the map

return a new ArrayList(map.values())

Question 18

Parentheses problem

Answer 18

Stacks and recursion

Question 19

How to find distinct values in a list

Answer 19

Use one slow pointer and other faster. move the faster pointer till you find a non distinct value and then swap with the value that repeats

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length == 0 || nums.length == 1) return nums.length;

        int i =0;
        for(int j = 1 ;j< n ;j ++){
           if(nums[i] != nums[j]) {
               i++;
             nums[i] = nums[j];
           } 
       }
        return j+1;
    }
}

Question 20

How to find the integer that occurs once in an array of integers in which there are exactly two occurrences of every value except for one?

Example:
Input: [2,2,1]
Output: 1

Answer 20

Hashmap can be using to keep track of counts
Hashset as well

In ONLY this scenario where there are exactly TWO occurrences we can do bit manipulation (XOR)
class Solution {
  public int singleNumber(int[] nums) {
    int a = 0;
    for (int i : nums) {
      a ^= i;
    }
    return a;
  }
}

Question 21

How to find max or min number of items in an array that appear consecutively?

Example:
Input :[1,1,2,2,2]
Output : 3 (2 occurs thrice)

Answer 21

Determine what is the starting point of a window(consecutive items) and then determine how to end that window

Question 22

Critical connections in a graph

Answer 22

Tarjan’s Algorithm:
We have to find the articulation points(the vertex if removed will cause the graph to be disconnected)

Need to do dfs because we have to go through each edge therefore recursion
maintain visitedTime and lowestTime

Question 23

Rotten oranges

Answer 23

We need to do bfs since we want the minimum path to make all oranges rotten

We need a queue of a pair in order to keep track of which row and column we are at
this will help us know if we have to continue going through the grid to ensure all oranges are rotten
int freshOranges = 0;
int minutes = -1;

//Put only rotten oranges in a queue so we can pull each one out and reduce freshoranges count by 1 for every neighbor
 //This is added to the queue to indicate one level so we will know that a minute is elapsed
        queue.offer(new Pair(-1, -1));

        //this shows all possible directions from say origin 0,0. It can be used to derive the neighbours for a give row and column
        int[][] directions = {{-1,0}, {1,0}, {0,1}, {0,-1}};

while we remove elemnts from queue if the value ==-1 that means we finished a level and can increment minutes else for every direction we set the value to 2(make them rotten) and add them to the q since they are now rotten and also reduce the number of fresh oranges.

in the end if the fresh oranges are 0 we have our answer else there was no way to make all them rotten

Question 24

Topological sort

Answer 24

Only can be performed on a directed acyclic graph

This means providing the order of vertices such that all edges are directed upwards

Useful for figuring out the precedence (like course schedule)

It uses dfs and a stack. For every node if it isnt visited perform dfs. After all the neighbors are visited , add the node to the stack

return the stack

Question 25

Krushkal Algorithm

Answer 25

To find the Minimum spanning tree which is the lowest weight tree that connects all vertices

Question 26

Backtracking algorithm

Answer 26

def backtrack(candidate):
    if find_solution(candidate):
        output(candidate)
        return

# iterate all possible candidates.
for next_candidate in list_of_candidates:
    if is_valid(next_candidate):
        # try this partial candidate solution
        place(next_candidate)
        # given the candidate, explore further.
        backtrack(next_candidate)
        # backtrack
        remove(next_candidate)

Question 27

How is a 2D array stored in reality in memory

Answer 27

So a 2D array is stored as a single one dimensional array.

the memory it is stored at is inumberOfCol +j where i is the row and j is the column.
For example: position arr[2][1] , in a matrix with 4 rows and 3 columns.
the memory location allocated to it is
23 +1 = 7

In order to get the row we will do 7/3 =2
In order to get the column we do 7%3 =1

Question 28

What are prefix sums

Answer 28

It allows for the fast calculation of sums of
elements in given slice (contiguous segments of array). Its main idea uses prefix sums which
are defined as the consecutive totals of the first 0, 1, 2, . . . , n elements of an array
for an array a,

p0 = 0
p1 = a0
p2 = a0 + a1 and so on

Question 29

What is the greedy approach?

Answer 29

Pick the locally optimal move at each step, and that will lead to the globally optimal solution.

Question 30

Two Sum Problem

Given an array return the indices of the two elements whose sum is equal to a given target

Answer 30

Iterate through the array and build a hashmap, key [ = target - current element in array] and value will be the index of the current element. Before doing so also check whether key exists, if so, you found the other index.

Question 31

Given a small string s and a big string b, we need to find all permutations of the shorter string s in b.

Answer 31

Sliding window solution.

Slide through b using the window size as s.Length and then see if a permutation of s exist in that window

Question 32

Permutation problems

Answer 32

Start thinking with Recursion.
For instance, find all the permutations for the string “abc”
we can start with permutation of a
a => a
a => insert b in every permutation of a => ab, ba
ab => insert c in every permutation of ab => cab acb abc
ba => insert c in every permutation of ba => cba bca bac

Question 33

Problem with ordering and finding medians

Answer 33

Start with trees or heaps

Question 34

Sorted array related problems and to solve it in-place as in without creating a new array

Answer 34

Think of two pointer or 3 pointer approach (whatever is applicable). Also whenever you’re trying to solve an array problem in-place, always consider the possibility of iterating backwards instead of forwards through the array. It can completely change the problem, and make it a lot easier.

Question 35

Data structure to process elements in order

Answer 35

Queue. For implementing queue there are two pointers head and tail. And you can calc tail using this formula:

tailIndex = (headIndex + count) % size - 1

where count is the number of elements filled and size is the total size of the array.

Question 36

Moving window average

Answer 36

We need to process elements in order, so Queue will be a perfect data structure for this

Question 37

IF sorted THEN

Answer 37

(binary search OR two pointer)

Question 38

IF all permutations/subsets THEN

Answer 38

backtracking

Question 39

IF tree THEN

Answer 39

(recursion OR two pointer OR obvious recursion)

Question 40

IF graph THEN

Answer 40

dfs/bfs

Question 41

IF linkedlist o(1) space THEN

Answer 41

two pointer

Question 42

IF obvious recursion problem but recursion banned THEN

Answer 42

stack

Question 43

IF options (+1 or +2) THEN

Answer 43

DP

Question 44

IF k items THEN

Answer 44

heap

Question 45

IF common strings THEN

Answer 45

(map OR trie)

Question 46

Stock buy and sell problems where prices are listed as array

Answer 46

These are considered peak-valley problems, where you want to find the lowest valley and highest peak.

Question 47

Robot bounded in circle or what are the conditions for limit cycle trajectory

Answer 47

These problems are solved using limit cycle trajectory. A trajectory is considered limit cycle if:

1. either we reach at the origin point after one cycle of instructions
2. or we end at a different direction after one cycle of instructions, so for instance, started towards north and ended towards west

Limit cycle trajectories are based on the principle that after 4 cycles the robot will reach at the origin