One of my fellow researchers asked me this question, which he said was an interview question for amazon.

Write an algorithm to reverse blocks of length k- in a list. i.e. if k=3 and the list is originally ; it should produce .

There’s already a clever trick to reverse a linked list without requiring any extra space. The idea is that we just iterate through the list and reverse all the pointers. In java this would look something like this

	public static Node reverse(Node list){
		Node prev = null;
		while(list != null){
			Node next = list.next;
			list.next = prev;
			prev = list;
			list = next;
		}
		return prev;
	}

This will reverse the entire list (by going until the next link is null), so if we want to reverse blocks of length instead, we should add an additional parameter and condition, to obtain below.

	public static Node reverse(Node list, int k){
		Node prev = null;
		while(list != null && k-- > 0){
			Node next = list.next;
			list.next = prev;
			prev = list;
			list = next;
		}
		return prev;
	}

So what happens when we call reverse on a list? Imagine we have the list after a call to reverse with on the first node (0), the list will be , and the call returns a pointer to ‘1’. Now we see that the trick we need to overcome is losing our place in the list as we do the block-wise reversal. I did this by keeping track of basically three positions : the first element of the block you are going to reverse, the last element of this block (which is returned by the call to reverse) and the first element of the next block to be reversed.

This way, after we have reversed the first j-1 blocks, we only need to reverse block j, point the end of block j-1 to the new beginning of block j, and then update positions to go to block j+1. In code this looks like… (I handle the first block specially so we know how to return the start of the list)

	public static Node kreverse(Node list, int k){
		Node prev = list;
		int i = 0;

		//first block special case?
		while(list != null && i++ < k){
			list = list.next;
		}
		Node retval = reverse(prev, k);

		while(list != null){
			i = 0;
			Node me = list;
			while(list != null && i++ < k)
				list = list.next;
			Node end = reverse(me, k);
			prev.next = end;

			prev = me;
		}

		return retval;
	}

What is great is that we have only visited each element in the list about twice, (once in the inner while loop of kreverse, and once in reverse) and at most constant extra space. In fact, we can even avoid visiting each element twice if we are clever with the reverse method, and return multiple values (Python!!!!). So this method is in both time and complexity. One other consideration is what will happen if the length of the list is not divisible by .

Some code that can be used in conjunction with the malloc code here. It adds an additional function to draw what the memory sort of looks like according to the boundary-tag allocator. It also tries to make the size of the regions appropriate.

Sample Output :

************
*ssssssssss*  1048568  ( 0x239dff8 )
*          *
*          *
*          *
*          *
*pppppppppp*  55952  ( 0x22aba90 )
*ssssssssss*  55944  ( 0x22aba88 )
*//////////*
*//////////*
*//////////*
*pppppppppp*  3600  ( 0x229ee10 )
*ssssssssss*  3592  ( 0x229ee08 )
*          *
*pppppppppp*  3248  ( 0x229ecb0 )
*ssssssssss*  3240  ( 0x229eca8 )
*//////////*
*//////////*
*pppppppppp*  0  ( 0x229e000 )
************

Additional code, just put this in myAllocator.c, maybe somewhere near the bottom? It will add some warnings about unsafe casting etc.

#define FREE ' '
#define ALLOC '/'
#define PREFIX 'p'
#define SUFFIX 's'
#define EDGE '*'
#define mem0(x) (void*)(x) - (void*)arenaBegin
#define MAXBLOCKS 1000

typedef struct RLine_s{
    int lines, sz;
    BlockPrefix_t *pfx;
}RLine;

//cannot dynamically allocate memory...assumes less than 1000 blocks will be allocated
RLine lpp[MAXBLOCKS];

void printMemLine(char type, int width, void* address){
    assert(width > 2);
    putc(EDGE, stderr);
    int i;
    for(i = 0; i < width - 2; i++) putc(type, stderr);
    putc(EDGE, stderr);
    if(type == PREFIX || type == SUFFIX)
        printf("  %d  ( 0x%x )", mem0((int)address), address);
    printf("\n");
}

int compRLineLoc(void *b, void *a){
    return (void*)((RLine*)a)->pfx - (void*)((RLine*)b)->pfx;
}

int compRLineSize(void *b, void *a){
    return ((RLine*)a)->sz - ((RLine*)b)->sz;
}

