Google | Onsite | TCP Stream
Anonymous User
2863

Implement the below TCPStream interface.

takePackets is called whenever we recieve packet from the internet. read is called by the application that wants the data - it returns data only if we have complete data up until now.
offset is the offset from which the current data starts. So if we have say offset 4 and bytes as 31, 23,, then currently our TCP stream would look something like _ _ _ _ 31 23, where _ is empty. If now we get offset 0 and bytes 23, the stream would look like 23 _ _ _ 31 23.

class TcpStream:
  def takePackets(offset : int, data: bytes[]):

  def read(size: int):

Sample calls to this interface and expected return value
stream = TcpStream()
stream.takePackets(3, [31, 242, 15])
stream.Read(10) -> []

stream.TakePacket(0, [9, 1])
stream.Read(10) -> [9, 1]

stream.TakePacket(2, [22])
stream.Read(3) -> [22,31,242]

stream.Read(10) -> [15]

Follow-up
Handle the case where we could have duplicated data as well. So in this case may recieve something like below. Note the data we recieve would not be changed, its just that we recieve it multiple times. See below example
takePacket(3, [23,41,53])
takePacket(2, [2,23])

My solution (including the followup) - Skip this and see below if you only want to see the edge cases that has to be handled

from sortedcontainers import SortedSet
class TCPStream:
	def __init__(self):
		self.buffer = SortedSet()
		self.current_offset = 0  #keeps track of offset up until where we have already read

	def takePacket(self,offset, data):
		for ind,val in enumerate(data) :
			if (offset + ind,val) not in self.buffer and (offset+ind)>=self.current_offset:
				self.buffer.add((offset+ind, val))

	def readData(self, max_size):
		ans = []
		if len(self.buffer) !=0:
			if self .buffer[0][0]==self.current_offset:
				count = min(len(self.buffer), max_size)
				prev_ind = self.buffer[0][0]-1 # to ensure we have consecutive bytes, used to break when consecutive data is not present
		for i in range(count):
			ind,val = self.buffer[0]
			if ind!=prev_ind+1:
				break
			ans.append(val)
			self.buffer.discard((ind, val))
			self.current_offset+=1
		return ans

I made a couple of errors when I coded it up. I probably would have caught it in a dry run, but interviewer pointed out before I could dry run a test case.
Edge case 1

takePacket(3, [23,41,53])
takePacket(0, [2,3])
readData(10) - Should return [2,3]. # I missed to break the loop and kept returning more

Edge case in the follow up:

takePacket(0, [23,41,53])
Read(2)
takePacket(1, [41,53]) # Not supposed to reinsert `41` because we have already read it

After completing the coding, when 10 mins was remaining, interviewer asked me if I could think of any better optimized solution for say large (1GB) of data. Since in this approach there is an overhead of storing index. I mumbled something like segment tree (which is wrong and not particularly useful in this case of infinite stream) - I was pretty beat as this point, knowing I took so many hints. Then he told me we could use a hash table with mapping from index -> list of bytes. So for large amount of data we would have less overhead. I think the expectation for this round is to be able to code that optimized solution out as well. Anyways he told there's no time now and ended the round 3 mins early.

Pretty sure this is No hire or in the very best case Lean No hire because of mistakes and all the edge cases I missed and the fact the expectation was for a better optimized solution that works for infinitely large streams as well.

Comments (6)