# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 2
#     language: python
#     name: python2
# ---

# +
# Kth largest element from a list.

import heapq

def kth_largest(arr, k):
    """
    Return the kth largest element from the list.
    
    Input:
        arr: a list of integers
        k: an integer
    Output:
        val: an integer
        
    >>>kth_largest([1, 2, 3, 4, 5, 6, 7], 5)
    5
    >>>kth_largest([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 8)
    8
    """
    if arr is None or k > len(arr):
        return None
    else:
        count = 0
        val = -1
        heapq.heapify(arr)
        while count < k:
            val = heapq.heappop(arr)
            count += 1
        return val

kth_largest([x for x in xrange(1, 11)], 4)        


# +
# Find the element that appears once/odd number of times in a list.

def find_element(arr):
    if arr is None or len(arr) == 0:
        return 
    else:
        val = 0
        for x in arr:
            val = val ^ x
        return val
    
print find_element([1, 1, 2, 3, 3, 2, 2, 2, 4, 4, 4])
print find_element([1, 2, 3, 2, 3, 1, 3])

# +
"""
Given an array and a number x, check for pair in the array with sum as x.
"""
def find_pair(arr, x):
    """
    A pair with sum x in the array.
    
    Input:
        arr: A list of integers
        x: An integer
    Output:
        res: A tuple of integers
    
    >>> find_pair([-8, 1, 4, 6, 10, 45], 16)
    
    """
    cache = {}
    for i in arr:
        val = x - i 
        if val in cache:
            return (i, val)
        else:
            cache[i] = 1
    return (None, None)
    
find_pair([-8, 1, 4, 6, 10, 45], 16)


# +
# Search an element in a sorted and rotated array.

def search(arr, x):
    if len(arr) == 0:
        return False
    
    start = 0
    end = len(arr)-1
    while start <= end:
        mid = start + (end-start)/2
        if x == arr[mid]:
            return True
        elif x < arr[0] and x < arr[mid]:
            start = mid+1
        elif x < arr[0] and x > arr[mid]:
            end = mid
            
        

# +
# Write a function that rotates an array of size n by d elements.

def rotate(arr, d):
    if d > len(arr):
        return arr
    
    left = list(reversed(arr[:d]))
    right = list(reversed(arr[d:]))
    return list(reversed(left+right))

print rotate([1, 2, 3, 4, 5, 6, 7], 3)


# +
# Segregate Even and Odd numbers in an array.

def odd_even(arr):
    left = 0
    right = len(arr)-1
    while left < right:
        while arr[left]%2==0 and left < right:
            left += 1
        while arr[right]%2 == 1 and left < right:
            right -= 1
        if left < right:
              arr[left], arr[right] = arr[right], arr[left]
              left += 1
              right = right-1  
    return arr

print odd_even([12, 34, 45, 9, 8, 90, 3])

# +
"""
Find common elements in three sorted arrays
Given three arrays sorted in non-decreasing order, print all common elements in these arrays.

Examples:

ar1[] = {1, 5, 10, 20, 40, 80}
ar2[] = {6, 7, 20, 80, 100}
ar3[] = {3, 4, 15, 20, 30, 70, 80, 120}
Output: 20, 80

ar1[] = {1, 5, 5}
ar2[] = {3, 4, 5, 5, 10}
ar3[] = {5, 5, 10, 20}
Output: 5, 5
"""

def intersect(arr1, arr2, arr3):
    x, y, z = 0, 0, 0
    res = []
    
    while x < len(arr1) and y < len(arr2) and z < len(arr3):
        if arr1[x] == arr2[y] and arr2[y] == arr3[z]:
            res.append(arr1[x])
            x += 1
            y += 1
            z += 1
        elif arr1[x] < arr2[y]:
            x += 1
        elif arr2[y] < arr3[z]:
            y += 1
        else:
            z += 1
    return res
     

arr1 = [1, 5, 10, 20, 40, 80]
arr2 = [6, 7, 20, 80, 100]
arr3 = [3, 4, 15, 20, 30, 70, 80, 120]
print intersect(arr1, arr2, arr3)
# -



StarcoderdataJupyterScriptsDedupFiltered