CareerCup

Hi All

This is just a slightly different take on the merge routine in merge sort. It does not require recursion nor does it require dynamic programming. It is implemented iteratively, with the efficiency being O(n+m), where n and m are the sizes of the two arrays.

The basic idea is as follows:
1) Let A and B denote the two arrays
2) Let idx1 be the current index of the array A, and let idx2 be the current index of array B
3) While the element at the current index of A (i.e. A[idx1]) is less then the element at the current index of B (B[idx2]) increment idx1, and add each element to a running total (call it sumA)
4) Now that A[idx1] > B[idx2], increment idx2 of B until B[idx2] is not less than A[idx1], and also add it to a running total (call it sumB)
5) If at this point, A[idx1] is equal to B[idx2], we have found our intersection point. So add the maximum of sumA and sumB i.e. max(sumA,sumB) to the totalresult. Set sumA and sumB to zero, and repeat the whole process until all the elements in A and B have been examined.

The code for the above is as follows:

int getMax(vector<int>& A, vector<int>& B) {
    int idx1 = 0,
        idx2 = 0,
        sumA = 0,
        sumB = 0,
        total = 0;

    while (idx1 < A.size() || idx2 < B.size()) {
        while (idx2 >= B.size() && idx1 < A.size() || idx1 < A.size() && A[idx1] < B[idx2]) 
            sumA += A[idx1++];

        while (idx1 >= A.size() && idx2 < B.size() || idx2 < B.size() && B[idx2] < A[idx1]) 
            sumB += B[idx2++];

        if (A[idx1] == B[idx2]) {
            if (idx1 < A.size()) sumA += A[idx1++];
            if (idx2 < B.size()) sumB += B[idx2++];
            total += max(sumA, sumB);
            sumA = sumB = 0;
        }
    } 

    total += max(sumA, sumB);

    return total;
}

Hi Guys

I normally don't comment on these questions, but I feel everyone has it wrong here. In a Pre-Order traversal where all non-leaf nodes have two children, what property can on extract? The thing to look for is that if a node value decreases, then there must be an increase somewhere. In other words, if a parent node has a left child (a decrease in value), then there must also be an increase value (a right child) in order for that parent to have two children. In short, if you count the number of times a node increases, and the number of times a node decreases, then in a tree with each non-leaf node that has two children, it should balance out perfectly.

Here is the algorithm

bool checkOneChild(vector<int> preOrderList) {
	if (preOrderList.size() == 1) return true; //Only root node is present, so return true;
	int increaseDecreaseCounter = 0; //long name, I know
	int prev = preOrderList[0];	

	for (int i=1; i < preOrderList.size(); i++) {
		if (preOrderList[i] >= prev)
			increaseDecreaseCounter++;
		else
			increaseDecreaseCounter--;
		
		prev = preOrderList[i];
	}

	return (increaseDecreaseCounter == 0);
}

Here is a solution (recursive of course - its really awful to do a permutation problem if one does not user recursion) without string manipulation.

It is in C++. I feel that this would be the answer that would score more brownie points in an interview:

#include <vector>
#include <iostream>

using namespace std;

void permutations(int s, int e, vector<int>& prfx) {
    if (!e) {
        for (int i=0; i < prfx.size(); i++)
            cout << prfx[i];
        cout << endl;
    }

    for (int i=s; i < 10; i++) {
        prfx.push_back(i);
        p(s+1, e-1, prfx);
        prfx.pop_back();
    }
}

int main() {
	vector<int> t;
	permutations(0,4, t);
	return 0;
}

This question (as is usual on any BST problem) is made for recursion. The trick is to pass a copy of the previous node to all subsequent recursive calls. Of course, when you start, there is no previous, so it should be set to NULL.

Here is the code:

Node * treeToDll(Tree* r, Node* pr) {
	if (!r) //The previous node is returned 
               return pr;
  
        Node* prev = treeToDll(r->left, pr);
        Node* c = new Node(r->val);
        if (prev) prev->next = c;
        c->prev = prev;

	return treeToDll(r->right, c); // Return the rightmost node, but if it does not
                                                     // exist then return the current node (c)
}

Yes, it's that simple! I urge you guys to try this code out (by hand or even better in any tree example that you could whip up). You will see that it works beautifully.

The basic premise is the same: Recursively traverse to the right, then start counting down until you have the desired node. Here is a c++ version:

Node *getK(Node* r, int &k) {
	if (!r) return NULL;
	Node* ret = getK(r->right, k);
	if (ret) return ret;
	if (!k) return r;
	k--; //remember, k is a reference, so this value will propogate to other calls
	return getK(r->left, k);
}

This question can be done very simply in three lines if you use recursion. The basic method is to go as right as possible down the tree, and only when you can't go anymore right, then start adding the sum. At the right most node (where we are starting to add the sum), traverse to the left child (if it exists).

