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 09-22-2016, 09:30 AM   #101
gaming_mouse
Carpal \'Tunnel
 
gaming_mouse's Avatar
 
Join Date: Oct 2004
Location: taking notes on u (see profile)
Posts: 13,782
Re: Interview Test Questions Problems, Solutions, Links, Discussion

with ramda, the essense of the algorithm distills into a single line:

Spoiler:


EDIT: eh, just noticed sholar's answer takes the same approach. still, i think the ramda version is more readable.

Last edited by gaming_mouse; 09-22-2016 at 09:39 AM.
gaming_mouse is offline   Reply With Quote
Old 09-22-2016, 10:17 AM   #102
gaming_mouse
Carpal \'Tunnel
 
gaming_mouse's Avatar
 
Join Date: Oct 2004
Location: taking notes on u (see profile)
Posts: 13,782
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by Lattimer View Post
I just realized my while condition should be OR not AND. The rotate idea is great but not practical for a low-level language like C, and unfortunately like 95% of my programming is done in C
resigning yourself to not using the good solution is only 1 of 2 possible escapes from your predicament
gaming_mouse is offline   Reply With Quote
Old 09-22-2016, 10:42 AM   #103
Lattimer
I are smart
 
Lattimer's Avatar
 
Join Date: Feb 2009
Location: New England
Posts: 13,997
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Hah well I have no choice re: using C in my job.
Lattimer is offline   Reply With Quote
Old 09-22-2016, 11:02 AM   #104
gaming_mouse
Carpal \'Tunnel
 
gaming_mouse's Avatar
 
Join Date: Oct 2004
Location: taking notes on u (see profile)
Posts: 13,782
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by Lattimer View Post
Hah well I have no choice re: using C in my job.
thinking about this more, i actually think it's probably the right approach even in C.

Recursion is easy in C, so all you need are the helper methods to transpose and reverse (to give you rotate). sure, writing those helpers is a bit more verbose in C, but after you have them you can now write essentially the same code as above, and you have a succinct, clear high-level algorithm.
gaming_mouse is offline   Reply With Quote
Old 09-22-2016, 11:25 AM   #105
candybar
old hand
 
Join Date: Aug 2011
Posts: 1,955
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by gaming_mouse View Post
thinking about this more, i actually think it's probably the right approach even in C.

Recursion is easy in C, so all you need are the helper methods to transpose and reverse (to give you rotate). sure, writing those helpers is a bit more verbose in C, but after you have them you can now write essentially the same code as above, and you have a succinct, clear high-level algorithm.
It's interesting but "right" approach is a stretch given that it takes an O(M*N) algorithm and turns it into something like O(M*N*min(M, N)). Even a naive virtual rotation algorithm is I think is the same (rotation then takes constant time but element look up is now number of cumulative rotations) - this is what I meant by optimization for multiple rotations btw.
candybar is offline   Reply With Quote
Old 09-22-2016, 11:29 AM   #106
Lattimer
I are smart
 
Lattimer's Avatar
 
Join Date: Feb 2009
Location: New England
Posts: 13,997
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by gaming_mouse View Post
thinking about this more, i actually think it's probably the right approach even in C.

Recursion is easy in C, so all you need are the helper methods to transpose and reverse (to give you rotate). sure, writing those helpers is a bit more verbose in C, but after you have them you can now write essentially the same code as above, and you have a succinct, clear high-level algorithm.
This is true. I write processor tests, and one of our highest priorities is minimizing simulation time, so I tend to take a dirtier approach (limiting helper methods) because it cuts down on # of operations. That's why I'm stuck with C; because we have to be cognizant of how the program breaks down into assembly, as well as performing DMAs and register accesses, it's as high level as I can practically get. I do enjoy when I have to do some scripting, because I do that in Perl or Python and it's nice to use those for a change.

Last edited by Lattimer; 09-22-2016 at 11:37 AM.
Lattimer is offline   Reply With Quote
Old 09-22-2016, 11:45 AM   #107
gaming_mouse
Carpal \'Tunnel
 
gaming_mouse's Avatar
 
