Tag: C++

C++: Max Product in a Matrix witout Backtrack

Problem

Given a matrix, find the path from top left to bottom right with the greatest product by moving only down and right.

The code is in C++.
The only moves allowed are down and right. The solution works for positive numbers.

Reference

Written with StackEdit.

Advertisements

C++: Find Longest Sequence of Numbers in An Unsorted Array

Given an unsorted array, find the length of the longest sequence of consecutive numbers in the array.

$ g++ -std=c++11 ./FindLongestSequence.cc
$ ./a.out
4

Reference

Written with StackEdit.

C++: Find Duplicates in a Positive Integers Range 1 to N

Given an array of integers where each value 1 <= x <= len(array), write a function that finds all the duplicates in the array.

C++ Solution

$ g++ -std=c++11 ./FindDuplicates.cc
$ ./a.out
1 2

Reference

Height of a Binary Tree: Recursion Unrolled & Explained

—
tags: >-
development, C++, tree, height, programming, recursion, internals, complete
flow
categories: development

—

Height of a Binary Tree is the longest path in the tree.

Code
int getHeight(node *root)
{
    if (root == NULL) {
        return -1;
    }
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);

    return (max(leftHeight, rightHeight) + 1);     
}

Suppose the tree is as follows:

         [10]
          |
       [8]  [12]
              |
           [4] [5]

The recursion flow is as following:

1. getHeight(10)
2. getHeight(left of 10) ==> getHeight(8)
3. getHeight(left of 8) ==> getHeight(NULL)
4. getHeight(NULL) returns -1
5. leftHeight = -1 and flow goes back to line # 3
6. Now, it calls right of 8, getHeight(right of 8)
7. getHeight(NULL) returns -1 to rHeight
8. Both subtree of 8 are traversed and leftHeight = -1, rightHeight = -1
9. It compares both values and return the max + 1
10. max( -1, -1) + 1 = 0
11. The node 8 is left subtree of 10, and returns to line # 2.
12. At node 10, leftHeight = 0
13. Now, rightHeight is calculated by moving to right of 10.
14. getHeight(right of 10) ==> getHeight(12)
15. Similar to above, height at node 12 is calculated as 1.
16. At the end, node 12 returns its height at line #14.
17. Again we compare max (0, 1) + 1
18. The answer is 2
Summary

Usually, all recursion steps are not visualized and just assumed to be working. This post tries to exhaust a recursion flow and help understand it better.

File system in userspace (FUSE) on Linux : C implementation

  • BBFS is a good starting point to develop a file system in C
  • Application should keep in mind file offset before issuing a request. A write should be followed with a seek to offset zero, before issuing read.
  • FUSE 2.7 reads 8K data by default, in two 4K chunks
  • Read happens in last 4K and the first 4K data block

Example:

I had set the file size as 4MB in getattr () implementation.

int bb_getattr(const char *path, struct stat *statbuf)
{
    int retstat = 0;
    char fpath[PATH_MAX];
    bb_fullpath(fpath, path);

    memset(statbuf, 0, sizeof(struct stat));
    if (strcmp(path, "/") == 0) {
        statbuf->st_mode = S_IFDIR | 0755;
        statbuf->st_nlink = 2;
    } else {
        statbuf->st_mode = S_IFREG | 0444;
        statbuf->st_nlink = 1;
        statbuf->st_size = 4 * 1024* 1024;
    }   
    return retstat;
}

The sequence of calls and their arguments is as follows:

bb_getattr(path="/abcd.txt", statbuf=0xc5387960)
    bb_fullpath:  rootdir = "/tmp", path = "/abcd.txt", fpath = "/tmp/abcd.txt"
bb_open(path"/abcd.txt", fi=0xc5daaa50)
    bb_fullpath:  rootdir = "/tmp", path = "/abcd.txt", fpath = "/tmp/abcd.txt"
    fi:
    flags = 0x00008002
    fh_old = 0x00000000
    writepage = 0
    direct_io = 0
    keep_cache = 0
    fh = 0x0000000000000001
    lock_owner = 0x0000000000000000
bb_write(path="/abcd.txt", buf=0xc4966050, size=10, offset=0, fi=0xc5387a50)
    fi:
    flags = 0x00000000
    fh_old = 0x00000001
    writepage = 0
    direct_io = 0
    keep_cache = 0
    fh = 0x0000000000000001
    lock_owner = 0x0000000000000000
bb_read(path="/abcd.txt", buf=0x06ccbd90, size=12288, offset=4096, fi=0xc5daaa50)  <- Here
    fi:
    flags = 0x00000000
    fh_old = 0x00000001
    writepage = 0
    direct_io = 0
    keep_cache = 0
    fh = 0x0000000000000001
    lock_owner = 0x0000000000000000

bb_read(path="/abcd.txt", buf=0x06ccbd90, size=4096, offset=0, fi=0xc5daaa50)
    fi:
    flags = 0x00000000
    fh_old = 0x00000001
    writepage = 0
    direct_io = 0
    keep_cache = 0
    fh = 0x0000000000000001
    lock_owner = 0x0000000000000000

Forward declaration of a structure in C

What do you think of following code?

/*
 * decl.h
 */
struct junk {
    int a;
};

----------------------------------------------
/*
 * fwd.c
 * We have not included the header file decl.h.
 */
#include 
struct junk;

int main()
{
    struct junk *ptr;
    printf("%d", ptr->a);
}

You will get compilation error that structure object ptr is incomplete. This is misleading if you do not go through all included header files. cscope will make you believe that definition exists. You just wonder till you find out that structure was never defined in fwd.c!