Top Interview Questions for Software Engineer (Google , Microsoft , Amazon , Uber , Airbnb)

 Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

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

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for i in range(len(nums)):
            if target-nums[i] in hashmap:
                return [i,hashmap[target-nums[i]]]
            else:
                hashmap[nums[i]] = i
        return []
            

TC : O(n) // Iterating over each element . SC: O(n) Extra space for Hashmap.

Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
            tailA = l1
            tailB = l2
            carry = 0
            dummyHead = ListNode(-1)
            resNode = dummyHead
            while tailA or tailB:
                x = tailA.val if tailA else 0
                y = tailB.val if tailB else 0
                val = x + y + carry
                resNode.next = ListNode(val % 10)
                carry = val // 10
                if tailA: tailA = tailA.next 
                if tailB: tailB = tailB.next
                resNode = resNode.next
                
            if carry == 1:
                resNode.next = ListNode(carry)
                resNode = resNode.next
     
            return dummyHead.next

TC : O(max(m,n)) SC: O(max(m,n)+1)