The Programming Riddles Thread!

[Borealis7]

Hi guys!
i'm in the process of looking for a job and in interviews i get asked a bunch of algorithm and programming riddles, so i decided to make a thread just for lolz.
i will update it with riddles from time to time.

Riddle 1: there is an Array of 99 cells, and in it the integers from 1 to 100 but one is missing.
(the first index of a cell in the array is 0).
describe the most efficient way of finding the missing number if:
a) the array is sorted in ascending order.
b) if the array is not sorted.

easy, eh? lets try another one.

Riddle 2: there is an Array of 1's and 0's of length n. can you sort the array IN PLACE, with all the 0's on one side and all the 1's on the other side while only reading each cell in the array ONCE? (this riddle simulates a very memory constrained situation)

i.e. 0110101001 => 0000011111 (n can be either odd or even)

still easy? check this out:

Riddle 3: describe a data structure which represents an array of length n that can be initialized to a specific value K in a fixed number of operations (meaning O(1), not the order of the length of the array which would be O(n) ). this class must also implement Set(index,value) in O(1) and Get(index) in O(1).

these are not "homework questions", those are some of the easier questions that pop up in interviews from time to time, but frankly IMO have no place when interviewing a skilled programmer with several years of experience...these can be useful when interviewing graduates with no professional experience. </rant>

have fun!

P.S if you already know the answer and no one has posted it use spoiler tags. let the people think for themselves.

 

[Ken g6]

[thread=2098239]Here[/thread] are some other interview questions, from a year ago.

 

[Borealis7]

nobody up for the challenge? post your answers in Spoiler tags and i'll tell you if you got it right.

 

[Ken g6]

Oh, I read that as "if you already know the answer, don't post it or use spoiler tags". I guess the comma matters.

1. a.

Spoiler

A half-interval search will locate the point where the index and the values become misaligned. O(log(n))

1. b.

Spoiler

Probably have to bucket sort in 100 buckets, then search for the empty bucket. As the first part is O(n) it doesn't matter that the second part is too.

2. Is there not even space to store

Spoiler

a count of 0's and a count of 1's? Can the array values store values larger than than 0 and 1?

3. I'd use

Spoiler

a hash, which returns K for any value not found. Problem: You really do need some time to allocate and clear the initial hash area, which ought to be at least O(log(n)).

 

[iCyborg]

2. Is there not even space to store

Spoiler

a count of 0's and a count of 1's? Can the array values store values larger than than 0 and 1?

Spoiler

You can have two indices: one goes from the beginning and skips 0s and stops when reaching 1, the other goes from end in reverse and skips 1s until reaching 0. When both stop, swap those two using xor trick and continue until the two indices meet.

 

[WildW]

I've been a software engineer for 10 years and I've never used or heard of any of this stuff. . . these things have names and known log formulae? Where do you learn these things?

 

[Crusty]

Oh, I read that as "if you already know the answer, don't post it or use spoiler tags". I guess the comma matters.

1. a.

Spoiler

A half-interval search will locate the point where the index and the values become misaligned. O(log(n))

1. b.

Spoiler

Probably have to bucket sort in 100 buckets, then search for the empty bucket. As the first part is O(n) it doesn't matter that the second part is too.

2. Is there not even space to store

Spoiler

a count of 0's and a count of 1's? Can the array values store values larger than than 0 and 1?

3. I'd use

Spoiler

a hash, which returns K for any value not found. Problem: You really do need some time to allocate and clear the initial hash area, which ought to be at least O(log(n)).

1.b

Spoiler

Iterate the array summing the values. Also sum (index+1) as you iterate, so you end up with the sum of 1...100. Then just subtract the two numbers to find the missing value

 

[Borealis7]

Ken g6 has 1a correct.
iCyborg got 2 right.
Crusty figured out 1b.

i see nobody got 3 yet. its a tricky one. i'll elaborate some more maybe you'll get an idea:
lets call this "QuickInitArray". the idea is that the constructor of QIA recieves one value, K, and initializes an array of predetermined size n to the value K. you may assume creating an array of size n is of O(1) complexity. the constructor must also run in O(1) time! afterwards QIA must be able to set and get values in O(1) time.

WildW, these are very common questions you get asked in interviews for Software Engineering jobs (at least in my country...) most of them are Bachelor's Degree levels, some of them use elements from electrical engineering.
hope this helps.

i'll give question 3 a couple of more days, then i'll give a hint if no one comes close.

 

[slugg]

