# Mock interview
## Q1
:man:：I'll start the timer right now.
:man:：So this is the question I want you to design a class that support this three operation. The first operation is inserting a value, and you can assume that there's no duplicates allowed so you might be given a duplicate but you don't want to actually store the duplicate. The second thing is removing a value from this class and where it gets interesting is I want you to be able to get a random value that is already inserted and among the values that are inserted I want it to be of equal probability. So just these three operations

- assume interger
- assume reasonable amount like in the terms of millioins but you shouldn't run into like any limitations like with memory or anything like that

Design a class:
    1. Inserting a value (no duplicates)
    2. removeing a value
    3. GetRandom a value that is already inserted (with equal probability)

## Q2

work for both for us
I want you to

return free slots of time during which these two people could have a meeting
to make sure we are really on the same page
list of len two

also give you daily bound

when we triedto get this to happen the smart coding interview we naturally had to put something on the calendar right yeah to find a time that works for both of us and you know give ourselves 45 minutes
3:20
or an hour to make sure that we had enough time to record this so I want you
3:25
to write an algorithm that is gonna basically take two peoples calendars you
3:31
can imagine Google calendars and it's gonna basically return free slots of
3:37
time during which these two people could have a meeting now here I'm gonna add a
3:42
few other things to make sure that we're we're really on the same page here you can imagine that our calendars are gonna
3:49
basically be in the format of the starting like either they're gonna be lists of tuples or lists of lists of
3:58
length two so it's going to something like you know one calendar would look like this where it might be noon to
4:07
let's say 1:00 p.m. then it might be 3 p.m. to 4:30 p.m. something like that it
4:15
would actually be in military time so it'd be 15 - okay 60 and 30 exactly okay
4:20
and so this would be one calendar maybe mine this means that I had meetings between noon and
4:26
one between three or thirty I'm gonna give you a second calendar which is gonna be your calendar and then I'm also
4:33
gonna give you some daily bounds because you can imagine that you might not want to have meetings before let's say 8:00
4:40
a.m. or you might not want to have meetings after let's say 6:00 p.m. so I'll also give you something like daily
4:46
bounds equals let's say 8:00 8:00 a.m. and let's say 6:00 p.m. which would be
4:53
18 so this means that you not only have these meetings here but you also don't
4:59
want to schedule meetings before 8:00 or after 6:00 p.m. okay okay so did then so
5:06
yeah given to calendars and to daily bounds and I'll give you a sample input
5:11
in a second and a meeting duration so in our example you know we need about an hour for this interview but the meeting
5:18
duration could be any duration I want you to return a list of availabilities
5:24
during which we could schedule our meeting so here's an example and then feel free to ask me anything you want okay
5:36
all right okay so sorry I'm just looking at that now I thought you're actually gonna continue that's why I was stuck no no no problem um okay yeah so can we
5:44
assume that any like time you give me for a meeting is within the bounds you
5:49
gave me what do you mean by that so for example say it like say you said
5:55
like you know person one says they have a meeting for like they only want to book meetings from 9:00 a.m. till in

Sample input:
[['9:00', '10:30'], ['12:00', '10:30'], ['16:00', '18:00']]
[['9:00', '20:00']]
[['10:00', '11:30'], ['12:30', '14:30'], ['14:30', '15:00'], ['16:00', '17:00']]
[['10:00', '18:30']]
30
Sample output: 
[['11:30', '12:00'], ['15:00', '16:00'], ['18:00', '18:30']]

## ANS

### Q1

class Solution:
    # Time complexity: O(ab)
    # Space complexity: O(1)
    def brute_force(self, a, b, x):
        ### BRUTE FORCE ###
        protien = []
        oil = []
        for i in range(a + 1):
            cal = i * 1  # each of the protien have 1 cal
            protien.append(cal)
        for i in range(b + 1):
            cal = i * 5  # each of the oil have 5 cal
            oil.append(cal)

        # print(protien)
        # print(oil)
        for i in range(a + 1):
            for j in range(b + 1):
                if (protien[i] + oil[j] == x):
                    return True
        return False    
    
    # Time complexity: O(a+b)
    # Space complexity: O(1)
    def hashing(self, a, b, x):
        hash_map = set()
        for i in range(a + 1):
            cal = i * 1  # each of the protien have 1 cal
            hash_map.add(cal)

        for i in range(b + 1):
            target = x - i * 5
            if target in hash_map:
                return True
        return False

### Q2

from collections import defaultdict

# This class represents a directed graph
# using adjacency list representation
class Graph:

	def __init__(self, vertices):
		# No. of vertices
		self.V = vertices
		
		# default dictionary to store graph
		self.graph = defaultdict(list)

		# default dictionary to store graph
		self.fuel = defaultdict(int)
		self.cost_arry = [0]
		self.ret = 1000

	# function to add an edge to graph
	def addEdge(self, u, v, c):
		self.graph[u].append(v)
		self.graph[v].append(u)
		self.fuel[(u, v)] = c
		self.fuel[(v, u)] = c

	'''A recursive function to print all paths from 'u' to 'd'.
	visited[] keeps track of vertices in current path.
	path[] stores actual vertices and path_index is current
	index in path[]'''
	def goThroughAllPath(self, u, d, visited, path, cost):

		# Mark the current node as visited and store in path
		visited[u]= True
		path.append(u)

		# If current vertex is same as destination, then print
		# current path[]
		if u == d:
			print (path)
			self.ret = max(self.cost_arry) if self.ret > max(self.cost_arry) else self.ret
			# print(self.ret)
			# print ('')
		else:
			# If current vertex is not destination
			# Recur for all the vertices adjacent to this vertex
			for i in self.graph[u]:
				if not visited[i]:
					self.cost_arry.append(self.fuel[(u, i)])
					self.goThroughAllPath(i, d, visited, path, cost)
		# Remove current vertex from path[] and mark it as unvisited
		path.pop()
		self.cost_arry.pop()
		visited[u]= False


	# Prints all paths from 's' to 'd'
	def printAllPaths(self, s, d):

		# Mark all the vertices as not visited
		visited =[False]*(self.V)

		# Create an array to store paths
		path = []

        # Create a array to stor
		cost = 0

		# Call the recursive helper function to print all paths
		self.goThroughAllPath(s, d, visited, path, cost)
		print(self.ret)



# Create a graph given in the above diagram
g = Graph(4)
g.addEdge(0, 1, 10)
g.addEdge(0, 2, 20)
g.addEdge(1, 3, 30)
g.addEdge(2, 3, 20)

s = 0 ; d = 3
print ("Following are all different paths from % d to % d :" %(s, d))
g.printAllPaths(s, d)
# This code is contributed by Neelam Yadav