Warm-up Challenges

Sock Merchant

John works at a clothing store. He has a large pile of socks that he must pair by color for sale. Given an array of integers representing the color of each sock, determine how many pairs of socks with matching colors there are. For example, there are $n=7$ socks with colors $ar = [1,2,1,2,1,3,2]$. There is one pair of color $1$ and one of color $2$. There are three odd socks left, one of each color. The number of pairs is 2.

n = 9, ar = 10 20 20 10 10 30 50 10 20
output: 3

Idea : We go throuh all unique values in the list (by translate it to a set), we can count the number of couple easily.

def sockMerchant(n, ar):
  count = 0
  for num in set(ar):
    count += ar.count(num) // 2
  return count

Counting Valleys

Gary is an avid hiker. He tracks his hikes meticulously, paying close attention to small details like topography. During his last hike he took exactly $n$ steps. For every step he took, he noted if it was an uphill, $U$, or a downhill, $D$ step. Gary’s hikes start and end at sea level and each step up or down represents a $1$ unit change in altitude. We define the following terms:

• A mountain is a sequence of consecutive steps above sea level, starting with a step up from sea level and ending with a step down to sea level.
• A valley is a sequence of consecutive steps below sea level, starting with a step down from sea level and ending with a step up to sea level.

Given Gary’s sequence of up and down steps during his last hike, find and print the number of valleys he walked through. For example, if Gary’s path is $s=[DDUUUUDD]$, he first enters a valley $2$ units deep. Then he climbs out an up onto a mountain $2$ units high. Finally, he returns to sea level and ends his hike.

n= 8
s= UDDDUDUU
_/\      _
   \    /
    \/\/
output : 1 (valley)

Idea : First, we need to convert all U to $1$ and D to $-1$. We take the sum from the begining of step (its value is $0$). Whenever the sum is $0$ again from the U, we have a valley need to be counted.

def countingValleys(n, s):
  char2num = lambda char: (char=="U") - (char=="D") 
  count = 0
  tmp = 0
  for char in s:
    tmp += char2num(char)
    if tmp==0 and char=="U":
      count += 1
  return count

Jumping on the Clouds

Emma is playing a new mobile game that starts with consecutively numbered clouds. Some of the clouds are thunderheads and others are cumulus. She can jump on any cumulus cloud having a number that is equal to the number of the current cloud plus $1$ or $2$. She must avoid the thunderheads. Determine the minimum number of jumps it will take Emma to jump from her starting postion to the last cloud. It is always possible to win the game.

For each game, Emma will get an array of clouds numbered $0$ if they are safe or $1$ if they must be avoided. For example, $c=[0,1,0,0,0,1,0]$ indexed from $0…6$. The number on each cloud is its index in the list so she must avoid the clouds at indexes $1$ and $5$. She could follow the following two paths: $0\to 2\to 4\to 6$ or $0\to 2\to 3\to 4\to 6$. The first path takes jumps while the second takes $4$.

7
0 0 1 0 0 1 0
output: 4

Idea : Because we can jump to maximum $2$ “steps”, we always consider jump this number of steps first. If we cannot jump $2$, we jump $1$. We consider only all the clouds before the last cloud maximum $2$ steps because in any case, we are able to go the the last cloud with this distance!

def jumpingOnClouds(c):
  cstep = 0
  count = 0
  while cstep < len(c)-3:
    cstep += (c[cstep+2]==0)*2 + (c[cstep+2]==1)
    count += 1
  return count + 1

Repeated String

Lilah has a string, $s$, of lowercase English letters that she repeated infinitely many times. Given an integer, $n$, find and print the number of letter a’s in the first $n$ letters of Lilah’s infinite string. For example, if the string $s=”abcac”$ and $n=10$, the substring we consider is $abcacabcac$, the first $10$ characters of her infinite string. There are $4$ occurrences of a in the substring.

aba
10
output: 7

Idea : We cannot find the very long string with s and n like s*n because of MemoryError. We have to figure out another way! We need to find out how many “whole” s (all characters in s conserved) will be repeated and then just count the number of a in the last part of s.

def repeatedString(s, n):
  floor = n // len(s)
  return floor * s.count("a") + s[:(n % len(s))].count("a")

Arrays

2D Array - DS

Given a $6\times 6$ 2D array, $arr$. We define a hourglass in $arr$ if it has below pattern in its presentation.

***
 *
***

There will be $16$ hourglass in $ar$, we take the sum of all number in each hourglass and then choose the largest one. For example, given the 2D array:

-9 -9 -9  1 1 1 
 0 -9  0  4 3 2
-9 -9 -9  1 2 3
 0  0  8  6 6 0
 0  0  0 -2 0 0
 0  0  1  2 4 0

We calculate the following $16$ hourglass values:

-63, -34, -9, 12, 
-10, 0, 28, 23, 
-27, -11, -2, 10, 
9, 17, 25, 18

The largest sum is $28$ which is from the hourglass

0 4 3
  1
8 6 6

