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
The only thing I can think of is using a multicore / multiple processors and using multithreaded solution.
For instance, since we have multiple processors available, divide the matrix into 2 equal parts and assign the 2 parts to 2 separate threads. Then we can have these two threads run simultaneously on multiple processors and get faster than O(nm) run time. Other than that I think the interviewer was trying a trick question
I propose a slightly better way of doing this. In worst case it will be O(N^2 log n) but in reality it will be better.
Say our original array is A = {10, 5, 3, 7, 4, 1}
Since we have to find all subsequences of length 3 in A which satisfy the triangle property, let us first sort the array. Complexity of this step is O(n log n)
A = {1, 3, 4, 5, 7, 10}
Now we can start going through this array and picking triplets. However, since they are already sorted, when picking up the triplets, we can quickly check if the sum of two smaller ones is less than the bigger one
So, if our triplet is a, b & c; in iterating through the above array:
a = 1 b = 3 c = 4, a+b !>(not greater than) c, this triplet does not satisfy the triangle property.
Therefore we donot need to consider any more triplets for a = 1 and b = 3,
(because our next c element will be 5, which again won't satisfy the triangle property! i.e. all the remaining elements are greater than 4)
As you see, using this algo we can skip many of the triplets outright without making necessary comparisons.
Basically, there are two way to do automatic garbage collection. First of all, only objects in the heap require garbage collection. Objects in stack are automatically cleaned once the function/program goes out of scope, objs in heap are not cleaned automatically.
1. Use reference counting i.e whenever a object is created, we also keep a count of number of pointers referring to that object called the reference count. Then, if the reference count become zero i.e. we have no pointer pointing to that object, we can safely release the memory. A good example of this is the shared/unique/weak pointers in C++ STL
2. We periodically do garbage collection i.e. after some interval a garbage collector runs and any unreferenced memory objects are freed. A good example is Java. Basically, we start from a set of base objects (say all objects in the stack), follow the references and mark any object we encounter on the way as ok. Then we sweep the entire heap again and any object found not marked is unreachable and therefore can be freed.
Which company was this for?
The aim of a Hashmap would be to store keyval pairs and allow search, insert and del operations in constant O(1) time.
A simplest implementation of a hashmap would be using a Hash Function H which gives you the index i using the key ( i = H(key) ). Using the index we will store the keyval at the appropriate place. However, if the index location is not empty, the simplest solution is to link the new keyval entry to the old one using a Linked List. Ofcourse, there are other solutions as probing and double hashing.
Some code:
A is our bool arr
i = 0
flag = false;
while (i < size of A)
if A(i) == true
possible starting point
call recusive fn with starting jump of len i
if the above call returns with true value, exit and return true
else
i++

puneet.sohi
December 02, 2015 Dynamic Programming / Recrusion should give us a natural solution.
Walk the bool array till you find a value of 1.
This represents a possible starting point for sequence of jumps.
Now make a recursive call with this position as the starting point and see if from can reach the other end.
If yes, search over.
if no continue walking the array till next true value found and similarly recurse over it.
This is the simplest solution I can think of. It can take some improvements, but the question itself is not
clear.
zr.roman: In this case the middle node would be the one containing substring "ef".
When we first walk the linked list, total number of chars = 13.
Therefore the middle element of the substring = 13/2 + 1 i.e. at index = 7 which is the char 'f'
We walk the second time, reversing the LL till we reach the node with 7th element and work from there.
I'm interested in knowing. Is question this from a Hackerrank contest?
 puneet.sohi November 30, 2015All of the operations being O(1) looks like the interviewer is asking for a hashmap implementation.
Simplest way of implementing a hashtable/map requires two things:
1. Data structure to store key value pairs, we take array named A of size = sz
2. A hash function F.
So, our Hashtable will store key value pairs and allow Insert, Delete, Search and getRandom in O(1) time.
Insert:
Using the Hash function F, find the index(idx) where the keyval pair will be stored i.e.
idx = F(key)
and store the keyval pair over there
H[idx] = key+val
Now, if that position is already occupied, it means we have a collision. Collisions can be handled in
multiple ways. One simple way is to keep increasing the index till an empty space found (linear probing):
while ( H[idx] != empty && idx < size) {idx++;}. When empty cell found, insert the keyval pair.
Search and Delete are along the same lines. Just find the idx using F(key) and see if it matches the input key
For delete, just insert an special value (called tombstone) to prevent our linear probing from going wrong.
getRandom:
Bascially return any random entry from the array. Pick a random number using random number generator and use
the modulus operator to convert it into a suitable index i.e. idx = random_number % size
Now, return the keyval pair at this size.
Both prefix and postfix can be implemented using a simple strategy using a stack(LIFO). We assume the
current prefix/postfix expression is present in a queue(FIFO)
A general algo is:
Till queue empty
Dequeue one element from queue
if element is a number/operand or an = expression
push it into the stack
else //element is an operand like +  * etc
pop top two elements from stack
perform the operation using the operand
push result onto stack
if(stack becomes empty before two elements can be popped)
error!
At this point, your queue will contain one element i.e. the answer

puneet.sohi
November 11, 2015 I'm curious how your code will perform agains the expresssion in question i.e. *  6 5 7 = 7?
Strting from the left, your stack will contain one 7 before = expression is encountered, when you try to remove
2 operands from the stack, you only have 1 operand > err
Instead I would suggest also pushing in the = operator into the stack
I agree with everyone above. The question is not clear. Merging two sorted arrays to produce a sorted array can only be done in one way. If that is what we're trying to do, the merge step from mergesort is a simple algorithm to follow.
however, we will only end up with one possible array.
Data structure can be as simple as using an array to store all the strings.
Arr1[n] = {a, ab, abc, abcd, ..., abcd..xy, abcd...xyz}
Complexity will be linear ~ O(n). We will walk the array once. At each step select one string, remove last char and compare to the next string.
If the words/strings in the library are all subsets of each other, then the longest possible chain will be n.
E.g. If the words are: a, ab, abc, abcd, abcde, abcdef, .... ,abcde..xyz. You have 26 words (n = 26). Start with the last word and remove the char z, it will now be the same as the second last word. Now remove the char y, it will be same as third last word and so on till we reach the first word a. So the longest possible chain is n
Lets consider all cases:
1. If the node has a right child, then its logical descendant will be somewhere in the right tree. Therefore, find the minimum element that is bigger that the node in its right tree i.e. go right and then keep going left till you find a left node.
2. If the node has no right child, then
a) If the node is a right child of its parent, the in order traversal will end at the node, so no in order successor
b) If the node is a left child of its parent, then the parent is the in order successor.
Can I rephrase the question? Traverse the tree and print out all the elements. That will flatten the tree into a linear array. A BST with only right children can be thought of as a linear.
For the example mentioned in the question, we can do a inorder traversal and get the desired result.
Neat solution. I think this would be the most efficient one. I propose a small change, an integer for each player to keep track of his score. The score will be +1 or 1 as per the prediction.
 puneet.sohi July 15, 2015b?
 puneet.sohi July 15, 2015Soln 2: If we're not allowed extra space: Sort the array.
