Find Median from Data Stream Python

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

For example,

[2,3,4], the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

• void addNum(int num) - Add a integer number from the data stream to the data structure.
• double findMedian() - Return the median of all elements so far.

Example:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

Follow up:

1. If all integer numbers from the stream are between 0 and 100, how would you optimize it?
2. If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?

class MedianFinder:

    def __init__(self):

        """

        initialize your data structure here.

        """

        self.small_heap = [ ] 

        self.large_heap = [ ] 

        

        

    def addNum(self, num: int) -> None:

        if len(self.small_heap) == len(self.large_heap):

            heappush(self.small_heap,-heappushpop(self.large_heap,num))

        else:

            heappush(self.large_heap,-heappushpop(self.small_heap,-num))

        

        

        

    def findMedian(self) -> float:

        if len(self.small_heap) == len(self.large_heap):

            return (float)(self.large_heap[0] - self.small_heap[0]) / 2

        else:

            return (float)(-self.small_heap[0])

        

        

# Your MedianFinder object will be instantiated and called as such:

# obj = MedianFinder()

# obj.addNum(num)

# param_2 = obj.findMedian()

// Time Complexity : O(logn)

//Space Complexity: O(n)

Find Median from Data Stream Python

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

For example,

[2,3,4], the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

• void addNum(int num) - Add a integer number from the data stream to the data structure.
• double findMedian() - Return the median of all elements so far.

Example:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

Follow up:

1. If all integer numbers from the stream are between 0 and 100, how would you optimize it?
2. If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?

Space Complexity : O(n)

Time Complexity : O(nlogn) + O(n) // Insertion sort . logn to find the ele position and n to shift elements.

class MedianFinder:

    def __init__(self):

        """

        initialize your data structure here.

        """

        self.inputlist = []

        

        

    def addNum(self, num: int) -> None:

        pos = bisect.bisect(self.inputlist,num)

        self.inputlist.insert(pos,num)

        

        

    def findMedian(self) -> float:

        length = len(self.inputlist)

        if length % 2 == 0:

            return (self.inputlist[length // 2] + self.inputlist[(length // 2)-1]) / 2

        elif length % 2 == 1:

            return self.inputlist[length // 2]

        else:

            return None

        

# Your MedianFinder object will be instantiated and called as such:

# obj = MedianFinder()

# obj.addNum(num)

# param_2 = obj.findMedian()

Find Median from Data Stream Python

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

For example,

[2,3,4], the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

• void addNum(int num) - Add a integer number from the data stream to the data structure.
• double findMedian() - Return the median of all elements so far.

Example:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

Follow up:

1. If all integer numbers from the stream are between 0 and 100, how would you optimize it?
2. If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?

class MedianFinder:

    def __init__(self):
        self.inputlist = []

    def addNum(self, num: int) -> None:
        self.inputlist.append(num)

    def findMedian(self) -> float:
        self.inputlist.sort()
        l = len(self.inputlist)
        return d
        if length % 2 == 0:
            return (self.inputlist[length // 2] + self.inputlist[(length // 2) - 1]) / 2        elif length % 2 == 1:
            return self.inputlist[length // 2]
        else:
            return None

Time Complexity : O(nlogn)
Space Complexity : O(n)

Bulls and Cows Python

You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called "bulls") and how many digits match the secret number but locate in the wrong position (called "cows"). Your friend will use successive guesses and hints to eventually derive the secret number.

Write a function to return a hint according to the secret number and friend's guess, use A to indicate the bulls and B to indicate the cows. 

Please note that both secret number and friend's guess may contain duplicate digits.

Example 1:

Input: secret = "1807", guess = "7810"

Output: "1A3B"

Explanation: 1 bull and 3 cows. The bull is 8, the cows are 0, 1 and 7.

Example 2:

Input: secret = "1123", guess = "0111"

Output: "1A1B"

Explanation: The 1st 1 in friend's guess is a bull, the 2nd or 3rd 1 is a cow.

Note: You may assume that the secret number and your friend's guess only contain digits, and their lengths are always equal.

class Solution:

    def getHint(self, secret: str, guess: str) -> str:

        cows = 0

        bulls = 0

        bulls = sum(secret[i] == guess[i] for i in range(0,len(secret)))

        cows = sum(min(secret.count(char),guess.count(char)) for char in set(secret))

        return f"{bulls}A{cows-bulls}B"

Time Complexity : O(n)

Space Complexity : O(1)                

Compare Strings by Frequency of the Smallest Character Python

Let's define a function f(s) over a non-empty string s, which calculates the frequency of the smallest character in s. For example, if s = "dcce" then f(s) = 2 because the smallest character is "c" and its frequency is 2.

Now, given string arrays queries and words, return an integer array answer, where each answer[i] is the number of words such that f(queries[i]) < f(W), where W is a word in words.

Example 1:

Input: queries = ["cbd"], words = ["zaaaz"]
Output: [1]
Explanation: On the first query we have f("cbd") = 1, f("zaaaz") = 3 so f("cbd") < f("zaaaz").

Example 2:

Input: queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
Output: [1,2]
Explanation: On the first query only f("bbb") < f("aaaa"). On the second query both f("aaa") and f("aaaa") are both > f("cc").

class Solution:
    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
        answers = []
        wordcount = sorted([word.count(min(word)) for word in words])
        for query in queries:
            querycount = query.count(min(query))
            pos = bisect.bisect(wordcount, querycount)
            answers.append(len(wordcount) - pos)
        return answers

Logger Rate Limiter Python

Design a logger system that receive stream of messages along with its timestamps, each message should be printed if and only if it is not printed in the last 10 seconds.

Given a message and a timestamp (in seconds granularity), return true if the message should be printed in the given timestamp, otherwise returns false.

It is possible that several messages arrive roughly at the same time.

Example:

Logger logger = new Logger();

// logging string "foo" at timestamp 1
logger.shouldPrintMessage(1, "foo"); returns true; 

// logging string "bar" at timestamp 2
logger.shouldPrintMessage(2,"bar"); returns true;

// logging string "foo" at timestamp 3
logger.shouldPrintMessage(3,"foo"); returns false;

// logging string "bar" at timestamp 8
logger.shouldPrintMessage(8,"bar"); returns false;

// logging string "foo" at timestamp 10
logger.shouldPrintMessage(10,"foo"); returns false;

// logging string "foo" at timestamp 11
logger.shouldPrintMessage(11,"foo"); returns true;

class Logger:

    def __init__(self):

        self.inputMap = {}

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
         if message not in self.inputMap:
            self.inputMap[message] = timestamp
            return True        
         elif message in self.inputMap and timestamp - self.inputMap[message] >= 10:
            self.inputMap[message] = timestamp
            return True        
         else:
            return False



Time Complexity : O(1)
Space Complexity : O(n)

Two Sum Python

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

// Single Pass method using HashTable
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        inputMap = {}
        for i in range(0, len(nums)):
            if target - nums[i] in inputMap and i != inputMap[target - nums[i]]:
                return [inputMap[target - nums[i]], i]
            else:
                inputMap[nums[i]] = i





Time Complexity : O(n)
Space Complexity : O(n)