05/21/16

Demystifying Virtual Tables in C++ – Part 1 Trivial Constructors

Introduction

This won’t be an easy read. After each claim I will provide supporting code in both C++ and assembly.

Recently I was working on a particularly sneaky bug. A thing happened to me in C++, that should not be possible under normal circumstances. By normal, I mean that 1+1 is guaranteed to 2; the sun rises in the East and sets in the West; all water is wet and the earth is dry…. Yet is still happened. Namely: the vptr of a fully constructed virtual object was pointing to the virtual table of it’s base class. To debug this particular issue one needs to dive deep into the compiler world and into the dreaded waters of assembly.

I hope that I do not have to point out that when I started I had absolutely no clue what is going on. I knew what virtual pointers do and that the compilers are reasonably smart about them. As every modern software engineer I consulted the web oracle only to realise that there is very little written online. I wanted to know how vptrs and vtables are implemented. Not your typical high level theory explaining how dynamic dispatch works. I wanted to know what makes it tick. And while doing so I might improve the world a bit by sharing my journey. So I hopped on my trusted GDB and rode of to the assembly land.

Continue reading


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
05/13/16

HackerRank ‘Bigger is Greater’ Solution

Short Problem Definition:

Given a word w, rearrange the letters of w to construct another word in such a way that is lexicographically greater than w. In case of multiple possible answers, find the lexicographically smallest one among them.

Link

Bigger is Greater

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

This task challenges us to find the next permutation of any given array. There are many implementations available online and it is worthwhile comparing them . I would recommend reading the article by Nayuki or re-implementing the std::next_permutation.

Solution:
def next_permutation(arr):
    # Find non-increasing suffix
    i = len(arr) - 1
    while i > 0 and arr[i - 1] >= arr[i]:
        i -= 1
    if i <= 0:
        return False
    
    # Find successor to pivot
    j = len(arr) - 1
    while arr[j] <= arr[i - 1]:
        j -= 1
    arr[i - 1], arr[j] = arr[j], arr[i - 1]
    
    # Reverse suffix
    arr[i : ] = arr[len(arr) - 1 : i - 1 : -1]
    return True 
        
def main():
    t = input()
    for _ in xrange(t):
        s = list(raw_input())
        if next_permutation(s):
            print "".join(s)
        else:
            print "no answer"
    
if __name__ == '__main__':
    main()

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin