Companies matching "facebook"

Awesome!!

The answer is already popular in computer vision fields!! It is called integral imaging. See this page http://en.wikipedia.org/wiki/Haar-like_features

Let a[][] be the 2d array, int i=0; for( j = row_start; j <= row_end; j++) for( k = col_start; k <= col_end; k++) i+=a[j][k];

Iterate over matrix as an array storing (new sums array) in each position the cumulative sum up to that point. For each row in the desired submatrix we can compute its sum as a difference between its end and start positions. Repeat for other rows. Add up all the row sums.

Do you know what a binary search is? You drop it from floor 12 next. If it breaks, you know it breaks between floors 12 and 1, inclusive. If it doesn't, you know it breaks between floors 13 and 25, inclusive. The main principle of binary search is that with each step you reduce your search space in half. Now your search space consists of only 12 floors. Wow, I want to get asked such a question in an interview!

>>you drop it from floor 12 next... if you broke it on 50 and 25... you are out of luck and out of bulbs...

19 drops is not the best worst case scenario... imagine trying floor 16, if it breaks, you try 1 - 15 and thats 16 tries. if it doesn't break, then try floor 31 and if it breaks, then try 17 - 30 (so 16 tries, including the try on floor 16). And on and on (45, 58, 70, 81, 91, 100). If you reach 91, you'll have tried 7 floors so far and if it doesn't break, then there's 9 more tries to get to 100 (thus 16 in the worst case)

Even a drop from the ceiling of 1st floor, a simple light bulb will break. thats what i think

It's a light bulb. It will break when dropped from the 2nd floor. Drop it there then go to the first floor, hold it over your head and drop it.

first do a binary search (agressive first step - fast) with 1 bulb. when first breaks, you know X(last but one fall - success) and Y(last fall - failure). now do a linear search starting from X(conservative but accurate second step - slow). complexity = in between logN and N.

Use Binary search starting with the middle 50 The complexity of binary search is logN . So it will be log(100) < 7. Based on my experience, I think it will be floor 1 itself .

Drop from 1st floor. If it didn't break, drop the same bulb from 2nd. If it still didn't break, drop the same bulb from 3rd... repeat as necessary. Only one light bulb required :)

Yes, but doing each floor, that will give you the most drops -- question relates to optimizing for "least" number of drops -- I didn't think about being able to re-use the bulbs...that obviously is helpful. Maybe a fibonaci sequence once you determine a "break" floor and a "non-break" floor. I'd probably fail completely at coding it...knowledge of optimization and prediction theory would certainly be useful.

Let f(m,k) be number of tries for m lamps and k floors. Obviously f(1,k)=k. let f(2,k) be s. k<=(s-1)+(s-2)...(1) =s(s-1)/2. Therefore f(2,100)=15.

Actually, 16 is not the optimal, nor is 15; you can do it in 14. Here is one solution (there are at least 5 other equivalents): * Drop first bulb at 14th, 27th, 39th, 50th, 60th, 69th, 78th, 85th, 91st, 96th, and (optionally) 100th until it breaks. * Go to the highest floor where the first bulb didn't break. * Repeatedly go up one floor and drop the second bulb. When it breaks, you have your answer. Why is 14 optimal? Since you are decrementing each time, you want (n) such that sum(1..n) barely reaches 100. The answer is n=14. Generally, if the number of floors is (f), the lowest number of drops is ceil((sqrt(8*f+1)-1)/2). This is the best worst-case scenario. An interesting related question is what gives the lowest expected number of drops. And no, I could not have gotten this in an interview.

In theory, use one bulb to determine an interval, and use the second bulb for a linear search within the interval. The solution that decreases the interval by one for each trial is quite clever. In practice, however, take the nature of the problem into account: Start on the first floor and move up by one floor. That's the answer I would be looking for.

Start with bulb 1 and drop it from floor 2. Doesnt break? then floor 4 Doesnt break? keep dropping the same bulb moving even number of floors all the way upto floor 100. If on some even floor the bulb breaks drop the second bulb from the odd floor below the even floor, to detect if its the even or the odd floor that breaks the bulb Best case detection: 2 tries (first bulb breaks on 2nd floor, second bulb breaks on 1st floor) Worst case: 51 tries (the fist bulb breaks at 100 and second bulb breaks or does not break at 99th floor.. )

Go to the 100th floor and drop the first bulb. It WILL break. Done, 1 drop. It doesnt say whats the lowest floor it will break at, just at what floor will it break with least drops. Thus floor 100.

Alright guys...you have two light bulbs. ...the second one has to be used for linear search, let the worst case number of items to be searched be x, then your interval will also have to be x, which will result a worst case of 100/x drops for the first light bulb. So now you are just trying to minimize n=100/x+x, find n'=0 when x=19...the candidate's answer is correct.

I meant...x=10. and n=19.

0 drops, 1 bulb......stop thinking like computer nerds. Use physics or an engineering mindset. They didn't prohibit the use of any tools. Grab a scale, figure out force req'd to fracture bulb. Calculate acceleration due to gravity adjusting for air resistance/barometric pressure at location (trivial for anyone who took a 1yr physics course). Figure out how many meters up you need to be based on the req'd acceleration. Done....

@Rich: I am sure they were hoping for you to give them a computing answer since they don't do physics, and rather do computer science. mer's answer is correct: 14.

Let F(s, n) be the optimal worst-case number drops for s stories and n bulbs. Suppose we drop at floor f, constituting one drop. If it breaks, we must make up to F(f-1, n-1) drops. If it doesn't break, we must make up to F(s-f, n) drops. Thus, for a given floor f, we have up to 1 + max { F(f-1, n-1), F(s-f, n) } drops. Optimizing over f: F(s, n) = 1 + min{ max { F(f-1, n-1), F(s-f, n) } for f in 1..s} Using the appropriate base cases, we have F(100, 2) = 14, as mer has given. Another way to think about it is in terms of decision trees. We want to construct a binary decision tree with leaf nodes for floors 1..100, and at most one "left" turn per path from root to leaf. To minimize the height of the tree, we want to reduce the variance in the length of each root-to-leaf path. This suggest we try dropping the first bulb at floors of the form: a, a-1, a-2, .. a-b, where the sum a + (a-1) + .. + (a-b) is equal to or barely over 100, so that determining almost any floor (possibly excluding the top few) takes a drops. Using this approach, we get the sequence of drops that mer has suggested.

