Google | Phone | Product of last K elements - Foobar
Anonymous User
2765
GooglePhone ScreeningInterview

Class Product will have 3 methods:

  1. constructor with k
  2. Insert() with int parameter
  3. Get () -> Returns the Product of the last k Insert()

Example:
Product(3)
Insert(4)
Insert(7)
Insert(2)
Get() -> 274 = 56
Insert(1)
Get() -> 1 * 2 * 7 = 14

Approach 1:
k = 3
list = []
[4]
[4,7]

[4,7,2]
list[-k]


class Product:
	def __init__(self,k):
		self.k = k
		self.list = []

	def Insert(self,val):
		self.list.append(val)

	def Get(self):
		length = len(self.list)
		result = 1
		if length > k:
			tmp_result = self.list[-k]
			for i in range(len(tmp_result)):
				result *= tmp_result[i]

		else:
			for i in range(length):
				result *= self.list[i]
		return result


Runtime: Get: O(k)
Space Complexity: O(N) where N is number of Insert() calls

Approach 2: Improve space from O(N) to O(k)
only store k elements
k = 3
[1]
[1,2]
[1,2,3]
[2,3,4]


class Product:
	def __init__(self,k):
		self.k = k
		self.list = []

	def Insert(self,val):
		length = len(self.list)
		if length < k:
			self.append(val)
		else:
			del self.list[0]
			self.append(val)
	
	def Get(self):
		length = len(self.list)
		result = 1
		if length > k:
			tmp_result = self.list[-k]
			for i in range(len(tmp_result)):
				result *= tmp_result[i]

		else:
			for i in range(length):
				result *= self.list[i]
		return result


Runtime: Get: O(k)
Space Complexity: O(k)

Follow up: Add element with value 0
Approach 3: Improve runtime from O(k) to O(1) - on the go product
k = 3
first = 1
count = 1

[1]
first = 1
count = 2
[1,2]
first = 1
count = 3
[1,2,3]
[2,3,4]



class Product:
	def __init__(self,k):
		self.k = k
		self.list = []
		self.product = 1
		self.zeroFlag = False

	def Insert(self,val):
		length = len(self.list)
		
if val == 0
			self.zeroFlag = True
		if self.zeroFlag:
			self.product = 0
		
if length < k:
			self.append(val)
			self.product *= val
		else:
			first_element = self.list[0]
			
			if first_element != 0:
				self.product /= first_element
				del self.list[0]
				self.append(val)
				self.product *= val

	def Get(self):
		return self.product


Product(2)
Insert(1)
[1] - 1, False
Insert(0)
[1,0] - 1, True
Get() -> 0?
[0,1] 1 , True
Insert(1)
[1,2] 1* 2, False
Insert(1)
Get()

Product(3)
Insert(0)
Insert(3)
Insert(0)


Runtime: Get: O(1)
Space Complexity: O(k)

Follow up : Handle scenario with multiple occurance of 0s
Run time: O(1)
Space: O(k)

class Product:
	def __init__(self,k):
		self.k = k
		self.list = []
		self.product = 1
		self.zeroCount = 0

	def Insert(self,val):
		length = len(self.list)
		
if val == 0:
			self.zeroCount += 1
				
if length < k:
			self.append(val)
		else:
			first_element = self.list[0]
			
			if first_element != 0:
self.product /= first_element
else:
	self.zeroCount -= 1

del self.list[0]
self.append(val)
		if val != 0:
			self.product *= val

	def Get(self):
		if self.zeroCount > 0:
			return 0
		else:
		return self.product


Runtime: O(1)

I followed all google phone screen question from this platform and its my time to give them back. Hope this helps to leetcode community.

I am waiting for my result of phone interview. --> cleared phone screen and got the update very next day that I am moving forward for the onsite. Hooray.

Comments (6)