Join Date: Oct 2004
Location: taking notes on u (see profile)
Posts: 13,782
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by candybar View Post
It's interesting but "right" approach is a stretch given that it takes an O(M*N) algorithm and turns it into something like O(M*N*min(M, N)). Even a naive virtual rotation algorithm is I think is the same (rotation then takes constant time but element look up is now number of cumulative rotations) - this is what I meant by optimization for multiple rotations btw.
my feeling is that clarity and simplicty are orders of magnitude more important than performance until performance specifically asserts itself as a pressing need.

so i have no problem with the word "right" here. i'll concede that i have a strong pov on the subject, and reasonable people disagree sometimes, but they're wrong
gaming_mouse is offline   Reply With Quote
Old 09-22-2016, 11:47 AM   #108
gaming_mouse
Carpal \'Tunnel
 
gaming_mouse's Avatar
 
Join Date: Oct 2004
Location: taking notes on u (see profile)
Posts: 13,782
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by Lattimer View Post
This is true. I write processor tests, and one of our highest priorities is minimizing simulation time, so I tend to take a dirtier approach (limiting helper methods) because it cuts down on # of operations. That's why I'm stuck with C; because we have to be cognizant of how the program breaks down into assembly, as well as performing DMAs and register accesses, it's as high level as I can practically get. I do enjoy when I have to do some scripting, because I do that in Perl or Python and it's nice to use those for a change.
this is a good followup to my response to candybar, because low-level jobs like yours are places where my pov is genuinely not appropriate. that said, i think when you're doing puzzles like these your habitual workplace constraints no longer apply
gaming_mouse is offline   Reply With Quote
Old 09-22-2016, 11:58 AM   #109
Lattimer
I are smart
 
Lattimer's Avatar
 
Join Date: Feb 2009
Location: New England
Posts: 13,997
Re: Interview Test Questions Problems, Solutions, Links, Discussion

I agree with everything you said. In an actual interview case I would use an approach more language appropriate for the position. I knew most here would be responding with high-level language solutions, so I took it as a chance to offer something unique. I don't think this type of puzzle would be used in an interview for a C job, it's something you'd have to code in C for a CS class homework assignment or something but that'd be the only time.
Lattimer is offline   Reply With Quote
Old 09-22-2016, 12:11 PM   #110
candybar
old hand
 
Join Date: Aug 2011
Posts: 1,955
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by gaming_mouse View Post
my feeling is that clarity and simplicty are orders of magnitude more important than performance until performance specifically asserts itself as a pressing need.

so i have no problem with the word "right" here. i'll concede that i have a strong pov on the subject, and reasonable people disagree sometimes, but they're wrong
It's an algorithm interview question specifically designed to test your understanding of things like runtime complexity of algorithms. And we're not talking about constant time differences - going from O(1) space to O(M*N) space (and times min(M,N) for the actual amount of garbage generated) and going from O(M*N) time to O(M*N*min(M,N)) are massive. And if the context is C, it's even more so - people don't use C these days for situations where performance is not a pressing need.

And for actual clarity and simplicity, not theoretical clarity and simplicity in a world only inhabited by functional programming enthusiasts, you need to use idioms and tools that are likely to be easily understood by your audience, instead of rolling your own. This is simply not idiomatic in C (because even properly handling memory is painful here) and it's going to be hard for people to follow and understand.
candybar is offline   Reply With Quote
Old 09-22-2016, 12:31 PM   #111
gaming_mouse
Carpal \'Tunnel
 
gaming_mouse's Avatar
 
Join Date: Oct 2004
Location: taking notes on u (see profile)
Posts: 13,782
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by candybar View Post
, not *actual* clarity and simplicity in a world only inhabited by *anyone with a homosapien brain*
fyp
gaming_mouse is offline   Reply With Quote
Old 09-22-2016, 12:41 PM   #112
candybar
old hand
 
Join Date: Aug 2011
Posts: 1,955
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by gaming_mouse View Post
that said, i think when you're doing puzzles like these your habitual workplace constraints no longer apply
I'm not sure what you mean here then - what does it mean for something to be a "right" approach for a puzzle? Why does an answer to a puzzle have to any particular attribute, whether clarity or simplicity? Note how I went for the exact opposite in my answer

