Rust - Simple graphs algorithms
Graphs (and trees - their special case) are data structures used in modeling complex problems such as finding an optimal route, exploring possible moves in a game, caching engines, modeling relations and more . That’s why they are very often the fundament of software engineer interview tasks in big companies - FAANG. Let’s implement some basic graph algorithms in Rust.
Rust - single ownership and self reference
Rust is a great programming language that achieves memory safety by forcing a single ownership model and borrow-checker mechanism.
That is actually problematic for data structures that require referencing Self type e.g. graphs, trees, and double-linked lists.
So it is impossible in Rust to express this:
Rust - Copy vs Clone vs Dupe
One of the features I love in Rust is very explicit copying.
Every potentially expensive copy (clone) is clearly visible and can be easily caught during code review even though a small piece of code has been changed.
That is probably one of the biggest advantages of Rust over C++.
Nevertheless, more experienced Rust programmers know that it is not always easy to judge if some clone is expensive or not.
In this article, I would like to present Facebook’s solution for that problem - Dupe trait from Gazeebo crate
.
Carbon instead of Rust? Which is the true successor of C++
Carbon, a new programming language by Google that was announced at CppNorth 2022 conference as part of the presentation “Carbon Language: An experimental successor to C++” by Chandler Carruth on July 22nd 2022 (link ). The news spread quickly over the Internet and a few friends reach out to me to ask about my opinion about it and if Rust is going to die because of the appearance of a new baby of a big player in this industry. Well, Rust is doing fine and I will summarize my thoughts about Rust, Carbon, and modern C++ (C++20 standard as of today).
Rust and Cpp interoperability
I’m a huge Rust enthusiast and you can read more about it in my previous article . Today, I’m gonna show you 2 examples of how Rust can be used together with some existing C and C++ codebases. Rust was designed with its FFI (Foreign Function Interface) in mind so it allows cheap (or even zero cost) interoperability with C and C++. For both solutions (plain C and C++), I’ll demonstrate that we can call C/C++ and Rust code back and forth (pass Rust callback to C++ code). I’ll focus on performance, flexibility, and limitations too.
Ubuntu - Missing Realtek Network Driver
Recently, I had the pleasure challenge to install Ubuntu on a new laptop.
After installation, I noticed that there is no WiFi option available.
Farther diagnosis with ifconfig showed that there was no network card supporting wifi.
Moreover, the laptop was “too new” to have an old-school Ethernet socket…
Flashback
A few years ago I had a similar problem. In short, the company I joined bought me the perfect new Dell laptop. The problem was that they told me to install an older Ubuntu LTS that didn’t have a WiFi driver for such new hardware. Fortunately, I also had an Ethernet socket so I could work in the old school way. Later, I downloaded the new driver’s source code and compiled it so eventually, I could use WiFi too. The problem never appeared again once I updated to newer Ubuntu LTE with a much newer kernel.
Why Rust
Usually, I’m skeptical about new technologies and programming languages. I take every novelty with a pinch of salt. Not because of the steep learning curve and lack of time but because I saw too many examples where promises were not delivered. The majority of the new technologies provided only minor improvements which were not really worth migration time.
When I heard about Rust for the first time, my feelings were the same: if you need strongly typed high-performance native language without GC, why not just modern C++11 (or newer) instead of a new language? Is it really worth creating a new language instead of providing a C++ library that can be added to existing projects? A few months ago, I finally dived deeper into Rust and started writing some code in it. Rust extremely positively surprised me and become my choice for high-performance applications. In this article, I would like to present to you my take on why Rust.
11 psychological traps in software engineering
There are certain common behavioral patterns and effects that you can observe while working with people. Knowledge of them helps me to advocate their behavior, avoid many mental mistakes, and make better decisions. Some of those psychological traps and patterns are especially noticeable in software engineering. Today, I would like to explain to you my top 11 psychological traps.
Dunning–Kruger effect
Let’s start with my favorite one. This effect was identified by 2 American social psychologists and professors David Dunning and Justin Kruger in 1999. It basically says that people with low abilities (low knowledge about something or who just started exploring some area) have a tendency to have high self-confidence and to believe that their skills/knowledge are much better than it really is (illusory superiority). On the other hand, people with mid ability have a tendency to low self-confidence and to underestimate their real knowledge. People with really high abilities start getting more self-confidence but they rarely reach the imaginary confidence of people with low skills.
How the type error cost NASA $ 327 million
On December 11, 1998, NASA launched the Mars Climate Orbiter - robotic space probe designed to explore Martian climate from orbit and also to act as a communications relay for polar lander sent 2 months later. Nobody expected that after 9 months journey it will crash in the atmosphere from such simple software mistake.
Hard problems in NASA scale
NASA puts a lot of effort into reliability. A lot of things can happen in space that we do not observe so often (or never) on Earth e.g.:
System Design Interview 2: News feed like Twitter
In previous article , I show you how to design a URL shortener service. I presented the basics of capacity planning, collecting requirements, DB sharding, etc. Now, I would like to cover another interesting system design interview question - How would you design Twitter?
Requirements and capacity planning
We want a system that allows a user to share short text messages (posts). Those messages will be displayed in 2 places:
- on user board
- on home board
User’s X board displays posts that user X published. Every logged-in user Y has also their own private home board. Home board displays posts of users subscribed by user Y.
How to free some disk space
I’m a Linux guy. That’s my favorite software development environment. I love its minimalism, and I’m delighted with my low resource usage Xubuntu distribution. Unfortunately, Linux partition needs to share my Yoga 500GB SSD drive with Windows 10 so I can play some games from time to time. Yes, on the integrated Intel UHD620 graphic (Intel i5-8250U CPU) but that’s a different story about portable laptop tradeoffs. I ended up with a 30GB Linux partition to preserve some space for games on Windows partition. Recently, I’ve noticed that disk space is running out on the Linux partition. How to clean it up?
duf - modern disk usage tool
In the past articles, I share with you modern Linux commands I use every day like htop, fd
or exa
.
Recently, I discovered a new cool Linux tool that I was seeking for a long!
duf - simple df and du
duf is Disk Usage/Free utility tool that combines old-shool du and df commands.
You can just type duf or specify mount point or device.
I especially love to just use current dir dif . to check how much free disk space do I have on this partition.
duf also provides rich filtering options and information about inodes utilization duf --inodes which might be useful if you use symbolic and hard links often.
DynamoDB design
In previous article , I explained you how to create a service like TinyURL. That kind of service requires storing a lot of data what implies sharding this data across multiple DB instances. I showed a really simple algorithm of how data could be distributed in that case and briefly mention something about replication. Now the question is what would we do in real life?
Real-life distribtued DB
Using existing NoSQL solution would be a good choice as they already solve main problems with distributed DB systems:
System Design Interview 1: URL shortener like TinyURL
A URL shortener is one of the most famous system design interview questions. In my opinion, it is also the most essential one from a scalability perspective and that is why global companies like the famous FAANG ask about it. Let’s go through it like during an interview to show you how you can structure this discussion.
There is no perfect system
Remember, there is no silver bullet to design the perfect system. There are also no good or bad answers to the question. It’s all about trade-offs and all you have to show is that you are aware of those trade-offs.
Lockdown - mental wellbeing
The first case of someone suffering from the SARS-CoV-2 virus can be traced back to November 2019 (source scmp.com ). A few months later, on 11th March 2020, the World Health Organization made the assessment that COVID-19 can be characterized as a pandemic (source who.int ). From that point, many companies announced that they send the majority of the employees to remote work. I would like to share my recent experience after 9 months of working from home during a lockdown, how it affected my widely understood mental wellbeing, and what helped me.
True NoSQL mindset
“You should use NoSQL here”, “SQL doesn’t scale” - those are the top buzz words you can hear at conferences or from candidates while interviewing for a software engineer position. 90% percent of the people cannot explain why is that. They simply repeat those empty buzz words to show that they are up to date with the “modern approach”. Is it really true that SQL does not scale? Let me put some light on the true mindset that stands behind NoSQL and SQL story.
Modern Linux commands - compile me
In the previous article of the Linux serie , I showed you modern Linux tools that you can just install on your distribution. Now, it’s time for a few tools which might not be available in your package manager so you can compile them by yourself like in old-times :) They are definitely worth that effort.
Some of those tools might already be in dnf or pacman but they were not in apt in the moment of writing of this article.
Taxes - increase or decrease?
Taxes are an important part of our lives. Everybody needs to pay them in one or another form. It’s a way of chip-in for common goods for a society e.g country or city. Thank that we can build shared roads, hospitals, schools, pay policemen and firemen to protect us, etc. So theoretically somebody would say - more is better. On the other hand, less money stays in our pockets to buy other goods we need.
Modern Linux commands - ready to go
All Linux users know commands like grep, ls or ifconfig but have you ever wondering if there is the contemporary alternative?
Here is my list of modern Linux commands I use every day.
For you convenience, I added apt command to install them but they are also available on Fedora and Arch using dnf and pacman. Check out details in the readme on package’s Github.
htop - colorful top
Both commands list processes managed by kernel in dynamic real-time mode.
htop does it in a more user friendly way. I use it every day to detect noisy processes.
gcc -Wall is not all
I love compilers! I cannot code without them. They can prevent entire classes of errors and warns if I accidentally try to do something stupid in the code.
Warnings
Besides compiling code and checking for type and syntax errors, compilers can also print useful warnings.
I’m a fan of turning on all warnings and writing a “paranoidly” safe code just to avoid potential correctness and performance problems.
While coding in C/C++, I use to use gcc with flag -Wall. But did you know that it doesn’t enable all warning as the name suggests?
Hello World 2.0
Welcome! I’m glad you are reading my blog. By the way, yes, you are right. This is “Hello World 2.0” in Elixir :)
defmodule Hello do
def main(args) do
IO.puts "Hello world 2.0"
end
endEdition 2.0
Actually, that’s my second approach to blogging. The first one somehow naturally burnt out. I needed to recharge my batteries to start fresh. Now, armed with new technologies, I am ready to write again. I ported my old articles from the previous blog so you can find them easily here.
Hash Code - Problems
Hash code is the crucial thing in hash-based algorithms like those used in hash maps and all problems come from that simple fact. Its efficiency is as important as the efficiency of the hashing algorithm itself. Let’s talk about those problems and how to solve them.
Why hash code can cause a problem?
The main problems are:
- Implementation determines the collision probability. This is an important factor and people tend to forget or underestimate it.
hashCode()should be implemented together withequals(Object)method as they are used jointly. The perfect implementation of those methods should correspond to each other e.g. use the same fields/methods and the same precedence.- You can easily forget to modify those two methods when you add a new field or modify it partially. This can sometimes break the correctness of the program. Of course, beside the case when you don’t want to use the new fields for objects comparison and hashing.
Simple hash collision examples
Here is my list of simple hash collisions (based on OpenJDK 11):
Hash Code - Java's collections
Welcome back to Hash Code miniserie where you can read how the hash codes (non-cryptographic hashing algorithms) and hash collections work in different programming languages. This time let’s take a look under the hood of Java’s collections and Strings. How hash codes are generated for them? Let’s check it out.
Arrays
Arrays in Java do not provide its own hashCode() implementation - it uses Object default which can cause a lot of error as hash depends on reference (an instance), not on its value.
Java also provides better implemenation via Arrays helper class.
Let’s take a look into the code:
Hash Code - Introduction
Welcome to the first article of the Hash Code miniserie where you can read how the hash codes (non-cryptographic hashing algorithms) and hash collections work in different programming languages. Every software engineer uses hash collections like Python’s dictionary, Java’s hash map or C++’s unordered map. You get them to know pretty early in your learning path as they are key data structures to solve many problems effectively but are you sure that you know them well? In this miniserie, I will shed some light on this subject.
Is Kotlin Java++ or beta of Java?
Is Kotlin just a beta version of Java and is it going to be superseded by Java and die? Or, is Java just trying to catch up from a better language but it will be never able to do this? Let’s check what is going on there!
From the birth of Kotlin to the present day
Java 8 was a big deal when it was released in March 2014. Lambdas and stream API enabled thousands of developers to start writing in a more functional style without boilerplate code as they could do before with Guava library. The first official Kotlin 1.0 release was in February 2016 between Java 8 and 9 releases (September 2017) and Kotlin already had Java 8 features (and many more) from day one.
UTF-8 - the brilliant trick to rule them all
UTF-8 is probably the biggest invention in electronic text communication since the invention of the ASCII table in 1967 and remains so to this day. It dominated the World Wide Web in 2009 and it is used by almost 95% of websites nowadays. In fact, everybody uses it but many might be not aware of why this standard has been chosen so let me put some light on this and show you the brilliant trick.
Make your shell prompt great again
What is shell prompt? Why it is not great nowadays? How to make it so again? In this article, I will show you a tool I have been successfully using for a long time. Liquid prompt - bash & zsh prompt which makes it great again!
What is shell prompt?
Shell prompt is the text which is displayed in a terminal by a system shell to prompt a user for an input. In most Linux distributions, it looks like this:
Uniq Integer
From time to time I like to solve some algorithmic tasks on Hackerrank. First of all, it is good to change the domain after constantly working on different kinds of challenges in professional life like solving business problems, fixing bugs and scaling the system. Secondly, it always reminds me of a very good period in my life - study times. Unfortunately, having an outstanding knowledge about algorithms is mostly useless for most developers. Many companies having department in Poland, where I worked for several years, totally skip this part during the interview process. As far as I know, only huge western companies with a big pool of tech talents like Amazon or Google use to ask interview questions mostly related to algorithm and general system designs than to specific technology but this is a topic for a separate article. In this article, I would like to talk about the challenge found a long time ago on Hackerrank and few cool extensions that jump to my head after I found the solution.
How Lombok saved my ass
Lombok is a Java library that generates boilerplate code for you during the compilation. You probably use it or at least heard how it can clean the code with annotations like @Data or @Value.
So I am not going to write yet another article on how to use the most popular annotations. I am going to show you one of the two most underrated features in Lombok - @Cleanup.
@Cleanup
It is just (or maybe even) an alternative to try-with-resource introduced in Java 7. Wait. What? In Java 7? When was that? On July 28, 2011. Why am I writing about alternative to feature introduced natively in Java almost eight years ago? We will get back to it soon. Let’s see a simple example first. Copy input stream into output stream with Lombok:
Hell of a time
The hell of a time idiom has two opposite meanings - having a good or a bad time. I would rather to talk explicitly about the hell which is dealing with time and time zones in computer science.
The first impression is innocent
There is a Unix time which is just 32-bit integer incremented every second. 0 value means the date 00:00:00 Thursday, 1 January 1970 UTC. It is also called UNIX epoch time as we calculate time inside one epoch. We switch to the next epoch and start counting from 0 value again when this 32-bit integer overflow. Second is the SI unit which is well defined as “the duration of 9 192 631 770 periods of the radiation corresponding to the transition between the two hyperfine levels of the ground state of the cesium 133 atom.” Definition of the second given by the BIPM at the 13th General Conference on Weights and Measures in 1967 (at a temperature of 0 K to be exact). The above part is obvious. Things start to be a little more complicated when time zones come into play.