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

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

How to setup a NAT server?

Image
How to setup an NAT server? Table of Contents What is NAT? How to setup NAT host? a shell script from vbird's book 1 What is NAT? NAT stands for Network Address Transition, which is the basic function of gateway host. I try to hack Bluetooth tethering module in android this week, it include the Bluetooth Pan profile and the NAT setup process, which means in order to implement the Bluetooth tethering, first, two devices must be connected by Bluetooth Pan profile, and then the server part device acted as gateway host to supply the network forward service. In other words, after Bluetooth Pan profile connected, the server must to setup its NAT rules to forward the IP packages. So how to setup NAT rules? 2 How to setup NAT host? My memory is still fresh that at the start of my Linux journey, I setup my Linux desktop as an NAT host to provide Internet services for my lab's classmates. During the days as a programmer, I once did a job to hacking android&
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