Easy Flashcards
- Remove Duplicates from Sorted Array
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
Two indexes approach
~~~
def removeDuplicates(self, nums: List[int]) -> int:
write = 0
# start with read pointer 1 ahead
for read in range(1, len(nums)):
# if read not bigger than write, it’s a dup
# so we skip over it, and everything after
# gets shifted left
if nums[read] > nums[write]:
write += 1
nums[write] = nums[read]
return write + 1
~~~
O(n)
- First Bad Version
Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
Binary search tree
Test middle value, then split the range in half and test again O(logn). Iterative uses less memory.
~~~
l = 1
r = n
while True:
if r - l == 0: return r
half = (r - l) // 2 + l
if isBadVersion(half):
r = half
else:
l = half + 1
~~~
- Search Insert Position
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
Binary search tree
~~~
def searchInsert(self, nums: List[int], target: int) -> int:
l = 0
r = len(nums) - 1
while True:
mid = (r - l) // 2 + l
if nums[mid] == target: return mid
if r - l == 0: # if range is only one
if nums[r] < target:
return r + 1
else:
return r
if nums[mid] < target:
l = mid + 1
else:
r = mid
~~~
O(logn)
- Remove element
Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
Two pointers
As we find instances of the target value, swap them to the end of the list, then shrink the list (bring right pointer in).
~~~
def removeElement(self, nums: List[int], val: int) -> int:
right = len(nums) - 1
result = 0
for left in range(len(nums)):
if nums[left] == val: # if this is the val we're looking for
# bring the right pointer left until there are no vals on the left
while right > left and nums[right] == val:
right -= 1
# swap the current number with one at the r pointer
nums[left] = nums[right]
# bring the r pointer in, to exclude the one we just swapped
right -= 1
if left <= right:
# count how many steps we took
result += 1
else:
break
return result ~~~
- Last Stone Weight
You are given an array of integers stones where stones[i] is the weight of the ith stone.
We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:
If x == y, both stones are destroyed, and If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.
At the end of the game, there is at most one stone left.
Return the weight of the last remaining stone. If there are no stones left, return 0.
Max heap
~~~
def lastStoneWeight(self, stones: List[int]) -> int:
self.heap = stones # max heap. python doesn’t provide a utility for max.
while len(self.heap) > 1:
# pop twice to get the two heaviest stones
# smash stones, get remainder
# if remainder > 0, push remainder
if len(self.heap):
return self.heap[0]
else:
return 0
~~~
- K Closest Points to Origin
Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).
The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).
Min heap
~~~
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
self.heap = list()
# build a list of tuples with the dist and point
for p in points:
self.heap.append((math.sqrt(pow(0 - p[0], 2) + pow(0 - p[1], 2)), p))
# heapify works on tuples
heapq.heapify(self.heap)
# pop the k smallest and return
output = list()
for i in range(k):
output.append(heapq.heappop(self.heap)[1])
return output
~~~
O(n*klogn) = O(n^2) worst case k = n
- Two sum
use a dictonary
def twoSum(self, nums: List[int], target: int) -> List[int]:
dict = {}
result = []
for i in range(len(nums)):
if nums[i] in dict.keys():
# this num’s reciprocal was found, add pair to result
result = [dict[nums[i]], i]
else:
# add this num’s reciprocal to the dict.
# if we find it later, we add it to the result
recip = target - nums[i]
dict[recip] = i
return result
- Number of 1 Bits
Write a function that takes the binary representation of an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).
If you bitwise AND a number n with n-1, it flips the least significant bit to 0. Do this until n has no 1-bits left, and count how many times you did it.
def hammingWeight(self, n: int) -> int:
sum = 0
while n != 0:
sum += 1
n &= (n - 1) # flip least sig bit to 0 until n == 0
return sum
- Reverse Bits
Reverse bits of a given 32 bits unsigned integer.
def reverseBits(self, n: int) -> int:
ret, power = 0, 31
while n: # when we’re done, all the 1-bits have been removed and we’re left with 0
# get the 1s-place bit and move it to the location in the output specified by power
ret += (n & 1) «_space;power
# shift all bits to the right, so we can get the 1s-place again
n = n»_space; 1
# next time, place the bit in the position to the right in the output, building the output from L to R
power -= 1
return ret
- Print in Order
Suppose we have a class:
public class Foo {
public void first() { print(“first”); }
public void second() { print(“second”); }
public void third() { print(“third”); }
}
The same instance of Foo will be passed to three different threads. Thread A will call first(), thread B will call second(), and thread C will call third(). Design a mechanism and modify the program to ensure that second() is executed after first(), and third() is executed after second().
Note:
We do not know how the threads will be scheduled in the operating system, even though the numbers in the input seem to imply the ordering. The input format you see is mainly to ensure our tests’ comprehensiveness.
Use a lock object
from threading import Lock
class Foo:
def __init__(self):
self.firstJobDone = Lock()
self.secondJobDone = Lock()
self.firstJobDone.acquire()
self.secondJobDone.acquire()
def first(self, printFirst: 'Callable[[], None]') -> None:
# printFirst() outputs "first".
printFirst()
# Notify the thread that is waiting for the first job to be done.
self.firstJobDone.release()
def second(self, printSecond: 'Callable[[], None]') -> None:
# Wait for the first job to be done
with self.firstJobDone:
# printSecond() outputs "second".
printSecond()
# Notify the thread that is waiting for the second job to be done.
self.secondJobDone.release()
def third(self, printThird: 'Callable[[], None]') -> None:
# Wait for the second job to be done.
with self.secondJobDone:
# printThird() outputs "third".
printThird()
- Find the Index of the First Occurrence in a String
Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = “sadbutsad”, needle = “sad”
Output: 0
Explanation: “sad” occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.
Brute force is easy using a sliding window. Advanced approaches include the Rabin-Karp Algorithm with single or double hashing. This uses the concept of a rolling hash, which allows you to compute hashes of substrings in O(1) time. There is also the Knuth–Morris–Pratt Algorithm (KMP).
