Computer programming thread

[hsilman]

This got a lot of responses previously, so let's start it again.

What's everyone up to?

I enrolled in school for real after finishing CS50X. Taking intro CS(Java), which as Hanley predicted would be mind numbingly dull if it was my only class. Easy stuff, though I will be doing JavaFX GUI stuff, which I haven't before.

I'm also taking Intro to Android Development, which complements the other class well. It's supposed to be taken with CS 102, but I figured I'd done enough work to adapt. It's filling most of my time, lots of stuff to learn.

[mgil]

I'm currently avoiding code. I'm usually telling people what to code now. I'll be coding again soon, probably.

[Idlehands]

My favorite interview question is "what's the last script you wrote"

Even to folks that are interviewing for a job that requires 0 coding. Cause you should still be a techie nerd that wants to tinker!

[mgil]

My favorite interview question is "what's the last script you wrote"

A: Romeo and Juliet [drops mic and walks out]

[iamsmu]

You have a 5 number random number generator (1-5). Based on the 1-5 generator, produce a 1-7 generator that gives an evenly distributed set of numbers.

[iamsmu]

Let's start with a much easier question. This one is a good warm up.

You have a sorted list of integers with no duplicates. There is no way to determine its length. Describe an algorithm for determining if any given number is contained in the list. (And in what time does your algorithm operate in.)

[iamsmu]

Those two were on the top of my head. . . I just dug up a sheet with a bunch of other interview questions I used to ask. Damn. I'd never get through my interviews at this point. I haven't done anything but write some groovy for home automation stuff in 7 years. It's a little sad how much I've forgotten. Oh well. I'd have to at least work through a data structures and algorithms text book before I could even think about interviewing again.

[cwd]

Let's start with a much easier question. This one is a good warm up.

You have a sorted list of integers with no duplicates. There is no way to determine its length. Describe an algorithm for determining if any given number is contained in the list. (And in what time does your algorithm operate in.)

Bonus points if your "infinite" singly-linked list can have loops, and your algorithm will still return eventually rather than busy-hanging.

[Root]

Let's start with a much easier question. This one is a good warm up.

You have a sorted list of integers with no duplicates. There is no way to determine its length. Describe an algorithm for determining if any given number is contained in the list. (And in what time does your algorithm operate in.)

Bonus points if your "infinite" singly-linked list can have loops, and your algorithm will still return eventually rather than busy-hanging.

He didn't say it was a linked list. In fact, if it was, this problem would be trivial.

[Root]

Let's start with a much easier question. This one is a good warm up.

You have a sorted list of integers with no duplicates. There is no way to determine its length. Describe an algorithm for determining if any given number is contained in the list. (And in what time does your algorithm operate in.)

This is just a binary search of the first n - f + 1 elements of the list, where n is the number we're searching for, and f is the integer in the first element.

Edit: Well, it resembles a binary search.

[GregoryDomnin]

Books and project sites for n00bs?

[hsilman]

Let's start with a much easier question. This one is a good warm up.

You have a sorted list of integers with no duplicates. There is no way to determine its length. Describe an algorithm for determining if any given number is contained in the list. (And in what time does your algorithm operate in.)

This is just a binary search of the first n - f + 1 elements of the list, where n is the number we're searching for, and f is the integer in the first element.

Edit: Well, it resembles a binary search.

How do you determine the high index element if you don't know the list length? Can't just say the nth index.

But maybe you're saying the same thing.

First, find your bounds. I'd just start at 0th for low and 1th for high. Is 1th higher than n? If yes, binary search. If not, high = 2*1tg, repeat. Go until the high bound is more than your number or you reach the end.

[hsilman]

Books and project sites for n00bs?

Define noob. And what's the goal?

[Root]

Well, they can't just tell you there's "no way" to know the length. At the very least, you need to get an indication when you attempt to access the list beyond its bounds. So I'd just assume that you don't know the length *up front*.

But you also know that the number you're searching for isn't beyond the index (n - f + 1)*, because there are no duplicates.

*Again, where n is the number you're searching for, and f is the first element in the list.

[iamsmu]

Let's start with a much easier question. This one is a good warm up.

You have a sorted list of integers with no duplicates. There is no way to determine its length. Describe an algorithm for determining if any given number is contained in the list. (And in what time does your algorithm operate in.)

This is just a binary search of the first n - f + 1 elements of the list, where n is the number we're searching for, and f is the integer in the first element.

Edit: Well, it resembles a binary search.

Exactly. I just requires that you realize that the number couldn't be in a position larger than the number itself. ( In interview contexts some people struggle with that. You can get them talking about what they know about the problems and see how they think. It's kind of an ice breaker. ) That gives you a length to work with. So, ya, it's just a binary search. . . . O log (n)

[There is no list like this. It's hypothetical. . . . You can just say that it trails off into MAXINT forever and ever. . . .]

[cwd]

He didn't say it was a linked list. In fact, if it was, this problem would be trivial.

If it's an indexable array, why don't we know the length?

[Root]

He didn't say it was a linked list. In fact, if it was, this problem would be trivial.

If it's an indexable array, why don't we know the length?

I don't know. The problem wouldn't even change that much if we did know the length.

It's just a weird question.

[hsilman]

He didn't say it was a linked list. In fact, if it was, this problem would be trivial.

If it's an indexable array, why don't we know the length?

usually when I read this question, it says it's an "infinite array".

I was going to ask why the number can't be at an index beyond itself, but I answered my own question when I was asking it. So I guess just a binary search of n-f+1 makes perfect sense. My answer added extra complexity that I don't think saves time.

[Hanley]

What's everyone up to?.

Mostly trying to figure out what the hell I was thinking when I decided to learn to code at age 39.

[Hanley]

Books and project sites for n00bs?

If you're brand-baby new, this site is nice: http://codingbat.com/

Project Euler is all about devising efficient solutions (problems range from pretty-damned-to-east to holy-fuck hard): https://projecteuler.net/

Not sure about books. Every book I've tried sorta sucked.