Idea : We sum up all $9$ elements in each $3\times3$ square containing the hourglass (we call this square “SHG”) and then remove $2$ excess elements. Note that, in order to determine each SHG, we only need to determine the first element on the first row and line of this SHG. It leads to a remark in that we only need to consider all elements from arr[0][0] to arr[3][3] to form all SHGs containing hourglasses we want.

def hourglassSum(arr):
  # each SHG is determined via the element a[i][j]
  for i in range(4):
    for j in range(4):
      try:
        # sum of all elements in SHG
        sumHG = sum(sum(arr[i+k][j:j+3]) for k in range(3))
        # remove 2 excess elements
        sumHG -= arr[i+1][j] + arr[i+1][j+2]
        if maxHG < sumHG:
          maxHG = sumHG
      except NameError:  # if maxHG isn't defined
        maxHG = sum(sum(arr[i][:3]) for i in range(3))
        maxHG -= arr[1][0] + arr[1][2]
  return maxHG

A shorter version, we don’t need to use the maxHG with the help of max() of a list and we take the sum of hourglass as its definition by going through the first element of each SHG.

def hourglassSum(arr):
  li = []
  for i in range(len(arr) - 2):
    for j in range(len(arr) - 2):
      li.append(sum(arr[i][j:j + 3] + arr[i + 2][j:j + 3]) + arr[i + 1][j + 1])
  return max(li)

Arrays: Left rotation

A left rotation operation on an array shifts each of the array’s elements $1$ unit to the left. For example, if $2$ left rotations are performed on array $[1,2,3,4,5]$, then the array would become $3,4,5,1,2$. Given an array $a$ of $n$ integers and a number, $d$, perform $d$ left rotations on the array. Return the updated array to be printed as a single line of space-separated integers.

5 4
1 2 3 4 5
output: 5 1 2 3 4

Idea : Remeber that if you wanna copy a list, use .copy(). In this case, going to the left $d$ units is equivalent to going to the right $d-len(arr)$ units.

def rotLeft(a, d):
  b = a.copy()
  for i in range(len(a)):
    b[i - d] = a[i]
  return b

# only 1 line
def rofLeft(a, d):
  return [a[d - len(a) + i] for i in range(len(a))]

New Year Chaos

It’s New Year’s Day and everyone’s in line for the Wonderland rollercoaster ride! There are a number of people queued up, and each person wears a sticker indicating their initial position in the queue. Initial positions increment by $1$ from $1$ at the front of the line to $n$ at the back. Any person in the queue can bribe the person directly in front of them to swap positions. If two people swap positions, they still wear the same sticker denoting their original places in line. One person can bribe at most two others. For example, if $n=4$ and Person $5$ bribes Person $4$, the queue will look like this: $1,2,3,5,4,7,8$.

Fascinated by this chaotic queue, you decide you must know the minimum number of bribes that took place to get the queue into its current state! Print an integer denoting the minimum number of bribes needed to get the queue into its final state. Print Too chaotic if the state is invalid, i.e. it requires a person to have bribed more than people.

2
5
2 1 5 3 4
5
2 5 1 3 4

output:
3
Too chaotic

Idea : This exercise is a little complicated. We talk about 3 parts:

1. When the “Too chaotic” happens? When there is some person moving from his old position to a new one more than $2$ units. Don’t forget that the value of that guy is actually his old position and his index in q is his new one.
2. How to find the minimum numbers of bribes? It’s actually the sum of all bribes that every person in the line take. In order to count the number of bribes some person takes, we count the number of people standing in front of him/her and they are wearing a bigger sticker (they are bigger than A so they have bribed and passed A to get this position).
3. The efficiency : If we check all of the guys standing before the current guy, the complexity of our algorithm is not so good. Remember that a person A cannot bribe more than two others and A still wears the same sticker denoting A’s original places. Therefore, we don’t need to check all of the guys standing before A, we just need to check the guys standing at most 2 from A. For example, the guy $5$ is standing at the place $8$, we just need to check all the guys standing from the position $3$ to the position $7$ (before where $5$’s standing). But why we don’t consider positions $1$ and $2$? It’s because if some B can bribe A to go up to position $1$ or $2$, they have to bribe $3$ and $4$ too. Other words, B have to bribe at least $3$ people, it breaks the rule!

def minimumBribes(q):
  count = 0
  for i, v in enumerate(q):
    if (v - 1) - i > 2:
      print("Too chaotic")
      return
    count += sum(e > v for e in q[max(0, v - 2):i])
    # if we don't need the efficiency
    # count += sum(e > v for e in q[:i])
  print(count)

Minimum Swaps 2

You are given an unordered array consisting of consecutive integers $\in [1,2,3,\ldots]$ without any duplicates. You are allowed to swap any two elements. You need to find the minimum number of swaps required to sort the array in ascending order. For example, given the array $arr=[7,1,3,2,4,5,6]$ we perform the following steps:

# input: 7 1 3 2 4 5 6