In production C code, you would not do this because it's a less efficient solution that requires far more lines of code to express and is much harder for C programmers to understand or review. In an interview situation, you're trying to demonstrate your ability to write clear, efficient code and that you understand runtime complexity. Code that offloads most of the responsibility to the libraries which the interviewer may or may not be familiar with, thus failing to demonstrate your ability to write code, which the interviewer wants to see, is counterproductive. Likewise, writing code with runtime characteristics that are worse than a naive solution - well if you could get the interviewer to even understand how your code is actually going to run - seems extremely counterproductive.
candybar is offline   Reply With Quote
Old 09-22-2016, 12:48 PM   #113
Barrin6
Carpal \'Tunnel
 
Barrin6's Avatar
 
Join Date: Dec 2005
Location: beyond legal blindness
Posts: 6,875
Re: Interview Test Questions Problems, Solutions, Links, Discussion

One week from today I have a technical phone interview where I will be writing code on a google doc. Recruiter sent me prep material telling me to basically learn everything about CS.

I am expecting an epic fail next week
Barrin6 is offline   Reply With Quote
Old 09-22-2016, 12:48 PM   #114
gaming_mouse
Carpal \'Tunnel
 
gaming_mouse's Avatar
 
Join Date: Oct 2004
Location: taking notes on u (see profile)
Posts: 13,782
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by candybar View Post
I'm not sure what you mean here then - what does it mean for something to be a "right" approach for a puzzle? Why does an answer to a puzzle have to any particular attribute, whether clarity or simplicity? Note how I went for the exact opposite in my answer

In production C code, you would not do this because it's a less efficient solution that requires far more lines of code to express and is much harder for C programmers to understand or review. In an interview situation, you're trying to demonstrate your ability to write clear, efficient code and that you understand runtime complexity. Code that offloads most of the responsibility to the libraries which the interviewer may or may not be familiar with, thus failing to demonstrate your ability to write code, which the interviewer wants to see, is counterproductive. Likewise, writing code with runtime characteristics that are worse than a naive solution - well if you could get the interviewer to even understand how your code is actually going to run - seems extremely counterproductive.
interview big o stuff aside, and excepting jobs like lattimers, the programmer's cognitive load is almost always the true bottleneck in software and the source of most bugs. that's the sense in which im right.
gaming_mouse is offline   Reply With Quote
Old 09-22-2016, 12:50 PM   #115
jjshabado
Carpal Tunnel
 
jjshabado's Avatar
 
Join Date: Jul 2006
Posts: 22,542
Re: Interview Test Questions Problems, Solutions, Links, Discussion

GM, even on a conceptual level I don't really see your solution as the most clear and simple.
jjshabado is offline   Reply With Quote
Old 09-22-2016, 12:51 PM   #116
candybar
old hand
 
Join Date: Aug 2011
Posts: 1,955
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by gaming_mouse View Post
fyp
I think there's a fairly small group of people for whom answers like this would appear simple and clear. Many of the best people would want to see exactly what is happening because they are used to abstractions failing and don't trust the underlying abstractions. Many normal developers are not all that comfortable with dealing with high levels of abstraction because it stretches their model of computation.

Also, don't forget that the context in which we most often read other people's code is when something is not working and we don't know where the not-working thing is. High-level indirection of this sort can add a lot of overhead if the reader isn't intimately familiar with all the edge cases for the abstractions that are being used.
candybar is offline   Reply With Quote
Old 09-22-2016, 12:54 PM   #117
gaming_mouse
Carpal \'Tunnel
 
gaming_mouse's Avatar
 
Join Date: Oct 2004
Location: taking notes on u (see profile)
Posts: 13,782
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by jjshabado View Post
GM, even on a conceptual level I don't really see your solution as the most clear and simple.
disagree but what is there to say? Id be willing to bet a couple hundo that if you posted our solutions side by side on hn or as answers on code review and asked a bunch of ppl to vote mine would win
gaming_mouse is offline   Reply With Quote
Old 09-22-2016, 12:56 PM   #118
gaming_mouse
Carpal \'Tunnel
 
gaming_mouse's Avatar
 
Join Date: Oct 2004
Location: taking notes on u (see profile)
Posts: 13,782
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by candybar View Post
I think there's a fairly small group of people for whom answers like this would appear simple and clear. Many of the best people would want to see exactly what is happening because they are used to abstractions failing and don't trust the underlying abstractions. Many normal developers are not all that comfortable with dealing with high levels of abstraction because it stretches their model of computation.

