Home » Other » General » Puzzle
Puzzle [message #414794] |
Thu, 23 July 2009 08:26 |
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 )
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 #414826 is a reply to message #414794] |
Thu, 23 July 2009 12:56 |
joy_division
Messages: 4963 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 #414836 is a reply to message #414834] |
Thu, 23 July 2009 14:18 |
ThomasG
Messages: 3212 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.
|
|
|
|
|
Re: Puzzle [message #414894 is a reply to message #414865] |
Thu, 23 July 2009 23:47 |
Frank
Messages: 7901 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 #415168 is a reply to message #414794] |
Sat, 25 July 2009 10:57 |
|
Michel Cadot
Messages: 68716 Registered: March 2007 Location: Saint-Maur, France, https...
|
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
|
|
|
Goto Forum:
Current Time: Mon Nov 25 22:40:02 CST 2024
|