Intersection of Two Linked Lists Python

Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
begin to intersect at node c1.

Example 1:
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:
Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

Notes:
  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.

class Solution:    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:        if not headA or not headB:            return None                hA = headA

        hB = headB

                while hA is not hB:            hA = headB if hA is None else hA.next            hB = headA if hB is None else hB.next


Time Complexity : O(n)

Space Complexity : O(1)

                    return hA

By at No comments:

Intersection of Two Linked Lists Python

Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
begin to intersect at node c1.

Example 1:
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:
Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

Notes:
  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        lA , lB = 0,0
        hA , hB = headA,headB
        if not hA or not hB:
            return None
        while hA != None:
            lA+=1
            hA = hA.next
        while hB != None:
            lB+=1
            hB=hB.next
        hA ,hB = headA,headB
        if lA > lB:
            k = lA-lB
            while k > 0:
                hA = hA.next
                k -=1
        elif lB > lA:
            k = lB-lA
            while k > 0:
                hB = hB.next
                k -=1
        while hA != hB:
            hA =hA.next
            hB =hB.next
        return hA
                
            
      Time Complexity : O(n)
      Space Complexity : O(1)


By at No comments:
Labels:

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)
By at No comments:

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()
By at No comments:

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)

By at No comments:

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)                
By at No comments:
Labels:
Subscribe to: Posts (Atom)

Featured Post

H1B Visa Stamping at US Consulate

  H1B Visa Stamping at US Consulate If you are outside of the US, you need to apply for US Visa at a US Consulate or a US Embassy and get H1...

  • Java quiz 1
    Ques 1 : Which declaration of the main method below would allow a class to be started as a standalone program. (A) public static int main(c...
  • Amazon List of LeetCode Questions
    1.  Two Sum Two Sum Solution 2.  LRU Cache LRU Cache Solution 3.  Number Of Islands 4. Longest Palindromic Substring 5.  Lowest...
  • Amazon Cloud Support Associate Interview Questions
    basics Linux fundamentals like system calls , strace , linux mange memory, shared memory, kernel using, boot process, DNS resolving ( how t...