An Algorithm for rotating a sequence


An algorithm for rotating a sequence

I attended a job interview today, the interviewer asks me a question about how to rotate a sequence with a good space efficiency.
I believe I give him a terrible answer. And the interviewer gives me his answer, well, thanks him a lot.

So how to rotate a sequence? There is a sequence blow? 

+--+--+--+--+--+--+--+--+
| 1| 2| 3| 4| 5| 6| 7| 8|
+--+--+--+--+--+--+--+--+
then rotate the sequence to left by 3? what we get is as following. 
+--+--+--+--+--+--+--+--+
| 4| 5| 6| 7| 8| 1| 2| 3|
+--+--+--+--+--+--+--+--+
So the following step to step tutorial is a space efficiency way.
  1. reverse the first 3 sequence.
  2. reverse the last (8 - 3) = 5 sequence.
  3. reverse the whole sequence.
Then, we get the result sequence which rotates to left by 3 items. I don't know whether it is the best way. I mean both the best space efficiency and time efficiency. 

orignal sequence
           n=3
    +--+--+--+--+--+--+--+--+
    | 1| 2| 3| 4| 5| 6| 7| 8|
    +--+--+--+--+--+--+--+--+

  step 1.  reverse first n sequence    
    +--+--+--+--+--+--+--+--+
    | 3| 2| 1| 4| 5| 6| 7| 8|
    +--+--+--+--+--+--+--+--+

  step 2. reverse last sequence 
    +--+--+--+--+--+--+--+--+
    | 3| 2| 1| 8| 7| 6| 5| 4|
    +--+--+--+--+--+--+--+--+

  step 3. reverse the whole sequence
    +--+--+--+--+--+--+--+--+
    | 4| 5| 6| 7| 8| 1| 2| 3|
    +--+--+--+--+--+--+--+--+

I wrote a sample code and upload into GitHub. Maybe I should add this algorithm into all my sequence related classes.

Comments

Post a Comment

Popular posts from this blog

How Bluetooth LE works? -- Link Layer

Image
How Bluetooth LE works? - Link layer Table of Contents 1 Bluetooth LE system architecture 2 Bluetooth LE Physical layer 3 Bluetooth LE Link Layer states 4 Bluetooth LE Link Layer packets 1 Bluetooth LE system architecture This is the first post and hopefully a series of upcoming postings about Bluetooth Low Energy. Above figure is the protocol stack of a whole Bluetooth LE system. The Bluetooth LE is one part of Bluetooth v4.0 specification, it was designed not to pursue high transmission speed but for lower energy consumption. So the Bluetooth LE products can be powered by a button-cell battery for years. How did it do that? This article is a review of Robin Heydon's excellent book – Bluetooth Low Energy, the developer's handbook. Bluetooth LE is completely redesigned of classic Bluetooth protocol, It seems that both the Bluetooth LE and classic Bluetooth has the same architecture from above figure, but actually they are so different inside, an...
Read more

Bluedroid stack in android

Image
Bluedroid stack in android Table of Contents Bluetooth stack in android Bluedroid .VS. Bluez Porting guide of Bluedroid stack 1 Bluetooth stack in android From Android 4.2, google use Bluedroid stack as its default Bluetooth host stack, before android 4.2, its default Bluetooth host stack was Bluez, which is also the Linux distribution's default stack. So why google changed its Bluetooth stack? The reason is maybe that Bluez stack was designed for the desktop environment, so in order to port Bluez into android, android must solve some dependency issues, like porting Dbus, Linux desktop's default IPC, into android. So there are at least five processes to power Bluetooth before android 4.2, they are systems, Bluetooth APP, Bluez, hciattach, and Dbus. The damn thing is that there are bugs between them, so Bluetooth stack is the weakest part in the android system before android 4.2, yeah, it is the usual reason that android system corrupted. So, what's t...
Read more

Network programming in elisp

  Network API in elisp Table of Contents 1 Introduction 2 A example 3 Http server implemented by elisp 1 Introduction Emacs is not just an editor, Yes, that's true. Emacs lisp can do network connection programming by its network API. But there is something difference with other kinds of programming language. First, elisp do not support multi-thread, pretty cool, huh!! Yeh, Multi-threads programming is a horrible venture for you, right! Second, There is no socket similarly conception in elisp, and elisp provide network programming ability as processes. Elisp can open a network connection by function – open-network-stream .  It can make network connection server listen a special port by function - make-network-process . Both of those function return a process object. Then you can communicate with the process by process's API. 2 A example I write a snippet code to figure out How to use it. ( require ' cl ) ( defvar my-network-client-b...
Read more