-
Binary Search Tree Complexity
Given a binary search tree with n nodes. What's the time and space complexity of finding the maximum element in that tree?
-> time complexity = O(n), space complexity = 0(1)
time complexity = O(lgn), space complexity = 0(1)
time complexity = O(Ign), space complexity = O(Ign)
time complexity = O(1), space complexity = O(1) -
Differences between linked lists and arrays
A linked list is a data structure that has sequence of nodes where every node is connected to the next node. They are linked using pointers to form a chain. This forms a chain-like link for data storage. Nodes of a linked list are not stored in adjacent memory locations.
Each node object has two parts:
value: the value of this node
• next: pointer to the next node
There are two special named nodes:
• head node (or first): The first node in a linked list
• last node (or last): The last node in a linked list, and its next field point to NULL, which represents it is the last node and there is no next node. NULL can be different in different programming language.
Comparing to array, which is a simple data structure storing elements stored in contiguous memory locations, please select all correct descriptions about these two data structures.
-->
opt1. Array utilize memory better because we need to define the size in initialization, and operating system can optimize it.
opt2. Insertion and deletion process is more expensive in a linked list because we need to go through all nodes to find proper target node. But in array, we can locate the target element by index easily with out going through from the beginning.
opt3. Linked lists is a dynamic data structure, they can grow or shrink based on the needs. But arrays are not, we need to specify the size of arrays in the initialization.
opt4. We use linked lists over arrays when we know there are very less number of random access operations.
3. Tom and Jerry: Cat Training Bootcamp 101
Tom is a genius cat, except that he doesn't know how to catch a mouse.
Tom decides to attend a Cat Training Bootcamp 101 to train himself. Tom is given a 0-Indexed 2D integer array 'catSessions' with dimension n x 2 representing the timestamp of available class sessions.
Jerry (the mouse) wants to help Tom to improve his capability as a cat, so he attends a Cat Bootcamp Support Center. Jerry is also given a 0-indexed 2D integer array 'mouseSessions' with dimension m * 2 representing the timestamp of available activity sessions at the cat support center.
In order for Jerry to help Tom, both of them decide to register for 1 session together such that Jerry's activity timestamp lies completely within Tom's class session timestamp.
More formally:
For 0 <= i < n:
catSessions[i][0] represents the start time of cat class session i.
catSessions[i][1] represents the end time of cat class session i.
For 0 <= i < m:
mouseSessions[j][0] represents the start time of cat support center activity session j.
mouseSessions[j][1] represents the end time of cat support center activity session j.
You want to find two indexes i and j such that:
** catSessions[i][0] <= mouseSessions[j][0] <= mouseSessions[j][1] <= catSessions[j][1]**
Return any possible pair (i, j) that satisfies the above conditions. If there is no such pair, return (-1, -1)
Function Description
Complete the function cat101 in the editor below. The function returns an integer array with size 2 representing the Pair (i, j).
cat101 has the following parameter(s):
. catSessions: a 0-indexed integer array with dimension n × 2 representing the timestamp of available cat class sessions.
• mouseSessions: a 0-indexed integer array with dimension m x 2 representing the timestamp of available activity sessions at the support center to help cats
Input:
3
2
1 5
2 2
4 10
1
2
2 4
output: 0 0
-
Hack The Bank
Tom is a cat and Jerry is a mouse. Tom wants to hack Jerry's bank with his knowledge.
ALL
Tom's bank account password is represented as a single integer tomPassword Jerry's bank account password is represented as a single integer JerryPassword
With Tom's cat knowledge, he thinks he can hack Jerry's account by reordering his password digits and maximizing his password value.
However, to be undetected by the policy, Tom's reordered password value should be less or equal to Jerry's password value.
Return a single string representing the maximum reordered password that is less or equal to Jerry's password value. If there is no such reordering, return "-14
Note that an integer (bank account passwotd) cannot have leading
zero.
Function Description
Complete the function hackTheBank in the editor below. The function returns a string representing Tom's reordered password.
hackTheBank has the following parameter(S):
.
tom Password, a single integer representing Tom's bank account password.
jerryPassword. a single integer representing Jerry's bank account
password.
input :
123
322
output: 321 -
Tom and Jerry: Jerry's Birthday
Tom is a genius cat, except that he doesn't know how to catch a
ALL
mouse.
Tom has a TikTok gift card worth ~ dollars ,and an Amazon gift card worth Y dollars
A TikTok gift card is only able to purchase gifts at the TikTok store.
Similarly, a Amazon gift card only allowed to purchase gifts at an Amazon store
3
Today is Jerry's (the mouse) birthday. Tom wants to buy exactly 2 distinct presents for both Jerry and himself to celebrate their friendship.
Tom is given a 0-indexed 2D integer array items with dimension n
3 representing the available items at both stores.
4
For 0 <= i ‹ n:
5
items/i|[0] represents the source of an item. It has value 1 ffit is from TikTok store. It has value 2 if it is from Amazon store.
• items i|/ represents the price of an Item. items (](2] represents the happiness value this item brings.
Tom is a versatile cat. With his 2 gift cards and his intelligence, return a single integer representing the maximum happiness Tom may bring to Jerry's birthday party by purchasing exactly 2 distinct presents from either store
Function Description
Complete the function maximumHappiness in the editor below. The function returns a single integer representing the maximum happiness Tom may bring to Jerry's birthday party by purchasing exactly 2 distinct presents from either store. maximumHappiness has the following parameter(s):
I : Tom's TikTok gift card value.
Y : Tom's Amazon gift card value
• items: a 0-indexed 2D array with dimension n * 3 representing the available items at both stores
input:
10
8
3
3
1 2 10
1 3 20
1 5 1
output: 30