c++ tagged posts

Implementation of atoi()

A while ago I had an interesting interview question with a big tech company. The question was straight forward: Implement atoi() to convert a string to int.

Some restrictions apply:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or ...

Read More

Reverse Linked List in time O(n) & space O(1)

I’m not a dev but I do enjoy a coding challenge. In this blog post I will explain how to reverse a singly linked linked-list.

The data structure looks like this:

A simple code to implement a singly linked linkedlist is:

struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}

To reverse the list: we need two pointers a previous pointer (prev) and a current one pointing to the current node we’re checking (curr). During exchanging pointers we will also a need a temporary pointer to hold the next pointer so we don’t lose track of our linked list during the reversing process

input: 1-2-3-4
output: 4-3-2-1

Needless to say you need to check for extreme cases such as an empty list, or a 1 element list.

Here is my code:

class Sol...
Read More

Finding longest path of a specially-shaped graph in O(Log(n))

First of all let’s clear thing up:

Finding the longest path of a graph algorithm is NOT the inverse of Dijkstra’s algorithm of finding the shortest path. In fact finding the longest path of a graph in NP-Hard problem.

In our case, the graph is a tree-shaped graph, more like a triangle.

Read More

Single Instance C# Application

While I was developing Auto CCleaner I faced a problem with allowing only one instant of the application. I found many solutions (using mutex) and others, but it didn’t work or it was inefficient. What I needed is a simple, easy, and efficient method. Hence I used little help from .NET Process class as follow:

I added this block to initialize (load) function:

Tada! Only a single instance is allowed now.
note: You need to add: using System.Diagnostics; at the beginning of your cs file.

Read More

Job Interview Programming problem: Math Expression legality.

Read More