Kth smallest element in a BST - C++ Code

Do inorder Traversal of BST and count number of elements traversed till now . As inorder traversal gives us the element in sorted Order, when count reaches k , we break out and Print the element.

/**
 * Definition for Binary Search Tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 * };
 */
int kthsmallest(TreeNode* root, int k) {
    if(root==NULL)
      return 0;
    stack<TreeNode*> s;
    bool complete=false;
    TreeNode* cur=root;
    int count=0;
    int val=0;
    while(!complete)
    {
        if(cur!=NULL)
        {
            s.push(cur);
            cur=cur->left;
        }
        else
        {
            if(!s.empty())
            {
                count++;
                cur=s.top();
                s.pop();
                if(count==k)
                {
                    val=cur->val;       
      break;
                }
                  cur=cur->right;
            }
            else
              complete=true;
        }  
    }
    return val;
}

Please comment if you find anything incorrect.

First Non Repeating Character in String

#include<iostream>
#include<string>
#include<memory>
#include<climits>
#define NUMBER_OF_CHARS 256
using namespace std;
struct CountIndex
{

 int count;
 int index;
};
char getFirstNonRepeatngCharacter(const string& str)
{
 char ch=' ';
 unique_ptr<CountIndex[]> ci(new CountIndex[256]());
 //Can also use shared_ptr
 //shared_ptr<CountIndex> ci(new CountIndex[256](),std::default_delete<CountIndex[]>());
 for(auto& it:str)
 {
  ci.get()[it].count++;
  if(ci.get()[it].count==1)
   ci.get()[it].index= &it - &str[0];
  else

   ci.get()[it].index= ci.get()[it].index;

 }
 int maxIndex=INT_MAX;

 for(int it=0;it<NUMBER_OF_CHARS;it++)
 {
  if(ci.get()[it].count==1 && ci.get()[it].index <maxIndex)
  {
   maxIndex= ci.get()[it].index;

  }
 }
 return maxIndex!=INT_MAX?str[maxIndex]:' ';
}
int main()
{    
 string str ;
 cin>>str;
 char ch=getFirstNonRepeatngCharacter(str);
 if(ch !=' ')
  cout<<" First Non repeating Character is "<< ch;
 else
  cout<<" No Repeating Character Exist ";


}

Folder Organizer

import os,errno
import sys,getopt
def main(argv):
    inputDir=''
    try:
        opts,args= getopt.getopt(argv,"hi:",["iDir="])
    except getopt.GetoptError:
        print 'DirectoryOrganizer.py -i <inputDirectory>'
        sys.exit(2)
    for opt,arg in opts:
        if opt == '-h':
            print 'DirectoryOrganizer.py -i <inputDirectory>'
            sys.exit()
        elif opt in ("-i","--iDir"):
            inputDir=arg
    files= os.listdir(inputDir)
    for file in files:
        extension= os.path.splitext(file)[1][1:]
        if extension:
            fileInputDir =inputDir+extension
            try:
                if not os.path.isdir(fileInputDir):
                    os.makedirs(fileInputDir)
                if not os.path.isfile(fileInputDir+"\\"+file):
                    os.rename(inputDir+file,fileInputDir+"\\"+file)
                else:
                    print "file with same name already exist in folder "+ fileInputDir+"\\"+file
            except OSError as e:
                if e.errno != errno.EEXIST:
                    raise

if __name__ == "__main__":
main(sys.argv[1:])

Allocating Void pointer memory using new operator

I was Implementing Generic List in C++ and was able to successfully allocate memory of void*  data using malloc ( malloc return void *) . But how about using new. Can we do below

void Test()
{
           void *f= new void[25];  //void *f=malloc(25); --> Works
           delete f;
}

The Answer is NO.
Because void has no size . How much space has to be allocated is not known.

So if you need to allocate memory using new use operator like

void Test()
{
          void *f=operator new(25);
          delete f;
}

Floyd Washall Algorithm Code in Java

We are given a directed graph and if we need to find out minimum distance between all the sources and destinations, we will use Floyd Warshall All Pair Shortest Path Algorithm.
Suppose we are given below graph

import java.util.*;
import java.lang.*;

