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
Nicely done Why are you sorting the array using prepareData? The array is already sorted?
- puneet.sohi June 16, 2015There is a very obvious linear time solution. Go through the entire array and count the number of zeros.
I don't understand the point of the question? Does the examiner want a more efficient solution?
Okay lets break the problem down. Begin with calcuation
1. Visit one site (1 URL)
2. Go through all of its images, mark them V Good - Poor and calculate some sort of average. We will need some scale of marking. So lets take: V Good = 4, Good = 3, Avg = 2, Poor = 1
S = Total score of the URL, N = Total number of images on the URL
S = 0; N = 0;
for (i = next image in URL; i < Last image in URL; i++)
{
//take next image say I
S = S + ScoreOf(I);
N++;
}
Avg_Score_For_URL = S / N;
3. Now to store the score of a website. Use a hashtable/ STP map which takes key-val pairs.
So key = URL, value = Avg_Score_For_URL. This will also serve as a check for already visited URL's. Before visiting a URL check if its entry already exists in the hashtable.
This would be a very basic solution.
Can you clarify your question?
What are those 5 machines capable of? Can they send emails simultaneously?
Are the machines having equal processing power?
What is a triangle triple? Is it that they should form a right angle triangle?
- puneet.sohi November 26, 2014Here is a small implementation:
bool isNumber(String s){
if (s.length() == 0)
return false;
int i=0;
char c
bool dot_flag = false;
is_number_flag = true;
if (s[i] == '-')
i++;
while( i < s.lenght() && is_number_flag ==true ){
c = s[i];
if (c >= '0' && c<= '9')
i++;
else if (c == '.'){
if (dot_flag == false)
dot_flag = true;
else
is_number_flag = false;
}
else
is_number_flag = false;
}
if (is_number_flag == false)
return false;
else
return true;
The general solution would be to check each char in turn
and report the first char that makes the string a non number.
There are some exceptions to watch out for:
The 1st char can be '-'
First occurence of '.' denotes a decimal. Subsequent
occurences mean that string is not a number
Looks about right.
What would the compare function look like?
What does duplicate parenthesis mean?
Do we need to find matching parenthesis pairs? Or find the extra parenthesis?
Why not just do an inorder traversal of first n nodes amigo?
In order traversal always gives you numbers in increasing order, so you'll get the first n numbers
That about covers everything Sri. What is LoC?
- puneet.sohi April 29, 2014Yep, that's what my final solution was.
Not sure why you say Hashmap will cost n log n
haha, agreed.
- puneet.sohi April 29, 2014Why isn't this array the max?
{4,6,1,5,9}
This has already been discussed. You can check it out here:
careercup dot com / question?id=6669318070730752
Nicely done!
@Ram: The only division he is doing is /2, which can be done by the right shift operator
It depends on the type of container. Some of them allow duplicate keys others donot.
Map does not allow duplicate keys.
So A is the key(not the val to be stored):
map<A, val1> and map<A, val2> would end in val2 being stored
If A is the value(not the key), then
map<key1, A> and map<key2, A> would result in two separate copies of A being stored in two separate places
Multimap, allows storage of duplicate keys.
It means, that one number is removed from the bag, randomly
- puneet.sohi April 24, 2014Simple and elegant. Took me some time to convince myself, that this will work for all cases, it does..
- puneet.sohi April 24, 2014simple!
Just to add to it, initial is the sum of first 100 natural number = 100 * 101 / 2
What would be the run time complexity for this? Linear/O(n) right?
- puneet.sohi April 23, 2014If it does not have to be a continuous subsequence,
just pick out all the positive integers in the array and add them up, this is your answer
Does it have to be a continuous subsequence?
If so, there is a linear time solution to this. You might want to lookup max subarray/ Kadane's algo
#include <iostream>
#include <tr1/unordered_map>
#include <vector>
#include <tr1/memory>
#include <memory>
using namespace std;
using namespace tr1;
int main(){
int i = 0;
string str3 = "gh";
string str1 = "asdfgjkl";
string str2 = "zzyadl";
string s; string s_final; //s_final stores final result
char c;
/*
=========== Remove S3 from S1 ============
*/
bool a1[256];
i = 0;
for(i=0;i<256;i++)
{
a1[i] = false;
}
i = 0;
for(i=0;i<str3.length();i++)
{
c= str3[i];
a1[c] = true;
}
i = 0;
for(i=0;i<str1.length();i++)
{
c = str1[i];
if (a1[c] != true)
s.append(1, c);
}
cout << s << endl;
/*
============ FIND common in S and S2 ============
*/
bool a2[256];
i = 0;
for(i=0;i<256;i++)
{
a2[i] = false;
}
i = 0;
for(i=0;i<str2.length();i++)
{
c = str2[i];
a2[c] = true;
}
i = 0;
for(i=0;i<s.length();i++)
{
c = s[i];
if (a2[c] == true)
s_final.append(1, c);
}
cout << s_final << endl;
return 0;
}
Hi Girish, no offense taken.
I'm not Java coder, so I don't know exactly what your code does.
I'm posting a working C++ code here(with examples)
I don't post code with my answers, because I prefer to leave something to the other person.
I'm not a Java expert, but I think you're talking about the Object class that is the parent for any other class?
- puneet.sohi April 22, 2014Girish, I didn't post this algorithm knowing that it is wrong. When I post answer, I know they're correct as far as I know.
Can you tell me whats wrong with it?
Yes you can.
One simple way is to create a class say A, extend with with different subclasses(class B for int, class C for float etc),
Then use an array of pointers to base class (A), and use it to store objects of derived classes.
Thanks!
- puneet.sohi April 22, 2014Simple and elegant, thumbs up!
- puneet.sohi April 22, 2014Interesting proposal using Tries.
How would you match Sea!tle with Seattle with this approach?
Create a bool array of 256 chars a[256]
Walk S3, char by char, for each char c set a[c] = TRUE
Walk S1, and if for any char c of S1, a[c] == TRUE, means this char is also present in S3, so delete it
Now , create another bool array of 256 chars b[256]
Walk S2, char by char, for each char c set b[c] = TRUE
Walk S1, and if for any char c , b[c] == TRUE, means this char is present both in S1 & S2 and not S3.
So, put this aside into a string (S)
At the end, S will give us the answer
I’m going to propose a linear time solution here.
Concept is to
1. Eliminate all characters of s3 from s1
2. Find the first subsequence of s1 that contains all chars of s2
My thoughts exactly.
- puneet.sohi April 21, 2014Its a string manipulation question.
Go through your string,
if you find !, replace with t unless it is at the end of a word(Like in Hard!)
if you find ., goto new line
Similarly, you can make other conversions..
Keeping that in mind, we could a line by line comparison between matrix m and the file present in the memory(this can be made more efficient, by hashing for instance)
If we overrun the the chunk present in the mem, there can be two cases.
1. If we had a partial match i.e. part of m was present in the current chunk. In that case, bring in the next chunk, and continue the search
2. If no match, bring in the next chunk, and start afresh.
If original bigger matrix is M, smaller matrix to be found is m.
Since file is too large to be in memory, it will have to be broken down and brought in chunk by chunk
I think there are two parts to this question:
1. If a piece of file/matrix M is present in the memory, how would we find the pattern m in it, most efficiently
2. If the patter m is present in two chunks i.e. if a chunk is present in the memory, m could be partly present in that and partly in the incoming chunk.
codeproject dot com has one repository.
You could check public Git repository or ask on stack overflow.
It does not differ from swapping element with each other. If anything, it add more complexity.
The point here is that we're simulating a parking lot, so if its full, to exchange the positions of two cars, we'll need an empty space. That is why we must use the empty slot within the array.
I think with min # of swaps, the interviewer actually means least run time complexity. That's what I was shooting for in my solution.
What company is this for?
Q3 is not possible to solve, you don't have any delimiters between the words.
Q1 and 2 can be solved in linear time.
If, A: Changed array, O: Original array
O(N^2) run time: For each element in A, we'll find its original position in O( O(N) time operation). We'll swap it with its original position. Do this N times and we get O(N^2) run time.
O(N) run time: Instead of walking the array O every time to find the original position of an element, pre process it, so that we can get the original position of an element in O(1) run time. We could maintain a hashtable, or another sorted array etc.
So, now putting an element in its correct position in A would be a constant time operation, O(1) lookup and O(3) to swap to original position.
Run time = O(N) to preprocess + O(4*N) to rearrange array in proper time = linear time.
I hope my algo comes across clearly, its hard to explain your thinking in writing.
@All, this question has been discussed quite well on Stack Overflow, just google for "rand 5 to rand 7"
- puneet.sohi April 17, 2014Two words: Stack Overflow :D
- puneet.sohi April 17, 2014Why not?
- puneet.sohi April 17, 2014We can do it in O(n) time, if we just pre process the original array, instead of finding the correct position by going over the array every time..
- puneet.sohi April 17, 2014Now for the algo:
Walk the array A,
1. Compare each element with its position in the original array O
(this can be optimized, so that we don’t need to lookup entire array O every time)
2. If element is not in proper position, swap it with its original position using empty space
3. Do not advance further yet
If (current element not in proper pos){
goto step 2
}
else {
goto next pos
}
We can have a linear time run for this.
First consider number of steps needed to swap two element using empty space e, it would take 3 steps
A = e 1 2 3 7 6 4 5
If we swap 2 and 5, steps would be:
1. Swap 2 and e i.e 2 1 e 3 7 6 4 5
2. Swap 5 and e i.e. 2 1 5 3 7 6 4 e
3. Swap 2 and e i.e. e 1 5 3 7 6 4 2
I think you'd need to check step by step (using a Unix Terminal)
1. Ping 127.0.0.1 -> It will confirm if the network stack is working fine on your OS(till the NIC)
2. Ping the default gateway -> Confirm if NIC working fine
3. Do a NSLookup, ping a well know website -> Check if DNS working fine
4. Again ping a well know website -> Check if our subnet, IP configured fine
If yahoo.com is still unavailable, as suggested above by Enthusiast, there could be multiple problems..
No I don't think it'll work in this case. I'm just looking for two elements that add up to the sum, not more than that.
If we want all such elements, then its a NP hard problem, we'll have to calculate all the subsets.
You're correct. So here's an implementation of it:
- puneet.sohi June 16, 2015