When people ask me what my first language is, I sometimes playfully answer, “C”. C taught me what it meant to be a programmer. Few days back when I decided to start hacking the linux kernel again, I realized how much I miss programming in C. Playing with the pointers was undoubtedly the best part! So, I thought I would write this post.
If you have irrational fear of pointers or preparing for a C interview or just want to have fun, you should read this post! I am assuming you know the basics of pointers, but just cannot get a total hold on them.
I will start by stating a quote by Joel Spolsky:
I don’t care how much you know about continuations and closures and exception handling: if you can’t explain why
while(*s++ = *t++); copies a string, or if that isn’t the most natural thing in the world to you, well, you’re programming based on superstition, as far as I’m concerned: a medical doctor who doesn’t know basic anatomy, passing out prescriptions based on what the pharma sales babe said would work.
“I don’t believe in Computer Science.”~ Richard Feynman at Bell Labs (1985).
Feynman argued that science is the study of the behavior of the nature. He pointed out the limitations of classical computers for simulating the nature, which is very difficult because nature is quantum mechanical. At his lectures at Caltech, Feynman talked about the limitations of computation due to mathematics, noise, thermodynamics, reversible computing (where it is possible to compute and un-compute), and quantum mechanics. He predicted a new type of computer that is not a Turing machine, which he called a quantum computer. Continue reading
“There has not been a king since the first brethren court, and that is not likely to change!”, Captain Chevalle sighed. Elizabeth Swann wondered, “Why not?”. “Because the pirate king is elected by popular vote…”, as Mr. Gibbs started to explain, Captain Barbossa finished the sentence, “…and each pirate only votes for himself.”~Pirates of the Caribbean.
Yesterday I was having lunch with my friends Jocelyn, Johnson, and Adrian. One thing lead to another, we started talking about pirates. In one of her interviews, Jocelyn came across a question about how a senior pirate would divide some gold coins among 4 other pirates so that they would not vote to kill him. It was immediately apparent that the senior pirate would not give any gold to 2 of the pirates, but how much he should give the other 2 pirates was not obvious to me. It was stuck in my mind. I concluded that there must be some missing pieces of the question. It turns out that this problem is of a significant theoretical interest to many people. Let’s define the problem first.
There are 5 pirates of different ranks in a ship and they have a treasure of 100 gold coins. The current highest ranking pirate will divide the coins, and all 5 pirates will vote for or against it. If half or more of the pirates vote for it, then the coins will be divided that way. Otherwise, the pirate proposing the scheme will be killed, and the process is repeated with the pirates that remain. The most important thing for a pirate is his life. After that he wants to get as much coins as possible. As every pirate is bloodthirsty, if voting for or against will give him the same number of coins, he will vote against so that the pirate who proposed the plan will be killed. All 5 pirates are intelligent, rational, and good at math. How will the highest ranking pirate divide the coins?
“A paradox is an argument that produces an inconsistency, typically within logic or common sense.”-Wikipedia.
Computer scientists study paradoxes to learn about logical inconsistencies because computers (being as stupid as they are!) can not handle them. This is particularly important in the fields of Operating Systems, Artificial Intelligence, Machine Learning, etc. On top of that, paradoxes are extremely fun thought exercises! The unexpected hanging paradox is described as follows:
A judge tells a prisoner that he will be hanged at noon on one weekday in the following week, but the execution will be a surprise to the prisoner.
Linked list is one of the simplest but most popular datastructures, perhaps because good linked list problems can be solved within 15-20 minutes. Linked list problems are interesting, fun, thought provoking, and easy to describe, which is why they are very common in a programming interview. Microsoft loves asking linked list questions, I mean, you WILL get at least one linked list question if you ever interview with Microsoft!
Wikipedia defines, “a linked list is a data structure consisting of a group of nodes that together represent a sequence”. So, a typical linked list node will have a reference to the next node and a data field. This is called a singly linked list. Therefore, the first node (commonly known as the head) can represent the entire linked list, since one can traverse all the nodes from head by using the next reference. The Java code for the traversal of a linked list is below: Continue reading
The Monty Hall problem is one of the most interesting probability puzzles. It is a veridical paradox because the result appears impossible but is demonstrably true. The problem is following:
Suppose you are on a game show. You are asked to choose one of three doors: behind one door is a car and behind the other two are goats. Your goal is to get the car. After you pick a door, the host, who knows what’s behind the doors, opens another door, which has a goat (since the two doors that you did not choose must have a goat). The Monty Hall problem asks, “Should you stick to your original choice or should you choose the remaining unopened door or does it make any difference?”
Despite all its criticism, singletons still exists today, perhaps because insecure programmers feel the illusion of doing the “right” thing, since they are after all using a design pattern. For those who think, “What experts do, must be right”, I will leave a famous quote by Christopher Hitchens-
Picture all experts as if they were mammals. … Seek out argument and disputation for their own sake.
The popularity of the word ‘singleton’ probably comes from set theory, where it is a set with exactly one element. Similar to its mathematical counterpart, a singleton pattern in software engineering ensures exactly one instance of a class for each running application. This is how you would write a singleton class in Java: Continue reading