Problem

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

1
2
3

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

1

string convert(string s, int numRows);

Example 1:

1
2

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

1
2
3
4
5
6
7
8

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

P     I    N
A   L S  I G
Y A   H R
P     I

Problem

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

1
2
3

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

1
2

Input: "cbbd"
Output: "bb"

Template left+1 < right: Finding Position of Target

Example Given nums = [1, 2, 2, 5, 7, 7].

For target = 2, return 1 or 2.

For target = 5, return 3.

For target = 6, return -1.

Problem

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be $O(log (m+n))$.

You may assume nums1 and nums2 cannot be both empty.

Example 1:

1
2
3
4

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

1
2
3
4

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Problem

Given a string, find the length of the longest substring without repeating characters.

Example 1:

1
2
3

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

1
2
3

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

1
2
3
4

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Problem

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:

1
2
3

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Problem

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

Example:

1
2
3
4

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Range Update an Array in Constant Time

Given an array arr of size $n$ with all elements initialized to $0$. Implement void add(int[] arr, int l, int r, int num) and void print(int[] arr) which meet the following requirements:

Binary Search

We assume the array elements are sorted, and we want to find if the input value is inside the array using binary search (divide and conquer).

We notice that the iterations it takes to find out the element in worse case is $O(\log n + 1)$.

Linked List

Normally, inserting into a list is constant time and inserting into an array is $O(n)$. Behind the scenes a python list is built as an array, so insert into a python list is $O(n)$ and finding an element is $O(1)$.