Well done @mer I have seen this question posed many ways, and that is the best answer I have ever seen. Sure hope I get asked this one now

14

In my experience light bulbs break when dropped from any height above 3 feet

Depends on how accurate u want to be. If i want exact answer, drop one from fifty, if it breaks start from first floor woth the remaining bulb. If it does not break, then start from fifty first florr. u will iterate fifty times as worst case. If u want a approximate answer, u can do binary way with give or take twenty five floors. Step over based on accuracy needed.

You are all ignoring valuable information in this question. We are talking lightbulb, not bowling ball, and building, not step ladder. The bulb will almost certainly break by being dropped from the second floor (assuming US numbering conventions). The chance of it surviving a 3rd floor drop are miniscule, but not zero. The chance of a 4th floor drop, even less. Therefore, drop it from the 3rd floor first. If it breaks, go to the second floor and try. If that breaks you know the answer is 2. If it by some miracle doesn't break from the 3rd floor drop, the answer is 4, but take the elevator up one floor and drop it just to see. Rinse and repeat to 5, but since it will have already broken, go out and grab a beer, and tell your friends how much fun you just had.

n*(n+1)/2 = 100. n approx = 14. In worst case u can figure it out in 14 drops. 14th, 27th, 39th, 50th, 60th, 69th, 78th, 85th, 91st, 96th, and (optionally) 100th until it breaks.

I believe the number sequence should be: 14, 27, 39, 50, 60, 69, ** 77, 84, 90, 95, 99 **. The 9 floor gap between floor 69 and 78 would result in 8+8 = 16 drops worst case.

Easy. Answer is zero. You don't need a test to find out that a lightbulb is going to break, even when you drop it from the first floor, because it's made of glass.

BigO(100/X + X-1), Where X is the number of floors. 100/X calculates the dropping times to break the first one and X-1 is the additional maximum overhead to break the second one starting from the previous dropping floor to the floor the previous bulb was broken. If you solve the derivative of the above equation equal to zero, the optimal solution becomes 9.9 ~= 10 . Worst case = 100/10 + 10 -1 = 19

If its a glass bulb it will break from a 2ft height...i wont even care climbing any floors to check.

