Arrays and Hashing

Question 1

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.

Please implement encode and decode

Answer 1

• Encode by specifying the length of the string followed by ‘#’ at the beginning of each string.
• Decode using this information, try to use string splicing instead of too many while loops.

O(n) / O(n) (but there’s this issue with string concatenation copying the entire string?

def decode(self, str):
    i = 0
    res = []
    while i < len(str):
        wordLen = ''
        while str[i] != '#':
            wordLen += str[i]
            i += 1
        j = 0
        res.append(str[i + 1 : i + int(wordLen) + 1])

        i += int(wordLen) + 1
    return res

Question 2

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Answer 2

Use a set to check if any number is repeated
O(n) / O(n)

https://leetcode.com/problems/contains-duplicate/

Question 3

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Answer 3

Understand def of anagram - check length of words are equal, use 2 hashmaps to count, then compare hashmaps. Also note, if you sort the letters and compare the strings, it’s a slower method of finding anagrams.

O(s + t) / O(s + t)

Question 4

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.

Answer 4

Find the difference of each number from the target, check if it’s in the hashmap, add number and index to hashmap

O(n) / O(n)

Question 5

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Answer 5

Use an array to map the counts to the list of nums that have that count. The counts can be at most len(inputArray) and you’ll list each possible count from 0 to len(inputArray)

O(2n)

Question 6

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Answer 6

Prefix and postfix - multiply each number by all that come before it and add to answer. Shift by 1, use 1 as placeholder. Postfix - go from end to beginning of array, multiply each number by all that come after it. Shift by 1. Multiply there arrays together.

O(n) / O(1)

Question 7

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Answer 7

Convert list to set, loop through array and check if (num - 1) exists in set, if not, num is beginning of sequence. Check if num + 1 in set and keep counting.

O(n) / O(n)

Question 8

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Answer 8

Map character count of each string to list of anagrams. Use ASCII character values as list indices to count the characters. Convert count list to tuple and add as key to dictionary, mapping to current string. When done, get dict values.

Question 9

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

For example, for arr = [2,3,4], the median is 3.
For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.
Implement the MedianFinder class:

MedianFinder() initializes the MedianFinder object.
void addNum(int num) adds the integer num from the data stream to the data structure.
double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

Answer 9

• Use a smallHeap and largeHeap
• Add to smallHeap by default, then check 2 conditions:
  1. Is the max or smallHeap larger than min of largeHeap?
  2. Do the sizes of the heap differ by no more than 1?
• To find the median: if one heap is larger than the other, take the min/max of that heap.
• Otherwise return min + max / 2
• Remember python heap syntax, and that there’s no maxHeap so -1 trick
• Heap operations are O(logn)def __init__(self):
  self.small = []
  self.large = []def addNum(self, num: int) -> None:
  heapq.heappush(self.small, -1 * num) # python does not have max heap so invert the number

    if self.small and self.large and self.small[0] * -1 > self.large[0]:
        val = -1 * heapq.heappop(self.small)
        heapq.heappush(self.large, val)
  
    if len(self.small) - len(self.large) > 1:
        heapq.heappush(self.large, -1 * heapq.heappop(self.small))
    elif len(self.large) - len(self.small) > 1:
        heapq.heappush(self.small, -1 * heapq.heappop(self.large))

  def findMedian(self) -> float:
  if len(self.large) == len(self.small):
  return (self.large[0] + -1 * self.small[0]) / 2
  elif len(self.large) > len(self.small):
  return self.large[0]
  else:
  return -1 * self.small[0]