Number 3 is a tad ambiguous. You want to initialize the entire array-like data structure of length N to ONE specific value, K? In other words:

MyStructure.initialize(size N, value K);

would that mean that for all 0 <= i < N, MyStructure.get(i) == K?

*OR* is K some other kind of collection/container structure? Or is it another object/structure of the same type?

Answer my questions and I'll answer yours. LOL!

 

[PhatoseAlpha]

For 3, can the array be of any type of variable, or is it limited to certain types? And can we assume that the memory in the array starts out zeroed?

 

[iCyborg]

i see nobody got 3 yet. its a tricky one. i'll elaborate some more maybe you'll get an idea:
lets call this "QuickInitArray". the idea is that the constructor of QIA recieves one value, K, and initializes an array of predetermined size n to the value K. you may assume creating an array of size n is of O(1) complexity. the constructor must also run in O(1) time! afterwards QIA must be able to set and get values in O(1) time.

What does it mean an array of size N? So there's a chunk of memory of size proportional to N and we can initialize it to something in O(1)? I'm pretty sure that's impossible.

Or you set something fixed and then dynamically grow the array, keeping track of what indices have been assigned something, and if unasigned, do "return K;" basically?

Anyway, even without this O(1) constructor I can't really see a way to do this, and I'd bet there are some restrictions you're forgetting to tell us. Like is 'value' of some integer type, or it has some range? With something 64-bit like 'long long', I can't see how it could be done on a non-imaginary computer, not to mention some general objects/structs.

 

[dwell]

Not so much a riddle but I ask this one on interviews.

I have a properties file with the contents:

# generated: 2011-12-02 08:18:01
key1=3f786850e387550fdab836ed7e6dc881de23001b

# generated: 2011-12-02 08:16:13.048303 
key2=89e6c98d92887913cadf06b2adb97f26cde4849b

The contents can be in any order but the key fields will always have a comment above them with the date they are generated.

Walk me through how you would write a program to read the contents of the file and write a new file with the value and comment of key1 rotated to key2 and a new key1 and comment generated. Key2 and its comment should be rotated to key3.

If it looks easy, that's because it is but there's a lot of ways to go at it. Walking through this really helps me weed out hackers and find developers who write efficient code. You can tell who's going to write 1000 line spagetti code methods vs someone who knows how to use data structures and language features plus get a feel for their thought process.

I also start to expand on this if the developer seems to know what they're doing.

 

[wantedSpidy]

Hi guys!
but frankly IMO have no place when interviewing a skilled programmer with several years of experience...these can be useful when interviewing graduates with no professional experience. </rant>

I don't think this is true at all. Every programmer should be able to answer these questions. Its a fundamental measure of problem solving for computer scientists and programmers (who aren't just doing boring simple services development).

 

[Borealis7]

hi guys, i'm back from the weekend and here to answer your questions.

slugg: yes, but not as you say it: i want a constructor of an array-like data structure to initialize to a value K (yes K can be any type, even Object).

QuickInitArray QIA = new QuickInitArray(K);
this operation shuold be done in O(1) complexity assuming creating a new TypeK[] is O(1) as well. that's all there is to it.
once the constructor finishes, then yes, "for all 0 <= i < N, MyStructure.get(i) == K".

PhatoseAlpha: you may assume the array starts out zeroed, though it doesn't matter for the solution i know.

iCyborg: it's very much possible! i now it sounds mad but it works. (you're getting close!)

i'll give out a hint that i think iCyborg already knows.
HINT: your QIA is actually comprised of 2 arrays, and not of the same type. (i gave no restrictions on memory space)

 

[iCyborg]

If you think it's possible to init a large chunk of memory to some constant in O(1), then perhaps you should contact people who implemented memset() since it's O(n)
That's why I'm pretty sure it's impossible.

If value is an int, then you can have the 2nd array "index back" the value, but you need a 16GB array. For long long, this is probably more memory than we have on Earth. And something like

struct quaternion {
    double r;
    double i;
    double j;
    double k;     //yeah, I know, i,j,k are not independent for quaternions...
};

would be completely intractable so I cannot consider this as a solution unless you restrict the range for 'value'. And I have no other ideas.

 

[Ken g6]

I still assert that my solution works. Given that:

you may assume the array starts out zeroed

I'll add that

Spoiler

we can set the hash size to the length of the array, and the hash function to be the identity function. (f(x) {return x})

Edit: More details:

Spoiler

One way to make a hash is to make an array of pointers to linked lists. In this case, if there's a one-to-one mapping, we can do away with the "linked" and "list" parts, and just have pointers to objects, or NULLs by default.

 

