Day3

Question 1

Given an unordered list of flights taken by someone, each represented as (origin, destination) pairs, and a starting airport, compute the person’s itinerary. If no such itinerary exists, return null. If there are multiple possible itineraries, return the lexicographically smallest one. All flights must be used in the itinerary.

Answer 1

1) use either call stack or self stack funtinon:
2) create a result list to keep comparing best result with current result for minimum distance and store it if it does
3) start the loop and continue until u reach starting point
4) start a recursion or stack call with flights without current one, origin=destination, list+origin
5) exit criteria is when list is empty, return path + destination.

if not flights:
return path + [origin]

result_list = None
for index, (start, end) in enumerate(flights):

    if origin == start:
        path = calculateflightpath(flights[:index]+flights[index+1:], end, path+[start])

        if path:
            if result_list is None or "".join(path) < "".join(result_list):
                result_list = path

return result_list

Question 2

create a datastruct to optimize selects of order.

hint: size is N and use -item to get

Answer 2

1) Create a new class and initialize it to size n
2) create 3 methods, record to add to the list and also check if list is more than the size then prune the oldest item by [1:]
3) get last item for an index, do it by [-index]
4) display method.

Question 3

remove k digits to get the smallest number

Hint: remove the highest k digits from left.

Answer 3

1) get the length of final string by len-k, this is to remove any trailing 0’s from the result [:finallen]
2) for every char in nums run a while loop to check and remove left digits and if you are removing then decrement k.
3) finally list should have smallest digits remaining.

Question 4

find kth largest item in an unsorted array

Hint: use heapsort

Answer 4

1) create an empty list, initialize heapsort
2) for every item in the array, keep pushing into the heapsort list so that heapop gives smallest item
3) if the list size equals k then replace top item which smaller of k items with new big umber, my_list[0] < num
4) trick: use heapq.heappushpop to pop and push at the same time.

Question 5

network delay time using djisktras algorithm

Answer 5

1) for any longest or shortest path problems, look for below approach.
2) Create a graph with default dict graph = collections.defaultdict(list)
for u, v, w in times:
graph[u].append((v,w))
# u is vertex, v are edges and w are weights of all neighbors
3) initalize the distances to sys.max, startvertex distance would be 0
4) have a set for processed vertexes
5) use a heapq to pop and push distances, vertexes, initialize it to 0, start node
6) for every heap item run a loop on its neghbours, check its new weight adding vertex weight and update distances table and push this new neighbor as a new distance, vertex to heap.
7) once all vertexes are visited, distance table should give you vertexes and their distances.
8) find max