Now iterate through the array and for each element, check its neighbors.
If a duplicate found, mark it and check the next neighbor and so on till you find a non duplicate number and repeat
Run time O(nlong n for sorting + n for subsequent iteration) = (nlongn)
Soln 1: If we're allowed extra space. Create an binary array B of size n1 and set all elements to false. Iterate through the array.
For each element in array A, use it to index into array B. If the element at arr B is false, set it to true. If it is true, means we
have a duplicate.
E.g. for elemnt 30 at index 27 in A, if B[30] == true, this means element 30 at index 27 is duplicate
Run time O(n)
We can have two solution, one will use extra space for faster run time O(n), the other will not use extra space but take longer O(nlogn).
Say we have array A of numbers in range 0  n1
Ingenious solution hnatsu.
My only doubt about it is what if the numbers are not increasing linearly?
For instance: Range is 0  9, Numbers are {1,2,5,7,7,9} will your algorithm work?
If we're not keeping track of nodes already visited, here is a solution I propose:
Lets say the depth of tree is N i.e. number of levels is N.
1. Select a random number between 0N1 say P. So we will go down P levels
2. Go down P levels, one level at a time. At each level, select a random number between 0or1: if number = 0 go left else go right
Each node will have equal probability of being selected.
Why do we need to keep track of the nodes we've already visited?
If I'm selecting a random number between 15 and I select #3 the first time, I can select #3 the second time or the third time too(since probability of number being selected is equal). So why would I keep track of numbers/nodes already selected?
Coming back to the discussion, I'm not sure if sorting the string after concatenation will be all that useful?
Consider 4 strings A < B < C < D (in that sorted order)
# of operations to concatenate without sorting:
A,B,C,D join A&B > A+B,C,D join A&B with C > 2A+2B+C,D
join A&B&C with D > 3A+3B+2C+D
# of operations to concat with sorting:
A,B,C,D join A&B > A+B,C,D sort > C,D,A+B > join C+D > C+D, A+B
sort > A+B, C+D join the two > 2A+2B+2C+2D
Without sorting might be faster?
Thank you! If there is one thing I hate with a passion, its people hiding behind anonymity. I mean, if you're downvoting it, give me a reason, say something, don't just hide behind your computer.
That being said, I'm pretty sure someone will be downvoting this comment too :)
Here is a solution I propose. Not sure if it is the fastest, I'd like to see others thoughts on it.
Start by concatenating the smallest strings and concatenate with a bigger string and so on.
Say we have three strings A, B & C with lengths L1 > L2 > L3.
If we concatenate largest to smallest (A with B and then with C),
# of operations = (L1 + L2)(For A&B) + (L1+L2 + L3 (For A&B with C)= 2L1 + 2L2 + L3
If however, we concatenate smallest to largest (C & B and then with A)
# of operations = L1 + 2L2 + 2L3 which would be less than the above case.
So, first sort the strings according to increasing length and then use concatenate function on them, from smallest to largest.
Nicely done!
 puneet.sohi July 06, 2015So, in essence, find all the rectangles enclosing the point. The find the rectangle with minimum area among those rectangles.
 puneet.sohi July 06, 2015This might sound silly, but can anyone help me understand
