Coding Problems Solved Ep.1

This problem was asked by Microsoft.

Compute the running median of a sequence of numbers. That is, given a stream of numbers, print out the median of the list so far on each new element.

Recall that the median of an even-numbered list is the average of the two middle numbers.

For example, given the sequence [2, 1, 5, 7, 2, 0, 5], your algorithm should print out:

หลังจากที่ผมนั่งอ่านและทำความเข้าใจโจทย์ข้างต้นแล้วผมสรุปตามประเด็น*แนวคิดได้ตามนี้

1. โจทย์ข้อนี้ให้ Input เป็น 2, 1, 5, 7, 2, 0, 5 ตามลำดับ และให้ Output เป็น 2, 1.5, 2, 3.5, 2, 2,2 ตามลำดับ อีกเช่นกัน
2. ให้หา median เอ๊ย! แล้วไอ้ median มันคืออะไร ? นี้คำถามแรกที่เกิดขึ้นมากับผมเพราะผมไม่เข้าใจ
3. ผมจึงนำ keyword ตัวนี้ไปหาข้อมูลต่อที่อาจารย์ Google เลยได้ถึงบางอ้อว่ามันคือ "มัธยฐาน"
4. หลังจากศึกษา theory of median เสร็จ ผมก็เลยเข้าใจวิธีแก้ปัญหาครับ
5. หลังจากไม่สงสัยอะไรแล้ว เราก็มาเริ่ม coding กันเลย

*อ้างอิงแนวคิดของผมที่ใช้แก้โจทย์หากใครจำไม่ได้กด "ตรงนี้ๆ"

สุดท้ายใครมีวิธีที่ล้ำลึก หรือ วิธีใหม่ๆ แนะนำกันมาได้ครับ ผมแก้ปัญหาได้ด้วยวิธี basic เท่านั้นเอง