Two Plus Two Publishing LLC Two Plus Two Publishing LLC
 

Go Back   Two Plus Two Poker Forums > >

Notices

Programming Discussions about computer programming

Reply
 
Thread Tools Display Modes
Old 10-27-2017, 03:03 AM   #226
Barrin6
Carpal \'Tunnel
 
Barrin6's Avatar
 
Join Date: Dec 2005
Location: beyond legal blindness
Posts: 6,657
Re: Interview Test Questions Problems, Solutions, Links, Discussion

It's a classical problem that has been done to death which is why it might be marked easy.

If you can think of the brute force solution, there is a slight optimization to make it faster.
Barrin6 is offline   Reply With Quote
Old 10-28-2017, 04:00 AM   #227
muttiah
Carpal \'Tunnel
 
muttiah's Avatar
 
Join Date: Aug 2004
Posts: 23,101
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by lostmypw View Post
https://leetcode.com/problems/maximu...y/description/

would you guys consider this question "easy"? I feel so stupid lol.
I recall the optimal solution requires knowledge of dynamic programming, so not an "easy" question.
muttiah is offline   Reply With Quote
Old 10-28-2017, 04:06 AM   #228
muttiah
Carpal \'Tunnel
 
muttiah's Avatar
 
Join Date: Aug 2004
Posts: 23,101
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by Barrin6 View Post
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 have 3 questions I've asked many times.
1) merge two sorted double linked lists - Sounds straightforward but most can't code this cleanly and correctly without a bunch of errors and help
2) parse and deserialize a json string to a Java object - Requires good code organization, recursion (or state machine), and string parsing. This one has everything it's great for a 1 hour question. I think 1 person has solved it completely but I evaluate for how they approach the problem and how far they get.
3) design an image sharing site like imgur or instagram. Open ended design. I dig into various parts of the stack to test how deeply they know a topic and how they approach the problem.
muttiah is offline   Reply With Quote
Old 10-29-2017, 07:01 PM   #229
lostmypw
newbie
 
Join Date: Mar 2017
Posts: 49
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by muttiah View Post
2) parse and deserialize a json string to a Java object - Requires good code organization, recursion (or state machine), and string parsing. This one has everything it's great for a 1 hour question. I think 1 person has solved it completely but I evaluate for how they approach the problem and how far they get.
you have them write a parser?
lostmypw is online now   Reply With Quote
Old 10-29-2017, 08:29 PM   #230
Sholar
Carpal \'Tunnel
 
Sholar's Avatar
 
Join Date: Jul 2007
Posts: 6,341
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by lostmypw View Post
https://leetcode.com/problems/maximu...y/description/

would you guys consider this question "easy"? I feel so stupid lol.
Quote:
Originally Posted by Barrin6 View Post
It's a classical problem that has been done to death which is why it might be marked easy.

If you can think of the brute force solution, there is a slight optimization to make it faster.
Easy/hard is always a bit weird; many problems are easy once you know the answer, although here the best solution is very straightforward/single-pass once you know the main idea (making it sort of a silly interview question) and quite a bit better than O(n^2) brute force.
Sholar is offline   Reply With Quote
Old 10-29-2017, 11:03 PM   #231
gaming_mouse
Carpal \'Tunnel
 
gaming_mouse's Avatar
 
Join Date: Oct 2004
Location: taking notes on u (see profile)
Posts: 13,767
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by muttiah View Post
I recall the optimal solution requires knowledge of dynamic programming, so not an "easy" question.
no dynamic programming needed. there is a "trick" for the efficient solution, but it's not too hard to find.

Spoiler:
gaming_mouse is offline   Reply With Quote
Old 10-29-2017, 11:31 PM   #232
gaming_mouse
Carpal \'Tunnel
 
gaming_mouse's Avatar
 
Join Date: Oct 2004
Location: taking notes on u (see profile)
Posts: 13,767
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by 8=====D View Post
Can someone point out what's wrong with my strategy for solving this in terms of my logic?

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.
Because you have to check all permutations, not simply all permutations generated by a single swap.

Eg, say you move N into position i and i into the final position. It could be that N is now in a valid position, but i is not -- but, swapping i with some other element now makes both of them valid, leading to a valid arrangement that you missed.
gaming_mouse is offline   Reply With Quote
Old 10-29-2017, 11:38 PM   #233
gaming_mouse
Carpal \'Tunnel
 
gaming_mouse's Avatar
 
Join Date: Oct 2004
Location: taking notes on u (see profile)
Posts: 13,767
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by Barrin6 View Post
The best method here is quick select which is O(n) and constant space complexity.
This is not guaranteed, though. Worst case for quick select is O(n^2)
gaming_mouse is offline   Reply With Quote
Old 10-30-2017, 04:35 PM   #234
daveT
S.A.G.E. Master
 
daveT's Avatar
 
Join Date: Jun 2005
Location: Why didn't I use Clojure instead?
Posts: 21,924
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Max subarray is the first algorithm in CLRS, so I suppose it's "easy" compared to others. I always forget how to do it, so it's not easy to me.
daveT is offline   Reply With Quote
Old 10-31-2017, 07:51 PM   #235
Sholar
Carpal \'Tunnel
 
Sholar's Avatar
 
Join Date: Jul 2007
Posts: 6,341
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by gaming_mouse View Post
This is not guaranteed, though. Worst case for quick select is O(n^2)
I thought everyone is implementing median-of-medians in their whiteboard interviews these days...
Sholar is offline   Reply With Quote
Old 11-01-2017, 01:11 AM   #236
Barrin6
Carpal \'Tunnel
 
Barrin6's Avatar
 
Join Date: Dec 2005
Location: beyond legal blindness
Posts: 6,657
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Yea I don't think people are expected to code out median-of-medians.

And yes you are right gaming_mouse, it's not O(n), but it's expected O(n) using a random pivot from what I remember.

If you are interested in learning about median-of-medians, I always found this as a good read through http://www.ics.uci.edu/~eppstein/161/960130.html
Barrin6 is offline   Reply With Quote
Old 11-02-2017, 03:39 AM   #237
muttiah
Carpal \'Tunnel
 
muttiah's Avatar
 
Join Date: Aug 2004
Posts: 23,101
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by gaming_mouse View Post
no dynamic programming needed. there is a "trick" for the efficient solution, but it's not too hard to find.

Spoiler:
Right. I solved this the other day when browsing through "cracking the coding interview". It's a good pattern that applies to many problems. Keeping 2 pointers and moving one of them at each step, so the algorithm never goes backwards and is O(n).
muttiah is offline   Reply With Quote
Old 11-02-2017, 11:31 AM   #238
gaming_mouse
Carpal \'Tunnel
 
gaming_mouse's Avatar
 
Join Date: Oct 2004
Location: taking notes on u (see profile)
Posts: 13,767
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by muttiah View Post
Right. I solved this the other day when browsing through "cracking the coding interview". It's a good pattern that applies to many problems. Keeping 2 pointers and moving one of them at each step, so the algorithm never goes backwards and is O(n).
not totally sure what you mean, but i don't think about it as 2 pointers. if replace the original array with scan sum (which costs O(n)), then you just need to keep track of two quantities -- the max value of scan sum to the right, and the min value of the scan sum to the left. you'll have these for the first position, and you can then calculate then for all positions in a single pass, since at each new index each quantity's change depends only on the value at that index.
gaming_mouse is offline   Reply With Quote

Reply
      

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off


Forum Jump


All times are GMT -4. The time now is 01:09 PM.


Powered by vBulletin®
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Copyright © 2008-2017, Two Plus Two Interactive
 
 
Poker Players - Streaming Live Online