[Pia]

I have a solution for riddle 3, for any datatype, without assuming the impossible O(1) memset. I use three arrays and I think a two-array solution must be flawed.

Spoiler

Array(K, N): Reserve an array D of K's datatype, plus array A and array B of integers, all length N. 0 -> S, where S is an integer keeping track of amount of cells set.

IsSet(index):
index is between 0..N-1 and
A[index] is between 0..N-1 and
B[A[index]] equals index and
A[index] < S

Set(index, value):
if IsSet(index) value -> D[A[index]]
else value -> D, index -> B, S -> A[index], S+1 -> S

Get(index):
if IsSet(index) D[A[index]]
else K

Obviously we can also refill the data structure with new default value in O(1) by 0 -> S, NewK -> K.

 

[iCyborg]

Oh, I think I have been solving a different problem. For some reason I thought Get() function was supposed to return an index for a given value - this is what I was babbling about above.

 

[Borealis7]

well you are getting close and i am enjoying the theoretical debate. but it has been long enough so i'll put the solution here for you:

Spoiler

QuickInitArray of length N for "typeK": has 2 arrays of length N and a "typeK" variable as members.
one array of length N of type "typeK", and one array of boolean of length N.

the array of boolean is initialized to false in most modern programming languages, and i said you may assume creating an array in memory is a fixed order complexity operation.

constructor of QIA which recieves a parameter for the value of K:
1) create a new array of "typeK" of length N- will be filled with nulls if typeK is not primitive
2) create an array of boolean of length N - init'ed to false.
3) set the private "typeK" member to K.

set(typeK value, int index):
1)typekArray[index] = value;
2)boolArray[index] = true;

get(int index)
1) if boolArray[index] == false, return the value of the private variable.
2) else return typeKArray[index].

it's that simple.
3 operations in O(1) complexity, all cells that have not been set are init'ed to K.

i've done the impossible! Mind->Blown.

i can also sort a set of numbers less than O(nLog n) complexity the riddle will shortly follow.

 

[Pia]

i've done the impossible! Mind->Blown.

No, you have assumed the impossible (that a compiler can produce code which formats a N-boolean array in O(1)). My solution works on actual computers.

i can also sort a set of numbers less than O(nLog n) complexity the riddle will shortly follow.

Oh, this one's easy as long as we are using your imaginary computer. We just need to make an empty datatype whose constructor sorts the set of numbers, reserve an array of one of that datatype, and the sort will magically happen in O(1).

 

[degibson]

I have to call foul on this one. Relying on new-memory initialization semantics in a programming riddle and calling it O(1) is a deep, deep misunderstanding of how memory initialization works.

 

[CU]

I have a solution for riddle 3, for any datatype, without assuming the impossible O(1) memset. I use three arrays and I think a two-array solution must be flawed.

Spoiler

Array(K, N): Reserve an array D of K's datatype, plus array A and array B of integers, all length N. 0 -> S, where S is an integer keeping track of amount of cells set.

IsSet(index):
index is between 0..N-1 and
A[index] is between 0..N-1 and
B[A[index]] equals index and
A[index] < S

Set(index, value):
if IsSet(index) value -> D[A[index]]
else value -> D, index -> B, S -> A[index], S+1 -> S

Get(index):
if IsSet(index) D[A[index]]
else K

Obviously we can also refill the data structure with new default value in O(1) by 0 -> S, NewK -> K.

Without initializing your integer arrays, how can you guarantee IsSet will return the correct value?

 

[CU]

Well I read Set again and that looks like it works. Did you just come up with that or is it a common solution you can find online or in a book?

 

[Pia]

The general principle of how to use uninitialized space feels familiar. But I don't recall where I have seen or figured it out before. I needed more than one sitting to figure out how to apply it appropriately here.

For anyone else figuring out why this works, about the best additional explanation I can come up with is that we initialize S, and we guarantee that (B, V) is a valid (index, value) pair whenever i < S. With just B and V, we'd have a working data structure that has an O(n) look-up as we'd have to walk through B to find our index. A is simply a look-up table to boost the look-up to O(1).

 

[Borealis7]

I have to call foul on this one. Relying on new-memory initialization semantics in a programming riddle and calling it O(1) is a deep, deep misunderstanding of how memory initialization works.

allocating some bytes of memory (which are zeroes already) and looking at them from the boolean perspective (which is primitive and thus zero equals 'false') is wrong? oh you 'unmanaged' boys...