Here is the code (in C++)

int rwsg(Node *r, int sg) {
	if (!r) return sg;
	r->val += rwsg(r->right, sg);
	return rwsg(r->left, r->val);
}

int main() {
	rwsg(r, 0); //start with 0 for sg
}

The above looks really simple, but it works. Take the examples given above and go over them using this algorithm by hand.

This is a classic recursive algorithm. The interviewer will want to see you puzzle it out, but the hint (as with all these interview questions) is that you should not write too much code.

Here is a solution in C++. It essentially creates another tree (thus keeping the original tree alone) within the defined range.

Node *range(Node *r, int s, int e) {
	if (!r) return NULL;
	Node *n = NULL;

	if (r->val >= s && r->val <= e)
		n = new Node(r->val);
	
	if (n) {
		n->left = range(r->left, s, e); 
		n->right = range(r->right, s, e);
	} else {
		if (r->val < s) n = range(r->right, s, e);
		else n = range(r->left, s, e);
	}
	
	return n;
}

Hi

It all depends on how you interprate zero. So in an interview, you should probably ask. For example, if 123000 is taken as correct, then what about 123000000 or 123000000000 etc etc. Where do you stop. I do agree with you though about 011. It is a trivial change to make this adjustment. I did it with one extra line of code. Make contact if you want my solution.

Edit: I have been asked for the algorithm. I will do so below, but before I give the algorithm, note that this is an interview question. Any attempt to write pages of code is inherently wrong. There is always a trick to these things, and the trick here is recursion.

Algorithm:

(*) Let x be your current number (x should start with 1, and iterate to 9
(*) Let y be your second number (y should loop from 0 to 9)
(*) Now create a new number, call it test (for want of a better name). test is x+y, but there is a condition: test must be greater than 0 and less than 9. If this condition is not passed, then the number is not even considered.
(*) Now that we have our candidate number, x,y,test, we need to recurse to find all numbers that satisfy the property we are looking for, but with x,y,test as the base number.

The problem basically involves both iteration and recursion. Definitely not the most efficient solution (a greedy solution would be more efficient), but guaranteed to be the solution that the interviewer is looking for.

This can easily be solved with recursion. Here is a recursive solution:

void an(int start, int end, int num) {
    if (num > end) return;
    if (num > 0 && num > start) cout << num << " ";

    for (int i=1; i < 9; i++)
        for (int j=0; j < 9; j++) {
            int test = i+j;
            if (test <= 9)
                an(start, end, num*1000 + i*100 + j*10 + test);
        }
}

int main() {
    int startRange = 800000, endRange = 900000;
    an(startRange, endRange, 0);
    return 0;
}

This can be quite easily done by recursion. This is an interview question, and not a real life example. So the emphasis is on doing something elegant, not long. Here is a recursive solution that accomplishes this:

void specialNum(int num, int st, int end) {
    if (num > end)
        return;

    if (num > st) cout << num <<" ";

    int digit = num % 10;

    if (digit < 9)
        sn(num*10+digit+1, st, end);

    if (digit > 0)
        sn(num*10+digit-1, st, end);
}

void specialNum(int st, int end) {
    for (int i=1; i < 10; i++)
        sn(i, st, end);
}

int main() {
	int startRange = 10, endRange = 200000;
	specialNum(startRange, endRange); //will print out numbers as specified in question
	return 0;
}

The easiest way to see this example is to note that it is just a special case of a combination. Here is a solution that will print out the results of the subsets as specified. The easiest way to do combinations is via recursion, hence my solution uses recursion. It is written in C++, and tested using g++ compiler on Linux.

#include <vector>
#include <iostream>

using namespace std;

//Will construct the subsets
void subsets(const int* arr, int start, int size, int k, vector<int>& res, vector<int>& prfx) {
    if (!k) {
        for (int j=0; j < prfx.size(); j++)
            res.push_back(prfx[j]);
        return;
    }

    for (int i=start; i < size; i++) {
        prfx.push_back(arr[i]);
        if (k)
            subsets(arr, i+1, size, k-1, res, prfx);

        prfx.pop_back();
    }
}

//Helper function to call the recursive function
void subsets(const int* arr, int size, int k) {
    vector<int> result;
    vector<int> prfx;
    subsets(arr, 0, size, k, result, prfx);
    int *ans = new int[result.size()];

    int t =0;
    for (int i=0; i < result.size(); i++) {
        if (!t)
            cout <<"{";

        if (t != k-1)
            cout << result[i] <<",";
        else
            cout << result[i];

        if (t== k-1) {
            cout <<"},";
            t=0;
        } else t++;

    }

    cout << endl;
}


int main	{
    int ss[6] = {1,2,3,4,5, 6};
 
    subsets(ss, 6, 2); //subsets with size 2
    subsets(ss, 6, 3); //subsets with size 3
    return 0;
}