puneet.sohi
BAN USER 0of 0 votes
AnswersThe question was:
 puneet.sohi in United States for AWS
What are general guidelines you follow while creating new classes in C++
My answer:
1. Keep variables pvt (use setter and getter methods)
2. Use reference counting to do mem management, he asked me to use shared_ptr within the class Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer Object Oriented Design  2of 2 votes
AnswersI have two arrays A and B(each containing 8 bit integers). Find the common elements between them.
 puneet.sohi in United States for AWS
The questions started out as a general discussion with the most inefficient method. Then the interviewer asked me to improve the solution (to give a NlogN and finally a linear time solution) Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer Algorithm
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;
}
}

puneet.sohi
April 11, 2014 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!
 puneet.sohi April 11, 2014Why not use binary search to find the first occurrence of the number and then walk linearly in both directions to find the range?
 puneet.sohi April 10, 2014Was this asked in Xfiles Mulder :D
 puneet.sohi April 10, 2014Without 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.
}

puneet.sohi
April 08, 2014 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.
 puneet.sohi April 02, 2014Even 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!
 puneet.sohi April 02, 2014I 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[size1]; //to hold sum while walking backwards
int fwd_sum = 0;
//put forward sum into S from 0 to len  1
while(i<size1){
S[i] = S[i1] + 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;
}

puneet.sohi
March 28, 2014 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.
 puneet.sohi March 28, 2014Heman, 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.
 puneet.sohi March 24, 2014vector<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;
}

puneet.sohi
March 24, 2014 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 inorder 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
}

puneet.sohi
March 14, 2014 haha, thats me, at every interview!
 puneet.sohi March 13, 2014I just discovered Aho–Corasick string matching algo, fascinating.. Thanks for the answer. thumbs up..
 puneet.sohi March 13, 2014@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..
 puneet.sohi March 12, 2014Nicely 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
 puneet.sohi March 12, 2014Approach 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
 puneet.sohi March 03, 2014If 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;
}

puneet.sohi
March 02, 2014 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_size1 << 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;
}

puneet.sohi
February 01, 2014
Thanks!
 puneet.sohi April 11, 2014Complexity 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:
N1 + N2(for the second #) + N3 + .. + 1 = sum of first N1 natural # = (N1)(N2)/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..