how the original question found 5 sets of anagrams:
Set: <abc,cab,dac,beed,deb,few,acd>
Anagrams:
abc, cab
dac, acd
deb, beed
So 3 sets of anagrams, not 5?
I like your idea of using a STL Map. The one obvious advantage I see is while in graph to start with node A, you would have to traverse the graph to find the actual node A; in Map you can directly start with node A.
However, beyond this both would be an ~O(n) solution since we would have to examine each node in turn.
The space complexity might be a little less in a graph since we're not storing each node and its children individually.
#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;
bool findRotationIdx(int *A, int length)
{
printf("length of array is %d \n", length);
if(length == 0)
{
printf("Empty array \n");
return false;
}
if(length == 1)
{
printf("Index is %d", length1);
return true;
}
int l = 0;
int h = length1;
int m = 0;
while(l<=h)
{
m = (l+h)/2;
if(l==h)
{
//match
printf("Rotation index is %d \n",l);
return true;
}
else if (A[l] < A[m])
{
//pivot is in upper half
l = m+1;
}
else
{
h = m1;
}
}
return true;
}
int main()
{
int A[10] = {6,7,8,9,10,11,1,2,3,4};
int B[7] = {6,7,1,2,3,4,5};
bool retVal = findRotationIdx(B, (sizeof(B)/sizeof(int)));
if (!retVal)
{
printf("Error in array, kindly check \n");
}
return 0;
}

puneet.sohi
June 26, 2015 As others have already suggested, we can use a modified binary search to find the pivot point. Here is a sample working code in C. Its self explanatory so I'm not going into the details.
 puneet.sohi June 26, 2015Complexity analysis:
Initially creating a graph out of the text file ~ O(n ^ 2)
BFS search ~ O(n). So we can produce linear time results if we spend initial time and create a graph.
A sample run would look like this:
Q1: A D,C,B C,D D F,E G,F G NULL
Q2: 0 1,1,1 1,1 1 2,2 3,2 3 NULL
o/p by level of association:
level 0: A
level 1: B,C,D
level 2: E,F
level 3: G
With our data in place, we will perform a BFS on the graph.
Since we want level (of association), we will use two queues:
Q1: to hold graph nodes
Q2: to hold association levels
I cannot draw the graph here, so I will leave the drawing of the graph to your imagination. To traverse the graph:
Start with A:
Enqueue it to Q1 and enqueue level of association 0 into Q2
Then repeat the following till Q1 is empty:
 Dequeue a node(N) from Q1 and the level(L) from Q2
 Enqueue all unvisited childern of N into Q1 with association level of L+1 and mark them visited

