Workshop - Data structures and algorithms #day2

[chunvv]

Informations:

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

Contents:

• Linked List
• Hashtables
• Divide and Conquer
• Maximum slice problem
• Leader

Details: Exs:

• Linked List:

  • Reverse a singly linked list
  • Delete/Insert a node in a linked list
  • Detect if there is a cycle in the list and return its starting point
  • Merge two sorted lists
  • Split a list into two lists one has even indexes other has odd indexes

• Hashtables:

  • Questions where you need to keep track of multiple occurences of same object
  • Questions where you want to have a 2 tuple as a key

• Divide and Conquer

  • Binary Search
  • Merge Sort
  • Quick Sort
  • Maximum Subarray Sum
  • MinMaxDivision
  • NailingPlanks

• Maximum slice problem

  • MaxProfit
  • MaxSliceSum
  • MaxDoubleSliceSum

• Leader

  • Dominator
  • EquiLeader

[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:

• Linked List: (5m)

  • Advantages of arrays/string: Time complexity of: space ,prepend ,append ,lookup ,insert ,delete
  • Strengths: ?
  • Weekness: ?
  • Uses: ?

• Hashtable: (5m)

  • Advantages of arrays/string: Time complexity of: space ,prepend ,append ,lookup ,insert ,delete
  • Strengths: ?
  • Weekness: ?
  • What is Hash collisions
  • When hash table operations cost O(n)O(n) time?
  • Dynamic array resizing

[chunvv]

Documents:

LinkedList:

Hashtable:

[chunvv]

LinkedList:

Test 1: Reverse a singly linked list Given pointer to the head node of a linked list, the task is to reverse the linked list. We need to reverse the list by changing links between nodes.

Examples:

Input : Head of following linked list
1->2->3->4->NULL Output : Linked list should be changed to, 4->3->2->1->NULL

Input : Head of following linked list
1->2->3->4->5->NULL Output : Linked list should be changed to, 5->4->3->2->1->NULL

Input : NULL Output : NULL

Input : 1->NULL Output : 1->NULL

[chunvv]

Test 2: Detect if there is a cycle in the list and return its starting point

[chunvv]

Hashtables

Test 3: Questions where you need to keep track of multiple occurences of same object

[chunvv]

Test 4: Questions where you want to have a 2 tuple as a key

[chunvv]

Divide and Conquer

Test 5: Binary Search

[chunvv]

Test 6: Merge Sort

[chunvv]

Test 7: Maximum Subarray Sum

You are given a one dimensional array that may contain both positive and negative integers, find the sum of contiguous subarray of numbers which has the largest sum. For example, if the given array is {-2, -5, 6, -2, -3, 1, 5, -6}, then the maximum subarray sum is 7 (see highlighted elements).

[chunvv]

Test 8: MinMaxDivision

[chunvv]

Test 9: NailingPlanks

[chunvv]

Maximum slice problem

Test 10: MaxProfit

[chunvv]

Test 11: MaxSliceSum

[chunvv]

Test 12: MaxDoubleSliceSum

[chunvv]

Leader

Test 13: Dominator

[chunvv]

Test 14: EquiLeader