Leetcode
Assessment
•
Shawn Saunders
•
others
•
•
1 plays
•
Hard
Student preview
80 questions
Show answers
1.
Open Ended
30 sec
1 pt
Trapping rain water problem
Evaluate responses using AI:
OFF
Answer explanation
traverse every array element and find the highest bars on left and right sides. Take the smaller of two heights. The difference between smaller height and height of current element is the amount of water that can be stored in this array element, MINUS the element height itself
An Efficient Solution is to prre-compute highest bar on left and right of every bar in O(n) time. Then use these pre-computed values to find the amount of water in every array element. Below is C++ implementation of this solution.
O(1) Space:
move in from both sides, keep highest left and highest right as 2 variables
keep going till left index is bigger than right index (lo <= hi)
we will calculate water trapped on smaller element out of A[lo] and A[hi] first and move the pointers till lo doesn't cross hi.
you pick the smaller of the 2 because if the right max is zero, doesnt matter that left has water (cant be held in)
2.
Open Ended
30 sec
1 pt
Repeated String Match
Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1.
For example, with A = "abcd" and B = "cdabcdab".
Return 3, because by repeating A three times ("abcdabcdabcd"), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").
Evaluate responses using AI:
OFF
Answer explanation
Reworded:
What is the smallest k such that B is a substring of A*k
Find the smallest q for which len(A*q) >= len(B)
Now try q and then q+1
Why up to q+1? that q+1 gives A enough repeated length to try every starting combination to fit B into
eg. if A = ABC and B = CABCA, in this case
ABCABC is not enough since in this case, B starts with the last letter of the pattern, but adding one more:
ABCABCABC allows the CABCA to appear
BETTER SOLUTION:
Use Rabin-Karp algorithm
3.
Open Ended
30 sec
1 pt
Rabin-Karp Algorithm
Evaluate responses using AI:
OFF
Answer explanation
String searching algorithm
uses hashing to find any one of a set of pattern strings in a text. For text of length n and p patterns of combined length m, its average and best case running time is O(n+m) in space O(p), but its worst-case time is O(nm).
4.
Open Ended
30 sec
1 pt
Find a pattern of length M in a search string of length N (usually N >> M)
Evaluate responses using AI:
OFF
Answer explanation
Use rabin-karp using rolling hash comparison by doing modulo of a prime number
5.
Open Ended
30 sec
1 pt
Height of a binary tree
Evaluate responses using AI:
OFF
Answer explanation
The height of a binary tree is the number of edges between the tree's root and its furthest leaf. This means that a tree containing a single node has a height of 0.
6.
Open Ended
30 sec
1 pt
Binary search tree
Evaluate responses using AI:
OFF
Answer explanation
binary tree in which the value of each parent node's left child is less than the value the parent node, and the value of the parent node is less than the value of its right child.
7.
Open Ended
30 sec
1 pt
Rolling hash for string comparison
Evaluate responses using AI:
OFF
Answer explanation
hash(S)=(∑N−1i=0Si∗pi)%MOD hash(S)=(∑N−1i=0Si∗pi)%MOD
Intelligent choices of p and MOD
help us avoid collisions. We will try to use p,MOD , where MOD is a prime and
p greater than number of distinct elements in our language.
8.
Open Ended
30 sec
1 pt
How to find substring in doc
Evaluate responses using AI:
OFF
Answer explanation
Use rabin karp or KMT, rabin karp can have worse case be O(n^2) i think... but KMT worst case is O(n)
9.
Open Ended
30 sec
1 pt
Next closest time given hr:mn string
Evaluate responses using AI:
OFF
Answer explanation
create a sorted list of digits, keep track of time as a new list of ints (convert from string) and a position dict. starts at [3], and check if current digit is the max it can take on using the pos dict (if number indexes into a value less than 3, its not the largest possible number), if not, check if the next largest number works. if it doesnt, move on to next index of time (left), if it does, reset any smaller indexes to smallest value they can have
10.
Open Ended
30 sec
1 pt
K Empty Slots
Evaluate responses using AI:
OFF
Answer explanation
Let days[x] = i be the time that the flower at position x blooms. For each window of k days, let's query the minimum of this window in (amortized) constant time using a MinQueue, a data structure built just for this task. If this minimum is larger than it's two neighbors, then we know this is a place where "k empty slots" occurs, and we record this candidate answer.
11.
Open Ended
30 sec
1 pt
Longest Substring with At Most K Distinct Characters
Evaluate responses using AI:
OFF
Answer explanation
Keep a left index (to signify start of substring) and keep length variable and current letter variable
Use hashtable to keep track of letter count, and keep track of a "unique characters" count for the current substring
do a rolling method, where you slide/roll the left/length index and keep adding more length if the number of uniques fit in
Its pretty straight forward honestly, but it was labeled as hard so idk
12.
Open Ended
30 sec
1 pt
Why Messaging Queue
Evaluate responses using AI:
OFF
Answer explanation
Enable asynchronous communication via the queue. If the distributed service is flaky and is not always online, you can use a rock solid message queue to persist the messages. The messages are then delivered when the distributed service comes back to life.
If the distributed service has low latency and the client service generates more requests than the distributed service can handle, a queue will hold the messages until the distributed service can process them while allowing the client to process uninhibited.
If requests need to be distributed to multiple services, an exchange will take care the important details such as delivering the message to each distributed service once and only once.
13.
Open Ended
30 sec
1 pt
Utility Class
Evaluate responses using AI:
OFF
Answer explanation
Class with only static methods
14.
Open Ended
30 sec
1 pt
Singleton, and is it thread safe?
Evaluate responses using AI:
OFF
Answer explanation
You need an object that only needs to be instantiate once, so, you can use a singleton. The class needs to declare a private constructor to prevent people to instantiate it from outside the class. Also, you need to declare a static field of the type of the singleton. The method getInstance() assures that only one instance of this class is created at runtime.
Singleton not thread safe
15.
Open Ended
30 sec
1 pt
Find k smallest items
Evaluate responses using AI:
OFF
Answer explanation
Sorting O(nlogn)
Selection sort O(nk)
Max Heap O(k+(n-k)logn)
16.
Open Ended
30 sec
1 pt
in a binary tree, the last row has how many leaves if full
Evaluate responses using AI:
OFF
Answer explanation
(n+1)/2
17.
Open Ended
30 sec
1 pt
array index of parent of i in maxHeap
Evaluate responses using AI:
OFF
Answer explanation
A[i//2]
18.
Open Ended
30 sec
1 pt
left/right child of i in maxHeap
Evaluate responses using AI:
OFF
Answer explanation
A[2i]/ A[2i + 1]
19.
Open Ended
30 sec
1 pt
Data structures used for DFS and BFS
Evaluate responses using AI:
OFF
Answer explanation
Stack for DFS, queue for BFS
20.
Open Ended
30 sec
1 pt
Implement stack using 2 queues
Evaluate responses using AI:
OFF
Answer explanation
2 ways: either make push operation costly or pop operation costly
Put node in empty q1 (q2 has all nodes), now 1 by 1 dequeue from q2 to queue onto q1, then swap names q1 <-> q2
21.
Open Ended
30 sec
1 pt
Queue from 2 stacks
Evaluate responses using AI:
OFF
Answer explanation
same deal: either dequeue expensive or queue
empty stack 1 into stack 2, then add node to stack 1, then empty stack 2 in stack 1
22.
Open Ended
30 sec
1 pt
Data Structure for LRU cache
Evaluate responses using AI:
OFF
Answer explanation
Queue using a doubly linked list and
Hash with page number as key and address of queue node as value
23.
Open Ended
30 sec
1 pt
how to check if tree is BST
Evaluate responses using AI:
OFF
Answer explanation
Do inorder traversal, if at any point, they are not in order (sorted), not a BST
in order: LEFT ROOT RIGHT
24.
Open Ended
30 sec
1 pt
height of binary tree
Evaluate responses using AI:
OFF
Answer explanation
number of edges between root and leaf
25.
Open Ended
30 sec
1 pt
find middle of a linked list
Evaluate responses using AI:
OFF
Answer explanation
Traverse linked list using two pointers. Move one pointer by one and other pointer by two. When the fast pointer reaches end slow pointer will reach middle of the linked list.
26.
Open Ended
30 sec
1 pt
How is a trie node represented
Evaluate responses using AI:
OFF
Answer explanation
letter string, array of pointers to children, array is of length of alphabet
endOfWord bool var to signify this node is the end of a word in the trie
27.
Open Ended
30 sec
1 pt
Complexity to make trie, insert and search
Evaluate responses using AI:
OFF
Answer explanation
insert and search and delete are both O(m), where m is the length of the word
Making a tri is O(m*n), where m is longest word and n is the number of words in the dict
28.
Open Ended
30 sec
1 pt
Memoization
Evaluate responses using AI:
OFF
Answer explanation
term describing an optimization technique where you cache previously computed results, and return the cached result when the same computation is needed again.
29.
Open Ended
30 sec
1 pt
Tabulation vs memoization
Evaluate responses using AI:
OFF
Answer explanation
Memoization:
Doesn't attempt to solve all sub problems.
Tabulation:
Can be done iteratively so less stack space.
Memory can be efficiently used , Unnecessary states can be discarded.
An additional advantage of the iterative approach is that you are often able to save memory by forgetting the solutions to subproblems you won't need in the future.
30.
Open Ended
30 sec
1 pt
When to use memoization vs tabulation
Evaluate responses using AI:
OFF
Answer explanation
Recursion with memoization is better whenever the state space is sparse -- in other words, if you don't actually need to solve all smaller subproblems but only some of them. In such cases the recursive implementation can be much faster. Recursion with memoization is also better whenever the state space is irregular, i.e., whenever it is hard to specify an order of evaluation iteratively.
Iterative solutions are better whenever the state space is dense and regular. If you need to compute the solutions to all the subproblems anyway, you may as well do it without all the function calling overhead.
An additional advantage of the iterative approach is that you are often able to save memory by forgetting the solutions to subproblems you won't need in the future.
31.
Open Ended
30 sec
1 pt
Optimal Substructure
Evaluate responses using AI:
OFF
Answer explanation
In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems. This property is used to determine the usefulness of dynamic programming and greedy algorithms for a problem
the idea that in order to solve a dynamic optimization problem from some starting period t to some ending period T, one implicitly has to solve subproblems starting from later dates s, where t
32.
Open Ended
30 sec
1 pt
Greedy algos and optimal substructure
Evaluate responses using AI:
OFF
Answer explanation
Typically, a greedy algorithm is used to solve a problem with optimal substructure if it can be proved by induction that this is optimal at each step
33.
Open Ended
30 sec
1 pt
Longest increasing subsequence
Evaluate responses using AI:
OFF
Answer explanation
Related to DAG shortest path problem?
Use DP. also O(n^2):
For a given index i in the array, computer DP[i], which is the LIS for the sequence up to i (including)
How do you compute DP[i] for each? You literally try out every possible jump from every number before i to i (0 to i, 1 to i, 2 to i, 3 to i...) in which case nums will be indexed by j
If for a given jump, its a) an increasing jump and b) beats the current record for DP[i], update DP[i] as DP[j] + 1
then take the max of the DP array
INITIALIZE DP[i] values to zero
For n log n, use list of lists method? Duplicate a list and discard lists depending on if num is greater/smaller than last element of lists
34.
Open Ended
30 sec
1 pt
word edit distance (insert, delete, replace)
Evaluate responses using AI:
OFF
Answer explanation
Use DP. make func that has (word1,word2,m,n) where m is len of 1, n is len of 2
make an [m+1][n+1] cache and iterate in a double for loop of (m*n)
35.
Open Ended
30 sec
1 pt
Code for word edit distance
Evaluate responses using AI:
OFF
Answer explanation
def minD(self,word1,word2,m,n):
cache = [ [0 for i in range(n+1)] for x in range(m+1)]
for i in range(m+1):
for x in range(n+1):
if i == 0:
cache[i][x] = x
elif x == 0:
cache[i][x] = i
elif word1[i-1] == word2[x-1]:
cache[i][x] = cache[i-1][x-1]
else: # insert,remove, replace
cache[i][x] = 1 + min( cache[i][x-1], cache[i-1][x],cache[i-1][x-1] )
return cache[m][n]
36.
Open Ended
30 sec
1 pt
Worst case for quicksort
Evaluate responses using AI:
OFF
Answer explanation
O(n^2) if its sorted ascending and pivot is the first index
or if its in descending order and pivot is at the end
thus, try picking a random index for pivot
37.
Open Ended
30 sec
1 pt
Minimum Cost path given a 2-d array of numbers, can only go right or down, min path from top left to bottom right
Evaluate responses using AI:
OFF
Answer explanation
keep a 2-d cache. use DP iterative tabulation bottom up
for loop (2-d), i, k
cache[i][k] = grid[i][k] + min (cache[left] , cache[above])
38.
Open Ended
30 sec
1 pt
Adjacency Matrix
Evaluate responses using AI:
OFF
Answer explanation
adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j
VxV where V is the number of vertices
Remove and lookup take O(1) time
Even if graph is sparse, O(V^2) space
39.
Open Ended
30 sec
1 pt
Adjacency List
Evaluate responses using AI:
OFF
Answer explanation
Array of linked lists
Arr[i] is list of vertices adjacent to vertex i
Can just use a dynamic array instead of linked list
Lookup can take O(V)
use vector in C++
Space is O(V+E), meaning worst case O(V^2)
40.
Open Ended
30 sec
1 pt
BFS graph
Evaluate responses using AI:
OFF
Answer explanation
Use boolean visited array to avoid duplicate visits.
Use a queue to keep track of next node
41.
Open Ended
30 sec
1 pt
DFS graph
Evaluate responses using AI:
OFF
Answer explanation
Use a stack to keep track of next node
42.
Open Ended
30 sec
1 pt
Remove invalid parentheses from string, enter all valid substrings that have the minimum number of removals. can be more than just one substring
Evaluate responses using AI:
OFF
Answer explanation
Super important: keep a level variable at any iteration of the queue popping, so that if you find a valid string at a certain level (of letters), you dont go any deeper
WITHOUT LEVEL LOCK, you will keep adding valid words that are valid but arent the "minimum valid"
BFS over state space of inputed string.
first, check if given word is valid
if it is, add it to the list
if its not, go through the word.
if you arrive at a parenthesis, try out a word without it specifically.
add that new subword to the queue only if its hasnt been visited yet
while char_q.len > 0:
wd = char_q.dequeue()
if self.checkValid(wd):
results.append(wd)
continue
if level_lock == True:
continue
i = 0
while i < len(wd):
charac = wd[i]
if charac == ')' or charac == '(':
temp_string = wd[:i] + wd[i+1:]
if temp_string not in visited:
char_q.enqueue(temp_string)
visited[temp_string] = 1
i += 1
return results
43.
Open Ended
30 sec
1 pt
Given preorder and inorder traversal of a tree, construct the binary tree (suboptimal)
Evaluate responses using AI:
OFF
Answer explanation
SUBOPTIMAL (also is O(N^2) if tree is left skewed)
first element of preorder has to be root of tree, so you look for root in inorder, to the left is the left overall subtree, to the right is the right overall subtree
keep track of indexing variables for the in/pre arrays by passing indexes as parameters (in_end and in_start)
be careful passing the pre variable, using +1 for left and +2 for right, since +1 might be for the right (assuming empty left)
ONLY increment the pre index onto the next root once you have validated your in indexes inhouse (inside the next function call)
44.
Open Ended
30 sec
1 pt
Given preorder and inorder traversal of a tree, construct the binary tree (optimal)
Evaluate responses using AI:
OFF
Answer explanation
IDK... uses a stack and a set.. on G4G if you want to look it up
45.
Open Ended
30 sec
1 pt
Height of a heap and given i, who is parent, left child, right child
Evaluate responses using AI:
OFF
Answer explanation
O(log N)
Root of tree is A[0].
- Parent of A[i] = A[ i/2 ].
- Left child of A[i] = A[2i].
- Right child of A[i] = A[2i + 1].
46.
Open Ended
30 sec
1 pt
Tiny URL shortener (has to be unique)
Evaluate responses using AI:
OFF
Answer explanation
Interviewer is not looking for you to take a string, store it to a map by hashing it, etc
Hes looking for a scalable,durable solution. Think about API (how the user is going to interact with my server), application layer and persistence layer
Draw a block diagram.
Persistence layer is where you are going to store keys
Load balancer takes HTTP client request and assigns it to a working server. At that level, there also could be a cache for requests
Cache layer like memcache or redis
Server/worker thread generates url, stores it in persistence layer
a-z,A-Z,0-9 is a total of 62 characters
Generating tinyURL:
Map storage: key as the tiny url, value as the longer url
Given a string, generate tinyURL and then check if its in the database, if its not, put it there.
PROBLEM:
Some other server thread, after checking, could have put that url in.
Sln: Have a put if absent method, that has to be supported by the database. Only works for relational?
Technique #3:
Generate tinyurl, then put long:tiny in DB.
______________
MD5 approach:
MD5 of longer url, take first 43 bits of that md5, then use that to generate tiny url. Probability of collision.
47.
Open Ended
30 sec
1 pt
Invert binary tree
Evaluate responses using AI:
OFF
Answer explanation
if root == None:
return None
temp = root.left
root.left = self.invertTree(root.right)
root.right = self.invertTree(temp)
return root
48.
Open Ended
30 sec
1 pt
find all possible subtree sums of a binary tree. then output a list of the most common sums (many if ties)
Evaluate responses using AI:
OFF
Answer explanation
Do POST ORDER traversal using a recursive function (kinda), but FIRST call another main function (that ends up calling the recursive search func)
keep track of a global cache map in order to remember the subsums (to use them for the root element sum calculation)
loop thru that map later to take care of the max occurences
class Solution:
def __init__(self):
self.cache = {}
self.nums = {}
def findFrequentTreeSum(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
ret_list = []
if root == None:
return ret_list
self.Search(root)
for key,val in self.cache.items():
if val in self.nums:
self.nums[val] += 1
else:
self.nums[val] = 1
max_num = 0
for key,val in self.nums.items():
if val > max_num:
max_num = val
for key,val in self.nums.items():
if val == max_num:
ret_list.append(key)
return ret_list
# does post order traversal left,right,root
def Search(self,root):
if root.left == None and root.right == None:
self.cache[root] = root.val
return
l_val = 0
r_val = 0
if root.left != None:
self.Search(root.left)
l_val = self.cache[root.left]
if root.right != None:
self.Search(root.right)
r_val = self.cache[root.right]
self.cache[root] = root.val + l_val + r_val
49.
Open Ended
30 sec
1 pt
In a MxN matrix, that is sorted row rise and column wise (in ascending order), count # of negative numbers
Evaluate responses using AI:
OFF
Answer explanation
Keep index i and j, starts at the last index of the arrays (-1) and at the top, so at the top right
If row a's number at index b is positive, then we know that row b's number at index b must at least be positive too, so we can already start looking at index b-1
Hence, you only move worst case O(m+n)
50.
Open Ended
30 sec
1 pt
Count # of palindromic substrings
Evaluate responses using AI:
OFF
Answer explanation
O(N^2), for string of length N, every possible palindrome could have 1 of the 2N-1 possible centers
Loop through the 2N-1 possible centers (each letters and each in-between letters) and at each, expand outward and count palindromes, until you run into one that is not.
At every even numbered center, it counts the actual letter center as a palindrome
O(N): Manacher's algorithm (pretty hard)
Manacher's algorithm fills in a table P[i] which contains how far the palindrome centered at i extends. If P[5]=3, then three characters on either side of position five are part of the palindrome. The algorithm takes advantage of the fact that if you've found a long palindrome, you can fill in values of P on the right side of the palindrome quickly by looking at the values of P on the left side, since they should mostly be the same.
https://stackoverflow.com/questions/10468208/manachers-algorithm-algorithm-to-find-longest-palindrome-substring-in-linear-t
51.
Open Ended
30 sec
1 pt
Frog crossing river given stones[] array, given position of ith stone
If the frog's last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.
Given a list of stones' positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.
Evaluate responses using AI:
OFF
Answer explanation
create a hashtable, with (key,value) pair being (stones[i], set) where the set keeps track of the jumpsizes (k's) that come to that stone (to calculate the different k-1,...,k+1 distances)
loop through stones, for each stone, look at every jumpsize that goes to it. Try out every of k-1,k,k+1 jumps and check if it leads to a stone (by checking if key exists in map), if it does, add jumpsize to set of that target stone
get the answer by asking if hashvalue of last stone is not an empty map, meaning there are jumps possible to it
52.
Open Ended
30 sec
1 pt
Best meeting point
A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group.
Evaluate responses using AI:
OFF
Answer explanation
The middle of a given coordinate is the best meeting point in that coordinate
Get a list of all (x,y) points with a "1" and keep track of a y_val array and x_val array for points
after going through the points, sort the y_val and x_val array. The middle index is the best meeting point
then loop through all the points and total up the distance to that point and return
O(M*N) complexity
53.
Open Ended
30 sec
1 pt
Burst balloon problem:
Evaluate responses using AI:
OFF
Answer explanation
The key idea is, instead of picking the first one to burst, pick the last one. The last one fix the boundary of the both sub-problems so we can divide and conquer.
Use dynamic programming
For each subarray possible, pick the last balloon to pop to maximize value
Can use that info to find max value for entire array
Take a 2-D array thats same size as N^2
[i][j] means subarrays that starts at i and end at j
store value (pop value, index of pop)
First look at subarrays of length of 1
54.
Open Ended
30 sec
1 pt
Longest common Subsequence between 2 input strings
Evaluate responses using AI:
OFF
Answer explanation
Use DP
55.
Open Ended
30 sec
1 pt
Fibonacci number
Evaluate responses using AI:
OFF
Answer explanation
Use DP iteratively, also use the fact that the power matrix to the power of N times the vector [0 1] gives you the fibonacci number for n
You can compute matrix square in log(N) of time but that doesnt mean you get log(N) for fibonacci (because of multiplication) The way out of this apparent paradox is to observe that we can't perform arbitrary-precision arithmetic in constant time
56.
Open Ended
30 sec
1 pt
Maximum subsequent sum
Evaluate responses using AI:
OFF
Answer explanation
O(N), using cache DP
loop through each number, and fill out DP[i], where DP[i] is the largest sum sequence that ends at this index
then loop through all of DP and pick the max
How to save time?
Only loop once, keep track of a best_max variable and a last_max variable
last_max will replace the cache[i-1], to save space and time
best_max avoids the loop at the end
57.
Open Ended
30 sec
1 pt
Buying and Selling Stock (more than once) (without cooldown)
The cost of a stock on each day is given in an array, find the max profit that you can make by buying and selling in those days
Evaluate responses using AI:
OFF
Answer explanation
Add up every interval of valley-->peak
move index i till you get to a valley, make that i the valley variable
keep moving i till find peak
then add peak-valley to sum
The key point is we need to consider every peak immediately following a valley to maximize the profit
58.
Open Ended
30 sec
1 pt
Calculate XOR from 1 to n.
Evaluate responses using AI:
OFF
Answer explanation
for base 2 numbers only:
n % 2^i = n & (2^i + 1)
so n %4 == n & 3
59.
Open Ended
30 sec
1 pt
Count number of set bits in number
Evaluate responses using AI:
OFF
Answer explanation
Use Brian Kernighan's Algorithm
Subtraction of 1 from a number toggles all the bits (from right to left) till the rightmost set bit(including the righmost set bit). So if we subtract a number by 1 and do bitwise & with itself (n & (n-1)), we unset the righmost set bit. If we do n & (n-1) in a loop and count the no of times loop executes we get the set bit count.
FOR O(1) LOOKUP, USE __builtin_popcount (n)
which is a special gcc thing
60.
Open Ended
30 sec
1 pt
middle index of array given start,end
Evaluate responses using AI:
OFF
Answer explanation
(start+end)/2
61.
Open Ended
30 sec
1 pt
Find unique element in sorted array
Evaluate responses using AI:
OFF
Answer explanation
Use binary search for O(log N)
1) Find the middle index, say 'mid'.
2) If 'mid' is even, then compare arr[mid] and arr[mid + 1]. If both are same, then the required element after 'mid' else before mid.
3) If 'mid' is odd, then compare arr[mid] and arr[mid - 1]. If both are same, then the required element after 'mid' else before mid.
62.
Open Ended
30 sec
1 pt
Print tree in level order
Evaluate responses using AI:
OFF
Answer explanation
Use queue, print value of curr node, enqueue left and right child, then dequeue whatever is next
63.
Open Ended
30 sec
1 pt
Daily temperature array, for each element, say the # of days until next warmer temperature
Evaluate responses using AI:
OFF
Answer explanation
use a stack and travel down arraybackwards
for given val at idx i, look at stack, keep popping until you get to a number thats bigger than you. if theres no such number set soln[i] = 0, else set soln at the difference in index between i and the number in the stack
then push yourself onto the stack
64.
Open Ended
30 sec
1 pt
Find duplicate in array of n+1 numbers [1,n]
Evaluate responses using AI:
OFF
Answer explanation
#1 sort N log N and then go over it once, O(1) space
#2 hashtable go over it once O(N)
#3 tortoise and hare cycle algo, have hare move by 2, turtoise moves once each turn (in terms of moving into index value --> index)
65.
Open Ended
30 sec
1 pt
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Evaluate responses using AI:
OFF
Answer explanation
Floyd's tortoise and hare
split into 2 phases:
#1 determines if cycle exists, if not, return null
otherwise, it uses the intersection point to find the entrance to the cycle
#2 We can harness the fact that hare moves twice as quickly as tortoise to assert that when hare and tortoise meet at node
h
h, hare has traversed twice as many nodes. Using this fact, we deduce the following
if they meet at position B, and the start of the cycle is at position A, by the time they meet at position B, and B to A is called C, the hare will have travelled twice as much as turtle, we know that, so we can deduce:
2x (turtle dist) = hare dist
2x (A+B) = (A+B+C+B)
2A + 2b = 2b + A + C
A = C
so to meet at the start of the cycle, they just have to reset one to zero, the other to A, and then march by one together until they meet.
66.
Open Ended
30 sec
1 pt
Iterative inorder traversal (left, root, right) so basically leftmost onwards
Evaluate responses using AI:
OFF
Answer explanation
USE A STACK
1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then
a) Pop the top item from stack.
b) Print the popped item, set current = popped_item->right
c) Go to step 3.
5) If current is NULL and stack is empty then we are done.
vector sln;
if (root == NULL)
return sln;
stack s;
TreeNode* curr = root;
int set = 1;
while(set == 1){
while(curr != NULL){
s.push(curr);
curr = curr->left;
}
sln.push_back(s.top()->val);
curr = s.top()->right;
s.pop();
if (curr == NULL && s.empty())
return sln;
}
67.
Open Ended
30 sec
1 pt
Generate all combinations of N pairs of parentheses
Evaluate responses using AI:
OFF
Answer explanation
Use recursion, try out both adding a closing and a opening bracket, splits into 2, recurse until you reach a bad leaf or if you find a good leaf, at it to the global array solution
void genPar(int opens, int closes, string s) {
if (opens < 0)
return;
if (closes < 0)
return;
if (opens > closes)
return;
if (closes == 0 and opens == 0){
sln.push_back(s);
return;
}
genPar(opens-1,closes,s+"(");
genPar(opens,closes-1,s+")");
}
68.
Open Ended
30 sec
1 pt
First unique character in sequence
Evaluate responses using AI:
OFF
Answer explanation
When building the hash count, make it link to not just the count, but a pair of (count,idx) where idx is first encountered
CAN USE AN ARRAY OF {POSSIBLE_CHARS]
and also use char to int indexing (for cpp)
69.
Open Ended
30 sec
1 pt
Reverse a string
Evaluate responses using AI:
OFF
Answer explanation
Use 2 pointers, reverse from both ends on the spot (string is mutable in CPP)
70.
Open Ended
30 sec
1 pt
Reverse words in a given string (reverse a sentence)
Evaluate responses using AI:
OFF
Answer explanation
(I prefer to first do step #2, then step #1)
1) Reverse the individual words, we get the below string.
"i ekil siht margorp yrev hcum"
2) Reverse the whole string from start to end and you get the desired output.
"much very program this like i"
71.
Open Ended
30 sec
1 pt
Find two nums that sum to X in an array
Evaluate responses using AI:
OFF
Answer explanation
To improve our run time complexity, we need a more efficient way to check if the complement exists in the array. If the complement exists, we need to look up its index.
In first iteration, add each elements value and its index to table, in the second iteration, we check if each element's complement (target-nums[i]) exists in the table
72.
Open Ended
30 sec
1 pt
Maximum Size Subarray Sum Equals k
Evaluate responses using AI:
OFF
Answer explanation
https://xiaokangstudynotes.com/2017/01/24/maximum-size-subarray-sum-equals-k/
int maxSubArrayLen(vector& nums, int k) {
unordered_map mapper;
int sum = 0;
int max_gap = 0;
for(int i=0; i < nums.size(); ++i){
sum += nums[i];
if(sum == k){
max_gap = i+1;
if(mapper.find(sum) == mapper.end())
mapper[sum] = i;
continue;
}
int diff = sum - k;
if (mapper.find(diff) != mapper.end()){
int gap = i-mapper[diff];
if (gap > max_gap)
max_gap = gap;
}
if(mapper.find(sum) == mapper.end())
mapper[sum] = i;
}
return max_gap;
}
73.
Open Ended
30 sec
1 pt
Compare version numbers
Evaluate responses using AI:
OFF
Answer explanation
https://www.geeksforgeeks.org/compare-two-version-numbers/
yeah.... idk
74.
Open Ended
30 sec
1 pt
Remove Nth Node From End of List
Evaluate responses using AI:
OFF
Answer explanation
Use 3 pointers, a,b,c
a and b start at head, c starts before head, at NULL
let a go ahead by N-1 (so if N=1, a,b should be same block)
then keep moving the whole unit together
HOLD UP, YOU CAN JUST USE 2 POINTERS, BUT MAKE THEM BOTH START AT NULL (instead of head) and let the first one go first by N+1
if(b == head)
head = head->next;
else if(b == a)
c->next = NULL;
else
c->next = b->next;
75.
Open Ended
30 sec
1 pt
Time complexity of building a heap
Evaluate responses using AI:
OFF
Answer explanation
o(n)
since heapify (done O(n) times) run time depends on the height of the tree, and most times
Heap of size N has at most n/(2^h +1) nodes with height h
76.
Open Ended
30 sec
1 pt
Split array with positives on 1 side and negatives on the other
Evaluate responses using AI:
OFF
Answer explanation
use 1 quicksort partition
77.
Open Ended
30 sec
1 pt
Find LCA given pointers to root and nodeA, nodeB
Evaluate responses using AI:
OFF
Answer explanation
First, make 2 vectors, both representing path to nodeA and path to nodeB, then loop through both until you find first point of divergence
BUT BETTER SOLUTION BELOW
The idea is to traverse the tree starting from root. If any of the given keys (n1 and n2) matches with root, then root is LCA (assuming that both keys are present). If root doesn't match with any of the keys, we recur for left and right subtree. The node which has one key present in its left subtree and the other key present in right subtree is the LCA. If both keys lie in left subtree, then left subtree has LCA also, otherwise LCA lies in right subtree.
make the function return a treenode
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL)
return NULL;
if(root->val == p->val || root->val == q->val){
return root;
}
TreeNode* l = lowestCommonAncestor(root->left,p,q);
TreeNode* r = lowestCommonAncestor(root->right,p,q);
if (l != NULL && r != NULL){
return root;
}
else{
return l ? l:r ;
}
}
78.
Open Ended
30 sec
1 pt
Find min number of coins to make a sum V
Evaluate responses using AI:
OFF
Answer explanation
use hashmap, build iteratively from 0 to V
watch the -1 return if its needed
79.
Open Ended
30 sec
1 pt
Merge K sorted lists
Evaluate responses using AI:
OFF
Answer explanation
CHECK IF LIST IS EMPTY FIRST (return NULL in that case)
Divide and conquer on vector of list pointers
Make a regular 2-list merge function
then iterate with 2 pointers pointing to start and end of vector, and close in from the ends, merging each pair and making front vector
Keep a last, left and right pointer
istNode* mergeKLists(vector& lists) {
int last = lists.size()-1;
while( last != 0){
int left = 0;
int right = last;
while(left < right){
lists[left] = mergeLists(lists[left],lists[right]);
left++;
right--;
}
last = right;
}
return lists[0];
}
80.
Open Ended
30 sec
1 pt
Pigeonhole sort
Evaluate responses using AI:
OFF
Answer explanation
Find minimum and maximum values in array. Let the minimum and maximum values be 'min' and 'max' respectively. Also find range as 'max-min-1'.
Set up an array of initially empty "pigeonholes" the same size as of the range.
Visit each element of the array and then put each element in its pigeonhole. An element arr[i] is put in hole at index arr[i] - min.
Start the loop all over the pigeonhole array in order and put the elements from non- empty holes back into the original array.
Explore this activity with a free account
Find a similar activity
Create activity tailored to your needs using
.svg)
75 questions
TERM TEST - FEEDBACK AND CONTROL SYSTEM
•
79 questions
DAA -1
•
79 questions
DAA -1
•
75 questions
Game Design Semester 1 Test Review
•
75 questions
test2
•
80 questions
PRf192
•
79 questions
тест
•
75 questions
Unit 4 exam
•