--------------------------------------------------------------------------------
You have a function rand5() that generates a random integer from 1 to 5,
returning each value with equal probability.
Use calls to rand5() to create a function rand7() that generates random
integers from 1 to 7 with equal probability.
--------------------------------------------------------------------------------
You have a function rand7() that generates a random integer from 1 to 7,
returning each value with equal probability.
Use calls to rand7() to create a function rand5() that generates random
integers from 1 to 5 with equal probability.
There is a simple answer. Is there a more efficient answer?
--------------------------------------------------------------------------------
Suppose we could access yesterday's stock prices as a list T(I), V(I), where:
* T(I) is the time in minutes past trade opening time, 9:30am.
* V(I) is the value in dollars of Apple stock at time T(I).
So if the stock cost $500 at 10:30am, stock_prices_yesterday[60] = 500.
Write an efficient function that takes stock_prices_yesterday and returns the
best profit I could have made from 1 purchase and 1 sale of 1 Apple stock yesterday.
For example, we might have:
T = [ 0, 30, 95, 137, 345, 437 ]
V = [ 10, 13, 5, 8, 11, 9 ]
in which case, the maximum profit would be 6, buying for $5 at 95 minutes
past the start, and selling for $11 at 345 minutes past the start.
--------------------------------------------------------------------------------
You have a list of N integers A(I). You want to make a new list of N values
B(I), so that B(I) is the product of all the A's except for A(I).
Write a function that takes the list A and returns the list B.
For example, given:
[ 1, 7, 3, 4 ]
your function would return:
[ 84, 12, 28, 21 ]
by calculating:
[7*3*4, 1*3*4, 1*7*4, 1*7*3]
There is a simple answer. It is not the most efficient answer.
What is an efficient code to do this? You may NOT use division.
--------------------------------------------------------------------------------
Given a list of 3 <= N integers A(I), find the maximum product you can get using
any three of the integers.
--------------------------------------------------------------------------------
Your company built an in-house calendar tool called HiCal. You want to add a
feature to see the times in a day when everyone is available.
To do this, you’ll need to know when any team is having a meeting. In HiCal,
a meeting is stored as pairs of integers (start_time, end_time). These
integers represent the number of 30-minute blocks past 9:00am.
For example:
(2, 3) # meeting from 10:00 – 10:30 am
(6, 9) # meeting from 12:00 – 1:30 pm
Write a function "condense_meeting_times()" that takes a list of meeting time
ranges and returns a list of condensed ranges.
For example, given:
[ (0, 1), (4, 8), (10, 12), (3, 5), (9, 10) ]
your function would return:
[ (0, 1), (3, 8), (9, 12) ]
Do not assume the meetings are listed in order.
Write a solution that's efficient even when we can't put a nice upper bound on
the numbers representing our time ranges. Here we've simplified our times down
to the number of 30-minute slots past 9:00 am. But we want the function to
work even for very large numbers, like Unix timestamps. In any case, the
spirit of the challenge is to merge meetings where start_time and end_time
don't have an upper bound.
--------------------------------------------------------------------------------
Imagine you landed a new job as a cashier.
Your quirky boss found out that you're a programmer and has a weird request
about something they've been wondering for a long time.
Write a function that, given:
* S, an amount of money
* D, a list of N distinct positive coin denominations
computes the number of ways to make a sum of S using coins of the available
denominations.
For example, for S=4 (4¢) and denominations = [1,2,3] (1¢, 2¢ and 3¢), your
program would output 4 - the number of ways to make 4¢ with those denominations:
#1 1¢ + 1¢ + 1¢ + 1¢
#2 1¢ + 1¢ + 2¢
#3 1¢ + 3¢
#4 2¢ + 2¢
--------------------------------------------------------------------------------
A crack team of love scientists from OkEros (a hot new dating site) have
devised a way to represent dating profiles as rectangles on a two-dimensional
plane.
They need help writing an algorithm to find the intersection of two users'
love rectangles. They suspect finding that intersection is the key to a
powerful matching algorithm.
Write a function to find the rectangular intersection of two given
love rectangles.
As with the example above, love rectangles are always "straight" and never
"diagonal." More rigorously: each side is parallel with either the x-axis
or the y-axis.
They are defined as dictionaries like this:
my_rectangle = {
# coordinates of bottom-left corner
'left_x': 1,
'bottom_y': 5,
# width and height
'width': 10,
'height': 4,
}
Your output rectangle should use this format as well.
--------------------------------------------------------------------------------
You decide to test if your oddly-mathematical heating company is fulfilling its
All-Time Max, Min, Mean and Mode Temperature Guarantee™.
Write a class TempTracker with these methods:
* insert(): records a new temperature
* get_max(): returns the highest temp we've seen so far
* get_min(): returns the lowest temp we've seen so far
* get_mean(): returns the mean ↴ of all temps we've seen so far
* get_mode(): returns the mode ↴ of all temps we've seen so far
Optimize for space and time. Favor speeding up the get functions (get_max(),
get_min(), get_mean(), and get_mode()) over speeding up the insert() function.
get_mean() should return a float, but the rest of the get functions can return
integers. Temperatures will all be inserted as integers. We'll record our
temperatures in Fahrenheit, so we can assume they'll all be in the range
between 0 to 110.
If there is more than one mode, return any of the modes.
--------------------------------------------------------------------------------
Write a function to see if a binary tree ↴ is "superbalanced" (a new tree
property we just made up).
A tree is "superbalanced" if the difference between the depths of any two
leaf nodes is no greater than one.
Here's a sample binary tree node class:
class BinaryTreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert_left(self, value):
self.left = BinaryTreeNode(value)
return self.left
def insert_right(self, value):
self.right = BinaryTreeNode(value)
return self.right
--------------------------------------------------------------------------------
Write a function to check that a binary tree ↴ is a valid binary search tree.
Here's a sample binary tree node class:
class BinaryTreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert_left(self, value):
self.left = BinaryTreeNode(value)
return self.left
def insert_right(self, value):
self.right = BinaryTreeNode(value)
return self.right
--------------------------------------------------------------------------------
Write a function to find the 2nd largest element in a binary search tree.
Here's a sample binary tree node class:
class BinaryTreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert_left(self, value):
self.left = BinaryTreeNode(value)
return self.left
def insert_right(self, value):
self.right = BinaryTreeNode(value)
return self.right
--------------------------------------------------------------------------------
I'm making a search engine called MillionGazillion™.
I wrote a crawler that visits web pages, stores a few keywords in a database,
and follows links to other web pages. I noticed that my crawler was wasting a
lot of time visiting the same pages over and over, so I made "set_visited"
where I'm storing URLs I've already visited. Now the crawler only visits a
URL if it hasn't already been visited.
Thing is, the crawler is running on my old desktop computer in my parents's
basement (where I totally don't live anymore), and it keeps running out of
memory because visited is getting so huge.
How can I trim down the amount of space taken up by "set_visited"?
--------------------------------------------------------------------------------
Suppose we had a sorted list of N integers. How quickly could we check
if the integer M is included in the list?
--------------------------------------------------------------------------------
I want to learn some big words so people think I'm smart.
I opened up a dictionary to a page in the middle and started flipping through,
looking for words I didn't know. I put each word I didn't know at increasing
indices in a huge list I created in memory. When I reached the end of the
dictionary, I started from the beginning and did the same thing until I
reached the page I started at.
Now I have a list of words that are mostly alphabetical, except they start
somewhere in the middle of the alphabet, reach the end, and then start from
the beginning of the alphabet. In other words, this is an alphabetically
ordered list that has been "rotated." For example:
words = [
'ptolemaic',
'retrograde',
'supplant',
'undulate',
'xenoepist',
'asymptote', # <-- rotates here!
'babka',
'banoffee',
'engender',
'karpatka',
'othellolagkage',
]
Write a function for finding the index of the "rotation point", which is where
I started working from the beginning of the dictionary. This list is huge
(there are lots of words I don't know) so we want to be efficient here.
--------------------------------------------------------------------------------
You've built an in-flight entertainment system with on-demand movie streaming.
Users on longer flights like to start a second movie right when their first one
ends, but they complain that the plane usually lands before they can see the
ending. So you're building a feature for choosing two movies whose total
runtimes will equal the exact flight length.
Write a function that takes an integer flight_length (in minutes) and a list
of integers movie_lengths (in minutes) and returns a boolean indicating whether
there are two numbers in movie_lengths whose sum equals flight_length.
When building your function:
* Assume your users will watch exactly two movies
* Don't make your users watch the same movie twice
* Optimize for runtime over memory
--------------------------------------------------------------------------------
You are a renowned thief who has recently switched from stealing precious
metals to stealing cakes because of the insane profit margins. You end up
hitting the jackpot, breaking into the world's largest privately owned stock
of cakes - the vault of the Queen of England.
While Queen Elizabeth has a limited number of types of cake, she has an
unlimited supply of each type.
Each type of cake has a weight and a value, stored in a tuple with two indices:
* An integer representing the weight of the cake in kilograms
* An integer representing the monetary value of the cake.
For example, here are two such tuples:
(7, 160) # weighs 7 kilograms and has a value of $160.
(3, 90) # weighs 3 kilograms and has a value of $90.
You brought a duffel bag that can hold limited weight, and you want to make
off with the most valuable haul possible.
Write a function "max_duffel_bag_value()" that takes a list of cake type tuples
and a weight capacity, and returns the maximum monetary value the duffel
bag can hold.
For example:
cake_tuples = [ (7, 160), (3, 90), (2, 15) ]
capacity = 20
in which case,
max_duffel_bag_value(cake_tuples, capacity)
returns 555, for 6 of the middle type of cake and 1 of the last type of cake.
Weights and values may be any non-negative integer. Yes, it's weird to think
about cakes that weigh nothing or duffel bags that can't hold anything. But
we're not just super mastermind criminals - we're also meticulous about keeping
our algorithms flexible and comprehensive.
--------------------------------------------------------------------------------
If we execute this Javascript, what will the browser's console show?
var text = 'outside';
function logIt()
{
console.log ( text );
var text = 'inside';
};
logIt ( );
--------------------------------------------------------------------------------
We're building a web game where everybody wins and we are all friends forever.
It's simple - you click on one of three boxes to see what nice thing you've won.
You always win something nice. Because we love you.
Here's what we have so far. Something's going wrong though. Can you tell what
it is?
The syntax is just fine, The problem is some unexpected behavior.
--------------------------------------------------------------------------------
Implement a queue with 2 stacks. Your queue should have an enqueue and a
dequeue function and it should be "first in first out" (FIFO).
Optimize for the time cost of mmm function calls on your queue. These can be
any mix of enqueue and dequeue calls.
Assume you already have a stack implementation and it gives O(1) time for
the push and pop operations.
--------------------------------------------------------------------------------
Your company delivers breakfast via autonomous quadcopter drones. And
something mysterious has happened.
Each breakfast delivery is assigned a unique ID, a positive 16 digit integer.
These ID's are not consecutive, and seem to have no particular order.
When one of the company's 100 drones takes off with a delivery, the delivery's
ID is appended to a list, "delivery_id_confirmations". When the drone comes
back and lands, the ID is again appended to the same list.
After breakfast this morning there were only 99 drones back on the tarmac.
One of the drones never made it back from a delivery. We suspect a secret
agent from Amazon placed an order and stole one of our patented drones.
To track them down, we need to find their delivery ID.
Given the list of IDs, which contains many duplicate integers and one unique
integer, find the unique integer.
--------------------------------------------------------------------------------
You have a singly-linked list and want to check if it contains a cycle.
A singly-linked list is built with nodes, where each node has:
* node.next - the next node in the list.
* node.data - the data held in the node.
For example, if our linked list stores people in line at the movies,
node.data might be the person's name. A class declaration might be:
class LinkedListNode:
def __init__(self, value):
self.value = value
self.next = None
A cycle occurs if there is at least one node N for which, after one or more
applications of the next function, returns N.
Write a function "contains_cycle()" which takes the first node in a
singly-linked list and returns a boolean indicating whether the list
contains a cycle.
--------------------------------------------------------------------------------
You're working on a secret team solving coded transmissions.
Your team is scrambling to decipher a recent message, worried it's a plot to
break into a major European National Cake Vault. The message has been mostly
deciphered, but all the words are backwards! Your colleagues have handed off
the last step to you.
Write a function reverse_words() that takes a string "message" and reverses
the order of the words in-place.
Since strings in Python are immutable, we'll first convert the string into a
list of characters, do the in-place word reversal on that list, and rejoin that
list into a string before returning it. This isn't technically in-place and
the list of characters will cost O(n) additional space, but it's a reasonable
way to stay within the spirit of the challenge. If you're comfortable coding
in a language with mutable strings, that'd be even better!
For example, if message is:
'find you will pain only go you recordings security the into if'
Then reverse_words ( message ) should return
'if into the security recordings you go only pain will you find'
When writing your function, assume the message contains only letters and
spaces, and all words are separated by one space.
--------------------------------------------------------------------------------
I like parentheticals (a lot).
Sometimes (when I nest them (my parentheticals) too much (like this (and this)))
they get confusing.
Write a function that, given a sentence like the one above, along with the
position of an opening parenthesis within that string, finds the matching
closing parenthesis.
For example, if the example string above is input with the number 10 as the
0-based position of the first parenthesis, the output should be 79, the
0-based position of the last parenthesis.
--------------------------------------------------------------------------------
You're working with an intern who keeps coming to you with JavaScript code that
won't run because the braces, brackets, and parentheses are off. To save you
both some time, you decide to write a braces/brackets/parentheses validator.
Let's say:
'(', '{', '[' are called "openers."
')', '}', ']' are called "closers."
Write an efficient function that tells us whether or not an input string's
openers and closers are properly nested.
Examples:
"{ [ ] ( ) }" should return True
"{ [ ( ] ) }" should return False
"{ [ }" should return False
--------------------------------------------------------------------------------
Define F(X) = (X-A)*(X-B)*(X-C)*...*(X-Z).
Simplify F(X).
--------------------------------------------------------------------------------
A man pushed his car all the way to a hotel, and realized he had just
lost all his money.
What is going on?
--------------------------------------------------------------------------------
How can you use a biased coin to simulate a fair coin?
You don't know the bias.
--------------------------------------------------------------------------------
How many basketballs could fit in this room?
--------------------------------------------------------------------------------
A hen and a half can lay an egg and a half in a day and a half.
How long will it take 2 hens to lay 8 eggs?
--------------------------------------------------------------------------------
You're sitting in a rowboat floating in a tank of water that is filled up
to the brim. Inside the rowboat is a heavy anchor. You take the anchor and
gently let it slip over the side of the boat into the water.
What happens to the water level?
--------------------------------------------------------------------------------
A typical car's tires are inflated to 30 pounds per square inch.
How would you estimate the weight of a car without touching it?
--------------------------------------------------------------------------------
How far away is the horizon for a person 6 feet tall.
Assume the earth is a perfectly smooth sphere.
--------------------------------------------------------------------------------
The Golden Gate Bridge extends between the South and North towers.
These towers are 1,280 meters apart at their base. They are 230 meters high.
Assuming each tower is perfectly vertical, then they are farther apart
at the top than at the base, because of the curvature of the earth.
How much further apart are they?
--------------------------------------------------------------------------------
What is the standard deviation of the set {1,2,3}?
If the set {1,2,3,M} has the same standard deviation, what is M?
--------------------------------------------------------------------------------
In a room of dogs and people, there are 72 heads and 200 legs.
How many dogs are in the room?
--------------------------------------------------------------------------------
I roll three dice, getting values A, B, and C.
What is the probability that A*B*C is odd?
--------------------------------------------------------------------------------
X, Y, and Z are digits between 0 and 8.
XYZ base 10 is equal o ZYX base 9.
What are X, Y, and Z?
--------------------------------------------------------------------------------
Write 1,000,000 as the product of two numbers A and B.
Neither A nor B can include any 0 digits.
--------------------------------------------------------------------------------
I'm sure you have failed at something many times in your life.
Tell me about one such time.
--------------------------------------------------------------------------------
You must have worked in a team to accomplish some task.
How did you fit in and what did you do?
--------------------------------------------------------------------------------
What would your friends say if I asked them what they like most about you,
and what about you drove them crazy?
--------------------------------------------------------------------------------
What's something you wish you could have included on your resume?
--------------------------------------------------------------------------------
A lot of the people I have interviewed seem just like you.
What makes you different?
--------------------------------------------------------------------------------
Describe a time you disagreed with a colleague.
How did you settle your disagreement?
--------------------------------------------------------------------------------
Do you have any questions for me?
("No" is a WRONG answer!)
--------------------------------------------------------------------------------