Once you break the first light bulb, you are FORCED to start at the highest safe floor + 1 (i.e. highest floor that you safely dropped bulb #1 from) and drop bulb #2 one floor at a time, moving upward. Therefore, the algorithm for the first light bulb is critical (cuz once it breaks you are counting by 1's upward). Binary search starts at the 50th floor ==> max # drops = 50 Choosing fixed increments rather than binary search, e.g. start at 10, increment by 10, yields better results ==> 25 The ideal solution is 14 drops ==> Start at 14, increment by 14 each step until it breaks (leaving for the reader why 14 is optimal).

It doesn't matter what floor you are on to make a bulb break. Doesn't it matter how high off the floor the bulb is dropped. If I am on the 5th floor and the bulb is sitting on the floor of the 5th floor, how high off of that 5th floor do I need to drop it before it breaks. This is a misleading question. The question doesn't say that you will drop the bulb out the window.

Drop both from eye level. Both will break, and I answered the question without even climbing one stair. Efficiency isn't always about math..Common sense

Answer: 14 drops Mathematically: 14 is the first number n, where the sum of numbers from 1 to n is greater than 100 Trial and error: The worst case happens when the bulbs break at floor 13. If you start from the 14th floor and the bulb breaks, then you start at the bottom floor and work your way up. If it doesn’t break and you try it again from the 28th floor and it breaks, then you go back down to the 15th and work your way up 1 floor at a time.

Assuming you know nothing about the light bulb, I believe the 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99 increment would by far be the best option. I compared it against fixed I did the calculations below with this method, fixed increments of 10 and fixed increments of 9. Average Drops per Digit (1-100) - 14inc is 9.47 -10fixed is 10 - 9fixed is 10.02 Max Potential Drops - 14inc is 14 - 10fixed is 19 - 9fixed is 19 Comparing the 3 vs the digits, how many times are they the most efficient method - 14inc wins out 48 times - 10fixed wins 41 times - 9fixed wins 40 times *Note the total is over 100, if there was a tie those methods each got a win. The only concern against the 14 increments is that it performs poorer at the beginning, but if you don't know when exactly it will break and believe that it could be at any floor then it wouldn't matter.

I flagged Nub data scientist's answer as useful, because it shows an interesting flaw in reasoning. The 3 random variables are not to be treated as intrinsically independent. Only conditioned on the truth (raining/not raining) are they independent.

Isn't the answer 2/3. The key thing is that they are ALL saying "Yes". You can't have all 3 says yes and have some people lying and some people telling the truth. It either is raining or it isn't. Not both. They either are all lying or all telling the truth. Since they are all in agreement (all lying or all truthful), they are essentially voting as one person. What is the probability that one person is telling the truth? 2/3

Answer from a frequentist perspective: Suppose there was one person. P(YES|raining) is twice (2/3 / 1/3) as likely as P(LIE|notraining), so the P(raining) is 2/3. If instead n people all say YES, then they are either all telling the truth, or all lying. The outcome that they are all telling the truth is (2/3)^n / (1/3)^n = 2^n as likely as the outcome that they are not. Thus P(ALL YES | raining) = 2^n / (2^n + 1) = 8/9 for n=3 Notice that this corresponds exactly the bayesian answer when prior(raining) = 1/2.

TLP and nub data scientists, Your answers include possibilities which are not feasible; we cannot have any combination of 2/3 and 1/3 together... what about (2/3)^3?

I agree with TLP and nub scientist. For me, the question is really (1 - the odds that all three of your friends are lying to you) Clearly 1 - 1/3 * 1/3 * 1/3. It's convenient that they all gave the same answer, otherwise it would be more difficult.

Let Y denote rain, N denote no rain Actual Answer probability ------------------------------------------ Y=> 8/27 YYY, 1/27 NNN, 12/27 YYN, 6/27 YNN N=> 1/27 YYY, 8/27 NNN, 6/27 YYN, 12/27 YNN So,  P(Y|YYY) = (8/8+1) = 8/9

The probability of raining is that they are all telling the truth, therefore, (2/3)^3.

26/27 is incorrect. That is the number of times that at least one friend would tell you the truth (i.e., 1 - probability that would all lie: 1/27). What you have to figure out is the odds it raining | (i.e., given) all 3 friends told you the same thing. Because they all say the same thing, they must all either be lying or they must all be telling the truth. What are the odds that would all lie and all tell the truth? In 1/27 times, they would the all lie and and in 8/27 times they would all tell the truth. So there are 9 ways in which all your friends would tell you the same thing. And in 8 of them (8 out of 9) they would be telling you the truth.

There is an obvious conceptual reason as to why several answers here (ones that don't use Bayes' formula) are incorrect. The probability in question has to depend on the probability of rain in Seattle. If, for the sake of discussion, it ALWAYS rains in Seattle, i.e. P(rain)=1, then the required prob. is always 1 as well. Likewise if it's a place where it never rains, or if the question asks about the prob. of it raining elephants given the 3 friends said yes, it'd be still 0. I believe this is a std. textbook example of the Bayes' formula, anything short of that I don't think will work out.

Please correct me if incorrect. But I would just prefer to condition. either they are all telling the truth and its it raining or they are all lying and it is not raining. P(rain)=P(rain|truth,truth,truth)*P(truth,truth, truth)+P(rain|lie,lie,lie)*P(lie,lie,lie) notice that truth does not mean yes it is raining, it simply corresponds to them telling the truth. Since they said yes, IF they were lying and we knew they were lying then the probability of rain would be zero, thus eliminating the second term. P(rain)=P(rain|3xtruth)*P(3xtruth) and the probability of the truth is (2/3)^3 and the probability of rain if they are telling the truth is 1. I did a little skipping of steps, since truth doesnt equal yes, but i just sort of meshed it toegher towards the end

YES=yes,yes,yes T=truth, truth, truth L=lie,lie,lie P(Rain|YES)=P(Rain|YES,T)*P(T)+P(Rain|YES,L)*P(L) P(Rain|YES,L)=0==> whats the probability of rain given we know that they are lying and theyve told us it is raining. P(Rain|YES)=P(Rain|YES,T)*P(T) P(Rain|YES,T)=1==> whats the probability of it raining given that they are telling the truth and have told us its raining then P(T)=(2/3)^3 its obvious. why in the world would i do bayesian methods when its certain

I agree with (2/3)^3.

Interview Candidate solves this problem using Bayesian stats despite the fact that no enough information is given to do Bayesian probability analysis i.e. he had to pull the probability of it raining in Seattle out of thin air when it was not given in the interview question. With only the information from the interview question, we have to assume that friends are either all lying or all telling the truth. Let truth=T and lie=L P(TTT)=8/27, P(LLL)=1/27, P(TLL)=2/27,P(TTL)=4/27. But we know that they all had the same answer, so we must compare P(TTT) to P(LLL). P(TTT) is 8 times more likely than P(LLL), so we have P(All same answers|TTT)=8/9, P(All same answers|LLL)=1/9. Therefore the solution given ONLY THE INFORMATION GIVEN is P(Rain)=8/9, P(Dry)=1/9.

This problem requires the marginal probability of rain to solve, following Interview Candidate's answer. M.B. provides the rationale behind why the bayes approach is necessary: if the pr(rain) = 0, then the pr(rain|y, y, y) = 0. (maybe it is July in Seattle). A few conceptual problems in many answers that I want to point out: 1) There is lots of conflation between Pr(truth) and Pr(Y). Pr(truth) = Pr(Y|R) does not equal Pr(Y). 2) Consider there is only a single friend and they say yes, the logical conclusion from a lot of these answers is that Pr(Rain|Yes) = Pr(Yes|Rain) = 2/3, which is not correct. Bayes' rule is very clear in this simpler case. 3) The friends' answers are conditionally independent assuming no collusion. The combinations of their honesty/lying adds no additional information. The marginal probabilities are not independent, Pr(y,y,y) does not equal pr(y)^3, it equals pr(y,y,y,rain) + pr(y,y,y, no rain), the integration of the joint space over rain. Using conditional independence and bayes rule, this becomes: pr(y|rain)^3*pr(rain) + pr(y|no rain)^3(1-pr(rain)). A more general solution using Pr(rain) = r. Pr(rain|y,y,y) = Pr(y,y,y|rain)*pr(rain)/pr(y,y,y) #Bayes' formula pr(y,y,y|rain) = pr(y|rain)^3 = (2/3)^3 #conditional independence pr(y,y,y) = pr(y|rain)^3*pr(rain) + pr(y|no rain)^3*pr(no rain) #by definition, see point 3 the answer: r*(2/3)^3 / [r*(2/3)^3 + (1 - r)*(1/3)^3]

It should be (2/3)^3, I think zen and todo is correct.

Most of the answers/comments made all unconditional assumptions except a few reasonings that lead to the 8/9 probability. Note that the question states that "Each of your friends has a 2/3 chance of telling you the truth". This essentially means P(raining, yes) + P (non-raining, no) = 2/3. Any attempts to interpret this as conditional probability P(raining | yes) = 2/3 or P(yes | raining) = 2/3 are making other assumptions.

8/27 is not the answer. For the weather to be nice in this case, all 3 of your friend NEED to have lied to you. Therefor the odds are 1/27.

What if the answer is 50% since the chance of rain and not rain does not depend on what your friends tell you.

