daniel.a.p
BAN USERWhat you can do here is a recursive solution where each "level" handles a single pattern key (handles a single index in the pattern key string - for instance, level 1 handles 'a', than level 2 handles 'b', than level 3 handles 'a').
Each level is responsible to create a string (substring) candidate for the pattern key if the later hasn't appeared before or to look for the same substring if the partner key has appeared before.
Here is a python solution
def match(pattern, str):
matches = dict()
return _match(pattern[:], str, 0, 0, matches), matches
def _match(pattern, str, current_ptrn, str_start, matches):
if current_ptrn == len(pattern):
if str_start == len(str):
return True
else:
return False
if pattern[current_ptrn] in matches:
for str_end in range(str_start + 1, len(str) + 1):
if matches[pattern[current_ptrn]] == str[str_start:str_end]:
if _match(pattern, str, current_ptrn + 1, str_end, matches):
return True
else:
for str_end in range(str_start + 1, len(str) + 1):
matches[pattern[current_ptrn]] = str[str_start:str_end]
if _match(pattern, str, current_ptrn + 1, str_end, matches):
return True
del matches[pattern[current_ptrn]]
return False
Since the question says the expressions have only + and * and numbers, we can leverage the fact that * precedes + and therefore can be computed as a unit. This is a fairly open question and the candidate must ask a few questions to the interviewer to make sure that he gets the proper problem.
For instance, 23+3*789 can happen? Or only single digits numbers will be sent? What about parenthesis?
To show a simplified algorithm, I will assume single digits and no parenthesis. With those assumptions, we can just have 2 loops each handling one level of precedence. The inner loop calculates the multiplication and "outputs" a number to be added by the outer loop.
PS: To handle multiple digits numbers, we just need to better tokenize the input, but the same algorithm would suffice. To handle parenthesis, then a stack or a DP solution should be used.
result, acc, i = 0, 0, 0
while i < len(input):
if (input[i] == '+'):
result = result + acc
acc = 0
elif (input[i] == '*'):
while (input[i] == '*'):
i += 1
acc = acc * int(input[i])
i += 1
result = result + acc
acc = 0
else:
acc = int(input[i])
i = i + 1
result = result + acc
print result
def is_alpha_palindrome(str):
if not str:
return True
chars = str[:]
start, end = 0, len(chars) - 1
# The idea is to use 2 indexes and move index 1 from start to end and
# index 2 from end to start.
# Every time both indexes find a alpha char, those must be compared.
while True:
while start < len(chars) and not chars[start].isalnum():
start += 1
while end >= 0 and not chars[end].isalnum():
end -= 1
# If pointers crossed, no news chars to look at
if start > end:
return True
if chars[start].lower() != chars[end].lower():
return False
# Move both pointers ahead otherwise we will be in a infinite loop
start, end = start + 1, end - 1
This is a simple graph problem where each agent is a vertex. We will mark all vertexes that can be reached starting with Fury and whatever is left are the HYDRA agents.
def uncover_hydra(communications, fury):
messages = dict()
for cmnt in communications:
_parse_communication(cmnt, messages)
print _find_hydra_agents(messages, fury)
def _parse_communication(cmnt, messages):
msg = cmnt.split(':')
sender = msg[0].strip()
receivers = [ receiver.strip() for receiver in msg[1].split(',')]
# An adjacent list to be further used on the vertex navigation
messages[sender] = receivers
def _find_hydra_agents(agents_msg, fury):
hydra, shield_agents, agents = set(), set(), [fury]
while len(agents) > 0:
# We get the next agent from the unvisited SHIELD agent set,
# add him to the SHIELD list and then add all agents
# this agent sent a message to to the unvisited SHIELD agent set.
# We do this until there are no more SHIELD agents to visit.
current = agents.pop()
shield_agents.add(current)
if current in agents_msg:
for agent in agents_msg[current]:
if agent not in shield_agents:
agents.append(agent)
# We look for all agents in all communications and grab the ones
# not in the SHIELD set.
for sender in agents_msg.keys():
if sender not in shield_agents:
hydra.add(sender)
for receiver in agents_msg[sender]:
if receiver not in shield_agents:
hydra.add(receiver)
return hydra
communication = [ "Nick Fury : Tony Stark, Maria Hill, Norman Osborn",
"Hulk : Tony Stark, HawkEye, Rogers",
"Rogers : Thor",
"Tony Stark: Pepper Potts, Nick Fury",
"Agent 13 : Agent-X, Nick Fury, Hitler",
"Thor: HawkEye, BlackWidow",
"BlackWidow:Hawkeye",
"Maria Hill : Hulk, Rogers, Nick Fury",
"Agent-X : Agent 13, Rogers",
"Norman Osborn: Tony Stark, Thor" ]
uncover_hydra(communication, "Nick Fury")
I think identifying that and handling it as, maybe, an error would be part of the solution
- daniel.a.p October 22, 2014Right or wrong, remember that this is an interview question. Code clarity, time to write, avoiding unnecessary structures and dependencies are measured as well. I believe the expectation for such question is that one can write the full code within 20-25 minutes...
- daniel.a.p October 22, 2014Not really. It means that those are numbers compose only by the prime factors of 2, 3 and 5. Attention to 1 which is 2^0 + 3^0 + 5^0. So they are only divisible by 1, 2, 3, 5 and itself. This is a known problem and it is one of the problems addressed by the book Cracking the Code Interview, whose author is the CEO of CareerCup. Do a quick search on the web and you should find references to this problem.
- daniel.a.p October 22, 2014Well, the question doesn't clearly explain the restriction "Constant Space". Your solution does not use a Space(N) auxiliary data structure, but it uses the call stack (N/2). My understanding is that if the interviewer meant by "constant space" no extra space that is proportional to N considering the call stack, then this solution would need some tweaks. Otherwise, it looks good.
If the extra space on the call stack is allowed, one can, for each node at position K up to the half of the list (watch out for odd lengths), find the node at position Length - K and compare them. This is O(N^2), but uses no extra space.
Here is my Python solution. Please be aware that I have not added the "Reading" the test cases from a file and "Writing" them back, however the main method will receive the same input and output the required resultes. Therefore, just the file read/write was skipped. I have also considered the overflow as an integer division so 100ml / 3 = 33ml.
The idea is to create a graph where each top glass has as connections the glasses it will overflow to. This way we can propagate the overflow to lower layers by looking if the above glass has more than 250ml. If so, we get the overflow, divide by 3 and add that to the connection glass. The next step would be similar to a Breath Search where we add the lower glasses to a queue e use the same overflow algorithm for them.
from collections import deque
class Glass(object):
def __init__(self, value, row):
self._value = value
self._row = row
self._connections = []
self._fill = 0
@staticmethod
def new_years_eve(bottles = 1, levels = 1, glass = 1):
if bottles < 1 or levels < 1 or glass < 1: raise ValueError()
full_distribution = Glass._distribute(levels, bottles, 750, 250)
if full_distribution.has_key((levels, glass)):
return full_distribution[(levels, glass)]._fill
else: raise ValueError("No such Level/Glass")
@staticmethod
def _distribute(levels, bottles, bottle_size, glass_size):
graph = Glass._build_graph(1, levels)
ml = bottles * bottle_size
entry_node = graph[(1,1)]
entry_node._fill = ml
queue = deque()
queue.append(entry_node)
while len(queue) > 0:
glass = queue.popleft()
if glass._fill > glass_size:
to_divide = glass._fill - glass_size
glass._fill = glass_size
for node in glass._connections:
node._fill += to_divide / len(glass._connections)
queue.append(node)
return graph
@staticmethod
def _build_graph(current_level, max_level):
if current_level < 1: raise ValueError()
current_nodes = Glass._level_nodes(current_level)
result = dict()
if current_level < max_level:
sub_graph = Glass._build_graph(current_level + 1, max_level)
result = sub_graph
for node in current_nodes:
node._connections.append(sub_graph[(current_level + 1, node._value)])
node._connections.append(sub_graph[(current_level + 1, node._value + node._row)])
node._connections.append(sub_graph[(current_level + 1, node._value + node._row + 1)])
for node in current_nodes:
result[(current_level, node._value)] = node
return result
@staticmethod
def _level_nodes(level):
nodes = []
last = 0
row = 1
while row <= level:
for i in range(row):
last += 1
nodes.append(Glass(last, row))
row += 1
return nodes
print Glass.new_years_eve()
print Glass.new_years_eve(bottles = 3, levels = 4, glass = 5)
print Glass.new_years_eve(bottles = 3, levels = 3, glass = 6)
print Glass.new_years_eve(bottles = 5, levels = 4, glass = 10)
print Glass.new_years_eve(bottles = 3, levels = 4, glass = 8)
You are right Maddy, I did for multiples and not prime factors. I`m adjusting the code. Please let me know if you find any issues. Sorry about that.
- daniel.a.p October 05, 2014The solution proposed by the person "Ugly numbers are numbers that can be divided by 1 OR 2 OR 3 OR 5, the wording of the problem is wrong. This can be solved with dynamic programming by creating an array of length n (where n is the nth ugly number we want to find) and generating multiples of 2, 3 and 5 until we reach n." seems correct. The trick here is keeping the order of the multiples since 2 * 3 == 3 * 2... We need to work on always getting the smallest uggly number that can be generated from the feeds 2, 3 and 5. Here is some sample code:
from collections import deque
def nth_uggly_number(n):
if n <= 0: raise "Invalid n"
uggly = [1]
q2 = deque()
q3 = deque()
q5 = deque()
q2.append(2)
q3.append(3)
q5.append(5)
for i in range(1, n):
r2 = q2[0]
r3 = q3[0]
r5 = q5[0]
i_uggly = min(r2, r3, r5)
if i_uggly == r2:
r2 = q2.popleft()
q2.append(i_uggly*2)
q3.append(i_uggly*3)
q5.append(i_uggly*5)
if i_uggly == r3:
r3 = q3.popleft()
q3.append(i_uggly*3)
q5.append(i_uggly*5)
if i_uggly == r5:
r5 = q5.popleft()
q5.append(i_uggly*5)
uggly.append(i_uggly)
print uggly
nth_uggly_number(50)
Manacher algorithm is what you are looking for. Here is the link: http://en.wikipedia.org/wiki/Longest_palindromic_substring
- daniel.a.p October 01, 2014With 3 dimensions it should not be a problem. Expanding this to K dimensions. You would work on all of those for the constraint, but for the height you would need to know which one is the height.
You need to consider that someone could turn the box and therefore change the height. In that case, you would need to expand the search so you can use any dimension as height. If so, you could always place the height on the same location inside the Box object.
So, you could for each box, turn and see if this new box can create the max stack... You could come up with a method that given a box, it will output a list of "new boxes" which are the turns for the first one. All those new boxes would be part of the box list and then you would use the same algorithm with the caveat of making sure that you are not putting the same box on top of itself and having the height always in the same place.
def max_stack(boxes, bottom, cache, in_use):
if boxes is None or cache is None: raise
if bottom is not None and cache.has_key(bottom):
return cache[bottom]
max_st = []
for i in range(len(boxes)):
box = boxes[i]
if box.is_allowed_above(bottom) and not in_use[i]:
in_use[i] = True
# Rotates for all dimensions (They all can be the height)
rotations = box.create_rotations()
for box_rotation in rotations:
max_sub = max_stack(boxes, box_rotation, cache, in_use)
# Since we have all possible rotations, we can assume that
# the height will always be placed on the same index (if we have
# an array as dimensions)
if calculate_height(max_sub) > calculate_height(max_st):
max_st = []
max_st.extend(max_sub)
in_use[i] = False
if bottom is not None:
max_st.append(bottom)
cache[bottom] = max_st
return max_st
I believe that figuring out that is part of the question. I would think that the class Box has 3 members (width, height, depth). The constraint would work on all 3, but the stack height would use just the height. Expanding this to K dimensions would be similar. You would work on all of those for the constraint, but for the height you would need to know which one is the height beforehand.
If you want to make this question even more interesting you can consider that someone could turn the box and therefore change the height. In that case, you would need to expand the search so you can use any dimension as height. I'm not solving this scenario, but the simpler one where the height is known. (My intention was just to show a line of thought)
However, I would think that you could work something like: for each box, turn and see if this new box can create the max stack... You could come up with a method that given a box, it will output a list of "new boxes" which are the turns for the first one. All those new boxes would be part of the box list and then you would use the same algorithm with the caveat of making sure that you are not putting the same box on top of itself.
What if some levels are not complete, how would your solution work?
- daniel.a.p September 29, 2014This problem is one of the problems in Cracking the Code Interview. Check out the Dynamic Programming chapter. The idea is that for every box, you will find the biggest stack that can be put on top of that box. The biggest stack for the current box is now the biggest stack you can put on top of it with the box itself as the bottom box. Just be careful when you get boxes with the same size. Unless you consider those "the same box", you will need to, maybe, mark boxes as used. Here is a simple code to give you some direction.
def max_stack(boxes, bottom, cache):
if boxes is None or cache is None: raise
if bottom is not None and cache.has_key(bottom):
return cache[bottom]
max_st = []
for box in boxes:
if box.is_allowed_above(bottom):
max_sub = max_stack(boxes, box, cache)
if calculate_height(max_sub) > calculate_height(max_st):
max_st = []
max_st.extend(max_sub)
if bottom is not None:
max_st.append(bottom)
cache[bottom] = max_st
return max_st
RepAahnaAllen, AT&T Customer service email at A9
I am a multilingual Judge with 5 years of combined experience in presiding over court proceedings, prosecuting cases, and tirelessly ...
I ran into a similar question in the past. The difference is that the final list was not circular. Here is the code I wrote for that question. Again, this is not the full answer since the list is not circular, but a simple tweak would do the job.
- daniel.a.p March 06, 2015