Month: February 2017

Linked Lists – Part I

For learning and reviewing purposes, I decided to build a linked list from scratch. The goal is to achieve a relatively featured implementation of a doubly linked list. At this point I have implemented a Node and a Widget to test with. Both classes and a Solution are all I have at this point in time. In the next day or two I hope to complete this task.

Given that I use among other IDEs Visual Studio, decided to use it. For programming language I selected C++. Expect to be using C++ for work about 50% of my development time. Continue reading “Linked Lists – Part I”

Longest Absolute Path File – Solved

I looked at the following LeetCode challenge:  https://leetcode.com/problems/longest-absolute-file-path/?tab=Description

Typically I write my test code using the Scanner class. Initially this time was no exception. I did notice that the input contained the strings “\n” and “\t” but I just went ahead. Processing of input created some side effects which I documented in a previous post with this same title. The approach which I will start using from now on was to place the input in an array of Strings and traverse it. This is illustrated in the following Java test code: Continue reading “Longest Absolute Path File – Solved”

LFU Cache III

I have spent some time attempting to implement the LFU Cache using the Java language. Perhaps I should put some additional time but given that Java does not support pointers perhaps it would be a convenient point to switch to C / C++ to get this done. After that I will probably returns to Java and attempt to implement this algorithm.

I have enhanced some and added other methods to the DoubleLinkList class.

Following is a screen capture of the console from the Eclipse IDE: Continue reading “LFU Cache III”

Longest Absolute File Path

A couple strange things are happening to me with this challenge. If you wish to take a look at the requirements and provide some insights you can find it at:  https://leetcode.com/problems/longest-absolute-file-path/?tab=Description

As you can see there are a couple of sample strings. They are:

dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext

dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext

Allow me to show a screen capture of the Eclipse IDE console: Continue reading “Longest Absolute File Path”

BotClean

I received a message from HackerRank suggesting the BotClean challenge. If interested take a look at the requirements at the following URL:  https://www.hackerrank.com/challenges/botclean

I had an issue with the Output Format description. Some time ago I looked at a different challenge and my solution generated a set of steps in order to complete each task. In this case only one step may be displayed at a time. Seems that the code that invokes the method next_move() updates the coordinates and the board each time after executing a move. Continue reading “BotClean”

Spiral Matrix

I ran into this challenge described in C/C++ as follows:

#define MATRIX_SIZE 3

#if MATRIX_SIZE == 3

int matrix[3][3] = {

    { 11, 12, 13 },

    { 21, 22, 23 },

    { 31, 32, 33 }

};

#elif MATRIX_SIZE == 4

int matrix[4][4] = {

{ 11, 12, 13, 14 },

{ 21, 22, 23, 24 },

{ 31, 32, 33, 34 },

{ 41, 42, 43, 44 }

};

#else

int matrix[6][6] = {

{ 11, 12, 13, 14, 15, 16 },

{ 21, 22, 23, 24, 25, 26 },

{ 31, 32, 33, 34, 35, 36 },

{ 41, 42, 43, 44, 45, 46 },

{ 51, 52, 53, 54, 55, 56 },

{ 61, 62, 63, 64, 65, 66 }

};

#endif

Given a rectangular matrix of integers [editorial: could be any type of data if one uses generics; I will skip that part] display the values in a spiral fashion. For example, the first matrix[3][3] would produce:  11 12 13 23 33 32 31 11 22. Continue reading “Spiral Matrix”

Queue – A Tale of Two Stacks

I looked at the HackerRank challenge Queues: A Tale of Two Stacks. If interested take a look at the requirements at the following URL:  https://www.hackerrank.com/challenges/ctci-queue-using-two-stacks

Initially I followed the recommendation of using two stacks. The brute force approach worked for the test case but it was too slow in 3 or 4 test cases. Continue reading “Queue – A Tale of Two Stacks”

Balanced Brackets – Possible Second Attempt

I selected the next unsolved challenge at HackerRank in the section labeled Cracking the Coding Interview. If interested you may use the following URL to get to the challenge: https://www.hackerrank.com/challenges/ctci-balanced-brackets

It seems to me like I have already solved this challenge.

Following is the console of the Eclipse Neon IDE: Continue reading “Balanced Brackets – Possible Second Attempt”

LFU Cache II – Double Linked List

This is the second post related to the LFU Cache. I have completed most (if not all) operations that I expect to require for the LFU Cache algorithm running O(1) implemented. Of course, as I have stated time and again, you start with an architecture, then mode to a design, implementation and testing and cycle as many times as needed modifying the steps until you and the customer (in this case the same) are satisfied with the end product.

I would like to start with a screen capture of the console on the Eclipse IDE: Continue reading “LFU Cache II – Double Linked List”

LFU Cache I – Single Link List

The motivation for this post was a LeetCode challenge titled:  LFU Cache for which I would like to develop a set of put() and get() methods that operate in O(1) running time. If you wish to take a look at the challenge you may find it at the following URL:  https://leetcode.com/problems/lfu-cache/

The actual challenge does not require O(1) methods but I read the following statement:

Follow up:

Could you do both operations in O(1) time complexity? Continue reading “LFU Cache I – Single Link List”