# A collection of top classic coding questions

This is a list of top classic coding questions which help understand various data structure and algorithms.

## [Leetcode 206] Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

1 | Input: head = [1,2,3,4,5] |

Example 2:

1 | Input: head = [1,2] |

Example 3:

1 | Input: head = [] |

Constraints:

- The number of nodes in the list is the range [0, 5000].
- -5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Solution:

1 | # Definition for singly-linked list. |

## [Leetcode 25] Reverse Nodes in k-Group

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list’s nodes, only nodes themselves may be changed.

Example 1:

1 | Input: head = [1,2,3,4,5], k = 2 |

Example 2:

1 | Input: head = [1,2,3,4,5], k = 3 |

Constraints:

- The number of nodes in the list is n.
- 1 <= k <= n <= 5000
- 0 <= Node.val <= 1000

Follow-up: Can you solve the problem in O(1) extra memory space?

Solution:

1 | # Definition for singly-linked list. |

## [Leetcoe 146] LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

- LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
- int get(int key) Return the value of the key if the key exists, otherwise return -1.
- void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Example 1:

1 | Input |

Constraints:

- 1 <= capacity <= 3000
- 0 <= key <= 10^4
- 0 <= value <= 10^5
- At most 2 * 10^5 calls will be made to get and put.

Solution:

1 | class LRUCache: |

### [Leetcode 224] Basic Calculator

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

1 | Input: s = "1 + 1" |

Example 2:

1 | Input: s = " 2 - (3 + 4) " |

Example 3:

1 | Input: s = "(1+(4+5+2)-3)+(6+8)" |

Constraints:

- 1 <= s.length <= 3 * 10^5
- s consists of digits, ‘+’, ‘-‘, ‘(‘, ‘)’, and ‘ ‘.
- s represents a valid expression.
- ‘+’ is not used as a unary operation (i.e., “+1” and “+(2 + 3)” is invalid).
- ‘-‘ could be used as a unary operation (i.e., “-1” and “-(2 + 3)” is valid).
- There will be no two consecutive operators in the input.
- Every number and running calculation will fit in a signed 32-bit integer.

Solution:

1 | class Solution: |