Wednesday, July 26, 2017

Reversing Linked List In-Place

In this post, I will go through a simple algorithm for reversing a singly-linked list with space complexity of O(1), i.e., in-place.

There are two methods: one with recursive and the other with iterative. To me, it is easier to solve in recursive format first and then apply iterative afterwards.

Let's dig right in!

By the way, I claim that the recursive algorithm actually has space complexity of O(N), since it is recursively called N times, growing up the stack by O(N). With this view, quick sort no longer becomes an in-place algorithm, as it requires O(log N) recursive calls.

To see why I claim this, compare the functions reverse_with_array and reverse_with_function_with_stack(_helper). They pretty much do the same thing, except that in the first case, we create an array (a list, to be exact, but can be easily replaced by an array) whereas in the second case we simply create this array using recursive function stack. In fact, the recursive way costs more in time as well as space complexity.

In any case, these methods all do the work with quite different implementations!

Three Minutes Daily Vim Tip: Displaying Currently Viewing File

This post is based on jmathew's answer here.

To display which file you are currently looking at in vim, simply insert the following lines in ~/.vimrc file:
set statusline=%F%m%r%<\ %=%l,%v\ [%L]\ %p%%
set laststatus=2


Saturday, July 22, 2017

Alternative to scp

For transferring files from remote computer, I use scp command. In this post. I will cover an alternative command: rsync.

The syntax is very similar to scp. For example,
$ rsync some/local/file user@remote:/location/in/remote
$ rsync user@remote:/location/in/remote some/local/file

However, the options are quite different. I would say just use -aP
$ rsync -aP some/local/file user@remote:/location/in/remote
$ rsync -aP user@remote:/location/in/remote some/local/file

Here, -a stands for archive, which includes recursive -r option, and -P stands for --partial and --progress. With these options, you can resume downloading the files when interrupted.

For more info, look up man page:
$ man rsync

Ah, by the way, if you are using port other than 22, make sure to use -e option as below:
$ rsync -aP -e 'ssh -P 1234' some/local/file user@remote:/location/in/remote
$ rsync -aP -e 'ssh -P 1234' user@remote:/location/in/remote some/local/file
where 1234 is the port you want to use.

Friday, July 21, 2017

Resume Downloading with wget

It is quite annoying when you are downloading a large file with wget or curl, and somehow your download is interrupted, because you have to download from scratch again. Well, here is what you can do to resume downloading where you left off.

With wget, simply add -c option:
$ wget -c http://url/to/download/file

That's it!

Friday, July 14, 2017

Polymorphism in C++

Every time I have a job interview, people ask me questions regarding polymorphism and the role of virtual keyword in C++. It saddens me that I did not know the answer to them, and this post is to explain what they are to others who may be asked the same questions in their job interviews.

First, polymorphism in programming means that an object may take different forms. Assume you have Polygon class, from which you derive Rectangle and Triangle classes. You have an object that will be either Rectangle or Triangle, but you do not know what it will be until the runtime. In order to write code such that it shares as much as it can, we can write the following:

Compile it
$ g++ poly.cpp

and running the program with various inputs should help us understand what is going on:
$ ./a.out 2
Polygon()
This is a polygon object with name: polygon
This is a polygon object with name: polygon
area with w=3 and h=4 is -1
~Polygon()

$ ./a.out 3
Polygon()
Triangle()
This is a triangle object with name: triangle
This is a polygon object with name: triangle
area with w=3 and h=4 is 6
~Triangle()
~Polygon()

$ ./a.out 4
Polygon()
Rectangle()
This is a rectangle object with name: rectangle
This is a polygon object with name: rectangle
area with w=3 and h=4 is 12
~Rectangle()
~Polygon()

Note that only virtual methods take polymorphic behavior, meaning that the method corresponding to the object's class is executed. This is the role of the keyword virtual. Another thing to note is that for virtual destructor, the base class' destructor is still called, unlike regular methods that are overriden.

Saturday, July 8, 2017

How to Use Vim on Macbook Pro Touch Bar

I really love my new Macbook Pro 15" model, with just one exception: its touch bar. I have no idea why the heck Apple wants to force everyone to use the touch bar in this model. You see, in the 13" Macbook Pro, you actually have an option to choose either the standard function keys or the touch bar, but with the 15" model, there is no such option.

My big complaints about touch bar should probably go into a separate thread, so I will start right into with my solutions to cope with the touch bar. I map F2 and F3 to work as :tabp and :tabn in Vim, but it just won't work with the touch bar, as there no long is standard function keys. What is even worse is that there is no physical ESC key, which is the most essential key in using Vim.

I actually remap CAPS LOCK to work as ESC key. This is supported by Mac OS X by default. To set this, go to Preferences --> Keyboard --> Modifier Keys --> Caps Lock --> Escape. For standard function key shortcuts, I simply remap ;n to Fn where n could be from 1 to 12. That is, for example, I have the following liens in ~/.vimrc:

nnoremap ;2 :tabp<CR>
nnoremap ;3 :tabn<CR>

for switching between tabs with ;2 and ;3 keystrokes. It takes some time to get used to, but at least this remapping makes touch bar usable.

Python Development with VIM

Just some notes regarding my quest for developing python using vim:

1. Never use anaconda. Most vim plugins will not support it

2. Use virtualenv instead.

3. Install python-mode.

First, run
$  mkdir -p ~/.vim/autoload ~/.vim/bundle && curl -LSso ~/.vim/autoload/pathogen.vim https://tpo.pe/pathogen.vim

Next, edit ~/.vimrc to have:
execute pathogen#infect()
syntax on
filetype plugin indent on

 
Finally, run
$ cd ~/.vim/bundle && git clone https://github.com/klen/python-mode.git

4. Install ctags.
$ sudo apt-get install ctags

Now I am happy with it for now.