1. Given an integer k and
a binary search tree, find the floor (less than or equal to) of k, and the ceiling (larger than or equal to) of k. If either does not exist, then print them as None.
2. You are given
two singly linked lists. The lists intersect at some node. Find, and return the
node. Note: the lists are non-cyclical.
Example:
A = 1 -> 2 -> 3 -> 4
B = 6 -> 3 -> 4
This should return 3 (you may assume that any nodes with the same value are the same node).
Example:
A = 1 -> 2 -> 3 -> 4
B = 6 -> 3 -> 4
This should return 3 (you may assume that any nodes with the same value are the same node).
3. You are given an array. Each element represents the price
of a stock on that particular day. Calculate and return the maximum profit you
can make from buying and selling that stock only once.
For example: [9, 11, 8, 5, 7, 10]
Here, the optimal trade is to buy when the price is 5, and sell when it is 10, so the return value should be 5 (profit = 10 - 5 = 5).
For example: [9, 11, 8, 5, 7, 10]
Here, the optimal trade is to buy when the price is 5, and sell when it is 10, so the return value should be 5 (profit = 10 - 5 = 5).
4. Implement a queue class using two stacks. A queue is a
data structure that supports the FIFO protocol (First in = first out). Your
class should support the enqueue and dequeue methods like a standard queue.
5. Given an array with n objects colored red,
white or blue, sort them in-place so that objects of the same color are
adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note: You are not suppose to use the library’s sort function for this problem.
Can you do this in a single pass?
Example:
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note: You are not suppose to use the library’s sort function for this problem.
Can you do this in a single pass?
Example:
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Output: [0,0,1,1,2,2]
6. Given a list of words, and an arbitrary
alphabetical order, verify that the words are in order of the alphabetical
order.
Example:
Example:
Input:
words = ["abcd", "efgh"], order="zyxwvutsrqponmlkjihgfedcba"
Output: False
words = ["abcd", "efgh"], order="zyxwvutsrqponmlkjihgfedcba"
Output: False
Explanation:
'e' comes before 'a' so 'efgh' should come before 'abcd'
Example 2:
Example 2:
Input:
words = ["zyx", "zyxw", "zyxwy"],
order="zyxwvutsrqponmlkjihgfedcba"
Output: True
words = ["zyx", "zyxw", "zyxwy"],
order="zyxwvutsrqponmlkjihgfedcba"
Output: True
Explanation: The words are in increasing alphabetical order
7. You
are given a binary tree representation of an arithmetic expression. In this
tree, each leaf is an integer value,, and a non-leaf node is one of the four
operations: '+', '-', '*', or '/'.
Write a function that takes this tree and evaluates the expression.
Example:
Write a function that takes this tree and evaluates the expression.
Example:
*
/ \
+ +
/ \ / \
3 2 4 5
/ \
+ +
/ \ / \
3 2 4 5
This is a representation of the expression (3 + 2) * (4 + 5), and should return 45.
8. You are given
the root of a binary tree. You need to implement 2 functions:
1. serialize(root) which serializes the tree into a string representation
2. deserialize(s) which deserializes the string back to the original tree that it represents
1. serialize(root) which serializes the tree into a string representation
2. deserialize(s) which deserializes the string back to the original tree that it represents
9. The
Fibonacci sequence is the integer sequence defined by the recurrence relation:
F(n) = F(n-1) + F(n-2), where F(0) = 0 and F(1) = 1. In other words, the nth
Fibonacci number is the sum of the prior two Fibonacci numbers. Below are the
first few values of the sequence:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...
Given a number n, print the n-th Fibonacci Number.
Examples:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...
Given a number n, print the n-th Fibonacci Number.
Examples:
Input: n = 3
Output: 2
Input: n = 7
Output: 13
Output: 2
Input: n = 7
Output: 13
10. Given
an array of integers, arr, where all numbers occur twice except one number
which occurs once, find the number. Your solution should ideally be O(n) time
and use constant extra space.
Example:
Example:
Input: arr = [7, 3, 5, 5, 4, 3, 4, 8, 8]
Output: 7
Output: 7
11. You are given
two strings, A and B. Return whether A can be shifted some number of times to
get B.
Eg. A = abcde, B = cdeab should return true because A can be shifted 3 times to the right to get B. A = abc and B= acb should return false.
Eg. A = abcde, B = cdeab should return true because A can be shifted 3 times to the right to get B. A = abc and B= acb should return false.
12. You are given the root
of a binary tree, along with two nodes, A and B. Find and return the lowest
common ancestor of A and B. For this problem, you can assume that each node
also has a pointer to its parent, along with its left and right child.
13. In many
spreadsheet applications, the columns are marked with letters. From the 1st to
the 26th column the letters are A to Z. Then starting from the 27th column it uses AA, AB,
..., ZZ, AAA, etc.
Given a number n, find the n-th column name.
Given a number n, find the n-th column name.
14. A fixed point
in a list is where the value is equal to its index. So for example the
list [-5, 1, 3, 4],
1 is a fixed point in the list since the index and value is the same. Find a
fixed point (there can be many, just return 1) in a sorted list of
distinct elements, or return None if
it doesn't exist.
15. Given
a binary tree, return the list of node values in zigzag order traversal. Here's
an example
# Input:
# 1
# / \
# 2 3
# / \ / \
# 4 5 6 7
#
# Output: [1, 3, 2, 4, 5, 6, 7]
# 1
# / \
# 2 3
# / \ / \
# 4 5 6 7
#
# Output: [1, 3, 2, 4, 5, 6, 7]
16. Given a list of
points, an interger k,
and a point p, find the k closest points to p.
17. Create a
class that initializes with a list of numbers and has one method called sum. sum should take in two parameters, start_idx and end_idx and return the sum of the list from start_idx (inclusive) to end_idx` (exclusive).
You should optimize for the sum method.
You should optimize for the sum method.
18. Given 2 binary
trees t and s, find if s has
an equal subtree in t, where the
structure and the values are the same. Return True if it exists, otherwise return False.
19. Given a list of words
in a string, reverse the words in-place (ie don't create a new string and
reverse the words). Since python strings are not mutable, you can assume the
input will be a mutable sequence (like list).
20. Given a list of
undirected edges which represents a graph, find out the number of connected
components..
21. Given a non-negative
integer n,
convert n to base 2 in string
form. Do not use any built in base 2 conversion functions like bin.
22. Given a string, we want to remove 2 adjacent
characters that are the same, and repeat the process with the new string until
we can no longer perform the operation.
23. Given a
list of strings, find the list of characters that appear in all strings.
24. Given a number n, generate all possible
combinations of n well-formed
brackets.
25. Given a sorted list of
size n,
with m unique elements
(thus m < n), modify the list
such that the first m unique
elements in the list will be sorted, ignoring the rest of the list. Your
solution should have a space complexity of O(1). Instead of returning the list (since you are just
modifying the original list), you should return what m is.
26. LRU cache is a cache
data structure that has limited space, and once there are more items in the
cache than available space, it will preempt the least recently used item. What
counts as recently used is any item a key has 'get' or 'put' called on it.
Implement an LRU cache class with the 2 functions 'put' and 'get'. 'put' should place a value mapped to a certain key, and preempt items if needed. 'get' should return the value for a given key if it exists in the cache, and return None if it doesn't exist.
Implement an LRU cache class with the 2 functions 'put' and 'get'. 'put' should place a value mapped to a certain key, and preempt items if needed. 'get' should return the value for a given key if it exists in the cache, and return None if it doesn't exist.
27. You are given two
singly linked lists. The lists intersect at some node. Find, and return the
node. Note: the lists are non-cyclical.
Example:
A = 1 -> 2 -> 3 -> 4
B = 6 -> 3 -> 4
This should return 3 (you may assume that any nodes with the same value are the same node).
Example:
A = 1 -> 2 -> 3 -> 4
B = 6 -> 3 -> 4
This should return 3 (you may assume that any nodes with the same value are the same node).
28. Given
a list of words, and an arbitrary alphabetical order, verify that the words are
in order of the alphabetical order.
Example:
Example:
Input:
words = ["abcd", "efgh"], order="zyxwvutsrqponmlkjihgfedcba"
Output: False
words = ["abcd", "efgh"], order="zyxwvutsrqponmlkjihgfedcba"
Output: False
Explanation:
'e' comes before 'a' so 'efgh' should come before 'abcd'
Example 2:
Example 2:
Input:
words = ["zyx", "zyxw", "zyxwy"],
order="zyxwvutsrqponmlkjihgfedcba"
Output: True
words = ["zyx", "zyxw", "zyxwy"],
order="zyxwvutsrqponmlkjihgfedcba"
Output: True
Explanation: The words are in increasing alphabetical order
29. Given a
list of words in a string, reverse the words in-place (ie don't create a new
string and reverse the words). Since python strings are not mutable, you can
assume the input will be a mutable sequence (like list).
30. Given a
list of words in a string, reverse the words in-place (ie don't create a new
string and reverse the words). Since python strings are not mutable, you can
assume the input will be a mutable sequence (like list).
0 Comments
Please do not Enter any spam link in the comment box