puneet.sohi
June 24, 2015 We'll use the example in the question:
A: B,C,D
D: B,E,F
E: C,F,G
Start with element A. Insert it into the graph
node * A = new node("A"); //Data of a node is the character A
Insert B,C & D as its childern
A>addChild(B); A>addChild(C); ...
Then we will repeat the process for A's childern.
Take the next child(say D).
Search the entire file for D. Since file is not sorted its a linear time operation O(n)
Insert D into graph and repeat for its childern.
Since its linear search time for every node:
Complexity would be ~ O(n + n + n ....n times) ~ O(n ^2)
Sample node of a graph:
struct node{
int data;
vector <node *>childern; //A Linked List would be equally fine
bool isVisited; //during BFS, check if the node has been visited
};

puneet.sohi
June 24, 2015 Oookay I think BFS traversal will work. However for that we would need to convert the file into a graph and then perform the BFS on it.
So the solution would broadly comprise of:
A) Convert the file into a graph. Its a one time operation, once done we won't need to do it again.
B) Starting with the appropriate node in the graph, perform a BFS(using queues)

puneet.sohi
June 24, 2015 Here is a sample code:
void findSeq(node *n, int sum, vector<int>V)
{
if(n>lt == NULL && n>rt == NULL)
{
//leaf node
if(n>data == sum)
{
//match
V.push_back(n>data);
cout << endl << "=================" << endl;
printVec(V);
cout << "=================" << endl;
}
else
{
//no match
return;
}
}
else
{
V.push_back(n>data);
//cout<< "Not a leaf node" << endl;
if(n>data == sum)
{
//match
cout << endl << "=================" << endl;
printVec(V);
cout << "=================" << endl;
}
//recurse on child nodes
if(n>lt != NULL)
findSeq(n>lt, (sum  n>data), V);
if(n>rt != NULL)
findSeq(n>rt, (sum  n>data), V);
}
}

puneet.sohi
June 23, 2015 So unless its a binary search tree, we will have to examine all possible paths.
We cannot stop if we find a matching sequence (E.g. 2,5). We will still need to keep going till we
reach the leaf node. (E.g. 2,5,2,2 would be a match, 2,3,4 would not be a match)
So here is a O(n^2) algorithm.
Start at root
For any node, check if there is a match till here and print it.
If its a leaf node, we return.
Else, we pass in the remaining sum (number to be found  previous node) to its children and recurse
// Main functions:
void findElement(int *Arr, int size, int element)
{
if(size == 0)
{
cout << "err" << endl;
return;
}
if(size == 1)
{
if (Arr[0] == element)
{
cout << "Found element at idx 0" << endl;
return;
}
else
{
cout << "Not found" << endl;
return;
}
}
int peak = findPeak(Arr, size);
int l1 = 0; int h1 = peak;
int l2 = peak+1; int h2 = size;
if (binarySearch(Arr, l1, h1, element)  invertedBinarySearch(Arr, l2, h2, element))
{
cout << "element found" << endl;
}
else
{
cout << "element not found" << endl;
}
return;
}
int main()
{
int A[9] = {1,2,3,5,7,9,11};
int B[9] = {11,9,7,5,3,2,1};
int C[9] = {1,2,5,8,13,9,3,1};
findElement(C, 7, 3);
return 0;
}

puneet.sohi
June 22, 2015 //Supporting functions:
int findPeak(int * myArr, int mySize)
{
//Find Peak Element
if (mySize == 0  mySize == 1)
{
return 0;
}
int h = mySize  1;
int l = 0;
int m = (l + h)/2;
while(l <= h)
{
if (l == h)
{
cout << "Peak element idx is " << l << endl;
return l;
}
m = (l+h)/2;
//cout << "low" << myArr[l] << " med" << myArr[m] << " high" << myArr[h] << endl;
if (myArr[m] > myArr[m1] && myArr[m] > myArr[m+1])
{
cout << "Peak element is at idx" << m << endl;
return m;
}
if(myArr[m] > myArr[m1])
{
//cout << "peak in upper half" << endl;
l = m+1;
cout << " l:" << l << endl;
}
else
{
//cout << "peak in lower half" << endl;
h = m1;
cout << " h: " << h << endl;
}
}
return 0;
}
bool binarySearch(int *Arr, int start_Idx, int end_Idx, int element)
{
if (start_Idx > end_Idx)
{
cout << "err" << endl;
return false;
}
if (start_Idx == end_Idx)
{
if (Arr[0] == element)
{
cout << "binarySearch found element at idx 0" << endl;
return true;
}
else
{
cout << "binarySearch Not found" << endl;
return false;
}
}
int l = start_Idx;
int h = end_Idx;
int m = 0;
while (l <= h)
{
m = (l+h)/2;
//cout << "binarySearch l " << l << " m " << m << " h " << h << endl;
if (Arr[m] == element)
{
cout << "binarySearch Found element at idx" << m << endl;
return true;
}
else if (Arr[m] > element)
{
//cout << "binarySearch Element in lower half" << endl;
h = m1;
}
else
{
//cout << "binarySearch Element in upper half" << endl;
l = m+1;
}
}
cout << "binarySearch Element not found" << endl;
return false;
}
bool invertedBinarySearch(int *Arr, int start_Idx, int end_Idx, int element)
{
//Binary search for a decreasing array. E.g. {9, 8, 7, 6}
if (start_Idx > end_Idx)
{
cout << "err" << endl;
return false;
}
if (start_Idx == end_Idx)
{
if (Arr[0] == element)
{
cout << "invertedBinarySearch found element at idx 0" << endl;
return true;
}
else
{
cout << "invertedBinarySearch Not found" << endl;
return false;
}
}
int l = start_Idx;
int h = end_Idx;
int m = 0;
while (l <= h)
{
m = (l+h)/2;
//cout << "binarySearch l " << l << " m " << m << " h " << h << endl;
if (Arr[m] == element)
{
cout << "invertedBinarySearch Found element at idx" << m << endl;
return true;
}
else if (Arr[m] > element)
{
//cout << "binarySearch Element in lower half" << endl;
l= m+1;
}
else
{
//cout << "binarySearch Element in upper half" << endl;
h = m1;
}
}
cout << "invertedBinarySearch Element not found" << endl;
return false;
}

