C++11 Threads

C++11 has introduced std::thread. The important thing to note about this class is that, it does not have copy constructor and copy assignment, but has move constructor and move assignment operator.

Below is the simple example I found

 #include <iostream>  
 #include <thread>  
 #include <vector>  
 #include <atomic>  
   
 std::atomic<bool> ready(false);  
 std::atomic_flag winner = ATOMIC_FLAG_INIT;  
   
 void count1m(int id) {  
      while (!ready)  
           std::this_thread::yield();  
   
      for (volatile int i = 0; i < 1000000; ++i) {  
           // just count;  
      }  
   
      if (!winner.test_and_set()) {  
           std::cout << "thread #" << id << "won!\n";  
      }  
 }  
   
 int main() {  
      std::vector<std::thread> threads;  
      std::cout << "spawning 10 threads that count to 1 million...\n";  
   
      for (int i = 1; i <= 10; ++i)  
           threads.push_back(std::thread(count1m, i));  
   
      ready = true;  
      for (std::thread& thread : threads)  
           thread.join();  
   
      getchar();  
 }  

BST using smart pointers and templates in C++

I am here trying to implement BST using smart pointers and template. For implementation of BST, I will be creating following classes.
1. BinTreeNode
2. BinTree
Also, In order to test I will be writing simple unit test file (source.cpp)

1. BinTreeNode.h

 #pragma once  
 #include <memory>  
 #include <iostream>  
 #include <string>  
 template <class T>  
 class BinTreeNode;  
 template <class T>  
 std::ostream& operator<<(std::ostream& out, const BinTreeNode<T>& binNode);  
 template <class T>  
 class BinTreeNode {  
 public:  
      T m_data;  
      std::shared_ptr<BinTreeNode> m_spleftNode, m_sprightNode;  
      std::weak_ptr<BinTreeNode> m_wpparentNode;  
      BinTreeNode(T data) :m_data(data), m_spleftNode(nullptr), m_sprightNode(nullptr) {}  
      ~BinTreeNode() {}  
      bool operator==(const BinTreeNode<T>& binNode) {  
           if (m_data == binNode.m_data)  
                return true;  
           return false;  
      }  
      bool insertNode(std::shared_ptr<BinTreeNode<T>> binNode) {  
           if (binNode->m_data > m_data) {  
                if (m_sprightNode == nullptr)  
                     m_sprightNode = binNode;  
                else  
                     m_sprightNode->insertNode(binNode);  
           }  
           else if (binNode->m_data == m_data) {  
                std::cout << "Data already present!!\n";  
                return false;  
           }  
           else {  
                if (m_spleftNode == nullptr)  
                     m_spleftNode = binNode;  
                else  
                     m_spleftNode->insertNode(binNode);  
           }  
           return true;  
      }  
      friend std::ostream& operator<< <>(std::ostream& out, const BinTreeNode<T>& binNode);  
 };  
 template <class T>  
 std::ostream& operator<<(std::ostream& out, const BinTreeNode<T>& binNode) {  
      if (binNode.m_spleftNode != nullptr)  
           out << "[Left: " << *(binNode.m_spleftNode) << " ] ";  
      out << "(" << binNode.m_data << ")";  
      if (binNode.m_sprightNode != nullptr)  
           out << " [Right: " << *(binNode.m_sprightNode) << " ]";  
      return out;  
 }  

2. BinTree

#pragma once  
 #include <iostream>  
 #include <memory>  
 #include "BinTreeNode.h"  
 template <typename T>  
 class BinTree;  
 template <typename T>  
 std::ostream& operator<<(std::ostream& out, const BinTree<T>& binTree);  
 template <typename T>  
 class BinTree {  
 public:  
      std::shared_ptr<BinTreeNode<T> > m_sproot;  
      BinTree() {}  
      ~BinTree() {}  
      bool insertdata(T data) {  
           std::shared_ptr<BinTreeNode<T>> spbinNode(new BinTreeNode<T>(data));  
           if (m_sproot == nullptr) {  
                m_sproot = spbinNode;  
                return true;  
           }  
           std::shared_ptr<BinTreeNode<T>> binNode(new BinTreeNode<T>(data));  
           return m_sproot->insertNode(binNode);  
      }  
      friend std::ostream& operator<< <>(std::ostream& out, const BinTree<T>& binTree);  
 };  
 template <typename T>  
 std::ostream& operator<<(std::ostream& out, const BinTree<T>& binTree) {  
      out << *(binTree.m_sproot);  
      return out;  
 }  

3. Source.cpp

