Find the minimum value in the stack in O(1) both time and space complexity.
Do you mean "design a stack where you can find the minimum value in O(1) both time and space complexity"? Because I don't see how you can do O(1) with an arbitrary stack.
Ask HN: What are the best interview questions you've been asked?
11–20 of 63 posts
Re: Ask HN: What are the best interview questions you've been asked?
#12one i really enjoyed solving: given an array of size (n - 1), containing all but one of the numbers between 1 and n, find the missing number in linear time and constant space.
Strict requirements (like linear and constant) give so much away about the nature of the solution.
"What's the best you can do within ..." adds an extra challenge - in particular I don't think I'd often see the constant space solution as perhaps one in logspace.
Re: Ask HN: What are the best interview questions you've been asked?
#13Find the minimum value in the stack in O(1) both time and space complexity.
Make another stack with the latest minimum, then when you pop that top value, you also pop it off the minimums stack. Then you have the last minimum before that one.
Is that it?
Re: Ask HN: What are the best interview questions you've been asked?
#14Find the minimum value in the stack in O(1) both time and space complexity.
Make another stack with the latest minimum, then when you pop that top value, you also pop it off the minimums stack. Then you have the last minimum before that one. Is that it?
What if you added values that are greater then the minimum at the top of the minimum stack but less than the next value on the minimum stack?
Re: Ask HN: What are the best interview questions you've been asked?
#15I liked one that involved implementing a graphing library for a memory-mapped bitmap display. It started with drawing a circle of radius R with origin X, Y but involved several iterations of optimization. You can get into a lot of interesting performance areas (caching, reuse, loop unrolling, etc.).
Re: Ask HN: What are the best interview questions you've been asked?
#16Find the minimum value in the stack in O(1) both time and space complexity.
Do you mean "design a stack where you can find the minimum value in O(1) both time and space complexity"? Because I don't see how you can do O(1) with an arbitrary stack.
Yes thats right, you can come up with any solution. But make sure O(1) is satisfied (both in time and space complexity).
Anyways I had failed to give proper answer and I was rejected in the interview. This was the last question of my last round!
Spoiler: Here is one such solution using a simple but very clever trick: http://www.geeksforgeeks.org/design-a-stack-that-supports-ge...
Re: Ask HN: What are the best interview questions you've been asked?
#17Find the minimum value in the stack in O(1) both time and space complexity.
Make another stack with the latest minimum, then when you pop that top value, you also pop it off the minimums stack. Then you have the last minimum before that one. Is that it?
Your using two stacks now. This is the solution that I had told but your not satisfying the condition w.r.t to space , its O(n) not O(1).
Re: Ask HN: What are the best interview questions you've been asked?
#18For a sys admin, devops, sre or whatever you want to call us this week, I like the following question for senior level people
What has been your biggest screw up to cause a production outage and what did you take from that?
If they say they never caused an outage or give some answer that isn't a screw up, I know one of two things
1) They arent senior level to be put in charge of handling major changes on production
2) They are the type of person that tries to hide screw ups from the rest of the team.
Re: Ask HN: What are the best interview questions you've been asked?
#19"We're going to build Google Maps using these satellite images. How would you do it?" This is the sort of open, large architectural question that I love and think really helps to understand a developer's skill set. It's great to be able to start very broad, but focus down into detail like CPU caching and the possible on-disk layout.
Any recommendations on sites where one can read about stuff like this? High Scalability (highscalability.com) is one resource I'm aware of (for people who are familiar with the site - any "must read" posts?). Thanks.
Re: Ask HN: What are the best interview questions you've been asked?
#20For a sys admin, devops, sre or whatever you want to call us this week, I like the following question for senior level people What has been your biggest screw up to cause a production outage and what did you take from that? If they say they never caused an outage or give some answer that isn't a screw up, I know one of two things 1) They arent senior level to be put in charge of handling major changes on production 2…
I like this, but I want to follow up by asking what your idea of a "good" answer is, what a "bad" idea is and how you would see through a bullshit answer.