puneet.sohi
June 22, 2015 As other have already suggested.
1. Do a binary search to find the peak or largest element. O(log n) operation
2. Split the original array at the peak element, say at element p
3. Do a binary search on the lower array. O(log p)
4. Do a binary search on the higher array. O(log np)
Complexity = O(log n) + O(log p) + O(log np) ~ O(log n).
I'm including some code.
Nice approach. However, I don't think the time calculation is correct since the max element will not always be in the center.
 puneet.sohi June 22, 2015It will happen whenever you try to dereference a pointer that is set to NULL.
In stdio.h, NULL is defined as zero
so if you have a pointer which is set to NULL, it will point to the memory location 0, which is reserved by the OS for its own use.
Therefore you would get this error.
class node
{
//each node has 3 childers
//to indicate leaf node, its first child is NULL
public:
node();
node(int _data);
int data;
node * childern[3];
};
bool isSumProp(node * input_node)
{
node * parent = input_node;
//check if leaf node
if(parent>childern[0] == NULL)
{
cout << "tis but a leaf node" << endl;
}
int sum_P = parent>data;
cout << "Parent sum: " << sum_P << endl;
int sum_C = 0;
int i = 0;
node * child = parent>childern[i];
while( (i < 3) && (sum_P > sum_C) )
{
sum_C += child>data;
if(sum_P == sum_C)
{
cout << "This node follows Sum Property "<< endl;
return true;
}
i++;
child = parent>childern[i];
}
cout << "This node DOES NOT follows Sum Property "<< endl;
return false;
}
bool findSumProp(node *current)
{
if(current>childern[0] == NULL)
{
cout << "Leaf node" << endl;
return false;
}
node *curr = current;
if( !isSumProp(curr) )
{
cout << "array does not follow Sum Property" << endl;
return false;
}
findSumProp(curr>childern[0]);
findSumProp(curr>childern[1]);
findSumProp(curr>childern[2]);
return true;
}

puneet.sohi
June 18, 2015 For every node N, you will check if the sum of its children. If the sum matches the parent, this node follows the Sum Property. Apply a recursive solution on all its children. Where ever we find that the Sum Property is not followed, we checking and return false.
 puneet.sohi June 18, 2015Can you clarify on the question.
What does intersection of Linked Lists mean? Two or more common elements in the same order?
Lazy alert! The above code still needs to handle some special cases (array length 0 or 1 or 2 and maybe array with all 1's), I was too lazy to do it :D
 puneet.sohi June 16, 2015
I propose a two step solution here:
1. Using a Depth First Traversal, push all the elements into a stack(S1) with a stub/delimiter in between each level. This can be achieved with a queue(Q) and stack(S1) as follows:
2. Using two stacks S1 and S2, pop the levels in the spiral way i.e. pop top level from S1(level 1 of the tree), then pop remaining S1 into S2. Pop first level of S2(level n of binary tree) and pop remaining S2 into S1 and repeat till empty.
 puneet.sohi December 10, 2015