# Coding Patterns in C# and Python for Coding Interviews (M/H)

Note: this post is being updated progressively.

## 1. Sliding window

Problem: Given a string `s`, find the length of the longest substring without repeating characters.

### C#

```Runtime: 84 ms, faster than 80.08% of C# online submissions for Longest Substring Without Repeating Characters.
Time Complexity : O(n)
Space Complexity: O(n)```

### Python 3

```Runtime: 64 ms, faster than 65.71% of Python3 online submissions for Longest Substring Without Repeating Characters.
Time Complexity : O(n)
Space Complexity: O(n)```

## 2. Two pointers

Problem: Container With Most Water.

Given `n` non-negative integers `a1, a2, ..., an`, where each represents a point at coordinate `(i, ai)``n` vertical lines are drawn such that the two endpoints of the line `i` is at `(i, ai)` and `(i, 0)`. Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

### C#

```Runtime: 176 ms, faster than 99.42% of C# online submissions for Container With Most Water.
Time Complexity = O(n)
Space Complexity = O(1)```

### Python 3

```Runtime: 748 ms, faster than 56.75% of Python3 online submissions for Container With Most Water.
Time Complexity = O(n)
Space Complexity = O(1)```

## 3. Fast and Slow Pointers (Hare and Tortoise algorithm)

Given a linked list, return the node where the cycle begins. If there is no cycle, return `null`.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the `next` pointer. Internally, `pos` is used to denote the index of the node that tail’s `next` pointer is connected to. Note that `pos` is not passed as a parameter.

Notice that you should not modify the linked list.

### C#

```Runtime: 96 ms, faster than 77.01% of C# online submissions for Linked List Cycle II.
Time complexity: O(N)
Space complexity: O(1)```

### Python 3

`Runtime: 48 ms, faster than 81.20% of Python3 online submissions for Linked List Cycle II.`

## 4. Merge intervals

### c#

Given an array of `intervals` where `intervals[i] = [starti, endi]`, merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

```Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].```
```Runtime: 248 ms, faster than 96.73% of C# online submissions for Merge Intervals.
Time Complexity: O(n.log(n))
Space Complexity O(log(n))```

### Python 3

`Runtime: 88 ms, faster than 52.59% of Python3 online submissions for Merge Intervals.`

## 5. Cyclic Sort

Given an integer array `nums` of length `n` where all the integers of `nums` are in the range `[1, n]` and each integer appears once or twice, return an array of all the integers that appears twice.

You must write an algorithm that runs in `O(n) `time and uses only constant extra space.

### C#

```Runtime: 304 ms, faster than 72.55% of C# online submissions for Find All Duplicates in an Array.
Time complexity: O(N)
Space complexity: O(1)```

### Python 3

`Runtime: 365 ms, faster than 50.56% of Python3 online submissions for Find All Duplicates in an Array.`

## 5. In-place reversal of a linked list

### C#

```Runtime: 76 ms, faster than 99.86% of C# online submissions for Reverse Linked List II.
Time Complexity: O(n)
Space Complexity: O(1)```

### Python 3

`Runtime: 32 ms, faster than 60.16% of Python3 online submissions for Reverse Linked List II.`

## 7. Tree BFS

Given the `root` of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).

### C#

```Runtime: 240 ms, faster than 75.21% of C# online submissions for Binary Tree Zigzag Level Order Traversal.
Time complexity O(n)
Space complexity O(1)```

### Python 3

`Runtime: 28 ms, faster than 88.64% of Python3 online submissions for Binary Tree Zigzag Level Order Traversal.`

## 8. Tree DFS

Given the `root` of a binary tree and an integer `targetSum`, return all root-to-leaf paths where each path’s sum equals `targetSum`.

leaf is a node with no children.

### c#

```Runtime: 248 ms, faster than 61.07% of C# online submissions for Path Sum II.
Time complexity: O(n)
Space complexity: O(log(n))```

### Python 3

`Runtime: 36 ms, faster than 97.15% of Python3 online submissions for Path Sum II.`

## 9. Two heaps

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.

Example 1:

```Input
[[], , , [], , []]
Output
[null, null, null, 1.5, null, 2.0]```

### C#

Doesn’t offer PriorityQueue built-in class.

### Python 3

```Runtime: 508 ms.
Time complexity: O(log(n))
Space complexity: O(1)```

## 10. Subsets

Given a string `s`, we can transform every letter individually to be lowercase or uppercase to create another string.

Return a list of all possible strings we could create. You can return the output in any order.

Example 1:

```Input: s = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]```

BFS Solution:

### C#

```Runtime: 252 ms
Time Complexity: O(n*m) // n the length of the string, m is the size of the queue
Space Complexity: O(n+m)```

### Python

`Runtime: 52 ms`

## 11. Binary Search

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once.

Follow up: Your solution should run in O(log n) time and O(1) space.

Example 1:

```Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2```

### C#

```Runtime: 100 ms
Time complexity: O(n)
Space complexity: O(1)```

### Python 3

`Runtime: 64 ms`

## 12. Top K elements

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

Example 1:

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

### C#

```Runtime: 252 ms
Time complexity: O(n)
Space complexity: O(1) ```

### Python 3

`Runtime: 104 ms`

Solution 2

## 13. Merge K lists

You are given an array of `k` linked-lists `lists`, each linked-list is sorted in ascending order.

Example 1:

```Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6```

### C#

`Runtime: 132 ms`

### Python 3

```Time complexity: O (Nlogk) where k is the number of linked lists.
Space complexity O(1)```

## 14. Topological sort

Given a characters array `tasks`, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

However, there is a non-negative integer `n` that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least `n` units of time between any two same tasks.

Return the least number of units of times that the CPU will take to finish all the given tasks.

Example 1:

```Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation:
A -> B -> idle -> A -> B -> idle -> A -> B
There is at least 2 units of time between any two same tasks.```

### c#

```Runtime: 144 ms
Time complexity: O(n)
Space complexity: O(1)```

### Python 3

`Runtime: 380 ms`