Not long ago, I spent a month learning the basics on how algorithms and data structures work and their practical use in our daily programming lives for a recent job application for one of the top software companies down under.
In the first place, I never truly appreciate how and why they are important to learn. After working with some startups, agencies and consulting firms for several years, a lot of things I did in my previous work never once find one or two things that data structures and algorithms would come in handy when solving difficult business problems. The mere thought of having to know them is nothing more but boring computer science fundamentals which bear no relevance in today’s modern computing age where technologies are evolving at rapid pace. With today’s computers’ raw computing power such as CPU, memory and speed took care by technology vendors that make such great advances, we never need to worry about making optimizations in our code.
Rightly so, we don’t need to care how efficiency in our programs are maintained. We just need to go away and focus truly solving more interesting problems in the projects. Thus I never bother learning (nor believing in) their value other than just being an academic material for people wishing to showcase their “smart” coding skills, who has no true work experience in solving difficult real-life problems. They spend their free time daily on platforms like HackerRank, LeetCode or Codility - just to see how far they can get in advancing their coding ranks.
Henceforth, I felt disconcerted or unconvinced with them… until now.
I came about to my epiphany when I stumbled on this page a few years ago. It’s really refreshing to read up the author of the original post, how as a self-taught successful elite programmer who’s done programming for over 20 years has built himself an impressive technology portfolio of writing complex systems such as machine learning, robotics and AI learning. Such an example of an individual who appreciates the art of crafting good software systems has won my awe and respect for his continuous learning of this field.
As I share the same firm beliefs in building software systems as he does, thus I also feel drawn to convince myself the ongoing value of having algorithms and data structures as part of your repertoire as a confident programmer.
So let’s get acquainted with them, shall we?
##Algorithms
Let’s start off with a few basic algorithms we need to familiarise ourselves.
###a) Strings
Strings are one of the core concepts every programmer of all levels should intimately know very well, by heart. We, practically use them every day in our projects, thus it’s not different why we’re often asked to do some string manipulation something like this.
####Java
Delete any pair of adjacent letters in a given string valuelinkimport java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner stdin = new Scanner(System.in);
StringBuffer s = new StringBuffer(stdin.nextLine());
for(int i = 1; i < s.length(); i++) {
if(s.charAt(i) == s.charAt(i-1)) {
s.delete(i-1, i+1);
i = 0;
}
}
if(s.length() == 0) System.out.println("Empty String");
else System.out.println(s);
}
}
####Python
import re
s, regex = raw_input().strip(), re.compile('r(\w)(\1)')
match = regex.search(s)
while match:
s = s.replace(match.group(), '')
match = regex.search(s)
print s if s else 'Empty String'####Ruby
s = gets.strip
s.gsub!($~.to_s, '') while s.match(%r((\w)(\1)))
puts s.empty ? 'Empty String' : s####Javascript
var arr = readline().split('');
for (var i = 0; i < arr.length; i++) {
if(arr[i] === arr[i + 1]) {
arr.splice(i, 2);
i = -1;
}
}
if(arr.length === 0) {
console.log('Empty String');
} else {
console.log(arr.join(''));
}####C++
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
char string[101];
scanf("%s",string);
char *stack=(char *)malloc(sizeof(char)*strlen(string));
int top=-1;
for(int i=0;i<strlen(string);i++){
if(i==0)
stack[++top]=string[i];
else
{
if(stack[top]==string[i])
top--;
else
stack[++top]=string[i];
}
}
if(top==-1)
printf("Empty String");
else {
for(int i=0;i<=top;i++)
printf("%c",stack[i]);
}
return 0;
}####PHP
$_fp = fopen("php://stdin", "r");
$str = trim(fgets($_fp));
$str = str_split($str);
function removeAdjacent($s, $len)
{
$j = 0;
for ($i = 1; $i < $len; $i++) {
while (($j >= 0) && $i < $len && $s[$i] == $s[$j]) {
$i++;
$j--;
}
if ($i < $len) {
$s[++$j] = $s[$i];
}
}
$uniqChar = [];
for ($k = 0; $k <= $j; $k++) {
$uniqChar[$k] = $s[$k];
}
return $uniqChar;
}
$str = removeAdjacent($str, count($str));
if (count($str)) {
echo implode('', $str);
} else {
echo 'Empty String';
}###b) Sorting algorithm
As with manipulating strings data (any type of data for that matter), we also work with organising data in some particular order. It can be either in alphabetical, numerical, descending or ascending order. Thus when we deal with large datasets of information, we always do need to find efficient ways of sorting them while at the same time storing them in a general-purpose data structure such as arrays. We can do general sorting like this one.
####Java
Sort the unsorted array's elements in an ascending order using bubble sortlinkpublic class Solution {
public static int bubbleSort(int[] arr) {
int totalSwaps = 0;
for(int i = 0; i < arr.length; i++) {
for(int j = 0; j < arr.length - 1; j++) {
if(arr[j] > arr[j + 1]){
//System.out.println("swapping");
swap(arr, j, j + 1);
totalSwaps++;
}
}
if(totalSwaps == 0) {
break;
}
}
return totalSwaps;
}
public static void swap(int [] arr, int current_index, int next_index){
int temp = 0;
temp = arr[current_index];
arr[current_index] = arr[next_index];
arr[next_index] = temp;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int a[] = new int[n];
for(int a_i=0; a_i < n; a_i++){
a[a_i] = in.nextInt();
}
int totalSwaps = 0;
totalSwaps = bubbleSort(a);
System.out.println("Array is sorted in " + totalSwaps + " swaps.");
System.out.println("First Element: " + a[0]);
System.out.println("Last Element: " + a[a.length - 1]);
}
}
####Python
def bubble_sort(numList):
numSwaps = 0
sortList = numList
def check(lst):
return sorted(lst) == lst
while not check(sortList):
for i in range(len(numList)-1):
if sortList[i] > sortList[i+1]:
sortList[i], sortList[i+1] = sortList[i+1], sortList[i]
numSwaps += 1
print('Array is sorted in {} swaps.'.format(numSwaps))
print('First Element: {}'.format(sortList[0]))
print('Last Element: {}'.format(sortList[-1]))####Ruby
n = gets.strip.to_i
a = gets.strip
a = a.split(' ').map(&:to_i)
swaps = 0
loop do
swapped = false
(a.length - 1).times do |i|
if a[i] > a[i+1]
a[i], a[i+1] = a[i+1], a[i]
swaps +=1
swapped = true
end
end
break if not swapped
end
puts "Array is sorted in #{swaps} swaps."
puts "First Element: #{a.first}"
puts "Last Element: #{a.last}"####Javascript
function main() {
var n = parseInt(readLine()); a = readLine().split(' '); a = a.map(Number);
var unsorted = false;
var numberOfSwaps = 0;
for(var i = 0 ; i < n- 1; i++) {
for(var j = 0; j < n - i; j++ ) {
if (a[j] > a[j+1]) {
swap(a, j);
}
}
if(!unsorted) {
break;
}
}
function swap(l, i) {
unsorted = true;
var temp = l[i];
l[i] = l[i + 1];
l[i + 1] = temp;
numberOfSwaps ++;
}
var firstElement = a[0];
var lastElement = a[n-1];
process.stdout.write("\nArray is sorted in " + numberOfSwaps +" swaps.\nFirst Element: " + firstElement + "\nLast Element: " + lastElement);
}
####C++
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int main(){
int n;
scanf("%d",&n);
int *a = (int *)malloc(sizeof(int) * n);
for(int a_i = 0; a_i < n; a_i++){
scanf("%d",&a[a_i]);
}
int totalNumOfSwaps = 0;
for(int i=0; i<n; i++) {
int numOfSwaps = 0;
for(int j=0; j<n-1; j++) {
if(a[j] > a[j+1]) {
swap(&a[j], &a[j+1]);
numOfSwaps++;
}
}
totalNumOfSwaps += numOfSwaps;
if(numOfSwaps == 0) {
break;
}
}
printf("Array is sorted in %d swaps.\n", totalNumOfSwaps);
printf("First Element: %d\n", a[0]);
printf("Last Element: %d\n", a[n-1]);
free(a);
return 0;
}####PHP
$handle = fopen ("php://stdin","r");
fscanf($handle,"%d",$n);
$a_temp = fgets($handle);
$a = explode(" ",$a_temp);
array_walk($a,'intval');
$count = bubble_sort($a);
$last_idx = count( $a ) - 1;
echo "Array is sorted in $count swaps. \n";
echo "First Element: {$a[0]}\n";
echo "Last Element: {$a[$last_idx]}\n";
function bubble_sort( &$array ) {
static $count = 0;
for ( $i = 0; $i < count( $array ); $i++ ) {
if ( isset( $array[$i + 1] ) ) {
if ( $array[$i] > $array[$i + 1] ) {
swap( $array, $i, $i +1 );
$count += 1;
bubble_sort( $array );
}
}
}
return $count;
}
function swap( &$array, $index1, $index2 ) {
$copy = $array[$index1];
$array[$index1] = $array[$index2];
$array[$index2] = $copy;
}###c) Searching algorithm
Again, when working with data structures, you’re dealing not only with sorting out homogeneous data, but you also want to be able to search or look up items based on search criteria you set aside. And, usually, this searching task needs to be done in the most optimal speed as possible, as searching for a needle in a very, very, very large haystack could take a very long time if you’re not careful with its implementation details… You should work on simple search algorithm problems using known techniques of binary search algorithm to write the following.
####Java
- Find the two disctinct ice cream flavours they could spend the money on ice cream parlourslinkimport java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
class IceCream implements Comparable<IceCream> {
int flavour;
int index;
public IceCream(int flavour, int index) {
this.flavour = flavour;
this.index = index;
}
public int compareInt(int num) {
return (int)(this.flavour - num);
}
@Override
public int compareTo(IceCream obj) {
return (int)(this.flavour - obj.flavour);
}
@Override
public boolean equals(Object obj) {
return (this.flavour == (int)obj ? true: false);
}
}
public class Solution {
private static int binarySearch(int first, int last, IceCream[] array, int search){
if(first <= last) {
int mid = (int)(first+last)/2;
if(array[mid].equals(search)) {return array[mid].index;}
if(array[mid].compareInt(search) > 0) {
return binarySearch(first, mid - 1, array, search);
} else {
return binarySearch(mid + 1, last, array, search);
}
}
else if( first == last && array[first].equals(search)){
return array[first].index;
}
else return - 1;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
for(int a0 = 0; a0 < t; a0++){
int m = in.nextInt();
int n = in.nextInt();
IceCream [] ic_array = new IceCream [n];
for(int i = 0; i < n; i++) {
ic_array[i] = new IceCream (in.nextInt(), i + 1);
}
Arrays.sort(ic_array);
int firstIndex = 100000, secondIndex = 100000;
for(int i = 0; i < n - 1 ; i++) {
int search = m - ic_array[i].flavour;
if(search >= ic_array[i].flavour) {
int index = binarySearch( i + 1, n - 1, ic_array, search);
if( index != -1 ) {
System.out.println( Math.min(ic_array[i].index, index) + " " + Math.max(ic_array[i].index, index));
break;
}
}
}
}
}
}
####Python
t = int(raw_input().strip())
for a0 in xrange(t):
m = int(raw_input().strip())
n = int(raw_input().strip())
a = map(int, raw_input().strip().split(' '))
# find matched number
cost_map = {}
for i, cost in enumerate(a):
sunny = cost
johnny = m - cost
if johnny in cost_map.keys():
print cost_map[johnny]+1, i+1
else:
cost_map[cost] = i
####Ruby
inputs = gets.chomp.to_i
inputs.times do
m = gets.chomp.to_i
n = gets.chomp.to_i
flavors gets.chomp.split.map { |e| e.to_i}
for i in 0...flavors.length - 1 do
for j in i + 1...flavors.length do
puts "#{i + 1} #{j + 1}" if flavors[i] + flavors[j] == m
end
end
end####Javascript
'use strict'
const processData = input => {
let lines = input.split("\n");
let tests = parseInt(lines[0]);
let index = 1;
for(let i = 0; i < tests; i++) {
let amount = parseInt(lines[index++]);
let length = parseInt(lines[index++]);
let costs = lines[index++].split(" ").map(i => parseInt(i));
let indexes = [];
for(let j = 0; j < length - 1; j++) {
for(let k = j + 1; k < length; k++) {
if(costs[j] + costs[k] === amount){
indexes.push(j + 1);
indexes.push(k + 1);
}
}
}
console.log(indexes.join(" "));
}
};
process.stdin.resume();
process.stdin.setEncoding("ascii");
let _input = "";
process.stdin.on("data", input => _input += input);
process.stdin.on("end", () => processData(_input));
####C++
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
void print(vector<int>v) {
for (int i = 0; i < v.size();i++) {
cout << v[i] << " ";
}
cout << endl;
}
vector<int> binSearch(vector<int>v, int m) {
map<int, int>mp; int ind1, ind2;
vector<int>out(2);
for (int i = 0; i < v.size();i++) {
if (mp.find(m-v[i])==mp.end()) {
mp[v[i]] = i + 1;
}
else {
ind1 = mp[m-v[i]];
ind2 = i + 1;
break;
}
}
out[0] = ind1;
out[1] = ind2;
return out;
}
int main()
{
int t;
cin >> t;
while (t-->0) {
int m;
cin >> m;
int n;
cin >> n;
vector<int>v;
for (int i = 0; i < n;i++) {
int num;
cin >> num;
v.push_back(num);
}
auto out = binSearch(v, m);
print(out);
}
system("pause");
return 0;
}
####PHP
<?php
$handle = fopen ("php://stdin","r");
fscanf($handle,"%d",$t);
for($a0 = 0; $a0 < $t; $a0++){
fscanf($handle,"%d",$m);
fscanf($handle,"%d",$n);
$a_temp = fgets($handle);
$a = explode(" ",$a_temp);
array_walk($a,'intval');
binaryIceCream($a, $m, 0, count($a)-1);
}
function binaryIceCream($array, $cost, $start, $end){
for($i=0; $i<count($array); $i++){
$first = $array[$i];
$second = $cost - $first;
if($second <=0) continue;
if($i>0){
$left = unsortedSearch($array, $second, 0, $i-1);
if($left!=null){
echo $i+1;
echo " ";
echo $left+1;
echo "\n";
return;
}
}
if($i<count($array)){
$right = unsortedSearch($array, $second, $i+1, count($array)-1);
if($right!=null){
echo $i+1;
echo " ";
echo $right+1;
echo "\n";
return;
}
}
}
}
function unsortedSearch($array, $value, $start, $end){
if($start>$end) return null;
$middle = ($end+$start) >> 1;
if(!isset($array[$middle])) return null;
if($value == $array[$middle]){
return $middle;
}
else{
$left = unsortedSearch($array, $value, $start, $middle-1);
if($left!=null) return $left;
$right = unsortedSearch($array, $value, $middle+1, $end);
if($right!=null) return $right;
}
return null;
}
?>
From the above examples, you can choose any language to write up simple algorithms when you first start off.
In my upcoming post, I’m going to lay out the basic and common data structures we ought to know, by heart. This includes stuff on arrays(again), linked lists, queues, trees and so on.
Stay tuned (and happy coding)!