Answer the question of why you did it the way you did throughly and completely.

Went really well actually, pretty much talked non stop for 50 mins till my throat hurt.

They did ask a few questions about how a library I chose to use worked, so it was fortunate I was a bit prepared for that. So if anyone else has something similar, if youre using a library for routing or whatever, make sure you know what the methods provided actually do with the info you give them.

I think one common set of questions is about how you would extend / add functionality. So good to think about where your design would be easy to extend and where it might fall down.

So the question is "given a list of numbers, return the max K numbers".

The approach I've been considering is using a min heap, insert the first K items from the List N, compare min vs N+1, if N+1 > min, insert N+1 and pop Min.

Second approach is use max heap, insert entire list then call pop K times (or poll or w/e the actual method is called)

So 2 questions Im debating with someone. What are the big Os for these 2 algorithms and is there a better way Im missing?

I believe approach one would be k initial inserts ( O(k lg k) ? ) + n potential inserts ( O(n lg k) ?)

Not sure on either of those at all tbh

Simplest: linear running time with some extra space for a heap is to just build a heap [O(n)], select the kth largest element [O(k) although O(n) is enough here], and then do a final pass through the list to return the larger numbers [O(n) time, O(n) space].

You can do this in less space by using a max-heap with k elements as you suggest; heapify the first k elements and then do n-k inserts [O(n log(k)) time, O(k) space].

But the best approach is introselect/quickselect style approach which can do this in linear time and no extra space (if you can mutate the original list).

O(n log n) runtime:
Just sort the list then traverse and return the first N elements

Assumes you can mutate the list. Does not require additional space complexity.

First approach: you are using a heap of size K. Thus each heapify(pop) is lg k. And since we have to go through the whole list, it will be O(n lg k)

Second approach: you insert the entire list in the beginning, thus the heap size of N. And you pop K times. Thus it is O(k lg n)

This question is a typical interview question. The best method here is quick select which is O(n) and constant space complexity.

This would be fine as a starting point for your answer but you should be able to improve significantly on this

I had a somewhat similar question at Google. A little more complex and I mentioned what Bantam222 suggested and they were quick to ask me if I can do better.

The running time for your second approach doesn't look right--it has to be at least Ω(n) since you need to read the list (and you can build the heap in the same time). But more to the point you can do better than just deleting the minimum k times--maybe you want to call this an "order statistic tree" but you basically can get it for free when building your heap as you can just check subtrees to find the kth smallest element.

Yeah, it's worth saying that, but of course they are going to ask you whether you can do better before you even finish saying sort :-). Still, if you don't already know the other answer, never hurts to say something correct first if it takes so little time.

I agree. If you start with the obvious brute force method, as long as you can explain it very simply and quickly, that's good. If you then move on to some better ways, then you're giving 2 or 3 correct answers instead of one. Also since allegedly what people are really looking for is your ability to solve problems on your feet, and not "knowing the answer" it looks more like what they want to see. I would argue that for most jobs being able to solve these problems is more of a curiosity than a really valuable skill.

Ah oops you are right! Forgot about the build heap. So it is O(n + k lg n).

I heard of order statistic tree, though it is still on my to-do list so I still don't quite understand it. Is it better than running quick select?

Another thing to add on to that problem. Once you start off with a brute force solution, you need to make sure your algorithm utilizes every info that is given.

For example in the problem described, the 3 key points are...

1. You know there are N elements
2. You know you need to select the top K elements.
3. Those K elements do not have to be sorted.

The 3rd point is an important point that the naive approach does not use to its advantage and should be a huge hint. Though if you don't know quick select, you are going to have a tough time in getting the optimal solution.

Not for this, no (I mean, you can't do better than linear!).

Sort of related to your last post (in thinking of what the minimal work to be done is, although sometimes that leads one astray): you have a heap: how quickly can you find the kth largest element? In particular, you might be able to search for it without having to pop elements off the heap (which requires some rebalancing/more work to modify and preserve some structure).

I'm curious to hear what kind of go-to interview questions that you guys ask?

I had a fun codeforces problem I was working on the other day that might have been a good interview question.

A store is selling N items. You know the prices of each item and also what the price will be next week. Some prices will go up and some will go down. Today you need to buy at least K items, and buy the rest of the N items next week.

What is the minimal amount of money you need to buy all N items?

I think everyone should choose Python or Java when they interview. I had a whiteboarding session with a guy who really did not like my use of idiomatic Ruby syntax and had trouble understanding/getting past it. You can blame the interviewer if you like, but that won't get you the job. Any thoughts on Java/Python2/Python3?

Can someone point out what's wrong with my strategy for solving this in terms of my logic?

This is a leetcode problem called 'beautiful arrangements':

The problem also states N will only be 15 at max, which I think is a hint they don't expect an efficient solution.

My method was to start with all the combinations for N-1, then append N to the arrays so for N=4 we start with the combos for N=3 and append 4,

Then for each of these arrays I check if I can swap the last element with any of the other elements. If so, I add that new array to another array called 'swaps'. The concatenation of the initial arrays and the swaps is then the solution.

So to get a solution for any N, I start with [[1,2],[2,1]] and just repeat the process up to N.

But my solution only works up to N==5 and then starts giving answers lower than expected. Here is the code,

For n=6 my function returns 32 but should be 36. I'm not ocd enough to be able to see which I'm missing...

Thanks for any help

One thing that might help with the counting is to recognize that prime numbers can only belong in certain places in the list (position 1, position i, or position ki where k is an even multiple of i).

Not sure if there is a shortcut way to turn that into a formula to quickly calculate the desired N for a given input size.

Build a table to see what slots a number can be in, and then do all permutations of that?

So table includes, for 1: [1 2 3 4 5 6] and for 2: [1 2 4 6] etc. Then start with 1, first element in valid list is 1. Then use for 2 the first element in its list which is 1, but that's occupied, so use the second, which is vacant, and so on.

For n<15 this should work fine.

this is a smart approach and I've seen a few implementations of it in the discussion area of leetcode.

what I'm really asking is why my strategy doesn't work. I don't see why I'm missing permutations.

Sorry by even I meant a natural number like k couldn't be 1.5 as opposed to k being even in the sense it is divisible by 2.

Sent from my SM-G900R4 using Tapatalk

Since you know of working approaches, why not just implement them and then figure out which permutations are missing from your solution? Having that list may give you some insight into what is going wrong.

so it's missing these 4 for n=6,

To look at the first one, in order to get there from a single swap would have required [2,3,1,4,5] be part of the solution to n=5... but it's not.

guess the type of answer I wanted doesn't exist. It just doesn't work lol. Just unfortunate it worked for small N and drove me down a dead end.

Subbed

https://leetcode.com/problems/maximu...y/description/

would you guys consider this question "easy"? I feel so stupid lol.