මම මේකට තව ටිකක් එකතු කරන්නම්. තාම Day 14 කරල නැති අය නම් මේව බලන්නවත් එපා තේරුමක් නෑ. demotivate වෙනව. අනික මේ problem එකට දෙන solution එක පට්ටම complex solution එකක්. interview එකේදි කියනව එච්චර දෙයක් බලාපොරොත්තු උනෙත් නෑ කියල. අඩුම ගානෙ මම වත් try කලේ නෑ. ඒතරමට අමාරුයි. එතකොට මේ
@hancok 10min වලින්හැදුව කියන්නෙ මොකද්ද?
ඒ ප්රශ්නෙ හරියට තේරුම් නොගැනීම. මෙතන අපිට output එක කොහොමහරි ගන්න එක නෙමේ challenge එක. algorithm එකක් ලියල output එක ගන්න එකයි challenge එක. ඒකට මම වෙන ප්රශ්නෙකින් පැහැදිලි කරන්නම්
දැන් අපිට list එකක තියෙන value එකක index එක හොයන්න කියල code challenge එකක් interview එකකදි දෙනව.
example
Python:
search_item = 33
items = [10, 14, 19, 26, 27, 31, 33, 35, 42, 44]
candidateල තුන් දෙනෙක් සහභාගි වෙනව.
1st candidate
@hancok වගේ කෙනා මෙහෙම ලියනව. ලියල කියනව තත්පර 10වත් ගියෙ නෑ කියල.
Python:
print(items.index(search_item))
2nd candidate මෙහෙම algorithm එකක් ලියනව.
Python:
def linear_search(ar, search):
for index in range(len(ar)):
if ar[index] == search:
return index
return 'Trace Error'
print(linear_search(items, search_item))
3rd candidate මෙහෙම algorithm එකක් ලියනව.
Python:
def binary_search(ar, search):
low = 0
high = len(ar) - 1
while True:
# search not found
if high < low:
return 'Trace Error'
mid = low + (high - low) // 2
if ar[mid] == search:
return mid
elif ar[mid] < search:
# upper bound
low = mid + 1
else:
# lower bound
high = mid - 1
print(binary_search(items, search_item))
දැන් interview එක අවසානෙදි තෝරගන්න කවුද. අනිවාර්යෙන්ම candidate 3. ඒකට හේතුව එයා තමා #හොදටම_කරල_තියෙන්නෙ.
එහෙම වෙන්න හේතුව මෙතන ඉල්ලන්නෙ algorithm එකක් මිසක් කොහොමහරි output එක print කරන එක නෙමේ. ඒ නිසා candidate 1
@hancok පයින් ගහල එලවන්නෙ.
2nd, 3rd candidate අතරෙන් 3rd එක්කෙනා හොද වෙන්න හේතුව මොකද්ද? ඒකට Big 'O' notation කියල එකක් තියෙනව. ඒකෙ සරල තේරුම අපි ප්රශ්නයකට විසදුමක් ලබා දීමේදි විසදුම ලැබෙන්න steps කීයක් යනවද කියන එක. ඒ කියන්නෙ ලියපු code lines ගාන නෙමේ. අවාසාන පිලිතුර ලැබෙන්න යන steps ගානයි. worst case scenario (දරුණුම දේ තමා) Big 'O' notation එකෙන් බලන්නෙ.
2nd candidate ලියපු පිලිතුරේ කරන්නෙ list එකේ මුල ඉදන් අගට loop කරල බලනව index value එක search value එකත් එක්ක match වෙනවද කියල match වෙනව නම් index එක return කරනව.
දැන් මේ solution එකේ ප්රශ්නයක් තියෙනව. අපිට දෙන list එක එන්න එන්න ලොකු වැඩි වෙනකොට අපිට ඕනෙ value එක හොයන්න යන කාලය එන්න එන්න වැඩි වෙනව. ලොකු වට ප්රමානයක් ඕනෙ වෙනව. ඒකියන්නෙ ලොකු steps ප්රමානයක් ඕනෙ වෙනව. හිතන්න items 1000ක් තියෙන list එකක 998වෙනි index එකේ තමා අපි හොයන value එක තියෙන්නෙ . දැන් මේ search algorithm එක පාවිච්චි කලොත් loop එක වට 998ක් ගියාම තමා අපිට ඕනෙ index එක return වෙන්නෙ.
Big 'O' notation එක බැලුවොත් O ( N )
https://www.tutorialspoint.com/data_structures_algorithms/linear_search_algorithm.htm
3rd candidate ලියපු පිලිතුරේ කරන්නෙ Divide and conquer approach එක. main problem එක sub problem වලට divide කරගෙන ඒ පොඩි sub problems වෙන වෙනම විසදන එක,
මේ algorithm එකේදි list එකේ මුල ඉදන් අගට බලන්නෙ නෑ. මුලින්ම list එකේ මැද්දෙන් පටන් අරන් search value එක තියෙන්න පුලුවන් පැත්ත හදුනාගෙන ඒ පැත්ත ආයිත් මැද්ද අරන් ඉස්සරහට යන algorithm එකක් තියෙන්නෙ.
Big 'O' notation එක බැලුවොත් O(log n)
https://www.tutorialspoint.com/data_structures_algorithms/binary_search_algorithm.htm
දැන් එතකොට 3rd candidate ගෙ algorithm එක තමා හොදම.
තව search algorithm වර්ග තියෙනව. දැන් තාම course එකේ මුල් දවස් වල ඉන්න අය මේක කියවල demotivate වෙන්න එපා. මේව ටිකක් programming ඇඟට සෙට් උනාම කරල බලන්න ඕනෙ වැඩ. දැන්ම මේව කරන්න ගිහින් මේව නම් බෑ කියල ඔක්කොම අතාරින්න එපා.
දවස් 14 complete අයට try කරල බලන්න හොද මේ වගේ තවත් problem එකක් තමා Largest prime factor problem එක.
https://projecteuler.net/problem=3
example දීල තියෙන 13195 number එකට algorithm code එකක් ලියාගන්න පුලුවන් උනත් අන්තිමට අහන number එකට algorithm එක වැඩ කරන්නෙ නැ කියල ඔයාලටම තේරෙයි. Big 'O' notation