/prog/ - [CHALLENGE] Sorting algorithm interview question

Name: Anonymous 2016-02-27 12:38

Sort a (linked) list of integers, min to max.
1. You're only allowed to compare the first and second elements.

2. You can swap the first and second elements.

3. You can move the first element to the end of the list.

This was an interview question and supposedly isn't on the internet anywhere. Here was my attempt: https://play.golang.org/p/_hsRXFFkNl and the line-by-line output: http://pastebin.com/raw/c2wZSEpR

Name: Anonymous 2016-02-27 12:42

I didn't know how to solve it, so I just brute forced it on paper and found a pattern from which I based the ``algorithm.'' I'm sure you can do better.

Name: Anonymous 2016-02-27 13:35

So, bubble sort?

Name: Anonymous 2016-02-27 13:55

>>3
The interviewer said "No" when I asked that same question. It cannot be bubble sort because copying the list or splitting up the list are against the rules.

Name: Anonymous 2016-02-27 13:58

>>4
It's bubble sort. The only difference is traversing the list is done by shifting the list itself rather than incrementing the current index. You still need an index though, so that you can tell when you've overstepped from the last element back to the first, since it's effectively a cyclic list.

Name: Anonymous 2016-02-27 14:02

>>4
Also, you don't copy or split the list for bubble sort.

Name: Anonymous 2016-02-27 14:18

It would make sense that it's "a" bubble sort.

Anyway, I realized that this is an impossible algorithm because you never know how to end it. I cheated by calling the length of the list (which requires accessing the memory after the second node, against the rules).

Name: Anonymous 2016-02-27 15:27

>>7
It's "a" bubble sort in the sense that you are running the bubble sort algorithm on a representation of the data that is not a fixed-length, random-access array, correct.

Anyway, it's not impossible.
Keep track of the maximum and mimimum elements as you keep running through the list.
The final check for sortedness is then basically:
While first < second, chuck first to end.
Now, first > second, so make sure first == maximum and second == minimum. Chuck first to the end one last time.

I wouldn't take the job, anyway, if your interviewer came up with this problem without realising it was bubble sort.

Name: Anonymous 2016-02-27 19:35

>>8
I know this sounds retarded, but I was told that I cannot "use memory as a crutch for saving old values." Otherwise, yeah you're right, that's how you can do it.

Name: Anonymous 2016-02-27 19:37

>>9
That does sound retarded. I hope you don't get it, for your sake.

Name: Anonymous 2016-02-27 21:50

>>10
Check 'em

Name: Anonymous 2016-02-28 2:24

>>8
if you can't get the size of list, it is impossible.

Name: Anonymous 2016-02-28 3:08

>>8
See >>12,10 .

Name: Anonymous 2016-02-28 12:05

>>9
Do you know about the technique of intentional caching? Sometimes, you find that you can improve some kind of performance metric by caching computational results rather than computing the same calculations time and time again. The tradeoff is that caching data requires more memory space than if you dynamically calculated the data every time.

Name: Anonymous 2016-02-28 14:01

>>11
Checked

Name: Anonymous 2016-02-28 14:06

>>13
What, exactly, did you add to this thread? >>8 cannot see into the future.

Name: Anonymous 2016-02-28 15:55

>>1
See >>2-1001

Name: Anonymous 2016-02-29 15:12

>>16
And what exactly did the >>11 and >>15 niggers add to the thread? AIDS

Name: Anonymous 2016-03-01 6:49

>>14
So you're telling me that I can convert my O(2ⁿ) time complexity, O(1) space complexity teledildonics thrust calculation algorithm into a O(1) time complexity, O(2ⁿ), smart guy? Don't make me laugh. Next you'll tell me that I don't need to recalculate the sine and cosine of an angle on every every vertex of a polygon I'm rotating, or that I could take advantage of distributivity when calculating and equation. Suck my dick you stupid faggot. The real world doesn't work that way. Stop wasting memory on crap that can easily be recomputed.

Name: Anonymous 2016-03-01 14:22

solved it in 10 mintues
what a breeze

Name: Anonymous 2016-03-02 20:26

fibs get

Name: Anonymous 2016-03-04 15:52

oh god oh god oh god. this is my first doubles get. I am so excited

Name: Anonymous 2016-03-04 16:12

dubs

Name: Anonymous 2016-03-05 10:02

>>22
Sorry dog, this board is for humans.

Name: Anonymous 2016-03-08 7:44

>>14

you mena memoization?

Name: Anonymous 2016-03-08 15:02

>>26
u mean HASKELL?

Name: Anonymous 2016-03-08 15:05

>>27
U MENA >>27?

[CHALLENGE] Sorting algorithm interview question

1 Name: Anonymous 2016-02-27 12:38

2 Name: Anonymous 2016-02-27 12:42

3 Name: Anonymous 2016-02-27 13:35

4 Name: Anonymous 2016-02-27 13:55

5 Name: Anonymous 2016-02-27 13:58

6 Name: Anonymous 2016-02-27 14:02

7 Name: Anonymous 2016-02-27 14:18

8 Name: Anonymous 2016-02-27 15:27

9 Name: Anonymous 2016-02-27 19:35

10 Name: Anonymous 2016-02-27 19:37

11 Name: Anonymous 2016-02-27 21:50

12 Name: Anonymous 2016-02-28 2:24

13 Name: Anonymous 2016-02-28 3:08

14 Name: Anonymous 2016-02-28 12:05

15 Name: Anonymous 2016-02-28 14:01

16 Name: Anonymous 2016-02-28 14:06

17 Name: Anonymous 2016-02-28 15:55

18 Name: Anonymous 2016-02-29 15:12

19 Name: Anonymous 2016-03-01 6:49

20 Name: Anonymous 2016-03-01 14:22

21 Name: Anonymous 2016-03-02 20:26

22 Name: Anonymous 2016-03-04 15:52

23 Name: Anonymous 2016-03-04 16:12

24 Name: Anonymous 2016-03-05 10:02

25 Name: Anonymous 2016-03-08 7:44

26 Name: Anonymous 2016-03-08 15:02

27 Name: Anonymous 2016-03-08 15:05