public class Floyd
{
 final static int INF=Integer.MAX_VALUE;
 void Path(int graph[][],int n)
 {
   int minDistance[][]=new int[n][n];
   for(int i=0;i<n;i++)
   {
    for(int j=0;j<n;j++)
    {
     minDistance[i][j]=graph[i][j];
     
      
    }
   }
   for(int k=0;k<n;k++)
   {
    minDistance[k][k]=0;
   }
   
   for(int k=0;k<n;k++)
   {
    for(int i=0;i<n;i++)
    {
     for(int j=0;j<n;j++)
     {
          if(minDistance[i][j]>minDistance[i][k]+minDistance[k][j] && minDistance[i][k] !=INF && minDistance[k][j]!=INF)   
          minDistance[i][j]=minDistance[i][k]+minDistance[k][j];
     }
    }
   }
  
  printMatrix(minDistance,n);
  
 }
  void printMatrix(int minDistance[][],int n)
  {
   for(int i=0;i<n;i++)
   {
    for(int j=0;j<n;j++)
    {
         System.out.print(minDistance[i][j]+ "  ");
    }
    System.out.println();
   }
   
  }
 public static void main(String[] args)
 {
  int a[][]={{0,5,INF,10},
             {INF,0,3,INF},
             {INF,INF,0,1},
             {INF,INF,INF,0}};
  Floyd f=new Floyd();
  f.Path(a,4);
 }
}

Puzzle - Given 10 points in Space, create a Closed Figure with 4 points in each Line

I recently stumbled upon a problem in which we need to create a  Closed Figure from 10 points in Space with constraint that we must include 4 points in any Line we use to create the figure.
Think about the solution before Reading the solution

Solution :
Create a Star Like below which satisfies the requirement with Yellow dots representing points used

                         


Please comment if you have any other solution for this  

Static Assertion in C++11

Pre C++11 , we had  run time assertion function assert(). If assertion fails , a message will be written to console  and abort() will be called, terminating the program execution at run time. As assert() works only when control passes over the assertion, there is a possibility that a failing run-time assertion may lay dormant, undetected for long period of time.

#include<iostream>
#include<cassert>
class A
{
    int x;
    public:
       A(int a):x(a){}
       int getX(){ return x; }
};
int main()
{
   A a(17);
   assert(a.getX()<10);
   std::cout<< "Assertion a.getX()<10 pass";
   return 0;
}

Above program will compile fine, even though assert condition is false but we got the failure only at runtime.

Output:

assertion "a.getX()<10" failed: file "assert.cpp", line 16, function: int main()

Aborted (core dumped)

Therefore C++11 introduced Compile time Assertion functionality using static_assert(). As Compilation will fail, developer will be aware of the problematic portion of the code and track bugs early in development phase. Also For Example, if some functionality of code critically depends on size of int to be exactly 4 bytes, we can use static_assert like below

#include<iostream>
class A
{
    public:
    static const int b = 3;
};
int main()
{
    static_assert(A::b > 4, "A::bar is less than 4");
    static_assert(sizeof(int) == 4,"size of integer is not 4 bytes");
}

static_assert can be also used to check whether class is default constructable or can be constructed with certain parameters or  can be copied or is movable or assignable using trivial/non trivial constructors.

#include<iostream>
class A
{
    int x;
    public:
       A():x(0)        
       {

       }
       A(int a):x(a)
       {

       }
};
int main()
{
    static_assert(std::is_constructible<A>::value, "Class is not constructible");
    static_assert(std::is_trivially_constructible<A>::value," Class is not trivially constructible ");
    static_assert(std::is_constructible<A,char,int>::value, "Class is not constructible with char,int ");
 static_assert(std::is_trivially_copy_constructible<A>::value,"Class is not trivially copy constructible");  
    return 0;
}

Output:

static_assert_constructors.cpp: In function ‘int main()’:

static_assert_constructors.cpp:20:9: error: static assertion failed:  Class is not trivially construtible

         static_assert(std::is_trivially_constructible<A>::value," Class is not trivially construtible ");

         ^

static_assert_constructors.cpp:21:5: error: static assertion failed: Class is not constructible with char,int

     static_assert(std::is_constructible<A,char,int>::value, "Class is not constructible with char,int ");

Few Other standard values introduced in C++11, that  you can use with static_assert are:

• std::is_move_assignable<T>::value,
• std::is_nothrow_copy_constructible<T>::value
• std::is_trivially_copyable<T>::value
• std::is_copy_assignable<T>::value
• std::is_default_constructible<T>::value
• std::is_assignable<T>::value