search

vietnamese-engineer-in-japan / workshop

All information related to workshop
3 stars 0 forks source link

Workshop - Data structures and algorithms #day1 #2

Open chunvv opened 5 years ago

chunvv commented 5 years ago

Informations:

Contents:

Details:

chunvv commented 5 years ago

Rules:

chunvv commented 5 years ago

Pre-preparation:

chunvv commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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.

image

chunvv commented 5 years ago

Test 6: BFS/DFS

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

chunvv commented 5 years ago

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 commented 5 years ago

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

image

chunvv commented 5 years ago

Prefix Sums

Test 9: PassingCars

Screen Shot 2019-04-27 at 23 44 15
chunvv commented 5 years ago

Test 10: GenomicRangeQuery

Screen Shot 2019-04-27 at 23 44 40
chunvv commented 5 years ago

Test 11: MinAvgTwoSlice

Screen Shot 2019-04-27 at 23 44 52
chunvv commented 5 years ago

Test 12: CountDiv

Screen Shot 2019-04-27 at 23 45 00
chunvv commented 5 years ago

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

image

chunvv commented 5 years ago

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 commented 5 years ago

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.

image

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 commented 5 years ago

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

image