Fourkites Interview Experience | Summer Internship
Round 1: Coding round on Hackerearth
Round 2: Technical Round 1
Question: Given a table, extract its odd columns
Question 1: Given two linked lists how can you merge them into one sorted linked list.
My Solution:
He asked me to improve the complexity of the solution.
he said no.
Now he said assume there is a limit on memory.
He asked the time complexity of merge sort and to assume its a sorted list now merge them.
def merge(list1, list2): """ list1, list2 are the two sorted lists Function returns the merged list """" ptr1 = 0 ptr2 = 0 finalList = [] # While any pointer reaches the end of the list while ptr1 < len(list1) and ptr2 < len(list2): # If list2 has the smaller element add it and increase the pointer to the next position if list1[ptr1]>list2[ptr2]: finalList.appennd(list2[ptr2]) ptr2 += 1 # Otherwise add element form list1 and increase the pointer to the next position else: finalList.append(list1[ptr1]) ptr1 += 1 # Adding the elements left in list1 or list2 if ptr1 == len(list1): while ptr2 <l en(list2): finalList.append(list2[ptr2]) ptr2 += 1 else: while ptr1 < len(list1): finalList.append(list1[ptr1]) ptr1 += 1 # finalList contains the merged list return finalList |
I was asked the time complexity of the program, I replied
Round 3: Technical Round 2
Question: You have
My solution:
Example: 5 logs of size 2 3 4 5 7. Answer: 47 Solution: 2+3 = 5, logs = 4, 5, 5, 7 cost = 5 4+5 = 8, logs = 5, 7, 9 cost = 5+9 5+7 = 9, logs = 9, 12 cost = 5+9+12 9+12 = 21, logs = 21 cost = 5+9+12+21 = 47 I could have sorted the list but after each join, I will have to insert a new log into the list that can take
import heapq def cost(n, logs): """ n is the number of logs logs is the list containing length of logs Returns the minimum cost of joining all the logs """ # Createing a min-heap using length of logs heap = [] for i in range(n): heap.heappush(logs[i]) cost = 0 # Loop until one log is left while len(heap)>1: # Log with minimum value log1 = heap[0] # Removing the minimum / root value heap.heappop() # Similarly second minimum log will be the minimum after the previous removal log2 = heap[0] heap.heappop() # Length of new log which is equal to the cost of operation newlog = log1 + log2 cost += newlog # Inserting the new log back in the heap heap.heapush(newlog) # Cost stores the total cost for this operation return cost |
I was asked the total time complexity of this operation which is
Round 4: Technical Round 3
Interviewee:
Me:
Interviewee:
Me:
Contact Us