CareerCup

Sorry, I didn't understand you. What do you want to say.

void arrange(int array[]){
	int len = sizeof(array)/ sizeof(array[0]);
	int low, mid;
	for(low = mid = 0; mid < len; ) {
		array[mid] == 0 ? swap(&array[low++], &array[mid++]) : mid++;
	}
}

It is bad answer. You are using extra memory. What if you have to do that in-place.

See my answer below

Guys, What's the fuss ??

Check my solution below...upvote it.

:-)

I think you have to use min priority queue or min heap.

Find the 3 largest number in array viz. n1 > n2 > n3 and 2 smallest number in array viz m1 < m2.

The largest product will be either n1 * n2 * n3 or n1 * m1 * m2

Take care of 0

This is tree diameter problem.

Idea is max distance will be in left subtree or in right subtree or it will pass through root.
We can do it recursively.

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

       int leftHeight = height(root->left);
       int rightHeight = height(root->right);
       if(leftHeight > rightHeight) {
              return leftHeight + 1;
       } else {
              return rightHeight + 1;
       }
}

int diameter(struct node* root) {
       if(root == NULL) {
              return 0;
       }
       int lHeight = height(root->left);
       int rHeight = height(root->right);

       int lDiameter = diameter(root->left);
       int rDiameter = diameter(root->right);

      return max(lHeight + rHeight + 1, max(lDiameter, rDiameter));
}

@eugene.yaravoi :- In my initial days, I never cared about integer overflow condition. My sole purpose used to be just solve the problem. So, yes I also had made this mistake in my college days. But, later on, I learned that overflow cases can occur. So, now I've become more attentive on these kind of details also.

@ gunsnroses23k :- You should never calculate mid like above.

Consider a scenario where low = 5, high = 7.
Note that these are numerals above are representing index of array not elements of array.

Ideally - our mid should be index no 6
But according to your code, it would be 1, which is wrong.
Now you can calculate mid like this

mid = (low + high) / 2

You will get correct answer which is 6. But this can fail when the sum of low and high exceeds the integer limit defined for that data type in that language.

So, the correct way is

mid = low + (high - low) / 2

Ya it is integer overflow case.

Instead one should do like

low + (high - low) / 2

Because it is a straight Binary Search question which is basic algorithm that first year students study in their college and a company of eBay's repute asking it, without any twist in words or twist in application of binary search.

So, I was shocked.

Are you joking ???

Ebay asked this question ???

Though questions does not seems clear to me. I assume that you want to convert one string to another by rotating it.

In this case append first string with itself and find index of start of the second string in it. That is the no of shifts required.

@eugene.yarovoi: In worst case it will be O(n), but in average case it will be O(log n).

It would be fun, if the problem would have been like this

A[1] <= A[2] <= ..... <= A[n]

Then it would have become more complex because of duplicates.

/* This function returns the leftmost child of nodes at the same level as p.
   This function is used to getNExt right of p's right child
   If right child of is NULL then this can also be sued for the left child */
struct node *getNextRight(struct node *p)
{
    struct node *temp = p->nextRight;

    /* Traverse nodes at p's level and find and return
       the first node's first child */
    while (temp != NULL)
    {
        if (temp->left != NULL)
            return temp->left;
        if (temp->right != NULL)
            return temp->right;
        temp = temp->nextRight;
    }

    // If all the nodes at p's level are leaf nodes then return NULL
    return NULL;
}

/* Sets nextRight of all nodes of a tree with root as p */
void connect(struct node* p)
{
    struct node *temp;

    if (!p)
      return;

    // Set nextRight for root
    p->nextRight = NULL;

    // set nextRight of all levels one by one
    while (p != NULL)
    {
        struct node *q = p;

        /* Connect all childrem nodes of p and children nodes of all other nodes
          at same level as p */
        while (q != NULL)
        {
            // Set the nextRight pointer for p's left child
            if (q->left)
            {
                // If q has right child, then right child is nextRight of
                // p and we also need to set nextRight of right child
                if (q->right)
                    q->left->nextRight = q->right;
                else
                    q->left->nextRight = getNextRight(q);
            }

            if (q->right)
                q->right->nextRight = getNextRight(q);

            // Set nextRight for other nodes in pre order fashion
            q = q->nextRight;
        }

        // start from the first node of next level
        if (p->left)
           p = p->left;
        else if (p->right)
           p = p->right;
        else
           p = getNextRight(p);
    }
}

I think function will take only 'A' and 'N' as input. If this is the case then it is simple.

Sort the Array [O(nlogn)]
Put one pointer at the beginning and one pointer at the end.
Now add cubes of two numbers pointed by two pointers.
If sum is greater than 'A', then move last pointer one step towards left side.
If sum is smaller than 'A', then move first pointer one step towards right side.
Otherwise, you will have one pair.

But my concern is there will only be one pair if all numbers are positive as given in question.