In the absence of further information, the only correct answer is the posterior probability of rain p is in the interval (0, 1). In the absence of further information any prior is as good as any other, so by implication the posterior can take any value as well. The interval for p can be restricted to [0, 1] on the assumption that the question to the friends would not be posed if the prior is absolute certainty whether it will rain or not. With the further assumption that the prior probability is measured with limited precision (e.g. rounded to a percentage point), the posterior would be in the interval (0,075, 1). If the alternative assumption is made that information from the friends will be requested only if it had any chance to move the posterior below or above 0.5, the posterior interval for the probability is (0.5, 1). any more precise answer than that requires further information about the prior which is not supplied in the original problem formulation. Also note that even a precise answer about the probability of rain is not sufficient to answer the question whether an umbrella should be brought or not.

The probability of each of the friend say "YES" is 2/3 * 2/3 * 2/3 = 8/27. Now the probability that it is actually raining in Seattle depends on that how do I select them to phone. There is only three way to select and phone them. So, the probability that it is actually raining in Seattle is 3 * (8/27) = 8/9.

Rule of conditional probability states P(A|B) = P( A & B ) / P(B) Reformulating to this case, P(Rain | 3Y) = P(R & 3Y) / P(3Y) P(R & 3Y) = 2/3 ^3 (if it is raining, then they must all speak the truth) = 8/27 (one could multiply probability of rain here. I assumed as prior) P(3y) = all truth or all lie = 2/3 ^ 3 + 1/3 ^3 = 9/27 hence P(R | 3Y) = 8/9

Let X be the probability it's raining. Obviously we want P(X|all three say yes). Now let Y be the probability at least one of them is lying. If Y = 0 it's easy to solve, if not then not so easy. Now you keep going.

Obvious, bayesian is a way to go...

There is a way to easily confirm the right answer. Just write a computer simulation and run it a few million times, which I did. If the long term chance of rain in Seattle is 25%, the chance it is raining now, given the YYY answers and the 2/3 truth 1/3 lying, is 73% (rounded to whole number), which is the same as 8/11, so the reasoning with the Bayesian math is correct.

This can easily be solved without Bayes: There are two cases: Case 1: It is raining and all friends are telling the truth: 0.25*(2/3)^3 = 1/4*8/27 Case1: It is not raining and all friends are lying: 0.75*(1/3)^3 = 3/4*1/27 Probability: P(E) = Case1 / (Case1+Case2) = (1/4*8/27) / (3/4*1/27 + 1/4*8/27) = 2 / (11/4) = 8/11

Closest points

If you group by parent_id, you'll be leaving out all posts with zero comments.

