Not too many guys here!

ekt_bear:

@omo_to_dun: Thanks, I saw your message. I actually have a book of programming puzzles that I'm working through now though. Thanks for those too, though.

Oya naw, I also need 2 be watered oooo, I nid a book on c++ dat Is self explanatory & a link to download a good compiler as I"m having issues with gettin GNU compiler o.
Please Help me out and I"d owe you my programming career!
Tnx in anticipation

hamziwhiz:

Oya naw, I also need 2 be watered oooo, I nid a book on c++ dat Is self explanatory & a link to download a good compiler as I"m having issues with gettin GNU compiler o.
Please Help me out and I"d owe you my programming career!
Tnx in anticipation

GCC is available for free. Are you on windows? If so you can google around for instructions for installing it on windows. It looks like can also get Visual Studio for free too: http://www.microsoft.com/visualstudio/en-us/products/2010-editions/express

Two more:

1) What is the sum of the #s from 1 to 1,000 (this is kind of a dumb question, you either will have seen the trick before or not. If you've not seen the trick before, try to think of a way to rearrange the summation to make it easier.)

2) What is the expected number of times I must flip a fair coin before I get two heads? (basically a conditional probability question)

Another one.

I'm given an array of N numbers. Call the array A.

Let's assume that arrays are zero-indexed, like in C, C++, Java, etc.

A)
Design an algorithm that will output a list B that is a rearrangement of A (i.e., permutation) such that:

1. The last element the new array B is the same as the last element of A. Call this pivot element x.
2. I have three indices I_1, I_2, and I_3, such that:
a. All elements with index less than I_1 are less than x.
b. All elements with index less than I_2 but >= I_1 are greater than x.
c. All elements with index >=I_2 are equal to x.

You are allowed to create a temporary array of size N for this problem.

B) Design a variant of the above algorithm that doesn't require a temporary array, that transforms A into B in place. You can use a constant amount of additional memory.

(Basically you are designing an in-place QuickSelect.)

Here is what a sample run of the algorithm looks like:


A=[2, 0, 3, 4, 3, 0, 2, 1, 4, 2]

produces:
B = [1, 0, 0, 3, 4, 4, 3, 2, 2, 2]

and

I_1, I_2, I_3 = [3, 7, 3]

The first one is basic arithmetic progression. That, n/2(na+(n-1)d); thingy.

Second one is 2 na?  

As for the most recent; check this; is it correct? Just a quick implementation. Without using a temporary array;


  package algorithms;

import java.util.Arrays;

public class NL {
public static void main(String [] args){

   int [] arr = {2,0,3,4,3,0,2,1,4,2};
   int arrlength = arr.length;
   int [] ind = {3,7,3};
   int [] fin = new int [10];
   int x = arr[arrlength - 1];
   fin[fin.length-1] = arr[arrlength-1];
   Arrays.sort(arr);
       for(int i = 0; i<arrlength; i++){
           if( arr[i] < x ){
                fin[i] = arr[i];
                continue;
           }
          if( arr[i] > x){
               fin[i-ind[0]] = arr[i];
          }
       }
       for(int j = ind[1]; j<arr.length; j++){
           fin[j] = x;
       }
   System.out.println(Arrays.toString(fin));


   }
}


The entire thing is easier with a sorted array.

Input array : [2, 0, 3, 4, 3, 0, 2, 1, 4, 2]
Outputted array : [0, 0, 1, 3, 3, 4, 4, 2, 2, 2]

1. Yep, first is pairing. You just pair the first and last, the second and second to last, etc. Then sum up.

2. Nope, not 2. It actually requires a bit of consideration of cases, and some effort. You expect 2 coin flips to get 1 head on average. But how many coin flips do you expect for 2 consecutive heads?

3. You create a big temporary array "fin" right? You are allowed to do this for (A), but not for (B). For (B), the idea is that you want to do some simple operations on arr that transform it into the desired result, but only using a constant amount of additional space (say you only have one temporary integer available to you.)

Also, if you sort the input array first, then the problem becomes dead easy. You want to avoid sorting. No sorting allowed for either (A) or (B) of this problem.

ekt_bear:

3. You create a big temporary array "fin" right? You are allowed to do this for (A), but not for (B). For (B), the idea is that you want to do some simple operations on arr that transform it into the desired result, but only using a constant amount of additional space (say you only have one temporary integer available to you.)

Also, if you sort the input array first, then the problem becomes dead easy. You want to avoid sorting. No sorting allowed for either (A) or (B) of this problem.

From my understanding; there is only one array in use as stated by the question;

Here as for (A)

Design an algorithm that will output a list B that is a rearrangement of A (i.e., permutation) such that:

1. The last element the new array B is the same as the last element of A. Call this pivot element x.

The main array in use, is the same array as the final array; So the entire question requires 2 arrays; the stipulated and the outputted;

As for no sorting, the bleep? I'd like someone to do that and post the code.

For (B) hmm. Feasible.

For part A, you can create a second array if you like.

For Part B, you cannot. You must generate the desired array through a series of operations on the input array.

Part A can definitely be done w/o sorting (once you've picked the pivot, cycle through the input array filling in the appropriate entries of your duplicate array.)

Part B can also be done w/o sorting, and w/o creation of any new arrays.

This is one of those things where you are best off taking out pencil and paper first, playing with a few examples first rather than directly diving into code.

Here is one I couldn't do and had to cheat by looking up the answer 

I knew it had to involve bisection of some sort (that is usually the only time you see log(N) time), but couldn't figure out how to do it until I looked it up.

Anyways:

You are given two sorted lists/arrays, one of length M, one of length N.

Find the Kth smallest item in both lists (i.e., if we considered the two lists to be one big list), and do this in no more than O([log(N)+log(M)]) iterations (for example, if you have a technique that does it in 5[log(N)+log(M)] iterations, you win the game.)

(Big hint: use bisection, since the lists are already sorted!)

You can assume that all the elements of the list are distinct (so there cannot be a tie.)