Workshop - Data structures and algorithms #day1

[chunvv]

Informations:

• Joiners: Trung Vu, Son Tran, Manh Nguyen, Long Tran, Khanh Tran
• Location: Meguro, Japan
• Time: 2019/04/30

Contents:

• Arrays/Strings
• Trees
• Prefix Sums
• Backtracking

Details:

• Arrays/Strings

  • Determine if a string is a palindrome
  • Merge two sorted arrays
  • Find substring
  • Find all duplicates in an array

• Trees

  • Check if tree is balancedCheck if tree is balanced
  • BFS/DFS
  • All traversals, recursive and iterative implementations
  • Find max path sum in the tree, negative nodes possible

• Prefix Sums

  • PassingCars
  • GenomicRangeQuery
  • MinAvgTwoSlice
  • CountDiv

• Backtracking

  • Find all permutations or combinations
  • Find all possible subsets
  • N queens problem
  • Convert numbers into words according to letters on an old phone keypad

[chunvv]

Rules:

• Keep all devices in silent mode.
• Don't eat/drink on my bed, sitting/lying is ok.
• Don't leave any trash on the floor. (I always have to clean my house after the seminar/workshop)
• On time: starting time, researching time and discussing time
• Share all your knowledge
• Don't disturb presenters/discussion

[chunvv]

Pre-preparation:

• Arrays/Strings: (5m)

  • Advantages of arrays/string: time complexity of: insert, get, update, delete
  • When we should use arrays/string?
  • Why in some cases, we should use arrays instead of LinkedList?
  • About immutable?

• Trees:(10m)

  • Advantages of tree: time complexity of: insert, get, update, delete
  • When we should use arrays/string?
  • About immutable?
  • List up all types of tree: balance, binary tree
  • List up all advantages of these trees
  • About immutable?

• Prefix Sums: (10m)

  • What is prefix sums problem?
  • When we should use prefix sums solution?
  • Time and space complexity?

• Backtranking:(10m)

  • What is backtracking alg?
  • When we should use prefix sums solution?
  • Time and space complexity?

[chunvv]

Arrays/Strings

Test 1. Determine if a string is a palindrome

Given a string, write a python function to check if it is palindrome or not. A string is said to be palindrome if reverse of the string is same as string. For example, “radar” is palindrome, but “radix” is not palindrome.

Examples:

Input : malayalam
Output : Yes

Input : geeks
Output : No

[chunvv]

Test 2. Merge two sorted arrays

We are given two sorted array. We need to merge these two arrays such that the initial numbers (after complete sorting) are in the first array and the remaining numbers are in the second array. Extra space allowed in O(1).

Example:

Input: ar1[] = {10};
ar2[] = {2, 3};
Output: ar1[] = {2}
ar2[] = {3, 10}

Input: ar1[] = {1, 5, 9, 10, 15, 20};
ar2[] = {2, 3, 8, 13};
Output: ar1[] = {1, 2, 3, 5, 8, 9}
ar2[] = {10, 13, 15, 20}

[chunvv]

Test 3. Find substring
Given two strings s1 and s2, find if s1 is substring of s2. If yes, return index of first occurrence, else return -1.

Examples :

Input : s1 = "for", s2 = "geeksforgeeks"
Output : 5
String "for" is present as a substring
of s2.

Input : s1 = "practice", s2 = "geeksforgeeks"
Output : -1.

[chunvv]

Test 4: Find all duplicates in an array

You are given an array of n+2 elements. All elements of the array are in range 1 to n. And all elements occur once except two numbers which occur twice. Find the two repeating numbers.
For example, array = {4, 2, 4, 5, 2, 3, 1} and n = 5

The above array has n + 2 = 7 elements with all elements occurring once except 2 and 4 which occur twice. So the output should be 4 2.

[chunvv]

Trees

Test 5: Check if tree is balanced

A tree where no leaf is much farther away from the root than any other leaf. Different balancing schemes allow different definitions of “much farther” and different amounts of work to keep them balanced.
Consider a height-balancing scheme where following conditions should be checked to determine if a binary tree is balanced.
An empty tree is height-balanced. A non-empty binary tree T is balanced if:

1. Left subtree of T is balanced
2. Right subtree of T is balanced
3. The difference between heights of left subtree and right subtree is not more than 1.

The above height-balancing scheme is used in AVL trees. The diagram below shows two trees, one of them is height-balanced and other is not. The second tree is not height-balanced because height of left subtree is 2 more than height of right subtree.

[chunvv]

Test 6: BFS/DFS

Understanding of:
https://www.geeksforgeeks.org/bfs-vs-dfs-binary-tree/

[chunvv]

Test 7: All traversals, recursive and iterative implementations

Using Stack is the obvious way to traverse tree without recursion. Below is an algorithm for traversing binary tree using stack. See this for step wise step execution of the algorithm.

1. Create an empty stack S.
2. Initialize current node as root
3. Push the current node to S and set current = current->left until current is NULL
4. If current is NULL and stack is not empty then
   a) Pop the top item from stack.
   b) Print the popped item, set current = popped_item->right
   c) Go to step 3.
5. If current is NULL and stack is empty then we are done.

[chunvv]

Test 8: Find max path sum in the tree, negative nodes possible

Given a binary tree, find the maximum path sum. The path may start and end at any node in the tree.

Example:

Input: Root of below tree
1
/
2 3
Output: 6

See below diagram for another example.
1+2+3

[chunvv]

Prefix Sums

Test 9: PassingCars

[chunvv]

Test 10: GenomicRangeQuery

[chunvv]

Test 11: MinAvgTwoSlice

[chunvv]

Test 12: CountDiv

[chunvv]

Backtracking

Test 13: Find all permutations or combinations

A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself. A string of length n has n! permutation.
Source: Mathword(http://mathworld.wolfram.com/Permutation.html)

Below are the permutations of string ABC.
ABC ACB BAC BCA CBA CAB

[chunvv]

Test 14: Find all possible subsets

Problem: Find all the subsets of a given set.

Input:
S = {a, b, c, d}
Output:
{}, {a} , {b}, {c}, {d}, {a,b}, {a,c},
{a,d}, {b,c}, {b,d}, {c,d}, {a,b,c},
{a,b,d}, {a,c,d}, {b,c,d}, {a,b,c,d}

[chunvv]

Test 15: N queens problem

We have discussed Knight’s tour and Rat in a Maze problems in Set 1 and Set 2 respectively. Let us discuss N Queen as another example problem that can be solved using Backtracking.
The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other. For example, following is a solution for 4 Queen problem.

The expected output is a binary matrix which has 1s for the blocks where queens are placed. For example, following is the output matrix for above 4 queen solution.

          { 0,  1,  0,  0}
          { 0,  0,  0,  1}
          { 1,  0,  0,  0}
          { 0,  0,  1,  0}

[chunvv]

Test 16: Convert numbers into words according to letters on an old phone keypad

Before advent of QWERTY keyboards, texts and numbers were placed on the same key. For example 2 has “ABC” if we wanted to write anything starting with ‘A’ we need to type key 2 once. If we wanted to type ‘B’, press key 2 twice and thrice for typing ‘C’. below is picture of such keypad.

Mobile-keypad

Given a keypad as shown in diagram, and a n digit number, list all words which are possible by pressing these numbers.
For example if input number is 234, possible words which can be formed are (Alphabetical order):
adg adh adi aeg aeh aei afg afh afi bdg bdh bdi beg beh bei bfg bfh bfi cdg cdh cdi ceg ceh cei cfg cfh cfi