Problem

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Examples

1
2
3
4
5

Input: 1->2->3->3->4->4->5
Output: 1->2->5

Input: 1->1->1->2->3
Output: 2->3

Problem

Given a sorted linked list, delete all duplicates such that each element appear only once.

Examples

1
2
3
4
5

Input: 1->1->2
Output: 1->2

Input: 1->1->2->3->3
Output: 1->2->3

Problem

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.

Examples

1
2
3
4
5
6
7
8
9

Examples:
Input: S = "a1b2"
Output: ["a1b2", "a1B2", "A1b2", "A1B2"]

Input: S = "3z4"
Output: ["3z4", "3Z4"]

Input: S = "12345"
Output: ["12345"]

Problem

Given a collection of distinct integers, return all possible permutations.

Example

1
2
3
4
5
6
7
8
9
10

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

Algorithm

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

from combinatorial_search import Backtracking

class Subsets(Backtracking):
    def is_a_solution(self, current_answer, kth, info):
        return kth == len(info)

    def process_solution(self, current_answer, kth, info):
        print([info[idx] for idx, val in enumerate(current_answer) if val])

    def generate_candidates(self, current_answer, kth, info):
        return [True, False]

    def all_subsets(self, info):
        self.backtrack([], 0, info)

# test case
Subsets().all_subsets([1,2,3]))

Algorithm

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

from combinatorial_search import Backtracking

class Permutation(Backtracking):
    def is_a_solution(self, current_answer, kth, info):
        return kth == len(info)

    def generate_candidates(self, current_answer, kth, info):
        return [candidate for candidate in info if candidate not in current_answer]

    def process_solution(self, current_answer, kth, info):
        print(current_answer)

    def permute(self, info):
        self.backtrack([], 0, info)

# test case
Permutation().permute([1,2,3])

Reference

• https://en.wikipedia.org/wiki/Permutation

Problem

Consider a rat placed at (0, 0) in a square matrix m[][] of order n and has to reach the destination at (n-1, n-1). Your task is to complete the function which returns a sorted array of strings denoting all the possible directions which the rat can take to reach the destination at (n-1, n-1). The directions in which the rat can move are ‘U’(up), ‘D’(down), ‘L’ (left), ‘R’ (right).

Read more »

What is Backtracking?

• It is a systematic way to iterate through all the possible configurations of a search space.
• It is a general algorithm which must be customized for each application.
• It is really just depth-first search on an implicit graph of configurations.
  • Can easily be used to iterate through all subsets or permutations of a set.
  • Ensures correctness by enumerating all possibilities.
  • For backtracking to be efficient, we must prune dead or redundent branches of the search space whenever possible.

Base_URL:

https://www.yelp.com/search?

Parameters:

• open_time:

  (day_of_the_week - 1) 24 60 + minute_of_the_day, where day_of_the_week starts from Monday

  e.g.

  • open at 8:00 pm, Mon => open_time= 1200 (0 24 60 + 20 * 60)
  • open at 8:00 pm, Tue => open_time= 2640 (1 24 60 + 20 * 60)
  • open at 8:00 pm, Wed => open_time= 4080 (2 24 60 + 20 * 60)

Problem

Given two strings str1 and str2 and below operations that can performed on str1. Find minimum number of edits (operations) required to convert ‘str1’ into ‘str2’.

1. Insert
2. Remove
3. Replace

All of the above operations are of equal cost.

Example

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

Input:   str1 = "geek", str2 = "gesek"
Output:  1
We can convert str1 into str2 by inserting a 's'.

Input:   str1 = "cat", str2 = "cut"
Output:  1
We can convert str1 into str2 by replacing 'a' with 'u'.

Input:   str1 = "sunday", str2 = "saturday"
Output:  3
Last three and first characters are same.  We basically
need to convert "un" to "atur".  This can be done using
below three operations. 
Replace 'n' with 'r', insert t, insert a