#include <iostream>  
 #include <string>  
 #include "BinTreeNode.h"  
 #include "BinTree.h"  
 int main() {  
      BinTree<std::string> bintree;  
      bintree.insertdata(std::string("text"));  
      bintree.insertdata(std::string("binary"));  
      bintree.insertdata(std::string("search"));  
      bintree.insertdata(std::string("tree"));  
      bintree.insertdata(std::string("implementation"));  
      std::cout << bintree;  
      getchar();  
 }  

[Euler Problem]: Finding the minimum sum

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.

131 673 234 103 18 201 96 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 37 331

This can be solved by an easy application of the DP.
A nice variation of the  above problem is to find the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297.

131 673 234 103 18 201 96 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 37 331

Here is my code. I applied Dijkstra in order to solve this problem.


#include<stdio.h>
#include<conio.h>
struct room
{
    int x,y;
    int count;
};

struct room heap[5000];
int size;

int board[71][71];
int count[71][71];
int flag[72][72];

void insert_heap(int x,int y,int count)
{
    int i;
    struct room temp;
    heap[++size].x = x;
    heap[size].y = y;
    heap[size].count = count;
    i = size;
    while(i>1)
    {
        if(heap[i].count<heap[i/2].count)
        {
            temp = heap[i];
            heap[i] = heap[i/2];
            heap[i/2] = temp;
            i/=2;
        }  
        else
           break;
    }  
}

struct room remove_heap()
{
    int i = 1,loc,min;
    struct room minroom = heap[1],temp;
    heap[1] = heap[size--];
   
    while(i<size)
    {
        loc = i;
        min = heap[i].count;
        if(2*i<=size)
        {
            if(heap[2*i].count< min)
            {
                loc = 2*i;
                min = heap[2*i].count;
            }  
        }
        if(2*i+1<=size)
        {
            if(heap[2*i+1].count< min)
            {
                loc = 2*i+1;
            }
        }
       
        if(loc!=i)
        {
            temp = heap[i];
            heap[i] = heap[loc];
            heap[loc] = temp;
            i = loc;
        }
        else
           break;        
    }
   
    return minroom;
   
}
   

int main()
{
    int rows,cols;
    int targetx,targety,threshhold;
    struct room min;
    scanf("%d",&rows);
    cols=rows;
    int i,j,k;
    int minx,miny;
    for(i=1;i<=rows;i++)
    {
        for(j=1;j<=cols;j++)
        {
            scanf("%d",&board[i][j]);
        }  
    }
    targetx=rows;
    targety=cols;
    for(i=0;i<=rows+1;i++)
    {
        flag[i][0] = 1; flag[i][cols+1] =1;
    }  
    for(j=0;j<=cols+1;j++)
    {
        flag[0][j] = 1; flag[rows+1][j] =1;
    }  
     
    insert_heap(1,1,board[1][1]);
    count[1][1] = board[1][1];
    flag[1][1] = 1;  
   
    while(size!=0)  
    {
        min = remove_heap();
        minx = min.x; miny = min.y;
       
        if(minx == targetx && miny == targety )
            break;
        if(flag[minx-1][miny]!=1)
        {
            insert_heap(minx-1,miny, min.count + board[minx-1][miny]);
            count[minx-1][miny] = min.count + board[minx-1][miny];
            flag[minx-1][miny] = 1;
        }
        if(flag[minx+1][miny]!=1)
        {
            insert_heap(minx+1,miny, min.count + board[minx+1][miny]);
            count[minx+1][miny] = min.count + board[minx+1][miny];
            flag[minx+1][miny] = 1;
        }
        if(flag[minx][miny-1]!=1)
        {
            insert_heap(minx,miny-1, min.count + board[minx][miny-1]);
            count[minx][miny-1] = min.count + board[minx][miny-1];
            flag[minx][miny-1] = 1;
        }
        if(flag[minx][miny+1]!=1)
        {
            insert_heap(minx,miny+1, min.count + board[minx][miny+1]);
            count[minx][miny+1] = min.count + board[minx][miny+1];
            flag[minx][miny+1] = 1;
        }      
    }
   
            printf("%d\n",min.count);
    getch();
    return 0;  
 
}  

[Amazon Online Test]: Finding the in-order successor

Given a binary search tree with the following node structure.
struct tree
{ int data;
  struct tree *left, *right , *next;
};
The next pointer of each pointer is pointing to NULL. Write a code to initialize the next pointer of each node to its in-order successor.

Here is my code, I have not tested it. Hope it works. Time complexity is O(n).