Also, don't forget that the context in which we most often read other people's code is when something is not working and we don't know where the not-working thing is. High-level indirection of this sort can add a lot of overhead if the reader isn't intimately familiar with all the edge cases for the abstractions that are being used.
sorry this is nonsense. its easier to debug 2 lines of functional code than 10+ of procedural. i have lots of experience with both and it's not close
gaming_mouse is offline   Reply With Quote
Old 09-22-2016, 12:57 PM   #119
jjshabado
Carpal Tunnel
 
jjshabado's Avatar
 
Join Date: Jul 2006
Posts: 22,542
Re: Interview Test Questions Problems, Solutions, Links, Discussion

I feel like if we gave our solutions to 100 average developers and didn't tell them what the code did, more people would correctly identify what mine does and faster.

But who knows. I'm probably not betting on it.
jjshabado is offline   Reply With Quote
Old 09-22-2016, 01:03 PM   #120
gaming_mouse
Carpal \'Tunnel
 
gaming_mouse's Avatar
 
Join Date: Oct 2004
Location: taking notes on u (see profile)
Posts: 13,782
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by jjshabado View Post
I feel like if we gave our solutions to 100 average developers and didn't tell them what the code did, more people would correctly identify what mine does and faster.

But who knows. I'm probably not betting on it.
yeah I mean it's tricky to remove the confound thay more ppl, as an actual number, know procederal constructs like for loops than even something like ternary. you could restrict to ppl with x years experience, blah, etc. but cmon on some gut level you know im right? I know you do
gaming_mouse is offline   Reply With Quote
Old 09-22-2016, 01:05 PM   #121
jjshabado
Carpal Tunnel
 
jjshabado's Avatar
 
Join Date: Jul 2006
Posts: 22,542
Re: Interview Test Questions Problems, Solutions, Links, Discussion

I legitimately don't think you're right. But its hard to remove my experience/background too.
jjshabado is offline   Reply With Quote
Old 09-22-2016, 01:08 PM   #122
gaming_mouse
Carpal \'Tunnel
 
gaming_mouse's Avatar
 
Join Date: Oct 2004
Location: taking notes on u (see profile)
Posts: 13,782
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by jjshabado View Post
I legitimately don't think you're right. But its hard to remove my experience/background too.
agree to disagree then. also, post more!
gaming_mouse is offline   Reply With Quote
Old 09-22-2016, 01:10 PM   #123
Lattimer
I are smart
 
Lattimer's Avatar
 
Join Date: Feb 2009
Location: New England
Posts: 13,997
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by gaming_mouse View Post
disagree but what is there to say? Id be willing to bet a couple hundo that if you posted our solutions side by side on hn or as answers on code review and asked a bunch of ppl to vote mine would win
when I compile and run this post it displays "HU4ROLLZ"
Lattimer is offline   Reply With Quote
Old 09-22-2016, 01:11 PM   #124
candybar
old hand
 
Join Date: Aug 2011
Posts: 1,955
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by gaming_mouse View Post
sorry this is nonsense. its easier to debug 2 lines of functional code than 10+ of procedural. i have lots of experience with both and it's not close
I think making this about functional vs procedural is a little off the mark though there's certainly correlation - functional code doesn't have to use a lot of abstractions and procedural code can use tons of abstractions that can make the resulting code hard to debug. I think you're also forgetting the context for this - I'm specifically objecting to you saying this is the right approach in C.
candybar is offline   Reply With Quote
Old 09-22-2016, 01:14 PM   #125
candybar
old hand
 
Join Date: Aug 2011
Posts: 1,955
Re: Interview Test Questions Problems, Solutions, Links, Discussion

Quote:
Originally Posted by gaming_mouse View Post
yeah I mean it's tricky to remove the confound thay more ppl, as an actual number, know procederal constructs like for loops than even something like ternary. you could restrict to ppl with x years experience, blah, etc. but cmon on some gut level you know im right? I know you do
I don't understand - reality is not a confounding variable. It's like saying that we should write everything in Esperanto because it is theoretically easier to understand, ignoring that 1000 times more people can read English.
candybar 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 11:55 PM.


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