Home » Other » General » Puzzle
Puzzle [message #414794] Thu, 23 July 2009 08:26 Go to next message
sasnrock
Messages: 19
Registered: August 2007
Junior Member
hello guys. I've attended an interview in microsoft and they gave me a problem infact a puzzle to be solved in 1hr. And code in any language u wish.

I used pl/sql which is the only one I know Smile)

Well ...here it goes

There are n number of persons standing in a circle. 1st person will have a gun. Now he kills a person in standing in his ACW direction and gives the gun next to him and this continues till only one is remaining.

for example if there are 5 people standing in a circle (say 1 to 5), 1kills 5 and gives gun to 4. 4 kills 3 and gives gun to 2. 2 kills 1 and gives it to 4. now 4 kills 2 and he is the one remaining. So we need to code such that we can find the one who is alive if we give n.

--- I'll post my code after 2 days. Meanwhile try for fun.


Re: Puzzle [message #414795 is a reply to message #414794] Thu, 23 July 2009 08:31 Go to previous messageGo to next message
Michel Cadot
Messages: 59499
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
If you don't explain how is this an Oracle question, the topic will be locked.

Regards
Michel
Re: Puzzle [message #414796 is a reply to message #414795] Thu, 23 July 2009 08:38 Go to previous messageGo to next message
sasnrock
Messages: 19
Registered: August 2007
Junior Member
hi michel,

its not really a question in oracle. however my point is how u do this in oracle.
i've seen some earlier posts from people requesting for some things to try their skills in oracle. So I thought this would be better to try.
however, if u think its inappropriate, then you can lock it. sorry Wink
Re: Puzzle [message #414802 is a reply to message #414796] Thu, 23 July 2009 09:31 Go to previous messageGo to next message
Michel Cadot
Messages: 59499
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
OK, first exercise for YOU, explain it with Oracle words that is table, columns, rows...

Regards
Michel
Re: Puzzle [message #414806 is a reply to message #414802] Thu, 23 July 2009 09:43 Go to previous messageGo to next message
Frank
Messages: 7878
Registered: March 2000
Senior Member
There, moved it to the general forum
No need to provide tables, data etc.
Re: Puzzle [message #414826 is a reply to message #414794] Thu, 23 July 2009 12:56 Go to previous messageGo to next message
joy_division
Messages: 4532
Registered: February 2005
Location: East Coast USA
Senior Member
sasnrock wrote on Thu, 23 July 2009 09:26
Now he kills a person in standing in his ACW direction and gives the gun next to him...



What is ACW?

I personally like puzzle questions.

It also seems that Microsoft is planning some devious actions to take out some of their competition and getting others to plan it out for them.
Re: Puzzle [message #414834 is a reply to message #414794] Thu, 23 July 2009 13:58 Go to previous messageGo to next message
BlackSwan
Messages: 22926
Registered: January 2009
Senior Member
>What is ACW?
Just guessing - anti-clock wise?

So what direction is clockwise on a digital timepiece?
Re: Puzzle [message #414836 is a reply to message #414834] Thu, 23 July 2009 14:18 Go to previous messageGo to next message
ThomasG
Messages: 3103
Registered: April 2005
Location: Heilbronn, Germany
Senior Member
Interesting problem. Basically some sort of wrap-around analytical with a twist. ;-P

Here is my solution :

SQL> set serverout on;

SQL> CREATE TABLE persons ( person NUMBER (10));

Table created.

SQL>
SQL> INSERT INTO persons
  2  (SELECT rownum FROM dual CONNECT BY LEVEL <= 5);

5 rows created.

SQL>
SQL> SELECT * FROM persons;
    PERSON
----------
         1
         2
         3
         4
         5
SQL>
SQL> DECLARE
  2    v_shooter       NUMBER:= 1;
  3    v_killed        NUMBER;
  4    v_next_shooter  NUMBER;
  5  BEGIN
  6
  7    LOOP
  8      SELECT shot    , NextShooter
  9        INTO v_killed, v_next_shooter
 10      FROM (
 11        SELECT person,
 12               Shooter,
 13               Shot,
 14               Nvl(Lag(shot) over (ORDER BY shot),
 15                   Max(shot) over () )             NextShooter
 16          FROM (
 17            SELECT person,
 18                   Decode(person, v_shooter,'Yes','No')      shooter,
 19                   Nvl( Lag(person) over (ORDER BY person),
 20                        (SELECT Max(person) FROM persons))   Shot
 21                   FROM  persons)
 22      )
 23      WHERE Shooter = 'Yes';
 24
 25      IF (v_shooter != v_killed) THEN
 26          Dbms_Output.put_line('Now ' || v_shooter || ' kills ' || v_killed);
 27      ELSE
 28          Dbms_Output.put_line('Last Man Standing ' || v_killed);
 29          EXIT;
 30      END IF;
 31
 32      DELETE FROM persons WHERE person = v_killed;
 33
 34      v_shooter := v_next_shooter;
 35
 36    END LOOP;
 37
 38  END;
 39  /

Now 1 kills 5
Now 4 kills 3
Now 2 kills 1
Now 4 kills 2
Last Man Standing 4

PL/SQL procedure successfully completed.

SQL>
SQL>
SQL> DROP TABLE persons;


I basically decided to "kill them" by deleting them from the table, but I wonder If someone will pull some analytical-SQL-Only solution out of his sleeve. Very Happy
Re: Puzzle [message #414851 is a reply to message #414826] Thu, 23 July 2009 16:03 Go to previous messageGo to next message
sasnrock
Messages: 19
Registered: August 2007
Junior Member
ACW - Anti clock wise
Re: Puzzle [message #414865 is a reply to message #414794] Thu, 23 July 2009 20:33 Go to previous messageGo to next message
BlackSwan
Messages: 22926
Registered: January 2009
Senior Member
no explicit LOOP

SQL> @lms
SQL> set serverout on;
SQL> DROP TABLE PERSONS;

Table dropped.

SQL> CREATE TABLE persons ( person NUMBER (10));

Table created.

SQL> INSERT INTO persons (SELECT rownum FROM dual CONNECT BY LEVEL <= 6);

6 rows created.

SQL> create or replace procedure recurse_dead(shooter IN number)
  2  as
  3  shot number;
  4  REMCNT number;
  5  PISTOL NUMBER;
  6  begin
  7  	DBMS_OUTPUT.ENABLE(100000);
  8  	SELECT count(*) INTO REMCNT from persons;
  9  	IF ( REMCNT > 1 )
 10  	THEN
 11  	   SELECT MAX(PERSON) INTO SHOT FROM PERSONS WHERE PERSON <> SHOOTER;
 12  	   DBMS_OUTPUT.PUT_LINE('SHOOTER - ' || SHOOTER || ' SHOT - ' || SHOT);
 13  	   DELETE FROM PERSONS WHERE PERSON = SHOT;
 14  	   COMMIT;
 15  	   SELECT count(*) INTO REMCNT from persons;
 16  	   IF ( REMCNT > 1 )
 17  	   THEN
 18  	      SELECT MAX(PERSON) INTO PISTOL  FROM PERSONS WHERE PERSON <> SHOOTER;
 19  	      RECURSE_DEAD(PISTOL);
 20  	   ELSE
 21  	      DBMS_OUTPUT.PUT_LINE('Last man standing is ' || SHOOTER);
 22  	   END IF;
 23  	ELSE
 24  	   DBMS_OUTPUT.PUT_LINE('Last man standing is ' || SHOOTER);
 25  	END IF;
 26  END RECURSE_DEAD;
 27  /

Procedure created.

SQL> exec recurse_dead(1);
SHOOTER - 1 SHOT - 6
SHOOTER - 5 SHOT - 4
SHOOTER - 3 SHOT - 5
SHOOTER - 2 SHOT - 3
SHOOTER - 1 SHOT - 2
Last man standing is 1

PL/SQL procedure successfully completed.
Re: Puzzle [message #414894 is a reply to message #414865] Thu, 23 July 2009 23:47 Go to previous messageGo to next message
Frank
Messages: 7878
Registered: March 2000
Senior Member
BlackSwan wrote on Fri, 24 July 2009 03:33


SQL> exec recurse_dead(1);
SHOOTER - 1 SHOT - 6
SHOOTER - 5 SHOT - 4
SHOOTER - 3 SHOT - 5
SHOOTER - 2 SHOT - 3
SHOOTER - 1 SHOT - 2
Last man standing is 1

PL/SQL procedure successfully completed.
[/code]

Nope, row 3: 3 shot 2, not 5
Re: Puzzle [message #414897 is a reply to message #414894] Thu, 23 July 2009 23:50 Go to previous messageGo to next message
Frank
Messages: 7878
Registered: March 2000
Senior Member
I think there's a structured outcome:

For a group of n people:
Find the largest x where 2^x + 1 < n
outcome is 2^x - (n - 2^x + 1)

I leave it to the math-people here to translate this to an algorithm Smile
Re: Puzzle [message #415168 is a reply to message #414794] Sat, 25 July 2009 10:57 Go to previous message
Michel Cadot
Messages: 59499
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
Here's a "pure" SQL solution. I used names instead of numbers, the initial gives the rank in the wheel of the fortune (you can get the numbers replacing "killer" by "ikiller" and "dead" by "idead").
SQL> col res format a40 heading "Steps"
SQL> def N=5
SQL> with 
  2    humans as (
  3                select 1 num,  'Abel'      human from dual
  4      union all select 2 num,  'Bethany'   human from dual
  5      union all select 3 num,  'Cain'      human from dual
  6      union all select 4 num,  'Deborah'   human from dual
  7      union all select 5 num,  'Esther'    human from dual
  8      union all select 6 num,  'Felix'     human from dual
  9      union all select 7 num,  'Gideon'    human from dual
 10      union all select 8 num,  'Hillel'    human from dual
 11      union all select 9 num,  'Isaiah'    human from dual
 12      union all select 10 num, 'Jacob'     human from dual
 13      union all select 11 num, 'Kolariah'  human from dual
 14      union all select 12 num, 'Levi'      human from dual
 15      union all select 13 num, 'Michaiah'  human from dual
 16      union all select 14 num, 'Nathanael' human from dual
 17      union all select 15 num, 'Ozias'     human from dual
 18      union all select 16 num, 'Philemon'  human from dual
 19      union all select 17 num, 'Quincy'    human from dual
 20      union all select 18 num, 'Rebekah'   human from dual
 21      union all select 19 num, 'Sarah'     human from dual
 22      union all select 20 num, 'Thomas'    human from dual
 23      union all select 21 num, 'Uriah'     human from dual
 24      union all select 22 num, 'Vaniah'    human from dual
 25      union all select 23 num, 'Wendy'     human from dual
 26      union all select 24 num, 'Xena'      human from dual
 27      union all select 25 num, 'Yanael'    human from dual
 28      union all select 26 num, 'Zuriel'    human from dual
 29    )
 30  select decode(step,
 31                &N, 'Last Person Standing: '||killer,
 32                'Now '||killer||' kills '||dead) res
 33  -- , debug
 34  from ( select level rn, level step, 'N' killed from dual connect by level <= &N )
 35  model
 36    reference humans on ( select * from humans ) dimension by (num) measures (human)
 37    dimension by (rn)
 38    measures (step, killed,
 39              cast(null as varchar2(20)) killer, cast(null as varchar2(20)) dead,
 40              cast(null as number) ikiller, cast(null as number) idead,
 41              cast(null as number) prev_killer
 42  -- , cast(null as varchar2(50)) debug
 43             )
 44    rules upsert all sequential order iterate (&N) (
 45  -- debug[iteration_number+1]='kd='||wm_concat(killed)[rn between 1 and &N],
 46      -- Calculate new killer, first one (iteration 0) is number 1
 47      ikiller[iteration_number+1] = 
 48        decode(iteration_number, 
 49               0, 1,
 50               mod(max(decode(killed,'N',mod(step-nvl(prev_killer,0)+&N,&N)))[rn between 1 and &N]
 51                    + nvl(prev_killer[1],0),&N)
 52              ),
 53      -- Grab new killer name
 54      killer[iteration_number+1] = humans.human[ikiller[iteration_number+1]],
 55  -- debug[iteration_number+1]=debug[iteration_number+1]||' pk='||prev_killer[1]||' k='||ikiller[iteration_number+1]||'/'||killer[iteration_number+1],
 56      -- Set previous killer as new killer
 57      prev_killer[rn between 1 and &N] = ikiller[iteration_number+1],
 58  -- debug[iteration_number+1]=debug[iteration_number+1]||' pk2='||prev_killer[1],
 59      -- Calculate new killed (dead), first one (iteration 0) is last number
 60      idead[iteration_number+1] = 
 61        decode(iteration_number, 
 62               0, &N,
 63               mod(max(decode(killed,'N',mod(step-prev_killer+&N,&N)))[rn between 1 and &N]
 64                    + prev_killer[1], &N)
 65              ),
 66      -- Grab new dead human name
 67      dead[iteration_number+1] = humans.human[idead[iteration_number+1]],
 68  -- debug[iteration_number+1]=debug[iteration_number+1]||' d='||idead[iteration_number+1]||'/'||dead[iteration_number+1],
 69      -- Flag human as killed
 70      killed[idead[iteration_number+1]] = 'Y'
 71    )
 72  order by step
 73  /
Steps
----------------------------------------
Now Abel kills Esther
Now Deborah kills Cain
Now Bethany kills Abel
Now Deborah kills Bethany
Last Person Standing: Deborah

5 rows selected.

SQL> def N=6
SQL> /
Steps
----------------------------------------
Now Abel kills Felix
Now Esther kills Deborah
Now Cain kills Bethany
Now Abel kills Esther
Now Cain kills Abel
Last Person Standing: Cain

6 rows selected.

Sorry for long lines, I keep them to allow you to see how it works uncommenting "debug" lines.

Regards
Michel
Previous Topic: Oracle profiler
Next Topic: Releasing Row Level Locks Manually
Goto Forum:
  


Current Time: Thu Oct 30 18:25:00 CDT 2014

Total time taken to generate the page: 0.10297 seconds