curl behind Authentication

curl dm01:8082/nodes

curl -vv -X POST -d username=foo -d password=foo123 dm01:8082/login
* Adding handle: conn: 0x7fcdb980aa00
* Adding handle: send: 0
* Adding handle: recv: 0
* Curl_addHandleToPipeline: length: 1
* - Conn 0 (0x7fcdb980aa00) send_pipe: 1, recv_pipe: 0
* About to connect() to dm01 port 8082 (#0)
* Trying 10.3.48.19...
* Connected to dm01 (10.3.48.19) port 8082 (#0)
> POST /login HTTP/1.1
> User-Agent: curl/7.30.0
> Host: dm01:8082
> Accept: */*
> Content-Length: 28
> Content-Type: application/x-www-form-urlencoded
>
* upload completely sent off: 28 out of 28 bytes
< HTTP/1.1 302 Found
< Set-Cookie: session=ufvuwYxNQWg5pjvSRTUyyHA921jwffc8; Max-Age=7776000; HttpOnly
< Set-Cookie: JSESSIONID=15757nag01iw5zxzo52cayz8n;Path=/
< Expires: Thu, 01 Jan 1970 00:00:00 GMT
< Set-Cookie: session=SRCdeb9kLBH5sSrWkNOQiKt4dlaeBWK2; Max-Age=7776000; HttpOnly
< Location: http://dm01:8082/
< Content-Length: 0
<
* Connection #0 to host dm01 left intact

curl -b session=ufvuwYxNQWg5pjvSRTUyyHA921jwffc8 dm01:8082/nodes
// Should work fine

[PHP] AD/LDAP Integration

// make sure your host is the correct one
// that you issued your secure certificate to
$ldaphost = "";
$ldapport = "";
$ldapbasedn = "ou=box.net,dc=ad,dc=whirl,dc=net";

// using ldap bind
$ldaprdn  = '';     // AD username
$ldappass = '';  // AD password

// connect to ldap server
$ldapconn = ldap_connect($ldaphost, $ldapport)
    or die("Could not connect to LDAP server.");

if ($ldapconn) {

    // binding to ldap server
    @ldap_bind($ldapconn, 'AD\\'.$ldaprdn, $ldappass) or die('Could not bind to AD');

    // verify binding
    if ($ldapconn) {
        $attributes_ad = array("sAMAccountName", "displayName","description","cn","givenName","sn","mail","co","mobile","company");
        $search = ldap_search($ldapconn, $ldapbasedn, "(sAMAccountName=$ldaprdn)", $attributes_ad) or die ("Error in search query");
        $result = ldap_get_entries($ldapconn, $search);
        print_r($result);
        echo PHP_EOL;
    } else {
        echo "LDAP bind failed..." . PHP_EOL;
    }
}

[PHP] Implement Binary Tree

class Node
{
    public $value, $left, $right;

    public function __construct($value)
    {
        $this->value = $value;
    }
}

Search:
class BST
{
    public $root;

    public function __construct($value = null)
    {
        if ($value !== null) {
            $this->root = new Node($value);
        }
    }

    public function search($value)
    {
        $node = $this->root;

        while($node) {
            if ($value > $node->value) {
                $node = $node->right;
            } elseif ($value < $node->value) {
                $node = $node->left;
            } else {
                break;
            }
        }

        return $node;
    }
}

Insertion:
public function insert($value)
{
    $node = $this->root;
    if (!$node) {
        return $this->root = new Node($value);
    }

    while($node) {
        if ($value > $node->value) {
            if ($node->right) {
                $node = $node->right;
            } else {
                $node = $node->right = new Node($value);
                break;
            }
        } elseif ($value < $node->value) {
            if ($node->left) {
                $node = $node->left;
            } else {
                $node = $node->left = new Node($value);
                break;
            }
        } else {
            break;
        }
    }
    return $node;
}


Min:
public function min()
{
    if (!$this->root) {
        throw new Exception('Tree root is empty!');
    }

    $node = $this->root;
    return $node->min();
}

public function min()
{
    $node = $this;
    while ($node->left) {
        if (!$node->left) {
            break;
        }
        $node = $node->left;
    }
    return $node;
}

Max:
public function max()
{
    if (!$this->root) {
        throw new Exception('Tree root is empty!');
    }

    $node = $this->root;
    return $node->max();
}

public function max()
{
    $node = $this;
    while ($node->right) {
        if (!$node->right) {
            break;
        }
        $node = $node->right;
    }
    return $node;
}

Bash command redirections

There are 3 file descriptors, stdin, stdout and stderr (std=standard).

Available options:

1. redirect stdout to a file
2. redirect stderr to a file
3. redirect stdout to a stderr
4. redirect stderr to a stdout
5. redirect stderr and stdout to a file
6. redirect stderr and stdout to stdout
7. redirect stderr and stdout to stderr
8. 1 'represents' stdout and 2 stderr.

Note: with the less command you can view both stdout (which will remain on the buffer) and the stderr that will be printed on the screen, but erased as you try to 'browse' the buffer.

Sample: stdout to file

This will cause the ouput of a program to be written to a file.

         ls -l > stdout.txt

        

Here, a file called 'stdout.txt' will be created and it will contain what you would see on the screen if you type the command 'ls -l' and execute it.

Sample: stderr 2 file

This will cause the stderr output of a program to be written to a file.

          ls -l 2> stderr.txt

        

Here, a file called 'stderr.txt' will be created and it will contain what you would see the stderr portion of the output of the ' ls -l' command.

Sample: stdout 2 stderr

This will cause the stderr ouput of a program to be written to the same filedescriptor than stdout.

          ls -l 1>&2 

        

Here, the stdout portion of the command is sent to stderr, you may notice that in different ways.

Sample: stderr 2 stdout

This will cause the stderr ouput of a program to be written to the same filedescriptor than stdout.

          ls -l 2>&1

        

Here, the stderr portion of the command is sent to stdout, if you pipe to less, you'll see that lines that normally 'dissappear' (as they are written to stderr) are being kept now (because they're on stdout).

Sample: stderr and stdout 2 file

This will place every output of a program to a file. This is suitable sometimes for cron entries, if you want a command to pass in absolute silence.

          ls -l &> /dev/null 

        

This (thinking on the cron entry) will delete every file called 'core' in any directory. Notice that you should be pretty sure of what a command is doing if you are going to wipe it's output.

Running background jobs in Unix

When you execute a Unix job in the background ( using '&', 'bg' command), and logout from the session, your process will get killed.

You can avoid this by executing the job with 'nohup' (stands for no hang up).

Usage:
nohup {command-with-options} &

'nohup' is very helpful when you have to execute a shell-script or command that take a long time to finish. In that case, you don’t want to be connected to the shell and waiting for the command to complete. Instead, execute it with nohup, exit the shell and continue with your other work.

Explanation about nohup.out file:
By default, the standard output will be redirected to nohup.out file in the current directory. And the standard error will be redirected to stdout, thus it will also go to nohup.out. So, your nohup.out will contain both standard output and error messages from the script that you’ve executed using nohup command.

Difference between .bash_profile & .bashrc

WHEN working with Linux, Unix, and Mac OS X, I always forget which bash config file to edit when I want to set my PATH and other environmental variables for my shell. Should you edit .bash_profile or .bashrc in your home directory?

You can put configurations in either file, and you can create either if it doesn’t exist. But why two different files? What is the difference?
According to the bash man page, .bash_profile is executed for login shells, while .bashrc is executed for interactive non-login shells.

What is a login or non-login shell?
When you login (type username and password) via console, either sitting at the machine, or remotely via ssh: .bash_profile is executed to configure your shell before the initial command prompt.
But, if you’ve already logged into your machine and open a new terminal window (xterm) inside Gnome or KDE, then .bashrc is executed before the window command prompt. .bashrc is also run when you start a new bash instance by typing /bin/bash in a terminal.

Why two different files?
Say, you’d like to print some lengthy diagnostic information about your machine each time you login (load average, memory usage, current users, etc). You only want to see it on login, so you only want to place this in your .bash_profile. If you put it in your .bashrc, you’d see it every time you open a new terminal window.

Mac OS X — an exception
An exception to the terminal window guidelines is Mac OS X’s Terminal.app, which runs a login shell by default for each new terminal window, calling .bash_profile instead of .bashrc. Other GUI terminal emulators may do the same, but most tend not to.

My Recommendation
Most of the time you don’t want to maintain two separate config files for login and non-login shells — when you set a PATH, you want it to apply to both. You can fix this by sourcing .bashrc from your .bash_profile file, then putting PATH and common settings in .bashrc.

To do this, add the following lines to .bash_profile:
if [ -f ~/.bashrc ]; then
   source ~/.bashrc
fi

Now when you login to your machine from a console .bashrc will be called.

[PHP] Send attachment in mail

date_default_timezone_set('America/Los_Angeles');

// Create a file with data to send
$file_name = "summary.txt";
$myfile = fopen($file_name, "w") or die("Unable to open file!");
$txt = "PHP Mail function example with attachment" . PHP_EOL;
fwrite($myfile, $txt);
fclose($myfile);

$filetype = filetype($file_name);

//read from the uploaded file & base64_encode content for the mail
$content = file_get_contents($file_name);
$encoded_content = chunk_split(base64_encode($content));

$boundary = md5("php-mail");

$from_email = 'from_email@gmail.com'; //sender email
$recipient_email = 'recipient_email@gmail.com'; //recipient email
$subject = 'Test mail'; //subject of email
$message = 'This is body of the message'; //message body

//header
$headers = "MIME-Version: 1.0\r\n";
$headers .= "From:".$from_email."\r\n";
$headers .= "Reply-To: ".$from_email."\r\n";
$headers .= "Content-Type: multipart/mixed; boundary = $boundary\r\n\r\n";

//plain text
$body = "--$boundary\r\n";
$body .= "Content-Type: text/plain; charset=ISO-8859-1\r\n";
$body .= "Content-Transfer-Encoding: base64\r\n\r\n";
$body .= chunk_split(base64_encode($message));

//attachment
$body .= "--$boundary\r\n";
$body .="Content-Type: $filetype; name=\"$file_name\"\r\n";
$body .="Content-Disposition: attachment; filename=\"$file_name\"\r\n";
$body .="Content-Transfer-Encoding: base64\r\n";
$body .="X-Attachment-Id: ".rand(1000,99999)."\r\n\r\n";
$body .= $encoded_content;

$sentMail = mail($recipient_email, $subject, $body, $headers);
if($sentMail) //output success or failure messages
{    
    die('Thank you for your email');
} else {
    die('Could not send mail! Please check your PHP mail configuration.');
}

[PHP] Convert command line parameters to array

When we write a script which will be run from command line, we may have a need to pass in certain input params. This is similar to the GET/POST parameters that a web page uses as input params.

The function below is an easy way to convert the command line input params and use it like an array in the script.

// Convert arguments to key/value pairs, like the $_GET or $_POST arrays
$args = array();
foreach ($argv as $arg) {
    if ($pos = strpos($arg, '=')) {
        $key = substr($arg, 0, $pos);
        $value = substr($arg, $pos+1);
        $args[$key] = $value;
    }
}

Input:
php run_my_script.php key1=value1 key2=value2 key3=value3

Output:
$args = [
    'key1' => value1,
    'key2' => value2,
    'key3' => value3,
];

[PHP] Implement Stacks (LIFO)

class ReadingList
{
    protected $stack;
    protected $limit;
    
    public function __construct($limit = 10) {
        // initialize the stack
        $this->stack = array();
        // stack can only contain this many items
        $this->limit = $limit;
    }

    public function push($item) {
        // trap for stack overflow
        if (count($this->stack) < $this->limit) {
            // prepend item to the start of the array
            array_unshift($this->stack, $item);
        } else {
            throw new RunTimeException('Stack is full!'); 
        }
    }

    public function pop() {
        if ($this->isEmpty()) {
            // trap for stack underflow
          throw new RunTimeException('Stack is empty!');
      } else {
            // pop item from the start of the array
            return array_shift($this->stack);
        }
    }

    public function top() {
        return current($this->stack);
    }

    public function isEmpty() {
        return empty($this->stack);
    }
}


Output:
$myBooks = new ReadingList();

// add some items to the stack
$myBooks->push('A Dream of Spring');
$myBooks->push('The Winds of Winter');
$myBooks->push('A Dance with Dragons');
$myBooks->push('A Feast for Crows');
$myBooks->push('A Storm of Swords'); 
$myBooks->push('A Clash of Kings');
$myBooks->push('A Game of Thrones');

// remove some items from the stack
echo $myBooks->pop(); // outputs 'A Game of Thrones'
echo $myBooks->pop(); // outputs 'A Clash of Kings'
echo $myBooks->pop(); // outputs 'A Storm of Swords'

// top of the stack
echo $myBooks->top(); // outputs 'A Feast for Crows'

[PHP] Implement Linked List

/**
 * Class Node
 */
class Node
{
    public $data;
    public $next;

    public function __construct($item)
    {
        $this->data = $item;
        $this->next = null;
    }
}

/**
 * Class LinkList
 */
class LinkList
{
    public $head = null;

    private static $count = 0;

    /**
     * @return int
     */
    public function GetCount()
    {
        return self::$count;
    }

    /**
     * @param mixed $item
     */
    public function InsertAtFist($item) {
        if ($this->head == null) {
            $this->head = new Node($item);
        } else {
            $temp = new Node($item);

            $temp->next = $this->head;

            $this->head = $temp;
        }

        self::$count++;
    }

    /**
     * @param mixed $item
     */
    public function InsertAtLast($item) {
        if ($this->head == null) {
            $this->head = new Node($item);
        } else {
            /** @var Node $current */
            $current = $this->head;
            while ($current->next != null)
            {
                $current = $current->next;
            }

            $current->next = new Node($item);
        }

        self::$count++;
    }

    /**
     * Delete the node which value matched with provided key
     * @param $key
     */
    public function Delete($key)
    {
        /** @var Node $current */
        $current = $previous = $this->head;

        while($current->data != $key) {
            $previous = $current;
            $current = $current->next;
        }

        // For the first node
        if ($current == $previous) {
            $this->head = $current->next;
        }

        $previous->next = $current->next;

        self::$count--;
    }

    /**
     * Print the link list as string like 1->3-> ...
     */
    public function PrintAsList()
    {
        $items = [];
        /** @var Node $current */
        $current = $this->head;
        while($current != null) {
            array_push($items, $current->data);
            $current = $current->next;
        }

        $str = '';
        foreach($items as $item)
        {
            $str .= $item . '->';
        }

        echo $str;

        echo PHP_EOL;
    }
}

$ll = new LinkList();

$ll->InsertAtLast('KP');
$ll->InsertAtLast(45);
$ll->InsertAtFist(11);
$ll->InsertAtLast('FE');
$ll->InsertAtFist('LE');
$ll->InsertAtFist(100);
$ll->InsertAtFist(199);
$ll->InsertAtLast(500);

$ll->PrintAsList();
echo 'Total elements ' . $ll->GetCount();
echo PHP_EOL;
$ll->Delete(45);
$ll->PrintAsList();
echo 'Total elements ' . $ll->GetCount();
echo PHP_EOL;
$ll->Delete(500);
$ll->PrintAsList();
echo 'Total elements ' . $ll->GetCount();
echo PHP_EOL;
$ll->Delete(100);
$ll->PrintAsList();
echo 'Total elements ' . $ll->GetCount();
echo PHP_EOL;

Output:
$ php LinkList.php
199->100->LE->11->KP->45->FE->500->
Total elements 8
199->100->LE->11->KP->FE->500->
Total elements 7
199->100->LE->11->KP->FE->
Total elements 6
199->LE->11->KP->FE->
Total elements 5

'this'

var foo = {

   first: function(){
     console.log('I am first');
   },

   second: function(){
     console.log('I am second');
   },
};

foo.first();
foo.second();

Everything works fine.

Now there is a need for function second to call function first. Try this and it will fail.

var foo = {

   first: function(){
     console.log('I am first');
   },

   second: function(){
     console.log('I am second');
     first();
   },
};

foo.second();

One way to fix this problem is to hardcode value foo inside the second function. Following code works.

var foo = {

   first: function(){
     console.log('I am first');
   },

   second: function(){
     console.log('I am second');
     foo.first();
   },
};

foo.second();

Above code works but hardcoding the value of foo inside the object literal is not good. A better way would be to replace the hardcoded name with this .

var foo = {

   first: function(){
     console.log('I am first');
   },

   second: function(){
     console.log('I am second');
     this.first();
   },
};

foo.second();

All is good.

Chasing this

Javascript allows one to create function inside a function. Now I am changing the implementation of method second. Now this method would return another function.

var foo = {

   first: function(){
       console.log('I am first');
   },

   second: function(){
     return function(){
         this.first();
     }
   },
};

foo.second()();

var foo = {

   first: function(){
       console.log('I am first');
   },

   second: function(){
     return function(){
         this.first();
     }
   },
};

foo.second()();

var foo = {

   first: function(){
       console.log('I am first');
   },

   second: function(){
     var self = this;
     return function(){
         self.first();
     }
   },
};

foo.second()();

Truth Table / Power Set

Output:
0 0 0 
0 0 1 
0 1 0 
0 1 1 
1 0 0 
1 0 1 
1 1 0 
1 1 1 

printTruthTable("", 0, 3);

$originalArr = array('a', 'b', 'c');
$outputArr = array();
powerSet("", 0, 3);
var_dump($outputArr);

function printTruthTable($str, $start, $strLength) {
  if ($start === $strLength) {
    if (/*Truth Table*/) {
      var_dump($str);
    }
    if (/*Power Set*/) {
      global $originalArr;
      global $outputArr;
      
      $tempArr = array();
      for($i=0; $i<$strLength; $i++){
        if ($str[$i] === 1) {
          array_push($tempArr, $originalArr[$i]);
        }
      }
      array_push($outputArr, $tempArr);
    }
    
    return;
  }
  $str[$start] = 0;
  printTruthTable($str, $start+1, $strLength);
  
  $str[$start] = 1;
  printTruthTable($str, $start+1, $strLength);
}

OR

function printPowerSet($set, $set_size)
{
    /*set_size of power set of a set with set_size
      n is (2**n -1)*/
    $pow_set_size = pow(2, $set_size);
 
    for($counter = 0; $counter < $pow_set_size; $counter++)
    {
      for($j = 0; $j < $set_size; $j++)
       {
          if($counter & (1 << $j))
            echo $set[$j]; // echo 
       }
       echo PHP_EOL;
    }
}
 
$set = 'abc';
printPowerSet($set, 3);

[JS] Function Bind

Why you need this?
 var x = 9;
var module = {
  x: 81,
  getX: function() { return this.x; }
};

module.getX(); // 81

var getX = module.getX;
getX(); // 9, because in this case, "this" refers to the global object

// create a new function with 'this' bound to module
var boundGetX = getX.bind(module);
boundGetX(); // 81

// ----------------------------------------------------

Function.prototype.bind = function(oThis) {
  var args = Array.prototype.slice.call(arguments, 1);
  var fToBind = this;
  var fToReturn = function() {
    return fToBind.apply(oThis, args.concat(Array.prototype.slice.call(arguments)))
  }
  return fToReturn;
}

[JS] Function Currying

Currying allows you to easily create custom functions by partially invoking an existing function. Here’s a simple example:

var add = function(a,b) {
    return a + b;
}

//create function that returns 10 + argument
var addTen = add.curry(10);
addTen(20); //30

// ----------------------------------------

Function.prototype.curry = function() {
    if (arguments.length<1) {
        return this; //nothing to curry with - return function
    }
    var fToBind = this;
    var args = Array.prototype.slice.call(arguments); // Converting to array
    return function() {
        return fToBind.apply(this, args.concat(toArray(arguments)));
    }
}

Palindrome

$a_inputString = "raddar"
function isPalindrome($a_inputString)
{
    $frontPointer = 0;
    $backPointer = str_length(inputString)-1;
   
    while ($frontPointer < $backPointer)
    {
       if ( strcmp(substr($inputString, $frontPointer, 1)
                  (substr($inputString, $backPointer, 1) == false)
           return false;
       $frontPointer ++;
       $backPointer --;
    }
   
    return true;
}

Merge sorted lists

Question:
n lists, each is sorted, each has size m
merge into one sorted list, overall size n*m

Easy Solution:
1. Pointers pointing to each position of the array
2. Compare the element at the positions
3. Find the minimum and insert in the outputArray

Complexity
1. Traverse all the lists (n*m)
2. Comparisons to find the minimum element ((n-1) comparisons) 
O((n*m)(n-1)) = O(n^2*m)

MinHeap heap = new MinHeap();

// $inList[n] - Input Lists
$outputArr = array();

// Push first elements of all the lists in the MinHeap
for (int i=0; i<n; i++)
{
    heap.push(i, array_pop($inList[i]));
}   

/*
  1. Pop element from MinHeap
  2. Push the next element from the inList from which the element was pop'd
  3. Do this till the MinHeap is empty  
*/
$popObj = heap.pop();
while (!empty($popObj))
{
    $listId = $popObj["listId"];
    $elementPop = $popObj["leastElement"];
   
    $outputArr[] = $elementPop;
    heap.push($listId, array_pop($inList[$listId]));
}

// Complexity
1. n-size heap
2. log n to insert in heap
3. O(n*m*logn)

OOP - Javascript

Using XOR operator for finding duplicate element

A XOR statement has the property that 'a' XOR 'a' will always be 0, that is they cancel out, thus, if you know that your list has only one duplicate and that the range is say x to y, 601 to 607 in your case, it is feasible to keep the xor of all elements from x to y in a variable, and then xor this variable with all the elements you have in your array. Since there will be only one element which will be duplicated it will not be cancelled out due to xor operation and that will be your answer.

void main()
{
    int a[8]={601,602,603,604,605,605,606,607};
    int k,i,j=601;

    for(i=602;i<=607;i++)
    {
        j=j^i;
    }

    for(k=0; k<8; k++)
    {
        j = j^a[k];
    }
    // j = duplicate element
}

Variation:

An array of 2 elements - one element occurs even number of times & the other odd number of times. How would you find the value that occurs odd number of times ?

Get all the unique numbers in the array using a set in O(N) time. Then we XOR the original array and the unique numbers all together. Result of XOR is the even occurring element. Because every odd occurring element in the array will be XORed with itself odd number of times, therefore producing a 0. And the only even occurring element will be XORed with itself even number of times, which is the number itself.

Reason:  
XOR a number with itself odd number of times we get 0,.
XOR a number with itself even number of times then we get the number itself.

You are given an array of integers and a sum. Find all pairs of integers that equal that sum. Assume you have some sort of data structures that will be able to store the pairs. Write an algorithm to find all these pairs

Solution1
O(n^2) solution - Have two for loops

Solution2
Using a hashMap

Solution3
Most efficient - as no extra storage like hashMap

Sort the array

Two pointer - one to the begining and the other to the end of the array.

Compare the values pointed by the pointers untill the pointers collide
If the sum is lesser than m then increment the left pointer by one
If the sum is greater than m then decrement the right pointer by one
If the sum is equal to m then return "YES"

Swap without using 3rd variable

Swap Algorithm

A = A + B
B = A - B
A = A - B

You can not use this approach as while adding A & B (A + B), it could result in a "OVERFLOW"

Hence, we use this approach

X := X XOR Y
Y := X XOR Y
X := X XOR Y

Design Patterns

[MySQL] Storage Engines

A storage engine is what stores, handles, and retrieves information from a table. There is no "perfect" or "recommended" storage engine to use, but for most applications the default MyISAM is fine. In MySQL there are 10 different storage engines, though all of them may not be available to you. To get a list of supported storage engines on your MySQL Server, you can do:

mysql -uroot -p

Password:

mysql> show engines;

This should provide a list of supported storage engines for your server. The standard engines supported by MySQL are:

MyISAM

InnoDB

MERGE

MEMORY (HEAP)

BDB (BerkeleyDB)

EXAMPLE

ARCHIVE

CSV

BLACKHOLE

ISAM

Benefits to selecting a storage engine comes down to the added benefits of speed and functionality,

Eg: If you store tore a lot of log data you might want to use the ARCHIVE storage engine which only supports INSERT and SELECT

MyISAM

• default storage engine
• not having TRANSACTION, and with having table-level locking as opposed to row-level locking
• best for performance and functionality
• great for sites that have a very low INSERT/UPDATE rate and a very high SELECT rate.

InnoDB

• some additional time spent during initial setup
• ability to do row-level locking, as opposed to table-level locking, to increase performance time. This allows parallel INSERT/UPDATE/DELETE queries to be ran on the same table, unlike MyISAM where each query has to wait its turn to run
• foreign key functionality
• provides caching for data and indexes in memory, as well as on disk, which provides a large increase in performance gain

MERGE

The MERGE storage engine was added in MySQL 3.23.25. It enables users to have a collection of identical MyISAM tables to be handeled by a single table. There are constraints to this type, such as all tables needing to have the same definition, but the usefullness here quickly becomes apparently. If you store sales transactions on your site in a daily table, and want to pull a report for the month, this would allow you to execute a query against a single table to pull all sales for the month.

MEMORY (HEAP)

The HEAP storage engine, also referred to as MEMORY, provides in-memory tables. MySQL Server will retain the format of the tables in order to quickly create a "trash" table and access the information on the fly for better processing, it is not great for long term usage due to data integrity. Similar to InnoDB, this is not for the light of RAM.

BDB (BerkeleyDB)

The BDB handles transaction-safe tables and uses a hash based storage system. This allows for some of the quickest reading of data, especially when paired with unique keys. There are, however, many downfalls to the BDB system, including the speed on un-index rows, and this makes the BDB engine a less than perfect engine choice. Because of this, many people tend to overlook the BDB engine. I feel, however, that it does have a place in database design when the right situation calls for it.

EXAMPLE

This storage engine was added in MySQL 4.1.3. It is a "stub" engine that serves no real purpose, except to programmers. EXAMPLE provides the ability to create tables, but no information can be inserted or retrieved.

ARCHIVE

The ARCHIVE storage engine was added in MySQL 4.1.3 as well, and is used for storing large amounts of data without indexes in a very small footprint. This engine will only support INSERT and SELECT, and all information is compresses. This makes it the perfect storage engine for logs, point of sale transactions, accounting, etc. While this may seem very useful, keep in mind that when reading data the entire table must be de-compressed and read before data can be returned. Therefore, this is the ideal engine for storage that is only called on a low-rate basis.

CSV

CSV, added in MySQL 4.1.4, stores data in text files using comma-separated values. As such this is not an ideal engine for large data storage, tables requiring indexing, etc. The best use-case for this is transferring data to a spreadsheet for later use.

BLACKHOLE

Though seemingly poinless at first, the BLACKHOLE engine, which does not allow for any data to be stored or retrieved, is good for testing database structures, indexes, and queries. You can still run INSERTS against a BLACKHOLE table, with the knowledge that all inserts will vanish into the void.

ISAM

The original storage engine was ISAM, which managed nontransactional tables. This engine has since been replaced by MyISAM, and while MySQL Engineers recommend that it should no longer be used, it does have its place in this article for historical purposes. If you feel that you need to use ISAM, just remember that MyISAM is backwards compatiable and should provide you with everything and more.

Conclusion

In conclusion, while there is no perfect catchall storage engine, it can be fairly safe to say that InnoDB and MyISAM are the typical go-to for many applications and DBAs. It is good to note, however, that though they are a good catchall, they may not be ideal for every situation and there may be another storage engine available that will increase performance in your application/environment.

Parking Lot

Design Patterns

Chat room

Coffee Vending Machine

Elevator

Singleton

class Singleton {
    public:
        static Singleton* GetInstance();
    private:
        Singleton();
        static Singleton* pSingleton;        // singleton instance
};

Singleton* Singleton::pSingleton= NULL;

Singleton::Singleton()
{
    // do init stuff
}

Singleton* Singleton::GetInstance()
{
    if (pSingleton== NULL) 
    {
        pSingleton = new Singleton();
    }
    return pSingleton;
}

The Singleton Pattern is one of the GoF (Gang of Four) Patterns. This particular pattern provides a method for limiting the number of instances of an object to just one. It's an easy pattern to grasp once you get past the strange syntax used. 

Consider the following class:

PHP Code:

class Database 

{ 

    public function __construct() { ... } 

    public function connect() { ... } 

    public function query() { ... } 

    ... 

}  

This class creates a connection to our database. Any time we need a connection we create an instance of the class, such as:

PHP Code:

$pDatabase = new Database(); 

$aResult = $pDatabase->query('...');  

Lets say we use the above method many times during a script's lifetime, each time we create an instance we're creating a new Database object (we're also creating a new database connection, but that's irrelevant in this example) and thus using more memory. Sometimes you may intentionally want to have multiple instances of a class but in this case we don't. 

The Singleton method is a solution to this common problem. To make the Database class a Singleton we first need to add a new property to the class, we'll call this $m_pInstance:

PHP Code:

class Database 

{ 

    // Store the single instance of Database 

    private static $m_pInstance; 

    ...     

}  

As the comment states, this property will be used to store the single instance of our Database class. You should also note that this property must be static. 

Next we need to change the constructor's scope to private. This is one of the strange syntaxes that usually confuse people. 

PHP Code:

class Database 

{ 

    // Store the single instance of Database 

    private static $m_pInstance; 

    private function __construct() { ... } 

}  

By making the constructor private we have prohibited objects of the class from being instantiated from outside the class. So for example the following no longer works outside the class:

PHP Code:

$pDatabase = new Database();  

We now need to add a method for creating and returning our Singleton. Add the following method to the Database class:

PHP Code:

public static function getInstance() 

{ 

    if (!self::$m_pInstance) 

    { 

        self::$m_pInstance = new Database(); 

    } 

    return self::$m_pInstance; 

}  

This funny looking function is responsible for handling our object instance. It's relatively easy to understand, basically we check our static property $m_pInstance, if it is not valid we create a new instance of the Database class by calling the constructor. Remember, we made the __construct() method private, so an instance of the object can only be created from within the class' methods. Finally the function returns a reference to our static property. On subsequent calls to getInstance(), $m_pInstance will be valid and thus the reference will be returned - no new instances are created.

So our Database class now looks something like this

PHP Code:

class Database 

{ 

    // Store the single instance of Database 

    private static $m_pInstance; 

    private function __construct() { ... } 

    public static function getInstance() 

    { 

        if (!self::$m_pInstance) 

        { 

            self::$m_pInstance = new Database(); 

        } 

        return self::$m_pInstance; 

    } 

}  

You can now get an instance of the Database class from anywhere (without using globals or function arguments) in your project. Here's an example and comparison:

This is the usual way we create objects:

PHP Code:

$pDatabase = new Database(); 

$aResult = $pDatabase->query('...');  

This is the Singleton way:

PHP Code:

$pDatabase = Database::getInstance(); 

$aResult = $pDatabase->query('...');  

To conclude, the Singleton is an easy-to-use design pattern for limiting the number of instances of an object.

Delete a Tree

#include<stdio.h>
struct binarysearchtree
{
      int data;
      struct binarysearchtree* left;
      struct binarysearchtree* right;
};
typedef struct binarysearchtree* tree;

void tree_free(tree T)
{
  if (T==NULL)
     return;
  else
  {
      tree_free(T->left);
      tree_free(T->right);
      free(T);
  }
}

Count the number of leaves in a tree

#include<stdio.h>
struct binarysearchtree{
        int data;
        struct binarysearchtree* left;
        struct binarysearchtree* right;
};
typedef struct binarysearchtree* tree;

int count_leaves(tree T)
{
        if(T==NULL)
            return 0;
        else if(T->left==NULL && T->right==NULL)
            return 1;
        else
            return count_leaves(T->left)+count_leaves(T->right);
}

Largest consecutive Sum

public static void main(String []args)
{
    int a[] = {-2,5,10,-3,5,-10,2,20,1};
    int result[] = new int[a.length];
    result[0] = a[0];
    
    for(int i=1;i<a.length;i++)
    {
        result[i] = (result[i-1] + a[i] > a[i]) ? result[i-1] + a[i] : a[i];
    }
    
    int max = result[0];
    for(int i=1;i<result.length;i++)
    {
        if(result[i] > max)
            max = result[i];
    }

    System.out.println(max);
}

Largest Non-Consecutive Sum

public static void main(String []args)
{
    int a[] = {1,13,10,2,5,9,15,20,8};
    int result[] = new int[a.length];
    result[0] = a[0];
    int max = 0;
    int index = 0;

    for(int i=0; i<a.length; i++)
    {
        max = 0;
        for(int j=0;j<i-1;j++)
        {
            if(result[j] > max)
                max = result[j];
        }
        result[i] = max + a[i];
    }

    for(int i=1; i<result.length; i++)
    {
        if(result[i] > max)
            max = result[i];
    }

    System.out.println(max);
    }
}

Check whether there exists a root to leaf path sum equal to a given number

int hasSum(struct node* root, int sum)
{
    if(root == NULL)
        return (sum == 0);

    sum = sum - root->data;

    return hasSum(root->left, sum) || hasSum(root->right, sum);
}

Find if a tree is symmetric / isMirror()

A symmetric binary tree is one where if you draw a vertical line passing through the root node then the left half should be the mirror image of the right half. Here is the recursive code,

int isSymmetric(struct node* l, struct node* r)
{
    if((l == NULL) && (r == NULL))
        return 1;

    if(((l == NULL) && (r != NULL)) ||
            ((l != NULL) && (r == NULL)))
        return 0;

    return isSymmetric(l->left, r->right) && isSymmetric(l->right, r->left);
}

Store the sum of left and right subtrees in a node

int sum(struct node* root)
{
    if(root == NULL)
        return 0;

    int lsum = sum(root->left);
    int rsum = sum(root->right);

    root->data = lsum + rsum + root->data;

    return root->data;
}

Find the kth largest element in a Binary Search Tree

Traverse the tree in descending order and keep a count of number of nodes visited. When this count is equal to 'k', print the element.

void printk(struct node* root, int k)
{
    if(root == NULL)
        return;

    static int index = 0;

    printk(root->right, k);

    if(++index == k)
    {
        printf("%d\n", root->data);
        return;
    }

    printk(root->left, k);
}

Calculate vertical sum of a Binary Tree

Vertical sums of a binary tree are the sum of its each vertical column. For e.g. consider the below tree,

                 5
             /        \
          3            8
         /  \          /    \
       2     4      6     9


Vertical Sum for first column: 2
Vertical Sum for second column: 3
Vertical Sum for third column: 15 (5+4+6)
Vertical Sum for fourth column: 8
Vertical Sum for fifth column: 9

Output: 2 3 15 8 9

Algorithm:
- start from root and hash its value in a map using a key, say, 'key_col'
- recursively hash left and right children with key value 'key_col-1' and 'key_col+1'
- if the key entry is not present in the hash map then create one and set value as 'root->data'
- if the key entry is already present then just add 'root->data' to the existing value

In the end, we have vertical sum stored in the hash map. Here is the code,

void mapNode(struct node* root, map& m, int col)
{
    if(root == NULL)
        return;
 
    map::iterator it = m.find(col);

    //if column is already mapped and map already
    //has some value stored for the column then
    //add root->data to already stored value, otherwise,
    //just store root->data.
    if(it == m.end())
        m.insert(pair(col, root->data));
    else
        it->second += root->data;

    mapNode(root->left, m, col-1);
    mapNode(root->right, m, col+1);
}

int main()
{
    struct node *root=NULL;
    map m;
    map::iterator iter;

    insert(&root, 50);
    insert(&root, 25);
    insert(&root, 100);
    insert(&root, 30);
    insert(&root, 20);
    insert(&root, 75);

    mapNode(root, m, 0);

    for(iter = m.begin(); iter != m.end(); iter++)
        printf("%d ", iter->second);

    printf("\n");

    return 0;
}

Count total number of vertical columns in a Binary Tree

Every node in a binary tree can be considered belonging to a column. If we assume that 'root' belongs to column '0' then root->left belongs to column '-1', root->right belongs to column '+1' and root->left->right belongs to column '0' and so on. We have to find the total number of such columns.

void totalCol(struct node* root, int col, int* minC, int* maxC)
{
    if(root == NULL)
        return;

    totalCol(root->left, col-1, minC, maxC);
    totalCol(root->right, col+1, minC, maxC);

    *minC = MIN(*minC, col);
    *maxC = MAX(*maxC, col);
}

int main()
{
    struct node *root=NULL;

    int minC=0;
    int maxC=0;

    insert(&root, 50);
    insert(&root, 25);
    insert(&root, 100);
    insert(&root, 30);
    insert(&root, 10);
    insert(&root, 5);

    totalCol(root, 0, &minC, &maxC);

    printf("Total Col: %d\n", maxC - minC + 1);

    return 0;
}

Print ancestors of a node in a Binary Tree

int isAncestor(struct node* root, int n)
{
    if(root == NULL)
        return 0;

    if(root->data == n)
        return 1;

    if(isAncestor(root->left, n) || isAncestor(root->right, n))
    {
        printf("%d\n", root->data);
        return 1;
    }

    return 0;
}

Serialization/Deserialization of a Binary Tree

Serialize:
to Array - (for node 'i', store left child at '2i+1' & right child at '2i+2')

Assume we have a binary tree below:

    _30_
   /        \
 10      20
 /          /  \
50     45  35

Using pre-order traversal, the algorithm should write the following to a file:

30 10 50 # # # 20 45 # # 35 # #

void writeBinaryTree(BinaryTree *p, ostream &out)
{
    if (!p)
    {
        out << "# ";
    }
    else
    {
        out << p->data << " ";
        writeBinaryTree(p->left, out);
        writeBinaryTree(p->right, out);
    }
}


Deserialize:


Reading the binary tree from the file is similar. We read tokens one at a time using pre-order traversal. If the token is a sentinel, we ignore it. If the token is a number, we insert it to the current node, and traverse to its left child, then its right child.

void readBinaryTree(BinaryTree *&p, ifstream &fin)
{
    int token;
    bool isNumber;
    if (!readNextToken(token, fin, isNumber))
        return;
    if (isNumber)
    {
        p = new BinaryTree(token);
        readBinaryTree(p->left, fin);
        readBinaryTree(p->right, fin);
    }
}

Construct a Binary Tree, given its Inorder and preorder

Consider the following tree,

               5
           /        \
         2          7
      /   \         /
     1    4      6

Inorder: 1 2 4 5 6 7
Preorder: 5 2 1 4 7 6

Algorithm:
1. Take first element from Preorder (in this case 5) and find it in Inorder.
2. Elements on the left side of '5' (1 2 4) form the left subtree of '5' and similarly elements on the right side (6 7) form right sub tree.
3. Recursively select each element from Preorder and create its left and right subtrees from Inorder.

struct node* create(int* in, int* pre, int inStrt, int inEnd)
{
    if(inStrt > inEnd)
        return NULL;

    int i;
    static int preIndex = 0;

    //create node from preOrder
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->data = pre[preIndex];

    //find node in inOrder
    for(i=inStrt; i<=inEnd; i++)
        if(in[i] == pre[preIndex])
            break;

    preIndex++;
   
    //recursively call create for the left and right
    //half of inOrder created by preOrder
    temp->left = create(in, pre, inStrt, i-1);
    temp->right = create(in, pre, i+1, inEnd);

    return temp;
}

Longest common subsequence problem

Given two character arrays, arr1[m] and arr2[n], determine a longest common subsequence among these two arrays.

Dynamic programming to solve it in O(mn) time and space.

LCS[i, j] = LCS[i-1][j-1] + 1                        ; arr1[i] == arr2[j]
               = MAX(LCS[i-1][j], LCS[i][j-1]) ; otherwise

#define MAX(a,b) ((a)>(b))?(a):(b)

int LCS[100][100];

int lcs(char* arr1, int len1, char* arr2, int len2)
{
    int i = 0;
    int j = 0;

    //LCS is 0 when arr2 is NULL
    for(i=0; i <= len1; i++)
        LCS[i][0] = 0;

    //LCS is 0 when arr1 is NULL
    for(j=0; j <= len2; j++)
        LCS[0][j] = 0;

    for(i=1; i <= len1; i++)
    {
        for(j=1; j <= len2; j++)
        {
            if(arr1[i] == arr2[j])
                LCS[i][j] = LCS[i-1][j-1] + 1;
            else
                LCS[i][j] = MAX(LCS[i-1][j], LCS[i][j-1]);
        }
    }

    int temp = LCS[len1][len2];

    return temp;
}

int main()
{
    char* arr1 = "adbcad";
    char* arr2 = "dbacd";

    printf("LCS: %d\n", lcs(arr1, strlen(arr1), arr2, strlen(arr2)));
    return 0;
}

OR

public static void main(String []args)
{
    String a = "ABCDEFGHIJKL";
    String b = "ABCD";
    int max = 0;
    int z=0; // Store the index of the last element of Substring
    int m[][] = new int[a.length()][b.length()];
    for(int i=0;i<a.length();i++)
    {
        m[i][0] = 0;
    }

    for(int i=0;i<b.length();i++)
    {
        m[0][i] = 0;
    }

    for(int i=0;i<a.length();i++)
    {
        for(int j=0;j<b.length();j++)
        {
            if(a.charAt(i) == b.charAt(j))
            {

                if(i==0 || j==0) // If first element is in the substring
                { 
                    m[i][j] = 1;
                }
                else
                {
                    m[i][j] = m[i-1][j-1] + 1;
                }

                if(m[i][j] > max)
                {
                    max = m[i][j];
                    z = j;
                }
            }
        }
    }

    System.out.println(max);
    System.out.println(z);
}

Longest Increasing Subsequence problem

Given an array of integers, determine the longest increasing subsequence (not necessarily contiguous).

Equations:
LIS[i] = MAX( LIS[j] ) + 1; where 0 <= j < i and A[i] > A[j]

#define MAX(a, b) ((a)>(b))?(a):(b)

int LIS[1000];

int lis(int* A, int len)
{
    int i, j;
    int max;

    LIS[0] = 1;

    for(i=1; i < len; i++)
    {
        max = 0;
        for(j=0; j < i; j++)
        {
            if(A[i] > A[j])
                max = MAX(max, LIS[j]);
        }

        printf("max: %d\n", max);

        LIS[i] = max + 1;
    }

    return LIS[len-1];
}

int main()
{
    int A[] = {4, 3, 9, 4 ,1 ,6};

    printf("LIS: %d\n", lis(A, 6));
    return 0;
}

Determine if a string has all unique characters

Solution #1: 
The most simple approach will be to check each character with every other character. The time complexity will be O(n^2) with no extra space requirement.

Solution #2:
If changes are allowed, then we can sort the string in O(n log n) time and then check the adjacent elements for duplicates. Total time complexity is n log n + n ==> n log n.

Solution #3: 
If the string is formed of extended ASCII characters then we can make an array of size 256 and store the occurrence of each character in this array.

int main(int argc, char** argv)
{
    int arr[256] = {0,};
    char *ptr = NULL;

    ptr = argv[1];

    while(*ptr != '\0')
    {
        if(arr[*ptr])
        {
            printf("Found Duplicate...\n");
            return 0;
        }
        else
        {
            arr[*ptr] = 1;
        }
        ptr++;
    }

    printf("No duplicates...\n");

    return 1;
}

Reverse a string

Solution #1: 
If extra space is available then copy the string in reverse order to a newly allocated string in O(n) time.

Solution #2: 
Again, if extra space is permissible then we can use a stack to first push the entire string on the stack and then pop it in reverse order.

Solution #3: 
If it has to be done in place, then we can take two pointers at the start and end of the string and can swap the characters they point to while incrementing and decrementing them respectively till they collide.

Solution #4: 
Approach three can also be done recursively as follows

void reverse(char *start, char *end)
{
    char temp;

    if(start >= end)
        return;
    
    temp = start[0];
    start[0] = end[0];
    end[0] = temp;

    reverse(start+1, end-1);    
}

int main(int argc, char** argv)
{
    char str[256] = {0,};
    int len;

    gets(str);
    len = strlen(str);

    reverse(str, str+len-1);

    printf("%s\n", str);

    return 1;
}

Check whether a string is a rotation of another string or not

The first thing, of course, would be to make sure that both the strings have same length. 

Now, suppose these strings are str1 and str2 and one of them is a rotation of the other(eq. str1 = "google" and str2 = "oglego"). Append str2 to itself(making "oglegooglego"). 

Now, if we have a function to find a substring within a string, we can use it to find str1 in modified str2. If found, then str2 is a rotation of str1.

REST API Best Practices

Base Url's
Only 2 base urls 1) collection & 2) singular
/dogs
/dog/ig

Use nouns & not verbs
/deals  - Groupon
/checkins - Foursquare

// do not have getDogs / getDogById
use HTTP Methods GET, POST, PUT, DELETE to define CRUD operations

How to handle associations
Get all dogs belonging to a owner 5678
eg: GET /owners/5678/dogs

Create a new new dog for a specific owner
eg: POST /owners/5678/dogs

Additional / optional parameters
GET /owners/5678/dogs?color=red&type=pet

Errors

1. code : use HTTP status codes
2. message : have message
3. more_info : have url for error docs; get more context; get help

Versioning

• have version at the start, do not have it in the middle 
• have highest level scope as much to the left as possible

eg:
/v1.2/dog/5678
Note: Do not release an API without versioning
why? FB moved from v1.2 to v1.3 and all apps supporting v1.2 broke

Partial Response

• If you only want some fields out of the whole data - want only id, name, type from an entire list of data

eg:
LinkedIn -> /people:(id,first-name,last-name,industry)
Facebook -> /saumilps/friends?fields=id,name,picture

Pagination

• have an offset & limit

eg:
/dogs?limit=25&offset=50

Formats
Spit more than one format

• /dogs.json
• /dog/1234.json
• Accept: application/json (pure RESTful way / in the header)
• ?type=json

Authentication
OAuth

REST vs SOAP

When to use REST ?

• Better performance
• Better scalability
• Reads can be cached
• Any browser can be used because the REST approach uses the standard GET, PUT, POST, and DELETE verbs
• Totally stateless operations: if an operation needs to be continued, then REST is not the best approach and SOAP may fit it better. However, if you need stateless CRUD (Create, Read, Update, and Delete) operations

When to use SOAP ?

• Asynchronous processing and invocation; if your application needs a guaranteed level of reliability and security then SOAP 1.2 offers additional standards to ensure this type of operation. Things like WSRM – WS-Reliable Messaging.
• Formal contracts; if both sides (provider and consumer) have to agree on the exchange format then SOAP 1.2 gives the rigid specifications for this type of interaction.
• Stateful operations; if the application needs contextual information and conversational state management then SOAP 1.2 has the additional specification in the WS* structure to support those things (Security, Transactions, Coordination, etc). Comparatively, the REST approach would make the developers build this custom plumbing.

WS-Security

While SOAP supports SSL (just like REST) it also supports WS-Security which adds some enterprise security features. Supports identity through intermediaries, not just point to point (SSL). It also provides a standard implementation of data integrity and data privacy. Calling it “Enterprise” isn’t to say it’s more secure, it simply supports some security tools that typical internet services have no need for, in fact they are really only needed in a few “enterprise” scenarios.

WS-AtomicTransaction

Need ACID Transactions over a service, you’re going to need SOAP. While REST supports transactions, it isn’t as comprehensive and isn’t ACID compliant. Fortunately ACID transactions almost never make sense over the internet. REST is limited by HTTP itself which can’t provide two-phase commit across distributed transactional resources, but SOAP can. Internet apps generally don’t need this level of transactional reliability, enterprise apps sometimes do.

WS-ReliableMessaging

Rest doesn’t have a standard messaging system and expects clients to deal with communication failures by retrying. SOAP has successful/retry logic built in and provides end-to-end reliability even through SOAP intermediaries.

Summary

In Summary, SOAP is clearly useful, and important. For instance, if I was writing an iPhone application to interface with my bank I would definitely need to use SOAP. All three features above are required for banking transactions. For example, if I was transferring money from one account to the other, I would need to be certain that it completed. Retrying it could be catastrophic if it succeed the first time, but the response failed.

Anagrams

Find whether two words are anagrams (cafe / face)

• Go to first word in hash table, add 1 in hash table then see whether all letters of 2nd word also in hash table, if it reaches end of 2nd word it means it is a anagram. Issue: 2 same letters in the word
• Increment values in the hash table instead of storing 1 for the first word & then for the 2nd word, decrement values, if all values 0 at the end of 2nd word - it means anagram Complexity = 3n (parse 1st word, parse 2nd word, parse the array)

Create sets of anagrams from a word list (cafe, face, fdga, dgfa - you you will have 2 lists => cafe/face & fdga/dgfa)

• Go to first word, see if any lists, if a list take a word from that list & run the above function for that two words, if return true then add to that list, if false do this for all the lists, create a new list with that word is still that word not in any list Complexity = l * 3n * x (l-no of words, x-no of unique lists)
• sort each word & sort list & then group
• aefc, aefc, adfg, adfg
• Complexity =>
• sorting = nlogn
• sorting each word = nlogn * size of each word
• sorting list = l*log l * total no of words
• total complexity = sorting each word + sorting list + grouping

Diameter of a Binary Tree

            5

         /      \
       2         9
     /    \      /
    1    4    7

Diameter: 5 (1-2-5-9-7 or 4-2-5-9-7)

int height(struct node* root)
{
    if(root == NULL)
        return 0;

    int lh = height(root->left);
    int rh = height(root->right);

    return 1 + MAX(lh, rh);
}

int diameter(struct node* root)
{
    if(root == NULL)
        return 0;

    int lheight = height(root->left);
    int rheight = height(root->right);

    int ldia = diameter(root->left);
    int rdia = diameter(root->right);

    return MAX(1 + lheight + rheight, MAX(ldia, rdia));
}

Detecting a Loop in a Singly Linked List

The naive approach requires O(N^2) time and O(N) space. Basically you store all visited nodes, and compare each of them while traversing each node.

Hint: 
The best approach uses only O(N) time and O(1) space.

Solution:

The best solution runs in O(N) time and uses O(1) space. It uses two pointers (one slow pointer and one fast pointer). The slow pointer advances one node at a time, while the fast pointer traverses twice as fast. If the list has loop in it, eventually the fast and slow pointer will meet at the same node. On the other hand, if the loop has no loop, the fast pointer will reach the end of list before the slow pointer does.

bool hasLoop(Node *head) 
{
    Node *slow = head, *fast = head;

    while (slow && fast && fast->next) 
    {
        slow = slow->next;
        fast = fast->next->next;    
        
        if (slow == fast)
            return true;
    }
    return false;
}