int save=NULL;
void Setsuccessor(struct tree *root)
{
           if(root==NULL)
              return;

          Setsuccessor(root->left);
         
           if(save!=NULL)
              save->next=root;
           save=root;

         Setsuccessor(root->right);
}
         

[Amazon Interview]: Finding the all possible sets.!!!

Q. Given an array of positive integers, find all possible sets that sum up to a given value K.

Here is my code..


#include<stdio.h>
#include<conio.h>
#define N 10
#define INF 12345678 //ignore
#define max(a,b) a>b?a:b

int M[1000][100];
int a[N+1]={INF,1,2,3,4,5,6,7,8,9,10};
 
void print(int i, int j,int *arr, int k)
{
     if(i<0)
      return;
     
     if(j==0)
     {
             int idx;
           
             for(idx=0;idx<k;idx++)
              printf("%d  ",arr[idx]);
              printf("\n");
              return;
     }
   
     if(j>=a[i])
     { if(M[i-1][j-a[i]])
       { arr[k]=a[i];
         print(i-1,j-a[i],arr,k+1);
       }
     }
   
     if(M[i-1][j])
      print(i-1,j,arr,k);
}

int main()
{
    int i,j,k,K=10;
    int arr[1000];
   
    for(i=0;i<=N;i++)
     M[i][0]=1;
   
    for(k=1;k<=K;k++)
     M[0][k]=0;
   
    for(i=1;i<=N;i++)
     for(k=1;k<=K;k++)
      M[i][k]=max(M[i-1][k-a[i]],M[i-1][k]);
     
    print(N,K,arr,0);
    getch();
    return(0);
}

Amazon written Test Question:

Here is one of Amazon's written Question which one of my friend got.
1. Convert an array "a1a2a3....b1b2b3...c1c2c3..." to "a1b1c1a2b2c2a3b3c3..." in-place.
 
Here is my code with time complexity O(n) and space complexity O(1).
This code works for both positive and negative numbers



#include<stdio.h>

#define N 4
int a[3*N]={1,2,3,4,5,6,7,8,9,10,11,12};
int main()
{
    int i,min,max,band,j,k,save,temp;
    //find min & max O(n).
    for(i=0;i<3*N;i++)
    { if(a[i]<min)
       min=a[i];
      if(a[i]>max)
       max=a[i];
    }
    band=max-min+1;
   
    // code to arrange the elements
    for(i=0;i<3*N;i++)
    {
              if(a[i]<=max)
              {
                           j=k=i;
                           save=a[i];
                           while(1)
                           {
                              if(j<N)
                                k=3*j;
                              else if(j<2*N)
                                k=3*(j-N)+1;
                              else
                                k=3*(j-2*N)+2;
               
                                temp=a[k];
                                a[k]=save+band;
                                save=temp;
               
                                j=k;
               
                                if(k==i)
                                 break;
                             }
                }
     
    }
   
    for(i=0;i<3*N;i++)
    { a[i]=a[i]-band;
      printf("%d  ",a[i]);
    }    
   
    return(0);
}

Microsoft Intern Experience

The process was followed by 1 written and 1 group process and 3 interviews(2 tech + 1 HR).

Written test:

 There were 5 questions. 

1. Extended Josephus problem

2. To find errors in a given program.

3. To detect loop in a linked list.

4. Writing test cases.

5. Suggest any application for desktop.

Group process:

There were 24 students shortlisted after first round. They gave us questions on a white board. It felt like a buzzer round. questions were very easy.

1. check if a given tree is balanced or not.

2. remove duplicates in given string.

1st technical interview:(60-90min)

After the group process, they shortlisted 10 students. The first question I was given was to write code for "MemMove" function. I had not heard that function before. so I asked him to explain it. He said its similar to "memcpy". I wrote code for memcpy. Now, he said to test the code. I wrote all test cases and got the limitation of memcpy function. Now he said to code it again and i did perfectly.
The second question he asked was based on counting sort problem. that was also easy one.

2nd Technical interview:(75-90min)
6 students got selected in first interview. I was also one of them :). I was asked the following question in my second interview.
Given a binary tree (root) and two node a,b in binary tree. find the nearest ancestor between them. After solving this he changed the problem to find the sum of all elements in path from a to b. Then he said to write the test case for this problem.

3rd HR interview: (10-15min)
In HR round, interviewer asked few definitions and formulas related to graphs and trees. He checked my written again paper and asked my logic for 1st question. Then he asked about myself and some project regarding questions.

Finally I dint get selected.