/* Draws the arena vertically, with each line representing a pseudo-address
 * The prefixes and suffixes for each block are always drawn along with their
 * addresses, however the size of the regions is somewhat arbitrary. It is true,
 * however that |A| > |B| ==> lines(A) >= lines(B) where A, B are two regions
 * and lines denotes how much space is left between them.
 * 
 * The leftmost address is base-10 and 0 is at arenaBegin, the rightmost is the
 * actual address in memory. 
 * 
 * Example Output: 
 *  ************
 *  *ssssssssss*  1048568  ( 0x225aff8 )
 *  *          *
 *  *          *
 *  *pppppppppp*  3248  ( 0x215bcb0 )
 *  *ssssssssss*  3240  ( 0x215bca8 )
 *  *xxxxxxxxxx*
 *  *pppppppppp*  0  ( 0x215b000 )
 *  ************ 
*/
void visualizeMemory(){
    assert(arenaBegin); //this would be boring if you havent allocated memory
    
    int LINES = 25, WIDTH = 12, rcount = 1, i,j;
    int MAXSZ = 5, smallr;
    int lines_left = LINES - 2;
    
    //count the number of regions
    BlockPrefix_t* p = arenaBegin;
    while((p = getNextPrefix(p)) && ++rcount);
    assert(rcount < MAXBLOCKS); //We do not have enough memory to do this
    lines_left -= 2*rcount;
    
    p = arenaBegin;
    for(i = 0; i < rcount; i++){
        lpp[i].pfx = p;
        lpp[i].sz = computeUsableSpace(p);
        lpp[i].lines = 1;
        p = getNextPrefix(p);
    }
    
    /* An algorithm to make larger regions look larger */
    if (lines_left >= 0){
        qsort(lpp, rcount, sizeof(RLine), compRLineSize);
        smallr = rcount - 1;
        while(lines_left >= 0 && smallr > 0){
            for(i = 0; i < smallr && lines_left>=0; i++){
                if(lpp[i].lines < MAXSZ) lpp[i].lines++;
            }
            smallr--;
        }
    }
    
    //sort them in reverse order of their location, so we can print them backwards
    qsort(lpp, rcount, sizeof(RLine), compRLineLoc);
    
    //do the printing!!!
    printMemLine(EDGE, WIDTH, 0);
    for(i = 0; i < rcount; i++){
        p = lpp[i].pfx;
        printMemLine(SUFFIX, WIDTH, p->suffix);
        for(j = 0; j < lpp[i].lines; j++)
            printMemLine(p->allocated ? ALLOC : FREE, WIDTH, 0);
        printMemLine(PREFIX, WIDTH, p);
    }
    printMemLine(EDGE, WIDTH, 0);
}

After moving all my music with EasyTag creator I was left with a directory structure with tons of directories which had no music (but maybe .cue or .m3u files or maybe even subdirs). If you run this on the root of your music folder, it will try to fix it!

#!/usr/bin/python
import re, os, sys, shutil
"""Script to delete all subfolders of a folder that do not
contain music (at any subdirectory level).
 - Alex Knaust 10/25/2012
"""

musicRegex = re.compile(r"\.(flac|mp3|ogg|mp4|aac|alac|ape|wav)", re.IGNORECASE)
def music_match(fname):
    """Determine if a file is music (according to musicRegex)"""
    return musicRegex.match(os.path.splitext(fname)[-1])

def has_any_music(files):
    """Check if a list of filenames contains any music files (via music_match)"""
    for f in files:
        if music_match(f):
            return True
    return False
                
def get_nomusic_directories(srcdir):
    """Returns a list of subdirectories with no music in them" (at any level)"""
    results = []
    for f in os.listdir(srcdir):
        f = os.path.join(srcdir, f)
        if os.path.isdir(f):
            hasmusic = False
            for dirpath, dirnames, filenames in os.walk(f):
                if has_any_music(filenames):
                    hasmusic = True
                    break
            
            if not hasmusic:
                results.append(f)            
    return results
    
    
def main():
    if len(sys.argv) != 2:
        print('Pass the directory to be cleaned')
        exit(1)
    
    nomusic = get_nomusic_directories(sys.argv[1])
    ans = raw_input('Will delete %d Directories OK? y/n : ' % len(nomusic)) 
    
    if not ans.lower()[0] == 'y':
        print 'OK! exiting...'
        exit(0)
    
    for directory in nomusic:
        def printfails(func, path, errinf):
            print('Failed to remove "%s"' % path)
            
        shutil.rmtree(directory, onerror=printfails)
    
if __name__ == '__main__':
    main()