bool match(char *first, char * second)
{
    // If we reach at the end of both strings, we are done
    if (*first == '\0' && *second == '\0')
        return true;
 
    // Make sure that the characters after '*' are present in second string.
    // This function assumes that the first string will not contain two
    // consecutive '*'
    if (*first == '*' && *(first+1) != '\0' && *second == '\0')
        return false;
 
    // If the first string contains '?', or current characters of both
    // strings match
    if (*first == '?' || *first == *second)
        return match(first+1, second+1);
 
    // If there is *, then there are two possibilities
    // a) We consider current character of second string
    // b) We ignore current character of second string.
    if (*first == '*')
        return match(first+1, second) || match(first, second+1);
    return false;
}

There is recursion in method2.

@Neha: You are wrong. Integer is of 4 bytes. So it can hold upto 32 bit info.

@hraha123: And still you made mistake. Find and correct it.

KMP

In case of two missing numbers, you are taking product. I think it is wrong as it will produce wrong result if our final product goes out of bound of integers. (Integer Overflow)

void print(int N)
{
    int arr[N];
    arr[0] = 1;
    int i = 0, j = 0, k = 1;
    int numJ, numI;
    int num;
    for(int count = 1; count < N; )
    {
       numI = arr[i] * 2;
       numJ = arr[j] * 5;
       if(numI < numJ)
       {
           num = numI;
           i++;
       }
       else
       {
           num = numJ;
           j++;
       }
       if(num > arr[k-1])
       {
          arr[k] = num;
          k++;
          count++;
       }
    }
    
    for(int counter = 0; counter < N; counter++)
    {
        printf("%d ", arr[counter]);
    }
}

Above answer is posted by me.

Ok.

If you look closely then you can see that, we are adding and removing each element in the deque, exactly once. So, it will be O(n)

The element which is repeated more than half times is also called as majority element which can be found by Moore's Voting algorithm.

This is a two step process.
1. Get an element occurring most of the time in the array. This phase will make sure that if there is a majority element then it will return that only.
2. Check if the element obtained from above step is majority element.

------------------------------------------------------------------------------------------------

/* Function to find the candidate for Majority */
int findCandidate(int a[], int size)
{
    int maj_index = 0, count = 1;
    int i;
    for(i = 1; i < size; i++)
    {
        if(a[maj_index] == a[i])
            count++;
        else
            count--;
        if(count == 0)
        {
            maj_index = i;
            count = 1;
        }
    }
    return a[maj_index];
}
  
/* Function to check if the candidate occurs more than n/2 times */
bool isMajority(int a[], int size, int cand)
{
    int i, count = 0;
    for (i = 0; i < size; i++)
      if(a[i] == cand)
         count++;
    if (count > size/2)
       return 1;
    else
       return 0;
}

I do not think that there is any complex thing to explain in my code.
I am using a deque whose front will always contain maximum element.
First I am putting first K element's index in my deque along with the condition such that, If coming element is less than last element of deque then there is no need to store its index.

Then in second while loop, I am checking if current maximum goes out of the window or not.

Third while loop is similar to first one.

I don't know what is difficult to understand in this code. People wants everything to be served to them ready to eat. Please apply your mind to understand the code by running over some example. This is how you will grow.

Downvoting just for fun is not good for such a great platform provided to us.

Why my answer is downvoted?

This can be done in O(n) using a deque whose front will always hold maximum in current window. Space Complexity - O(k)
------------------------------------------------------------------------------------------------------------

void maxInWindow(int* arr, int k)
{
      std::deque<int> Qi(k);
      int i;
      for(i = 0; i < k; i++)
      {
            while(!Qi.empty() && arr[i] >= arr[Qi.back()])
            {
                    Qi.pop_back();
            }
            Qi.push_back(i);
      }

      for( ; i < length; i++)
      {
              std::cout << arr[Qi.front()] << std::endl;
              while(!Qi.empty() && i - k >= Qi.front())
              {
                     Qi.pop_front();
               }

               while(!Qi.empty() && arr[i] >= arr[Qi.back()])
               {
                    Qi.pop_back();
               }
               Qi.push_back(i);
      }
     std::cout << arr[Qi.front()] << std::endl;
}

Is it not a deadlock problem.

Use Banker's Algorithm. It does exactly this thing

Its time complexity is exponential.
Also if I am understanding your logic, there is one bug.

Second instance of "part_sum += a[cur];"
should not be there.

Who said to remove constants. Use look up table.

Time complexity can be reduced.

Yes the problem is different but it can be modified.

www[dot]geeksforgeeks[dot]org/tug-of-war/

:)

Trick is to start from end.

KMP

So you started reading cracking the coding interview :P

The trick is to start from the end.

We have to return level with maximum number of node. In other words we have to find width of the tree. Traverse the tree in pre-order fashion.

int getMax(int count[], int n)
{
     int max = arr[0];
     int i;
     for (i = 0; i < n; i++)
     {
         if (arr[i] > max)
            max = arr[i];
     }
     return max;
}

int getMaxWidthRecur(struct node* root, count, level)
{
      if(root == NULL)
      {
           return 0;
       }
       count[level]++;
       getMaxWidthRecur(root->left, count, level + 1);
       getMaxWidthRecur(root->right, count, level + 1);
}

