# Interview Question (Coding)

## Find the unique number in an array

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

Constraints:

1 <= nums.length <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104
Each element in the array appears twice except for one element which appears only once.

 int singleNUmber(int *nums, int size){
    int n = nums[0];
    for(int i =1; i++ i<size){
        n^= nums[i]
    }
    return n
}

def singleNumber(nums: List[int]) -> int:
    res = nums[0]
    for i in range(1, len(nums)):
        res ^= nums[i]
    return res
# poor solution
def singleNumber(nums: List[int]) -> int:
    if len(nums) == 1:
        return nums[0]

    for num in nums:
        if nums.count(num) == 1:
            return num

<div style="page-break-after: always"></div>

## Sum of 2 elements in 2 arrays

Given 2 arrays `A`,`B` containing non-negative integers, Find all the pair of 2 elements `A[i]`, `B[j]` such that `a[i] + b[j]` is equal `target`

Example 1:

Array A: [1,2,3,4,5]
Array B: [5,6,7,8,9]
target = [[4,5]]

output: true

explain: 5 + 4 = 9 

Example 2:

Array A: [1,0,1,0,...skip 10000...,1,0]
Array B: [2,3,1]
target = 5
output: []

Example 3:

Array A:[30,41,88,25,54,6,55,62,89,96,84,94,36,18,8,60,45,49,44,39,38,22,46,15,69,73,82,56,12,34,21,72,16,74,3,77, 5,91,76,80,11,23,67,7,59,00,71,53,85,1,2,87,9,86,81,43,65,48,78,37,40,14,27,99,10,61,83,24,57,42,32,26,52,28,93,64,79,35,13,20,17,90,95,33,29,98,19,92,58,31,66,63,97,70, 4,47,68,51,50,75]
Array B: [70,63,54,12,91,5,80,49,23,28,42,69,39,22,37,41,4,36,24,93,71,19,58, 3,97,1,78,47,15,96,61,51,86,7,64,32,16,62,79,38, 2,31,44,20,99,48,34,57,29,00,56,21,26,13,95,92,76,77,52,10,89,94,74,67,81,46,18,11,14,85, 9,65,33,87,35,6,43,17,72,73,59,83,84,60,50,55,45,68,53,82,27,30,90,75,40,88,8,66,98,25]

target = 100
output = [[19, 81], [37, 63], [46, 54], [88, 12], [9, 91], [95, 5], [20, 80], [51, 49], [77, 23], [72, 28], [58, 42], [31, 69], [61, 39], [78, 22], [63, 37], [59, 41], [96, 4], [64, 36], [76, 24], [7, 93], [29, 71], [81, 19], [42, 58], [97, 3], [3, 97], [99, 1], [22, 78], [53, 47], [85, 15], [4, 96], [39, 61], [49, 51], [14, 86], [93, 7], [36, 64], [68, 32], [84, 16], [38, 62], [21, 79], [62, 38], [98, 2], [69, 31], [56, 44], [80, 20], [1, 99], [52, 48], [66, 34], [43, 57], [71, 29], [44, 56], [79, 21], [74, 26], [87, 13], [5, 95], [8, 92], [24, 76], [23, 77], [48, 52], [90, 10], [11, 89], [6, 94], [26, 74], [33, 67], [30, 70], [54, 46], [82, 18], [89, 11], [86, 14], [15, 85], [91, 9], [35, 65], [67, 33], [13, 87], [65, 35], [94, 6], [57, 43], [83, 17], [28, 72], [27, 73], [41, 59], [17, 83], [16, 84], [40, 60], [50, 50], [45, 55], [55, 45], [32, 68], [47, 53], [18, 82], [73, 27], [70, 30], [10, 90], [25, 75], [60, 40], [12, 88], [92, 8], [34, 66], [2, 98], [75, 25]]
explain: 19 + 81 = 100, 37 + 63 = 100...

### Suggested Solution

# Array version
def solve(A, B, target):
    flag = False;
    maxA = max(A)
    C = [0] * (maxA + 1)
    for i in A:
        C[i] = 1
    for i in B:
        if ((target - i >= 0) and (target - i < (maxA + 1))):
            if C[target - i] :
                flag = True
                break
                # print (target - i, i)
    return flag

# Object version
def solve2(A, B, target):
    flag = False
    C = dict.fromkeys(A, 1)
    for i in B:
        if (target - i) in C:
            flag = True
            break
            # print(target - i, i)
    return flag

# Poor solution
def poorMethod(A, B, target):
    for i in A:
        for j in B:
            if i + j == target:
                return True
    return False

A = [30,41,88,25,54,6,55,62,89,96,84,94,36,18,8,60,45,49,44,39,38,22,46,15,69,73,82,56,12,34,21,72,16,74,3,77, 5,91,76,80,11,23,67,7,59,0,71,53,85,1,2,87,9,86,81,43,65,48,78,37,40,14,27,99,10,61,83,24,57,42,32,26,52,28,93,64,79,35,13,20,17,90,95,33,29,98,19,92,58,31,66,63,97,70, 4,47,68,51,50,75]
B = [81,63,54,12,91,5,80,49,23,28,42,69,39,22,37,41,4,36,24,93,71,19,58, 3,97,1,78,47,15,96,61,51,86,7,64,32,16,62,79,38, 2,31,44,20,99,48,34,57,29,00,56,21,26,13,95,92,76,77,52,10,89,94,74,67,70,46,18,11,14,85, 9,65,33,87,35,6,43,17,72,73,59,83,84,60,50,55,45,68,53,82,27,30,90,75,40,88,8,66,98,25]

print(solve(A, B, 100))

<div style="page-break-after: always"></div>

## Number of Good Pairs

Given an array of integers nums.

A pair `(i,j)` is called good if `nums[i] == nums[j]` and `i < j`.

Return the number of good pairs.

Example 1:

Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.

Example 2:

Input: nums = [1,1,1,1]
Output: 6
Explanation: Each pair in the array are good.

Example 3:

Input: nums = [1,2,3]
Output: 0

Constraints:

1 <= nums.length <= 10^9
1 <= nums[i] < 2^31

def nC2(num):
    fact = num * (num - 1) / 2
    return int(fact)
def numIdenticalPairs(nums) -> int:
    ans = 0
    result = {}
    for i in nums:
        if i in result:
            result[i] += 1
        else:
            result[i] = 1
    for i in result.keys():
        if result[i] > 1:
            ans += nC2(result[i])
    return ans
print(numIdenticalPairs([1,2,3]))

# poor solution
def numIdenticalPairs(self, nums: List[int]) -> int:
    count=0
    for i in range(len(nums)):
        for j in range(len(nums)):
            if nums[i]==nums[j] and i<j:
                count=count+1
    return count

## Balanced Parantheses

Problem Description

Given a string A consisting only of '(' and ')'.

You need to find whether parantheses in A is balanced or not ,if it is balanced then return 1 else return 0.

Problem Constraints

1 <= |A| <= 10^5

Input Format:
First argument is an string A.

Output Format:
Return 1 if parantheses in string are balanced else return 0.

## Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb `1` or `2` steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:

> 1 <= n <= 45

Suggest solution:

class Solution:
    mem = {1: 1, 2: 2}

    def climbStairs(self, n: int) -> int:
        if n in self.mem:
            return self.mem[n]
        else:
            self.mem[n] = self.climbStairs(n - 1) + self.climbStairs(n-2)
            return self.mem[n]

s = Solution()
print(s.climbStairs(12))