Solution for interview

interview_question.py

"""
Q1. Given an unsorted array with multiple duplicate elements. Find the most repeated element. Return the bigger number if multiple numbers have the highest frequency.
For example:
T1:
Input: [2, 1, -2, 55, 2, 1, 3, 9, 3, 3]
Answer: 3
T2: [1, 1, 2, 2, 2, 2, 1, 1]
Answer: 2
"""
def most_frequent(arr):
    result = None
    frequency_dic = {}
    for num in arr:
        frequency_dic[num] = frequency_dic.get(num, 0) + 1
    
    highest_freq = 0
    for num, freq in frequency_dic.items():
        if freq >= highest_freq:
            if freq == highest_freq:
                result = max(result, num)
            else:
                highest_freq = freq
                result = num
    return result

# print(most_frequent([2, 1, -2, 55, 2, 1, 3, 9, 3, 3]))
# print(most_frequent([1, 1, 2, 2, 2, 2, 1, 1]))


"""
Find Kth largest/smallest element in an unsorted array? For example, given an array: [2, -11, 54, 78, 61...], find the 19th maximum element. Expecting a better solution than sorting.
"""
def k_largest(arr, k):
    if k >= len(arr):
        raise ValueError("K can't be larger than array length")
    arr.sort(reverse=True)
    return arr[k - 1] # assuming k is 1-indexed

# other approach could be to use HEAP
# print(k_largest([9,4,0,7,2], 1))


"""
Q3. Given a list of digits: [3, 5, 1]. Now if these digits were to be treated as a number it would make 351. If we were to list and sort all the permutations of this number, we would get the following:

135
153
315
351
513
531

Find a permutation of this list where the resulting number is the next greater number in this list. For our given list, the answer would be: [5, 1, 3] as 513 is next greater to 351. Note the list of digits can be huge, can have thousands of digits so we can't just generate all the permutations.
"""

def next_perm(digits):
    for i in range(len(digits) - 1, -1, -1):
        curr = digits[i]
        for j in range(i - 1, -1, -1):
            if digits[j] < curr:
                # shift all element towards right
                for k in range(i, j, -1):
                    digits[k] = digits[k - 1]
                digits[j] = curr
                return digits
    return None

# print(next_perm([3, 5, 1]))