int getMaxWidth(struct node* root)
{
     int height = getHeight(root);
     int* count = (int *) calloc(sizeof(int), height);
     int level = 0;
     getMaxWidthRecur(root, count, level);
     return getMax(count, height);
}

@beg: Total no of paths will be stored in our static variable total_ways.

It can be solved with dynamic programming. Assuming that you can move either right or down which can be a good point to discuss with interviewer. Also this is recursive solution.

Suppose you are at position N, M you can come to it either by N-1, M or by N, M-1. This way we can work upwards to find total no of ways.

static int total_ways = 0;
class Point{
     int x,
     int y,
     Point(int a, int b)
     {
          x = a;
          y = b;
      }

boolean getPath(int x, int y, ArrayList<Point> path, Hashtable<Point, Boolean> cache)
{
      Point p = new Point(x, y);
      if(cache.containsKey(p))
      {
           return cache.get(p);
      }
      path.add(p);
      if(x == 0 && y == 0)
      {
           total_ways++;
           return true;
      }
      boolean success = false;
      if(x >= 1 && isFree(x - 1, y)
      {
           success = getPath(x - 1, y, path, cache);
      }
      
      if(!success && y >= 1 && isFree(x, y - 1))
     {
           success = getPath(x, y - 1, path, cache);
      }
      if(!success)
      {
           path.remove(p);
      }
      cache.put(path, success);

      return success;
}

Its a knapsack problem where we have to minimize value instead of maximizing it.

0-1 knapsack problem - If it is mandatory to pick all books of given price.

Fractional knapsack problem - If it is allowed to pick any quantity of books of given price.

This is very good point to discuss with your interviewer.

This can be done using quick sort.

Randomly pick one player (A) then place players who lost to A at right hand side and players who won to A at left hand side.

Repeat above step. At the end we will get the result.

Comments welcome

/* Given a stream of numbers and index, find the digit at that index 
 * e.g. 01234567891011121314 index = 15, answer is 1 (of 12)
 */

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<math.h>

/* Function to find number of digits */
int findNoOfDigits(int* index)
{
    int no_of_digits = 1;
    if(*index <= 10)
    {
        return no_of_digits;
    }
    int num = 90;
    int temp = *index - 10;
    *index = temp;
    while(temp > 0)
    {
        no_of_digits++;
        temp -= (num * no_of_digits);
        if(temp < 0)
        {
            break;
        }
        *index = temp;
        num *= 10;
    }
    return no_of_digits;
}

/* Function to find value at some position */
int position(int index)
{
    int no_of_digits = findNoOfDigits(&index);
    printf("%d %d\n", no_of_digits, index);
    
    if(no_of_digits == 1)
    {
        return index - 1;
    }
    else
    {
        int temp = no_of_digits - 1;
        int num  = pow(10, temp);
        int rem = index % no_of_digits;
        int quotient = index / no_of_digits;
        num += quotient;
        if(rem == 0)
        {
               return (num % 10);
        }
        else
        {
               int digit;
               int count = no_of_digits + 1 - rem;
               while(count > 0)
               {
                   count--;
                   digit = num % 10;
                   num = num / 10;
               }
               return digit;
        }
    }
}

/* Main driver function */
int main(void)
{
    int index;
    scanf("%d", &index);
    printf("\n");
    printf("%d",position(index));
    getch();
    return 0;
    
}

Can you explain the logic ?

How about using KMP for each pattern.

If the path can start anywhere. In that case, we can make a small modification. On every node, we look up to see if we have found the sum.
When we recurse through each node n, we pass the functin the full path from root to n.This function then adds the nodes along the path in reverse order from n to root. When the sum of each subpath equals sum, then we print the path.

void findSumUtil(Treenode node, int sum, int[] path, int level)
{
     if(node == null)
    {
         return;
    }
    path[level] = node.data;
    int t = 0;
    for(int i = level; i >= 0; i--)
    {
         t += path[i];
         if(t == sum)
         {
              print(path, i, level);
    }
   
    findSumUtil(node.left, sum, path, level + 1);
    findSumUtil(node.right, sum, path, level + 1);

    path[level] = Integer.MIN_VALUE;
}


void findSum(Treenode  node, int sum)
{
      int depth = depth(node);
      int[] path = new int[depth];
      findSumUtil(node, sum, path, 0);
}

void print(int[] path, int start; int end)
{
     for(int i = start; i <= end; i++)
    {
         printf("%d    ", path[i]);
    }
}

int depth(Treenode node)
{
     if(node == NULL)
     {
            return 0;
     }
     else
     {
           return (1 + Math.max(depth(node.left), depth(node.right));
     }
}

I think it would be top-down only. I will post my solution after sometime.

Mask all odd bits with 10101010 in binary (which is 0xAA), then shift them left to put them in the even bits. Then, perform a similar operation for even bits. This takes a total 5 instructions.

public static int swapOddEvenBits(int x) {
    return ( ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1) );
}