A collection of top classic coding questions

Posted on Edited on In , Views:

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
2
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

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

Example 3:

1
2
Input: head = []
Output: []

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    # Time: O(n) Space: O(1)
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev, curr = None, head
        while curr:
            next = curr.next # save next node before we break the pointer
            curr.next = prev # point to previous node
            prev = curr # shift previous pointer 
            curr = next # shift current pointer

        return prev

    # Time: O(n) Space: O(1)
    def reverseList_recursive(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None

        # e.g.
        #   1 -> 2 -> 3 -> 4
        #   ^    ^
        # head  head.next
        #
        #   4  ->  3  ->  2    ->     1   -> None
        #   ^             ^           ^
        # newHead        head.next   head
        newHead = head
        if head.next:
            newHead = self.reverseList(head.next)
            head.next.next = head
        head.next = None

        return newHead

[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
2
Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

Example 2:

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

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # check if reverse is needed
        curr = head
        for _ in range(k):
            if not curr:
                return head # no need to reverse, thus return the original head
            curr = curr.next

        # Reverse the sub-list with k nodes
        # e.g.
        # None  1 -> 2 -> 3 -> 4 -> 5 -> 6, k = 3
        # ^     ^
        # prev  head(curr) 
        #
        # After reverse the first 3 nodes,
        # 3 -> 2 -> 1 -> 4 -> 5 -> 6
        # ^         ^    ^
        # prev      head curr
        prev, curr = None, head
        for _ in range(k):
            next = curr.next # save the next before we break the pointer
            curr.next = prev # point to previous node(reverse)
            prev = curr # shift previous pointer
            curr = next # shift current pointer 

        # after reverse, the curr pointer points to the "head" of next k nodes, 
        # and the previous pointer points to the new "head" of the reversed k nodes.
        head.next = self.reverseKGroup(curr, k) 

        # the previous pointer points to the head of reversed list
        return prev

[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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class LRUCache:
    # double-linked list
    class Node:
        def __init__(self, key=None, val=None):
            self.key = key
            self.val = val
            self.next = None
            self.prev = None

    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}

        # dummy head and tail for the doubled-linked list
        self.head = self.Node()
        self.tail = self.Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def addNode(self, node):
        node1 = self.head.next
        node.next = node1
        node1.prev = node
        self.head.next = node
        node.prev = self.head

    def deleteNode(self, node):
        prev = node.prev
        next = node.next
        prev.next = next
        next.prev = prev

    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            val = node.val
            del self.cache[key]
            self.deleteNode(node)
            self.addNode(node)
            self.cache[key] = self.head.next
            return val
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            del self.cache[key]
            self.deleteNode(node)

        # delete the least recently used node when the capacity is full
        if len(self.cache) == self.cap:
            del self.cache[self.tail.prev.key]
            self.deleteNode(self.tail.prev)

        # insert the most recent used node to the front
        self.addNode(self.Node(key, value))
        self.cache[key] = self.head.next


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

[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
2
Input: s = "1 + 1"
Output: 2

Example 2:

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

Example 3:

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

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
class Solution:
    def calculate(self, s: str) -> int:
        """
        Refer to https://leetcode.com/problems/basic-calculator/solutions/546092/simple-python-solution-using-stack-with-explanation-inline/?envType=study-plan-v2&envId=top-interview-150
        1. Take 3 containers:
        num -> to store current num value only
        sign -> to store sign value, initially +1
        res -> to store sum
        When ( comes these containers used for calculate sum of intergers within () brackets.
        --------------------
        2. When c is + or -
        Move num to res, because we need to empty num for next integer value.
        set num = 0
        sign = update with c
        --------------------
        3. When c is '('
        Here, we need num, res, sign to calculate sum of integers within ()
        So, move num and sign to stack => [num, sign]
        Now reset - res = 0, num = 0, sign = 1 (default)
        --------------------
        4. When c is ')' -> 2-(3+4), Here res=3, num=4, sign=1 stack [2, -] 
        res +=sign*num -> calculate sum for num first, then pop items from stack, res=7
        res *=stack.pop() - > Pop sign(+ or -) to multiply with res, res = 7*(-1)
        res +=stack.pop() - > Pop integer and add with prev. sum, res = -7 + 2 - 5
        --------------------
        Simple Example: 2 - 3
        Initially res will have 2,i.e. res = 2
        then store '-' in sign. it will be used when 3 comes. ie. sign = -1
        Now 3 comes => res = res + num*sign
        Return statement: res+num*sign => res = 2 + 3(-1) = 2 - 3 = -1
        """
        num = 0
        sign = 1
        res = 0
        stack = []
        for i in range(len(s)): # iterate characters
            c = s[i]
            
            if c.isdigit(): 
                # parse the consecutive digits. e.g. 23 -> 2 * 10 + 3
                num = num*10 + int(c) 
            
            elif c in '-+': # check for - and +
                # calculate the temporary result before '+' or '-'
                res += num*sign
                # save the new sign
                sign = -1 if c == '-' else 1
                # reset num to 0 for parsing the next operand
                num = 0
            elif c == '(':
                # we need res and sign to save the temporary result within '()'. Reset sign to default 1.
                stack.append(res)
                stack.append(sign)
                res = 0
                sign = 1
            elif c == ')':
                # calculate the result within '()'
                # e.g. 2 -(3 + 4) -> res = 3, num = 4, sign = 1, stack = [2, -]
                res +=sign*num # res = 3 * 1 + 4 = 7
                res *=stack.pop() # res = 7 * (-1) = -7
                res +=stack.pop() # res = -7 + 2 = -5
                num = 0 # reset num to 0
                
        return res + num*sign

    def calculate_recursive(self, s: str) -> int:
        def evaluate(i):
            res, digits, sign = 0, 0, 1

            while i < len(s):
                
                if s[i].isdigit():
                    # parse the operand
                    digits = digits * 10 + int(s[i])
                
                elif s[i] in '+-':
                    # evaluate the subresult before the next operator
                    res += digits * sign

                    # reset digits to 0
                    digits = 0

                    # reset operator sign
                    sign = 1 if s[i] == '+' else -1

                elif s[i] == '(':
                    # evalute the sub results in '()' and return the index of ')'
                    subres, i = evaluate(i+1)

                    # accumulate the result
                    res += subres * sign

                elif s[i] == ')':
                    # evaluate the subresult before ')'
                    res += digits * sign

                    # return the result and index
                    return res, i
                
                i += 1

            return res + digits * sign        

        return evaluate(0)