i   arr                     swap (indices)
0   [7, 1, 3, 2, 4, 5, 6]   swap (0,3)
1   [2, 1, 3, 7, 4, 5, 6]   swap (0,1)
2   [1, 2, 3, 7, 4, 5, 6]   swap (3,4)
3   [1, 2, 3, 4, 7, 5, 6]   swap (4,5)
4   [1, 2, 3, 4, 5, 7, 6]   swap (5,6)
5   [1, 2, 3, 4, 5, 6, 7]

# output: 5

Idea : We go through the array (by each position from the left to the right) and check the number at each position whether it has a right position or not. A number is said to have a “right position” if it stands at the position whose value is less than the number’s value 1 unit. For example, the number 6 which stands at position 5 has a right position. If the current number doesn’t have a right position, we make a swap between this number with the number occupying the place of considered number. For example, the current number is 4 at the position 2, we make a swap between the number 4 (at position 2) with the number at position 3 (which is the right position of 4). A special idea in this case is that, we only go next if the current number has a right position. If it doesn’t, we keep checking the number (of a new array after the swap) at the current place (checking_pos).

def minimumSwaps(arr):
  count = 0
  checking_pos = 0 # we start to check at the first number on the left
  last = len(arr) - 1 # until the last number of the array
  while checking_pos < last:
    while(arr[checking_pos] == checking_pos + 1 and checking_pos < last):
      checking_pos += 1 # we only go next if the current number has a right position
    if checking_pos < last:
      tmp = arr[checking_pos] - 1 # real position of arr[checking_pos]
      arr[checking_pos], arr[tmp] = arr[tmp], arr[checking_pos] # swap 2 numbers
      count += 1
  return count

Array Manipulation

Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in your array. For example, the length of your array of zeros n = 10. Your list of queries is as follows:

a b k  # add k to the numbers between the indexes a and b inclusive
1 5 3  # add 3 to the numbers between the 1st and 5th number of the array
4 8 7  # add 7 to the numbers between the 4th and 8th number of the array
6 9 1  # add 1 to the numbers between the 6th and 9th number of the array

Add the values of k between the indices a and b inclusive:

index ->	1 2 3  4  5 6 7 8 9 10
	       [0,0,0, 0, 0,0,0,0,0, 0]  # initial array
	       [3,3,3, 3, 3,0,0,0,0, 0]  # add 3 to the numbers between the 1st and 5th number of the array
	       [3,3,3,10,10,7,7,7,0, 0]  # add 7 to the numbers between the 4th and 8th number of the array
	       [3,3,3,10,10,8,8,8,1, 0]  # add 1 to the numbers between the 6th and 9th number of the array

The largest value is 10 after all operations are performed.

Idea : The following solution is not mine! The main idea is that we don’t want to add all numbers between a and b. If we can find a way in that we only consider the numbers at positions a and b, that’s better! Let’s consider above example, at each operation, instead of getting an array like [3,3,3,3,3,0,0,0,0,0], we get an array like [3,0,0,0,0,-3,0,0,0,0,0], what’s this? It’s the difference between the current number from the previous one in an array.

Check this

def arrayManipulation(n, queries):
  # queries contains mx3 matrix of necessary numbers
  lst = [0]*(n+1)
  for i in range(len(queries)):
    a, b, k = queries[i] # taking a, b and k from each line of queries
    lst[a-1] += k
    lst[b] -= k 
  maxval = x = 0
  for i in lst: # find the max sum in the list lst
    x += i
    if maxval < x:
      maxval = x
  return maxval

Dictionaries and Hashmaps

Hash Tables: Ransom Note

• Problem.
• Hiểu lại: Cho 2 list chứa các cụm từ. Xem thử xem có thể tạo thành list note được từ các từ của list magazine hay không (case-sensitive). Nếu có thể thì print Yes, ngược lại print No.

• Một vài trường hợp lưu ý

  # case-sensitive
  note = ['dinh', 'Anh']
  magazine = ['dinh', 'anh', 'thi']
  # print 'No'
    
  # không đủ từ
  note = ['dinh', 'Anh', 'dinh']
  # print 'No'
  

• Nếu không xét tính hiệu quả: Cứ so sánh từng chữ của note xem nó có trong magazine hay không, nếu có thì mình xóa đi chữ đó trong magazine (xem như dùng rồi).

  def checkMagazine(magazine, note):
    result = 'Yes'
    
    for item in note:
      if not item in magazine:
        result = 'No'
        break
      else:
        magazine.remove(item)
    
    print(result)
  

• Ở trên sẽ gặp lỗi # timeout error ở vài trường hợp, sửa lại tối ưu (sort list trước khi thao tác giúp nhanh hơn):

  def checkMagazine(magazine, note):
    magazine.sort() # điểm khác biệt!!!!
    note.sort() # điểm khác biệt!!!!
    
    result = 'Yes'
    if len(magazine) < len(note):
      result = 'No'
    else:
      for item in note:
        if not item in magazine:
          result = 'No'
          break
        else:
          magazine.remove(item)
  

Two Strings

• Problem.
• Tóm tắt: