KK's blog

An underground railway system is keeping track of customer travel times between different stations. They are using this data to calculate the average time it takes to travel from one station to another.

Implement the UndergroundSystem class:

void checkIn(int id, string stationName, int t) A customer with a card ID equal to id, checks in at the station stationName at time t.
A customer can only be checked into one place at a time. void checkOut(int id, string stationName, int t)
A customer with a card ID equal to id, checks out from the station stationName at time t. double getAverageTime(string startStation, string endStation)
Returns the average time it takes to travel from startStation to endStation. The average time is computed from all the previous traveling times from startStation to endStation that happened directly, meaning a check in at startStation followed by a check out from endStation.
The time it takes to travel from startStation to endStation may be different from the time it takes to travel from endStation to startStation. There will be at least one customer that has traveled from startStation to endStation before getAverageTime is called.

You may assume all calls to the checkIn and checkOut methods are consistent. If a customer checks in at time t<sub>1</sub> then checks out at time t<sub>2</sub>, then t<sub>1</sub> < t<sub>2</sub>. All events happen in chronological order.

Example 1:

Input
[“UndergroundSystem”,”checkIn”,”checkIn”,”checkIn”,”checkOut”,”checkOut”,”checkOut”,”getAverageTime”,”getAverageTime”,”checkIn”,”getAverageTime”,”checkOut”,”getAverageTime”]
[[],[45,”Leyton”,3],[32,”Paradise”,8],[27,”Leyton”,10],[45,”Waterloo”,15],[27,”Waterloo”,20],[32,”Cambridge”,22],[“Paradise”,”Cambridge”],[“Leyton”,”Waterloo”],[10,”Leyton”,24],[“Leyton”,”Waterloo”],[10,”Waterloo”,38],[“Leyton”,”Waterloo”]]

Output
[null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]

Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, “Leyton”, 3);
undergroundSystem.checkIn(32, “Paradise”, 8);
undergroundSystem.checkIn(27, “Leyton”, 10);
undergroundSystem.checkOut(45, “Waterloo”, 15);  // Customer 45 “Leyton” -> “Waterloo” in 15-3 = 12
undergroundSystem.checkOut(27, “Waterloo”, 20);  // Customer 27 “Leyton” -> “Waterloo” in 20-10 = 10
undergroundSystem.checkOut(32, “Cambridge”, 22); // Customer 32 “Paradise” -> “Cambridge” in 22-8 = 14
undergroundSystem.getAverageTime(“Paradise”, “Cambridge”); // return 14.00000. One trip “Paradise” -> “Cambridge”, (14) / 1 = 14
undergroundSystem.getAverageTime(“Leyton”, “Waterloo”);    // return 11.00000. Two trips “Leyton” -> “Waterloo”, (10 + 12) / 2 = 11
undergroundSystem.checkIn(10, “Leyton”, 24);
undergroundSystem.getAverageTime(“Leyton”, “Waterloo”);    // return 11.00000
undergroundSystem.checkOut(10, “Waterloo”, 38);  // Customer 10 “Leyton” -> “Waterloo” in 38-24 = 14
undergroundSystem.getAverageTime(“Leyton”, “Waterloo”);    // return 12.00000. Three trips “Leyton” -> “Waterloo”, (10 + 12 + 14) / 3 = 12

Example 2:

Input
[“UndergroundSystem”,”checkIn”,”checkOut”,”getAverageTime”,”checkIn”,”checkOut”,”getAverageTime”,”checkIn”,”checkOut”,”getAverageTime”]
[[],[10,”Leyton”,3],[10,”Paradise”,8],[“Leyton”,”Paradise”],[5,”Leyton”,10],[5,”Paradise”,16],[“Leyton”,”Paradise”],[2,”Leyton”,21],[2,”Paradise”,30],[“Leyton”,”Paradise”]]

Output
[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]

Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, “Leyton”, 3);
undergroundSystem.checkOut(10, “Paradise”, 8); // Customer 10 “Leyton” -> “Paradise” in 8-3 = 5
undergroundSystem.getAverageTime(“Leyton”, “Paradise”); // return 5.00000, (5) / 1 = 5
undergroundSystem.checkIn(5, “Leyton”, 10);
undergroundSystem.checkOut(5, “Paradise”, 16); // Customer 5 “Leyton” -> “Paradise” in 16-10 = 6
undergroundSystem.getAverageTime(“Leyton”, “Paradise”); // return 5.50000, (5 + 6) / 2 = 5.5
undergroundSystem.checkIn(2, “Leyton”, 21);
undergroundSystem.checkOut(2, “Paradise”, 30); // Customer 2 “Leyton” -> “Paradise” in 30-21 = 9
undergroundSystem.getAverageTime(“Leyton”, “Paradise”); // return 6.66667, (5 + 6 + 9) / 3 = 6.66667

Constraints:

1 <= id, t <= 10<sup>6</sup> 1 <= stationName.length, startStation.length, endStation.length <= 10
All strings consist of uppercase and lowercase English letters and digits. There will be at most 2 * 10<sup>4</sup> calls in total to checkIn, checkOut, and getAverageTime.
* Answers within 10<sup>-5</sup> of the actual value will be accepted.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution(TestCases):

    def __init__(self):
        self.start_to_end_time = {}
        self.start_end_to_total = collections.defaultdict(lambda: [0, 0])  # cant use defaultdict

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        self.start_to_end_time[id] = (stationName, t)

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        if id not in self.start_to_end_time:
            return
        (start_station, start_time) = self.start_to_end_time[id]
        total, n_trips = self.start_end_to_total[(start_station, stationName)]
        total += t - start_time
        n_trips += 1
        self.start_end_to_total[(start_station, stationName)] = (total, n_trips)

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        total, n_trips = self.start_end_to_total[(startStation, endStation)]
        return total / n_trips

You are given a 0-indexed array of positive integers w where w[i] describes the weight of the i<sup>th</sup> index.

You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w).

For example, if w = [1, 3], the probability of picking index 0 is 1 / (1 + 3) = 0.25 (i.e., 25%), and the probability of picking index 1 is 3 / (1 + 3) = 0.75 (i.e., 75%).

Example 1:

Input
[“Solution”,”pickIndex”]
[[[1]],[]]
Output
[null,0]

Explanation
Solution solution = new Solution([1]);
solution.pickIndex(); // return 0. The only option is to return 0 since there is only one element in w.

Example 2:

Input
[“Solution”,”pickIndex”,”pickIndex”,”pickIndex”,”pickIndex”,”pickIndex”]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]

Explanation
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.

Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
……
and so on.

Constraints: 1 <= w.length <= 10<sup>4</sup>
1 <= w[i] <= 10<sup>5</sup> pickIndex will be called at most 10<sup>4</sup> times.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution(TestCases):

    def __init__(self, w: List[int]):
        self.presum = []
        sum = 0
        for n in w:
            sum += n
            self.presum.append(sum)

    def pickIndex(self) -> int:
        rand_value = random.randint(0, self.presum[-1] - 1)
        return bisect.bisect(self.presum, rand_value)

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = [“flower”,”flow”,”flight”]
Output: “fl”

Example 2:

Input: strs = [“dog”,”racecar”,”car”]
Output: “”
Explanation: There is no common prefix among the input strings.

Constraints:

1 <= strs.length <= 200 0 <= strs[i].length <= 200
* strs[i] consists of only lower-case English letters.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def longestCommonPrefix(self, strs: List[str]) -> str:
	min_len, res = sys.maxsize, ''
	for s in strs:
		min_len = min(min_len, len(s))
	for i in range(min_len):
		char = strs[0][i]
		same_char = True
		for j in range(1, len(strs)):
			if char != strs[j][i]:
				same_char = False
				break
		if not same_char:
			break
		res += char
	return res

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Example 1:

Input: s = “()”
Output: true

Example 2:

Input: s = “()[]{}”
Output: true

Example 3:

Input: s = “(]”
Output: false

Example 4:

Input: s = “([)]”
Output: false

Example 5:

Input: s = “{[]}”
Output: true

Constraints:

1 <= s.length <= 10<sup>4</sup> s consists of parentheses only '()[]{}'.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

PARENTHESES_DICT = {'(': ')', '[': ']', '{': '}'}
class Solution:
    def isValid(self, s: str) -> bool:
        if not s:
            return False
        stack = []
        for char in s:
            if char in '([{':
                stack.append(char)
            else:
                if not stack:
                    return False
                left = stack.pop()
                if PARENTHESES_DICT[left] != char:
                    return False
        return True if not stack else False
                

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

The replacement must be in place and use only constant extra memory.

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:

Input: nums = [3,2,1]
Output: [1,2,3]

Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]

Example 4:

Input: nums = [1]
Output: [1]

Constraints:

1 <= nums.length <= 100 0 <= nums[i] <= 100

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 135864 -> 136854 -> 136458
# 1355864 -> 1356458
# 99
def nextPermutation(self, nums: List[int]) -> None:
	to_be_swapped_index, greater_index = -1, -1
	for i in range(len(nums) - 2, -1, -1):
		if nums[i] < nums[i + 1]: # 5 < 8
			to_be_swapped_index = i # 2
			break
	if to_be_swapped_index == -1:
		nums.sort()
		return nums
	for i in range(len(nums) - 1, to_be_swapped_index, -1): #
		if nums[to_be_swapped_index] < nums[i]: # 5 < 6
			greater_index = i # 4
			break # 136854
	nums[to_be_swapped_index], nums[greater_index] = nums[greater_index], nums[to_be_swapped_index]
	# nums[to_be_swapped_index + 1:] = sorted(nums[to_be_swapped_index + 1:]) # 136458
	nums[to_be_swapped_index + 1:] = nums[:to_be_swapped_index:-1]
	return nums