Interview questions DS

1. Write a program to add sum of all left most leaf node in a tree.

In this example you have to add the nodes 2,5 & 4

Answer:

enum direction{
    left=1,
    right
};


int calculateleftmost(struct tree* root, direction d)
{
    int  ls=0, rs =0;
    if(root->left == NULL && root->right == NULL)
    {
        if(d == left)
        {
            return root->data;
        }
    }
    if(root == NULL)
        return 0;
    ls = calculateleftmost(tree->left, left);
    lr = calculateleftmost(tree->right, right)
    return ls+rs;
}


2.  How to get the Kth largest number in an unsorted array

Answer:

soluton 1: 2 nested loop
     outer loop is from 0-K & innerloop is from 0-n & use bubble sort the    array[n-k] is the answer.

order is k*n
solution 2:  use K loops one after another then get number arr[n-3].
solution 3: traverse the array & create a BST. in that tree perform the tree traverse operation in (right, root left ) order then find the 3rd most element
solution 4: create a temporary flag array having maximum limit of the current array. traverse the current array and get the value & mark the flag array on the corresponding index. Then traverse the flag array from maximum range to down when the flag is 'true' then increase the counter. When counter is 3 that value is 3rd largest number of the array
This approach is better is we compare the performance as it take o(n) but this solution contain extra space.


3. count number of 1 bits in a number
Answer: using right shift operation and '&' operation with 1. :)



 

Comments

Post a Comment

Popular posts from this blog

STL Questions

1. Sorting a vector of custom objects     a)Using operator()         struct MyStruct {             int key;             std::string str;             MyStruct(int k, int s) : key(k), str(s) {}         };         struct less_than{             inline bool operator()(const MyStruct &s1, const MyStruct &b)             {                 return s1.key<s2.key;             }         };         std::vector<MyStruct> vec;         vec.push_back(MyStruct(4, "a")); ...
Read more

Producer Consumer problem using mutex

  #include<stdio.h> #include<pthread.h> #include<stdlib.h>   // Max buffer size user for producing #define buff_sz 10   // buffer index would be the current index volatile int buff_idx = -1; // buffer used to produce item volatile char *buff = NULL;;   // Initialization and declaration of muetxt and condition variables pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER; pthread_cond_t buff_not_full = PTHREAD_COND_INITIALIZER; pthread_cond_t buff_not_empty = PTHREAD_COND_INITIALIZER;   // Consumer thread void *Consumer() {          while (1)          {                  // Taking lock to avoid race condition                  pthread_mutex_ lock(&m...
Read more

Interview questions

C++ 1. How to implement vector Answer: http://codefreakr.com/how-is-c-stl-implemented-internally/ 2. how to implement string class Answer: http://www.ccs.neu.edu/home/sbratus/com1101/mystring.txt 3. How to implement list in STL  Answer: http://codefreakr.com/how-is-c-stl-list-implemented-internally/ 4. how many casting are there in c++ & their corresponding use. Answer: http://studymustgoon.blogspot.in/2017/05/casting-in-c.html 5. what is copy constructor, write the syntex. Why we pass reference in copy constructor. 6. Is it possible virtual constructor and virtual copy constructor. 7. why virtual destructor. 8. In copy constructor can we pass pointer as an argument? Linux 1. Difference between mutex & semaphore 2. write a code for producer consumer problem. 3. in which scenario we use semaphore. C 1. how realloc is implemented.  Answer: this concept is just like malloc implementation.
Read more