CareerCup

Thanks!
Complexity would be too big a topic to explain here.
In a few lines, it means what would be worse case number of calculations required to achieve the result.

In your algorithm, you're comparing each number with every different one. So, if the array had N numbers, starting from the 1st, # comparisons:
N-1 + N-2(for the second #) + N-3 + .. + 1 = sum of first N-1 natural # = (N-1)(N-2)/2 = N^2 -3N + 2
The highest power in this case is N^2, so your operation could take that much time in worst case.

I recommend looking up big O notation on google/youtube. Also bigocheatsheet dot com has some good info..

Part 2. Now, any elements after this number i.e. which are > 5 are useless, so we'll focus on the subarry to the left of 5(including 5) i.e. [0, 1, 2, 3, 5].
Lets say this subarray is A. Let N = 5

Have two pointers i and j. i = 0 and j = A.length

while(i<j){
	if(A[i] + A[j] < N) {
		/* if sum of elements at current indices is < required number, 
		   we need to increase the sum, so i++
		*/
		i++;
		}
	else if (A[i] + A[j] > N){
		//decrese the sum
		j--;
	}
	else{
		//we have a match, 
		print i and j and 
		decrease sum: j--;
	}
}

Even with the optimization, the solution would be O(N^2), because you're summing up every pair of numbers.

Here I propose a solution, which would be linear time. It has two parts. I'm assuming the array is sorted in ascending order and has only +ve numbers (can be modified for -ve numbers also)

Part 1. Find the number(5) within array using binary search. O(Log N) run time

Nicely done, thumbs up!

Why not use binary search to find the first occurrence of the number and then walk linearly in both directions to find the range?

Was this asked in X-files Mulder :D

Without going into specifics, a general idea would be:

Class  chessPiece{
	//Variables
	/*general char variables such as 
	# moves allowed, direction constraint (rook only moves diagonally) etc
	*/
	
	//Methods:
	/*
	   chessPiece(//with custom variables for different peices)  -> ctor
	   moveMethod -> how to move chess piece with constraints, make sure 
	   the piece does not fall off the edge   
	*/

};


int main(){
	//create array of chess pieces, for both sides
	//fork two threads, each will one array. These will act like two playes.

}

Its a modification of Level Order traversal / BFS of binary tree.

For each level, find the count of -ve numbers. Compare it with a max_count, which indicates what level has the max -ve numbers and swap if needed.

As for the BFS search with level number, it can be done in many ways:
1. Using a dummy node
2. Keeping a count of nodes in current level and next leve
3. Using separate queues for current and next level.

Rodrigo and Anon, I agree with you guys. O(N Log N) is not possible. We will have to examine all the possibilities, so exponential run time.

Even with this input {2,3,4 }, my algo will still return -1 (if we're searching for 5), which is the correct answer.
I see your point, but I don't think its necessary to run through all the inputs?

Thanks for the inputs Rodrigo. My algo needs a little correction.

If no match found i.e. if we reach end of array and no number found < sum,
return -1

A={2,4}

Find smallest # < S, this would be 4. Now, S = 5 - 4*1 = 1
Find smallest # < S, no number found and we reach end of array, so return -1.

Thumbs up, looks like the correct solution. It would be polynomial run time though!

I think the most efficient you can get is an O(N Log N) solution:

-Sort the array (E.g, After sorting our array is {1,3,5}

Repeat the following:
- Starting from the end, find the next smallest number A < S(5 in this case)
- Multiple A as many times as possible till its becomes > S (5 * 3 > 11 so we'll save 2)
- Subtract this from the sum and repeat (11 - 5*2 = 1)

Run time = Sorting array + Walking it once = NLog(N) + N = N Log (N)

I just did a Google search of this code and looks like the same exact code is available on multiple websites.

Where did you get this code from?

This is a DFS search through the graph to determine if there exists a path between the start and the end node.

A general idea of how this works:
push the root node onto a FIFO structure(a queue in this case)
You're basically repeating this step:
- remove top node
- check its adjacencies, if any node == end node => there is path between start and end node, so returns true
- else add that node to end of queue

If no match found, return false i.e no path

Code:

#include <iostream>
#include <map>
#include <tr1/unordered_map>
#include <tr1/unordered_set>

using namespace std;
using namespace tr1;


bool isSplittable(int *A, int size){
	
	if(size < 2){return false;}
	
	//array to hold sums
	int *S = new int[size];
	S[0] = A[0];
	int i = 1;
	int bkwd_sum = A[size-1]; //to hold sum while walking backwards
	int fwd_sum = 0;
	//put forward sum into S from 0 to len - 1
	while(i<size-1){
		S[i] = S[i-1] + A[i];
		i++;
	}
	i--;
	
	//Start walking backwards till a match in sum is found
	while(i>0){
		fwd_sum = S[i];
		if(fwd_sum == bkwd_sum){
			cout << "array can be split at idx:" << i << endl;
			return true;
		}
		bkwd_sum = bkwd_sum + A[i];
		i--;
	}
	
	return false;
}

int main (int argc, char * const argv[]) {
	int a[7] = {5, 7, 10, 10, -30, 17, 19};
	int size = sizeof(a)/sizeof(int);
	
	isSplittable(a, size);
	

	
	return 0;
}

Now, for quickest run time, we’ll use an extra array to hold the sums.(S)
Algo would be:
Going forward, add and store the sum till that idx i into S[i].
Once the end is reached, walk backward, adding the sum of terms from back
and compare with the sum from front (S[i]
If match found, return true, else return false

Run time would be O(n)

First lets prove that an array can be split at only one point:

E.g
Array = [……….17……….19]
Lets say its split able at 19. To be also split able at 17, the sum of numbers b/w 19 and 17 would have to be -ve(-2 in this case). Which means sum total going from 17 to 19 would be < 17 (=15 in this case). So array would not be split able at 19.

Same can be proven if there is a num > 19 say 23

This is a question asked on the Amazon coding test right?
Can you please provide this info when posting the question..

This is a question asked on the Amazon coding test right?
Can you please provide this info when posting the question..

I don't think we're allowed to modify the array. You're sorting it and in process modifying it.

Heman, I think the above code does not handle left to right(or R to L) rule for operators of same precedence (E.g. * / or % in C++)
As JJ suggested, some improvements might be needed.

This can be solved by just using the level order traversal O/P.

For a level order traversal(stored in an array with starting idx = 0),
if node is at idx = n, its children are at idx: 2n + 1, 2n+2.

If tree is:

A
   B	     C
D   E  F   G                     

Level order traversal = {A, B, C, D, E,  F, G}
Now for node A(idx = 0), children are at 2*0 + 1 and 2*0 + 2 i.e. B & C 
and so on..

Use this to recursively build the tree.

vector<string> findSubStr(string s){
	//find all unique substr of s. Hashmap used
	//to filter out the duplicates
	vector<string> v (1);
	vector<string> v1 (1);
	char c;
	int i=0;
	string s1, t;
	string subS;
	unordered_map<string, int>m;
	
    if(s.length() <= 1){
	    c = s[0];
		s1.append(1, c);
		v[0] = s1;
		return v;
	}
	
	c = s[0];
	s1.append(1,c);
	v[0] = s1;
	m[s1] = 1;
    subS = s.substr(1, s.length()-1);
	v1 = findSubStr(subS);


	for(i=0; i < v1.size(); i++){
	    t = v1[i];
		if(m[t] == 0){
			v.push_back(t);
			m[t] = 1;	
		}
				
		t = s1 + t;
		if(m[t] == 0){
			v.push_back(t);
			m[t] = 1;	
		}		
	}	
	return v;
}

Agree with the consensus above. Its same as finding perms of a string.

Here's working C++ code, with hashmap to remove any dups:

Looks like an coding test question?

One simple way to implement would be using linked lists.
Every time TinyAlloc and TinyFree is done, have a LL node point to the mem allocated and the next chunk of available mem.
One thing to watch out here for is fragmentation.

For anyone interested I'm putting a small visual presentation at my blog:
ptechpedia (dot) blogspot (dot) com

Even though this question has been beaten to death, here is my two cents on it :
We need to find in-order successor to the a node in BST
In addition to std BST, we'll need a pointer to the parent

Algorithm:

If (node has a rightChild){
	find min in right subtree i.e. go right and keep going left
	till you encounter a NULL
}
else if (node is a leftChild of its parent){
	parent is the in order successor
}
else{
	node is the right Child. 
	while(parent != NULL){
	1. Keep going up the parents till you find a node that is 
	the left child of its parent. That parent is the in order successor
	or 2. Keep going up till you find a node >= current node
	}
	if no successor found this means that the node was the rightmost 
	one and has no successor
}

haha, thats me, at every interview!

I just discovered Aho–Corasick string matching algo, fascinating.. Thanks for the answer. thumbs up..

@SS: You're right. It would be much costlier.
I think it would be
nP0 + np1 + np2 .... npn -> A combinatorics problem( I don't know the answer to this)

So this approach will be quite time intensive..

Being a fairly easy question overall, in this case, I think the examiner would focus more on technical aspects. E.g. did you cover corner case, or NULL string, or syntax for overloading an operator

<< or >> can be implemented using any of the two approaches mentioned above:
a) Reverse entire string and then reverse parts of it
b) Get a relevant substring at starting pos and append remaning string. Would require extra space

= can be implemented using a simple strncpy or memcpy
== is strncmp

Home automation. We've seen fire alarms under Nest,
however, in general home automation is lagging behind and has a lot of scope for improvement..

Its a good method. Only caveat I see is, with a large # of entries in dictionary, your hash table would take up a lot of space..

Nicely done.
How about the case, when you need to insert after the last node? Will your code handle that?

Its a possible solution. However, it would be quite costly. I think approaching the dictionary as a trie would give a quicker solution

Approach 2:
Assuming dictionary is implemented as trie.

For each char in the string S, walk its trie entry in dictionary, checking to see if the path we're walking in trie has characters present from the string.

E.g. Say input string = "abzd"

Dictionary looks something like this:
b
a b c ... z

so we know 'b' is present in string and in dictionary, we follow this entry
'ba' is present in dictionary, as seen from above trie, its also present in string and so on.
Run time: O(n^2)

Assuming #letters in the given string is n

Approach 1:
1. Find and put all sustrings of string in array A. Run time : O(n^2)
2. Sort this array. Run time O(n^2 * log(n^2)
3. Starting from longest entry in this array, check if present in dictionary. A match will give the ans. Run time O(n^2) assuming lookup time is O(1)

so total run time = O(n^2 * log n^2)

Dave: The question states that exchange should happen only if a[i] > a[j] and not otherwise

If we want to sort the array,
as mentioned previously, use mergesort to count the #swaps, itwill give most time efficient solution with minimum #swaps.
Some people are using a version of insertions/selection sort, this will not be as efficient as mergesort in time or #swaps

As a small eg, sorting arr = {10, 6, 5}
Mergesort takes 2 swaps
Insertion sort takes 3 swaps

I think there is vagueness in the question.
What does the examiner intend to do? Sort the array? Or just a comparison between different elements

Your solution is correct. However, I think the question is vague.
Does the interviewer ask the #swaps required to sort the array
or is it just #swaps required, comparing each element with the other

2. Trie could be a ok solution, but
a) Its not mentioned dictionary is implemented as a trie
b) Lookup is O(n) which is > O(log n) for binary search

1. Binay search will give O(log n) soln:
maxidx = maximum index of the dictionary
W: Word whose idx is to be found

string W1 = getWord(maxIdx/2);
int temp = strncmp(W1, W);
if (temp > 0){
	//W1 > W. search in upper half
        findIdx(maxidx/2, W);
}
else if (temp < 0){
	//find in lower half
	findIdx((1.5*maxidx), W);
}
else{
	//word matched, return this idx
	return maxidx/2;
}

Working code in C++. Not optimized. As mentioned above, I'm still looking for a O(n) time and/or space complexity

#include <iostream>
#include <tr1/unordered_map>
#include <vector>

using namespace std;
using namespace tr1;

void findRepeatSubStr(string s, int req_size){
    if(s.size() < 2*req_size){
	    cout << "string is not long enough" << endl;
		return;
	}
	
	int i = 0;
	string t;
	unordered_map<string, bool>m;
	int max_itr = s.size() - req_size;
	vector <string> v (1);
	unordered_map<string, bool>m1;

    for(i=0; i <= max_itr; i++){
		//cout << "start idx: "<< i << endl;
		//cout << "end idx: "<< i+req_size-1 << endl;

		t = s.substr(i, req_size);
		cout << "t: " << t << endl;
		if(m[t] != true){
			//unique entry
			m[t] = true;
		}
		else{
			//dup entry
			if (m1[t] != true){
				//not added to v, add
				v.push_back(t);
				m1[t] = true;
			}
		}
	}
	for(i=0; i<v.size(); i++){
		cout << v[i] << endl;
	}
	
	return;
}


int main(){
	string s = "abcabcabc";

	findRepeatSubStr(s, 3);
	
	return 0;
}