select number_comments, count(submission_id) as number_posts from ( # more than zero comments select submission_id, count(post_id) as number_comments from ( select submission_id, case when parent_id is null 1 else 0 end as post, case when parent_id is not null parent_id else null end as post_id, body from Submissions )k where post =0 group by submission_id ) k1 group by number_comments union select number_comments, count(submission_id) as number_posts from ( # comments= 0 select submission_id, 0 as number_comments from ( select submission_id, case when parent_id is null 1 else 0 end as post, case when parent_id is not null parent_id else null end as post_id, body from Submissions )k where post =1 group by submission_id ) k1 group by number_comments

@ RLeung shouldn't you use left join? You are effectively losing all posts with zero comment.

select k.post_id, count(submission_id) -1 from (select submission_id, case when parent_id is null then submission_id else parent_id end as post_id from submissions) t group by post_id

select t.post_id, count(t.submission_id) -1 from (select submission_id, case when parent_id is null then submission_id else parent_id end as post_id from submissions) t group by post_id

select parent_id as post, count(parent_id) as num_of_comments from submissions group by parent_id union select submission_id as post, 0 as num_of_comments from submissions where parent.id=null

select comments_count, count(submission_id) as post_count from ( select submission_id, count( distinct parent_id) as comments_count from Table A group by submission_id )A group by comments_count

I think all of the Posts are missing Parent_ID. I am editing the code shared above. This will solve the duplicate problem select parent_id as post, count(parent_id) as num_of_comments from submissions group by parent_id union select submission_id as post, 0 as num_of_comments from submissions where parent.id not in (select submission_id from submissions)

Here is the solution. You need a left self join that accounts for posts with zero comments. Select children , count(submission_id) from ( Select a.submission_id, count(b.submission_id) as children from Submissions a Left Join submissions b on On a.submission_id=b.parent_id Where a.parent_id is null Group by a.submission_id ) a Group by children

I've tested all these on a mock data set and none of them work! Does anyone have the correct solution? I'm stuck on this one..

Posts and comments in the same table looks weird. Here's my attempt (made easy with CASE) to exclude all the posts from the table and grouping/counting comments. SEL parent_id ,COUNT(*) as comment_count ( SEL * ,CASE WHEN perent_id IS NULL THEN 'Post' ELSE 'comment' END as post_or_comment FROM Submissions ) a WHERE post_or_comment = 'comment'

I think it is pretty straight forward. All the posts will have null parent_id. Considering the table schema to be something like this: CREATE TABLE submissions ( submission_id INT, body VARCHAR(500), parent_id INT ); SELECT DISTINCT nvl(parent_id::TEXT,'Post with no comments') AS post_id, COUNT(CASE WHEN parent_id IS NOT NULL THEN submission_id ELSE 0 END) AS number_of_comments_or_post FROM submissions GROUP BY 1; This will give results like this: post_id number_of_comments_or_post Post with no comments 8 1 10 7 11 13 8 19 9 25 7 So, the first row will give the number of posts with no comments which is 8 and remaining rows tell the number of comments per post. Is there a flaw in this?

Not the shortest answer but I think much clearer than anything posted here. Also gives output table that could actually be fed directly into a histogram which was part of the question. SELECT CASE WHEN num_comments IS NULL THEN 0 ELSE num_comments END AS num_comments, COUNT(parent_post_id) AS cnt_posts FROM ( SELECT submission_id AS parent_post_id, comment_count.num_comments FROM Submissions WHERE parent_id IS NULL LEFT JOIN ( SELECT parent_id, COUNT(parent_id) AS num_comments FROM Submissions WHERE parent_id IS NOT NULL GROUP BY 1 ) comment_count ON submission_id = comment_count.parent_id ) GROUP BY 1 ORDER BY 1

select p.parent_id as posts, count(c.submission_id) as commentcount from submissions c inner join submissions p on c.parent_id = p.submission_id group by p.parent_id;

select case when parent_id is not null then parent_id else sub_id end as post_id, sum(case when parent_id is not null then 1 else 0 end) as comment_count from submissions group by case when parent_id is not null then parent_id else sub_id end;

Create table: create table submissions ( submission_id int null, body varchar(500) null, parent_id int null ); Insert records: (change your database name) INSERT INTO employees.submissions (submission_id, body, parent_id) VALUES (1, 'POST1', null); INSERT INTO employees.submissions (submission_id, body, parent_id) VALUES (null, 'C1', 1); INSERT INTO employees.submissions (submission_id, body, parent_id) VALUES (2, 'POST2', null); INSERT INTO employees.submissions (submission_id, body, parent_id) VALUES (3, 'POST3', null); INSERT INTO employees.submissions (submission_id, body, parent_id) VALUES (null, 'C2', 3); INSERT INTO employees.submissions (submission_id, body, parent_id) VALUES (null, 'C3', 3); Solution: SELECT a.submission_id AS post_id, a.body, sum(CASE WHEN t.parent_id > 0 THEN 1 ELSE IFNULL(t.parent_id,0) END) AS comment_id FROM submissions AS a LEFT JOIN (SELECT b.parent_id FROM submissions AS b) t ON a.submission_id = t.parent_id WHERE a.submission_id IS NOT NULL GROUP BY post_id; Results: 1 POST1 1 2 POST2 0 3 POST3 2

CREATE TABLE users( sid INT , pid INT , body Varchar(255)); insert into users Values ( 2,null, "cover"), (1,2,"Ami is"),(3,2,"hi"),(4,2,"good pic"),(5,null ,"profil pic"),(6,5,"nice"); (select pid , COUNT(pid) as total from users where pid is not null group by pid)

create table subs( sub_id integer, parent_id integer ) insert into subs values(1,null); insert into subs values(2,null); insert into subs values(3,null); insert into subs values(4,null); commit; insert into subs values(5,1); insert into subs values(6,1); insert into subs values(7,1); insert into subs values(8,1); insert into subs values(9,2); insert into subs values(10,2); insert into subs values(11,3); insert into subs values(12,3); insert into subs values(12,4); commit; select * from subs select cc, count(sub_id) from ( select a.sub_id, count(b.sub_id) cc from subs a inner join subs b on(b.parent_id = a.sub_id) group by 1) group by 1

I found it easier to explain when I broke it out into named sub tables to handle the case when there are no comments on a post and you want the end result to be the histogram of the number of comments per post: with parent_comment_ct as ( SELECT parent_id, COUNT(parent_id) AS num_comments FROM submissions WHERE parent_id IS NOT NULL GROUP BY parent_id ), submission_comment_ct as ( SELECT su.submission_id AS parent_post_id, pcc.num_comments AS num_comments FROM submissions su LEFT JOIN parent_comment_ct pcc ON su.submission_id = pcc.parent_id WHERE su.parent_id IS NULL ) SELECT CASE WHEN scc.num_comments IS NULL THEN 0 ELSE scc.num_comments END AS num_comments, COUNT(scc.parent_post_id) AS cnt_posts FROM submission_comment_ct scc GROUP BY 1 ORDER BY 1

SELECT recommended_page FROM (SELECT f.user1_id as users, f.user2_id as freinds, l.page_id as recommended_page FROM friendship f INNER JOIN likes l ON f.user2_id = l.user_id WHERE f.user1_id = 1 UNION ALL SELECT f.user2_id as users,f.user1_id as friends,l.page_id as recommended_page FROM friendship f INNER JOIN likes l ON f.user1_id = l.user_id WHERE f.user2_id = 1) MINUS (SELECT page_id as recommended_page FROM likes WHERE user_id = 1);

SELECT recommended_page FROM (SELECT f.user1_id as users, f.user2_id as freinds, l.page_id as recommended_page FROM friendship f INNER JOIN likes l ON f.user2_id = l.user_id WHERE f.user1_id = 1 UNION ALL SELECT f.user2_id as users,f.user1_id as friends,l.page_id as recommended_page FROM friendship f INNER JOIN likes l ON f.user1_id = l.user_id WHERE f.user2_id = 1) MINUS (SELECT page_id as recommended_page FROM likes WHERE user_id = 1);

select c.subID as SubmissionID, count(c.body)-1 as Counts_Comments from subm c LEFT JOIN subm b ON c.subID = b.pID where b.pID is null AND c.pID is NULL group by c.subID UNION ALL select a.pID as SubmissionID, count(a.body) as Counts_Comments from ( select *, case when pID IS NULL then 'P' Else 'C' END as P_O_C from subm)a where P_O_C = 'C' group by a.pID Order by SubmissionID;

select a.user_name,b.user_name,page_liked from services_db.pages_liked a, services_db.user_friends b where 1=1 and a.user_name = b.friend_user and a.page_liked not in ( select page_liked from services_db.pages_liked c where 1=1 and c.user_name = b.user_name ) ;

function reposition(arr, indices) { var newArr = []; // I'm not sure if extra space is allowed. If it is, the solution should be this simple. for(var i = 0; i < arr.length; ++i) { var newIndex = indices[i]; newArr[newIndex] = arr[i]; } return newArr; } var arr = ["a", "b", "c", "d", "e", "f"]; var indices = [2, 3, 4, 0, 5, 1]; reposition(arr, indices); // returns: ["d", "f", "a", "b", "c", "e"]

Essentially the same as Anh's answer but less code, assuming ES5 is available var arr = ["a","b","c","d","e","f"]; var indices = [2, 3, 4, 0, 5, 1]; arr = indices.map(function (item, index) { return arr[indices.indexOf(index)]; });

//Bringing 2 UNIDEAL solutions var A = ['a', 'b', 'c', 'd', 'e', 'f']; var B = [4, 3, 2, 5, 1, 0]; //PROBLEM we need a copy of an A to get a proper base index of an element in the sort function var BaseA = A.concat([]); A.sort(function(a, b){ return A.indexOf(a) < B.indexOf(BaseA.indexOf(a)); }); alert[A); //OR We'll just add up to A sorted values and then cut off the tail, I believe it's //almost same performace as to create new array but well, it does mutate A //so is it "Done is better then perfect" after all? :) for(var i = 0, l = B.length; i < l; i++){ A.push(A.splice(B[i], 1, undefined).pop()) } A.splice(0, B.length); alert[A);

void swap(int a[],int b[], int i,int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; temp = b[i]; b[i] = b[j]; b[j] = temp ; } void mutate(int a[], int b[], int n) { // solutions 1 . we can sort an array b and while doing that we will // adjust the A[] elements as well // but it is going to be nlogn // Solution 2: swap the elements of b[] ( together with a[] elements) until the number in the b[i] matches the index i then move on to i+1 // for each swap we are placing one item in the right place. // so the complexity would be O(n) for(int i=0;i= n) { cout << "Index out of bound " << b[i] <<< endl; break; } if(i != b[i]) // this may go in infinite loop, if the indices are not good in b like two 0s in the b[] { if(b[i] == b[b[i]]) { cout << "Infinite Loop Detected for the index " << b[i] << endl; break; } swap(a,b,i,b[i]); } else { i++; } } }

var assert = require('assert'); var arr = ['a','b','c','d','e','f','g', 'a']; var indexes = [2,1,0,3,4,5,7,6] var mutate = function mutate(arr, ind){ var swapped = {}; indexes.forEach(function(nI, i){ var newEl, el; el = arr[i]; arr[i] = swapped[nI] || arr[nI]; swapped[i] = el; }); }; mutate(arr, indexes) assert.deepEqual(arr, ['c','b','a','d','e','f','a', 'g']);

function remap(arr1, arr2){ var tmp1 = arr1.slice(); arr2.map(function(newIdx, realIdx){ arr1[newIdx] = tmp1[realIdx]; }); }

Working off of Travis' answer, but removing the need for a new array: function swap(arr, idx1, idx2) { var temp = arr[idx1]; arr[idx1] = arr[idx2]; arr[idx2] = temp; } function reposition(input, indices) { indices.forEach(function(newIdx, i) { if (indices.indexOf(i) > i) { swap(input, i, newIdx) } }); }

Here's my take on this, though I think my approach is cheating a little bit since I'm mutating, but not directly in place. It does add a little space complexity since I'm adding a new array, but there are no infinite loop problems and the runtime is just O(n) (I think...I'm really bad at big O notation calculation). function mutateArray(arr,indexes) { var newArr = []; indexes.forEach((ix) => { newArr.push(arr[ix]); }); arr.splice(0).push.apply(arr,newArr); }

OK, and after seeing that there's some confusion amongst expected outputs, I've updated my implementation based on the other take on the expected output. This version assumes that each index in the provided index array is the index value of where the element is in the starting array. So if the value at indexes[0] = 3, that would mean the first value in the output would be originalArray[3]; function mutateArray(arr,indexes) { var newArr = new Array(arr.length); indexes.forEach((ix, i) => { newArr[ix] = arr[i]; }); arr.splice(0).push.apply(arr,newArr); } var original = [2, 3, 1, 6, 4]; var ixes = [1, 2, 0, 4, 3]; expected results: [1, 2, 3, 4, 6] For clarity, the other variant is in my answer above. That assumes that the value of each element in the indexes array represents the index of the value of the original array. So in the example above, the output would be [3, 1, 2, 4, 6]. Apparently a common twist is to then ask the interviewee to do this without a new array. So that's worth practicing too.

OK, and here's my in place version. It could definitely be improved since I just wrote it using the bubble sort algorithm. Any other sorting algorithm would work just fine too. Basically it works by sorting the index array and every time something in the index array is moved, it moves the same elements on the original array. function mutateArray(arr,indexes) { var swapped = true; while(swapped) { swapped = false; for(var i = 1; i indexes[i]) { swap(arr,i-1,indexes[i-1]); swap(indexes, i-1, indexes[i-1]); swapped = true; } } } } function swap(arr, oldIx, newIx) { var temp = arr[newIx]; arr[newIx] = arr[oldIx]; arr[oldIx] = temp; } An example: var arr = [5,2,1,8,9,1]; var indexes = [2,4,1,0,3,5]; var expectedResult = [8,1,5,9,2,1];

function changeArr(arr,indArr) { var i, retArr = []; for( i = 0; i

Simple solution using .map() & ES6: const inputArray = ["one", "two", "three", "four", "five", "six"] const indexArray = [2, 1, 3, 5, 4, 6] function mutate(input, index) { const newArray = index.map(i => input[i - 1]) return newArray } // output: ["two", "one", "three", "five", "four", "six"]

or if you truly want to mutate the array rather than outputting a new array: let inputArray = ["one", "two", "three", "four", "five", "six"] const indexArray = [2, 1, 3, 5, 4, 6] inputArray = indexArray.map(i => inputArray[i-1]) // output: ["two", "one", "three", "five", "four", "six"]

const sortBy = (inputArr, idxArr) => idxArr.reduce((acc, x) => acc.concat(inputArr[x]), [])

For all of the answer using map, and visited arrays, just to say that you are creating a new array, and from the word "mutate" I assume they don't want any extra space being used at all (also it takes longer) My solution using ES6 is: function mutate(input, indices) { const swap = (i, j) => { let tmp = input[i]; input[i] = input[j]; input[j] = tmp; }; indices.forEach((newIndex, i) => swap(newIndex, i)); return input; }

Also for those using indexOf that's an extra O(n) you're using there!

let input = [1,2,3,4,5]; let newIndex = [3,1,0,4,2]; function transform(input, newIndex) { let res = []; for (let i = 0; i < input.length; i++) { let index= newIndex[i]; let val = input[i]; res[index] = val; } return res; } function transform2(input, newIndex) { let i = 0; while (i < input.length) { if (i == newIndex[i]) { i++; } else { swap(input, i, newIndex[i]); swap(newIndex, i, newIndex[i]); } } } function swap(arr, i, j) { let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }

function sort(a,b){ for(let i=0, l=b.length; i

function correctTheOrder(arr, indices) { return arr.map((noUse, index) => { return arr[indices.indexOf(index)] }) } // Time complexity = O(n2) // Space complexity = O(n) function correctTheOrder2(arr, indices) { let i = 0; while (i < arr.length) { if (indices[i] === i) { i++; } else { let temp = arr[i]; arr[i] = arr[indices[i]]; arr[indices[i]] = temp; temp = indices[i]; indices[i] = indices[indices[i]]; indices[temp] = temp; } } return arr; } // Time complexity = O(n) // Space complexity = O(1)

O(n) time and O(1) solution. Only issue is input can't be negatives or zeroes. function changeIdxO1(A,I) { for (let i = 0; i 0) { [A[next], A[current]] = [A[current], A[next]]; [I[next], I[current]] = [I[current], I[next]]; A[next] = -A[next]; next = I[current]; } } for (let i = 0; i < A.length; i++) A[i] = Math.abs(A[i]); return A; }

const updatePositions = (A,B) => B.map(item => A[item]) Would that be enough?

function excludeItems(items, excludes) { return excludes.reduce((arr, pair) => { arr.push(items.filter(item => item[pair.k] === pair.v)); return arr; },[]); }

If the objetive is exclude the elements using the excludes filters the function should be: function excludeItems(items, excludes) { excludes.forEach(pair => { items = items.filter(item => item[pair.k] !== pair.v); }); return items; }

This solution will give much faster and immutable result. You can test with performance.now items.reduce((allItems, item) => { if(!excludes.some(exclude=>item[exclude.k] === exclude.v)){ allItems.push(item); } return allItems; }, []);

you can map the exclude array into objects of object to make it run in constant time. var excludes = turnIntoMap(excludes); function turnIntoMap(arr){ var hash = {}; arr.forEach(function(val){ if(hash[val[k]]){ hash[val[k]][val[v]] = 1 } else { hash[val[k]] = {}; hash[val[k]][val[v]] = 1 } }); } items.filter(function(item){ for(var key in item){ if(excludes[key]){ if(excludes[key][item[key]]){ return false; } } } return true; });

let newItems = items.reduce((acc, item) => { let result = excludes.some(exclude => item[exclude['k']] === exclude['v']); if (!result) { acc.push(item); } return acc; }, []); console.log(newItems);

I agree with converting the excludes to an object, but in order to get linear performance that doesn't depend on the number of excluded things, you have to concatenate the k and v into one value to be used as the key in the object: let excludesObject = {}; excludes.forEach(pair => excludesObject[`${pair.k}_${pair.v}`] = true); Then you can check if an item should be excluded in O(k) time where k is the number of keys in an item. And the whole thing will run in O(nk) where n is the number of items. // if there is some key which is found in the excludesObject, the filter will return false items = items.filter(item => !Object.keys(item).some(key => excludesObject[`${key}_${item[key]}`]); ); Facebook, hire me! lol

build excludes table as follows map = { color: { red: 1, green:1 }, type: { tv: 1 } } Solution: function excludeItems(items, excludes) { let map = {}; for (let exclude of excludes) { let { k, v } = exclude; if (map[k] != null) { map[k][v] = 1; } else { map[k] = { [v]: 1 }; } } return items.filter(item => { for (let key in item) { if (map[key] && map[key][item[key]]) { return false; } } return true; }); }

const items = [ {color: 'black', type: 'phone', age: 20}, {color: 'red', type: 'tv', age: 18}, {color: 'silver', type: 'tv', age: 20}, ]; const excludes = [ {k: 'type', v: 'tv'}, {k: 'color', v: 'silver'}, ]; function excludeItems(items, excludes) { excludesObject = {}; excludes.forEach(pair => { excludesObject[pair.k] = pair.v; }); items = items.filter(item => { for (key in excludesObject) { if (item[key] === excludesObject[key]) { return false; }; } return true; }); return items; } console.log(excludeItems(items, excludes));

function excludeItems(items, excludes) { const map = new Map( excludes.map( el => [ el.v, el.k ] ) ); return items.filter(item => ( !Object.keys(item).some(key => map.has(item[key]) && map.get(item[key]) === key) )); }

1. Excluding any items that is has an element in the "excludes" collection. 2. (a) "filter" returns anything that is true in the conditional. This is doing the opposite. (b) it's checking item[pair.v], which will never return a value. It should be "item[pair.k] !== pair.v" 3. Currently, it's O(n^2). For each excluding element, it's traversing through the entire 'items' list. A start would be to condense the "excludes" object by creating lists. Ex: excludes = {['k': 'color', 'v': ['blue', 'red', 'purple']] "item[pair.k].includes(pair.v)" ***NOTE: (this is still O(n^2), but it's more efficient than before)*** Not sure how to condense it down to O(n log(n))

"excludes table as follows" answer from above can be improved if replace the constructed object (aka excludes table) with Set.

1. fixing a bug in the filter function. function excludeItems(items, excludes) { excludes.forEach(pair => { items = items.filter(item =>item[pair.k] !== pair.v); }); return items; } 2. optimizing... the function is O(n^2). still we can optimize in worst case O(n^2) but , as soon as it finds excluded condition meets, no need to see remaining excluded pairs. just jumping to next item. Array.forEach or Array.map does not allow bread in the middle of loop while for sentence does. So, I replaved Array.forEach to 'for' sentence. function excludeItems(items, excludes) { let result = items.filter(item => { for(let e = 0; e < excludes.length; e++) { let pair = excludes[e]; if((item[pair.k] === pair.v)) { return false; // moving to next item. no need to see next excluded element } } return true; }); return result; }

(fixing typo) 1. fixing a bug in the filter function. function excludeItems(items, excludes) { excludes.forEach(pair => { items = items.filter(item =>item[pair.k] !== pair.v); }); return items; } 2. optimizing... the function is O(n^2). still we can optimize in worst case O(n^2) but , as soon as it finds an excluded condition meets, no need to see remaining excluded pairs. just jumping to next item. Array.forEach or Array.map does not allow 'break' in the middle of loop while regular FOR sentence does. So, I replaced Array.forEach with FOR sentence. function excludeItems(items, excludes) { let result = items.filter(item => { for(let e = 0; e < excludes.length; e++) { let pair = excludes[e]; if((item[pair.k] === pair.v)) { return false; // moving to next item. no need to see next excluded element } } return true; }); return result; }

I got this problem to in my video interview, The way I solved the problem is re-estrcuturing the excludes array with and Object that the keys are the attributes of the items and the value is a set I was told that the number of attributes of one item is always less than 10 so the overall complexity of my solution was O(10*n)

function excludeItems(items, excludes) { let excludesMap = excludes.reduce((entry, result)=>{ entry[result.k + result.v] = true; return entry; },{}); return items.reduce( (result, item) => { let updatedObject = Object.keys(item).reduce( (result,key) => { if(!excludesMap[key + item[key]]){ result[key] = item[key] } return result; }, {}) result.push(updatedObject) return result; }, []) }

function excludeItems(items, excludes) { const keyFormat =(key,value)=>`${key}_${value}`; excludes = excludes.reduce((result, exclude)=>{ result[keyFormat(exclude['k'], exclude['v'])] = true; return result; },{}); return items.filter((item)=>{ for(let key of Object.keys(item)){ if(excludes[keyFormat(key,item[key])]) return false; } return true; }); } const items = [{ color: 'red', type: 'tv', age: 18 }, { color: 'silver', type: 'phone', age: 20 }]; const excludes = [{ k: 'color', v: 'silver' },] console.log(excludeItems(items, excludes)); //Time Complexity: O(E + K * n) {where E: is excludes length, K: keys in the items, n: Total number of items }

// space O(n) time 0(n * k) function excludeItemsBetter(items, excludes) { const map = new Map(); // O(n) for (let i = 0; i { for (const key in item) { const mapKey = `key:${key}-val:${item[key]}`; if (map.has(mapKey)) { return false; } } return true; }); }

function excludeItemsBetter(items, excludes) { const map = new Map(); for (let i = 0; i { for (const key in item) { const mapKey = `key:${key}-val:${item[key]}`; if (map.has(mapKey)) { return false; } } return true; }); }

Time complexity O(n*k) where k is the number of excludes. Nothing change if you change from: for(const item of items){ for(const exclude of excludes) { ... } } to for(const exclude of excludes){ for(const item of items) { ... } } time complexity will be the same. Main problems in this code I see next: 1. typo in the line ```item[pair.k] === item[pair.v]``` should be ```item[pair.k] === pair.v``` 2. overriding incoming parameter, it does not mutate the global items, but still it's bad practice in my opinion. 3. we can rewrite the code without using extra variables. my try: const excludeItems = (items, excludes) => items.filter(item => !excludes.some(({k,v}) => item[k] === v))

In Python: (just numbers) def rem_elem_num(listA,listB): sumA = 0 sumB = 0 for i in listA: sumA += i for j in listB: sumB += j return sumA-sumB (general) def rem_elem(listA, listB): dictB = {} for j in listB: dictB[j] = None for i in listA: if i not in dictB: return i

How about this in python, will this work? x = set(listA)-set(listB) print(x)

All these supposed answers are missing the point, and this question isn't even worded correctly. It should be lists of NUMBERS, not "objects". Anyway, the question is asking how you figure out the number that is missing from list B, which is identical to list A except one number is missing. Before getting into the coding, think about it logically - how would you find this? The answer of course is to sum all the numbers in A, sum all the numbers in B, subtract the sum of B from the sum of A, and that gives you the number.

# python code def missing_obj(original_lst, new_lst): for x in new_lst: original_lst.remove(x) return original_lst

select b.element from b left join a on b.element = a.element where a.element is null

two ways to do it using sql: 1. select * from A where not in (select * from B) -- assuming you know what element you're looking for 2. select * from (select * from A UNION select * from B) having count(element) = 1 -- again assuming you know the element

In R: removed_element <- A[which(!A %in% B)] removed_element

Depends on the kind of elements in the lists. If they're numbers, sum(A) minus sum(B) will give the missing element. If they're characters/strings, just dump the elements of A into a dictionary and check each element in B for existence in A.

[i for i in A if i not in [j for j in B]]

SQL: select a.list as a, b.list as b from ListA as a full join ListB as b on a.list = b.list where a.list eq '' OR b.list eq "" ;

missing_letters = [] for letter in A: if letter in B: pass else: missing_letters.append(letter) print (missing_letters)

Python: sum(A)-sum(B)

In SQL: SELECT A.object FROM A LEFT JOIN B ON A.object = B.object WHERE B.object IS NULL;

Careful, there could be a repeated object that's being removed. i.e. A = [3, 4, 5, 6, 5] B = [3, 4, 6, 5] This is how I would do it on Python (works for numbers and strings) def missingval(lA, lB): a = sorted(lA) b = sorted(lB) c = None for i in range(len(b)): if a[i] != b[i]: c = a[i] break if c is None: c = a[-1] print(c, "was removed from list A")

A = [1,2,3,4,5,6,7,8] B = [1,2,3,4,5,6,8] [i for i in A if i not in B]

find the sum of the two list and subtract. ans = sum(a) - sum(b) where a and b are list of numbers.