DayOne Flashcards
Remove nth item from end of singlylinked list
Create 2 pointers with n distance between them.
1) Traverse once to reach nth node of the list to initialize pointer 1
2) initialize pointer 2 to start of the node.
3) Traverse second time with while loop to reach end of the node.
4) pointer 2 should be at the node that needs to be deleted.
5) to delete, either copy next node to current node and delete next node or just point to the next to next node.
single pass solution:
1) create a size variable to 1
2) start looping increment first pointer for every step
3) increment second pointer only after size > n+1.
4) is size equals n return head.next
4) node.next = node.next.next to delete the node.
ARRAYS/Strings
Decode alphabets to number of ways.
Input: s = “12”
Output: 2
Explanation: It could be decoded as “AB” (1 2) or “L” (12).
1) Use recursion to go from end of the string to the start of the string
2) create memory object to save time
3) check code for 26 digits.
4) straight iterative approach using DP.
5) use index to go from 0 to end of the length,
https: //medium.com/javascript-in-plain-english/facebook-coding-interview-questions-9e40bdbbec35
6) 2 base cases:
for single digit return 1
for double digit return 1 if number less than 26
If the length is 2, we always have 1 way with all digits separately, plus one if a number is less than 26, we also use this one as a base case.
'12':
['1', '2']
['12']
---------------------
F('12') = f('12') + 1
F(‘123’) = f(‘1’) * F(‘23’) + F(‘12’) * f(‘3’) = 3
Final, all next cases can be calculated using this way.
F(‘4123’) = f(‘4’) * F(‘123’) + f(‘41’) * F(‘23’) = 3
Number of Islands: Graphs and BFS traversal.
try dfs solution when reviewing
1) Matrix is a list of lists, grid[0][0] is row 1 and column2
2) numbers of rows is len(grid), number of columns is len(grid[0])
3) loop twice for row and nested for column with range(rows) and range(cols)
4) create a bfs search on row and column, create a visited tuple.
5) while loop in bfs with queue for neighors of row and col with directions [[0,1],[0,-1],[1,0],[-1,0]]
6) condition to add to queue is:
if (r in range(rows) and c in range(columns)
and grid[r][c] == “1” and (r,c) not in visited):
my_queue.append((r,c))
visited.add((r,c))
7) condition to increment islands is:
if grid[row][col] == “1” and (row,col) not in visited:
bfs(row,col)
islands +=1
Best time to buy stock/array traversing
hint:
greedy approach
1) initialize the maxprofit as arr[1] - arr[0]
2) min price as arr[0]
3) traverse the array starting 1
4) get current price
5) potential profit is currentorice-minprice
6) max profit is max of potential or maxprofit
7) min is current price or prev min price.
Given a string of round, curly, and square open and closing brackets, return whether the brackets are balanced (well-formed).
For example, given the string “([])”, you should return true.
1) make a list with opposite brackets
2) edge cases, odd length len%2==0 ir starting with invalid
3) for every valid bracket append opposite in stack.
4) check for opposite pop in the stack
5) does not match return false, or is stack list is > 0 after the loop
6) return true
6
f
7
g
8
h
9
i
10
j
