Google Interview Question
Software DevelopersCountry: United States
Interview Type: Phone Interview
#!/usr/bin/python
A = [4,5,6,1,7,2]
l = 0
r = 0
def rotate(A, l, r):
while (l < r):
t = A[l]
A[l] = A[r]
A[r] = t
l += 1
r -= 1
if __name__ == "__main__":
max = len(A)
print A # original list/array
for l in range(max):
r = l
for i in range(l,max):
# print l, i
if A[r] > A[i]:
r = i
print r
rotate(A,l,r)
print A
public class RotateArray{
public static void main(String []args){
int[] arr = {4,5,6,7,1,2};
for (int ass: rotate(arr, 2))
System.out.println(ass);
}
static int[] rotate (int[] arr, int n){
if(arr == null || arr.length <=1) return null;
int[] arrn = new int[arr.length];
while(n > 0){
int in = arr[1];
int ind = 0;
for(int i=1; i<arr.length; i++){
if(arr[i] < in){
in = arr[i];
ind = i;
}
}
int aind = ind+1;
for(int i=0; i<arr.length; i++, ind--){
if(ind <0){
arrn[i] = arr[aind++];
} else arrn[i] = arr[ind];
}
for(int i=0; i< arr.length; i++)
arr[i] = arrn[i];
n--;
}
return arr;
}
}
public class RotateArray{
public static void main(String []args){
int[] arr = {4,5,6,7,1,2};
for (int ass: rotate(arr, 2))
System.out.println(ass);
}
static int[] rotate (int[] arr, int n){
if(arr == null || arr.length <=1) return null;
int[] arrn = new int[arr.length];
while(n > 0){
int in = arr[1];
int ind = 0;
for(int i=1; i<arr.length; i++){
if(arr[i] < in){
in = arr[i];
ind = i;
}
}
int aind = ind+1;
for(int i=0; i<arr.length; i++, ind--){
if(ind <0){
arrn[i] = arr[aind++];
} else arrn[i] = arr[ind];
}
for(int i=0; i< arr.length; i++)
arr[i] = arrn[i];
n--;
}
return arr;
}
}
public class RotateArray{
public static void main(String []args){
int[] arr = {4,5,6,7,1,2};
for (int ass: rotate(arr, 2))
System.out.println(ass);
}
static int[] rotate (int[] arr, int n){
if(arr == null || arr.length <=1) return null;
int[] arrn = new int[arr.length];
while(n > 0){
int in = arr[1];
int ind = 0;
for(int i=1; i<arr.length; i++){
if(arr[i] < in){
in = arr[i];
ind = i;
}
}
int aind = ind+1;
for(int i=0; i<arr.length; i++, ind--){
if(ind <0){
arrn[i] = arr[aind++];
} else arrn[i] = arr[ind];
}
for(int i=0; i< arr.length; i++)
arr[i] = arrn[i];
n--;
}
return arr;
}
}
class Cylinder {
public:
Cylinder(int height, int id)
{
h_ = height;
id_ = id;
}
int h_, id_;
};
void Reverse(vector<Cylinder> &a, int from, int to)
{
if (to > from) {
for (int i = from; i < to; ++i) {
if (a[i].h_ == a[i + 1].h_) {
int dups_end_idx = i + 1;
while (dups_end_idx + 1 <= to &&
a[dups_end_idx + 1].h_ == a[i].h_)
{
++dups_end_idx;
}
reverse(a.begin() + i, a.begin() + dups_end_idx + 1);
}
}
reverse(a.begin(), a.begin() + to + 1);
}
}
void RoboSort(vector<Cylinder> &a)
{
for (int i = 0; i < a.size(); ++i) {
int min_idx = i;
for (int j = i + 1; j < a.size(); ++j) {
if (a[j].h_ < a[min_idx].h_) {
min_idx = j;
}
}
Reverse(a, i, min_idx);
}
}
#include<iostream>
#include<vector>
using namespace std;
struct Cylander {
int index;
int height;
};
void robo_rotate(vector<Cylander>& lst, int left, int right){
for(;left<right; left++, right--){
Cylander temp = lst[left];
lst[left] = lst[right];
lst[right] = temp;
}
}
void robo_sort(vector<Cylander>& lst){
for(int left = 0; left< lst.size(); left++){
Cylander min = lst[left];
int min_index = left;
for(int right = left+1; right < lst.size(); right++){
if(min.height > lst[right].height || (min.height == lst[right].height && min.index > lst[right].index)){
min_index = right;
min = lst[right];
}
}
robo_rotate(lst, left, min_index);
}
}
int main(){
vector<Cylander> cylanders(6);
cylanders[0] = {0, 1};
cylanders[1] = {1, 7};
cylanders[2] = {2, 6};
cylanders[3] = {3, 7};
cylanders[4] = {4, 4};
cylanders[5] = {5, 2};
robo_sort(cylanders);
for(int i=0; i< 6; i++){
cout << "(" << cylanders[i].height << "," << cylanders[i].index << ") ";
}
cout << endl;
}
#include<iostream>
#include<vector>
using namespace std;
struct Cylander {
int index;
int height;
};
void robo_rotate(vector<Cylander>& lst, int left, int right){
for(;left<right; left++, right--){
Cylander temp = lst[left];
lst[left] = lst[right];
lst[right] = temp;
}
}
void robo_sort(vector<Cylander>& lst){
for(int left = 0; left< lst.size(); left++){
Cylander min = lst[left];
int min_index = left;
for(int right = left+1; right < lst.size(); right++){
if(min.height > lst[right].height || (min.height == lst[right].height && min.index > lst[right].index)){
min_index = right;
min = lst[right];
}
}
robo_rotate(lst, left, min_index);
}
}
int main(){
vector<Cylander> cylanders(6);
cylanders[0] = {0, 1};
cylanders[1] = {1, 7};
cylanders[2] = {2, 6};
cylanders[3] = {3, 7};
cylanders[4] = {4, 4};
cylanders[5] = {5, 2};
robo_sort(cylanders);
for(int i=0; i< 6; i++){
cout << "(" << cylanders[i].height << "," << cylanders[i].index << ") ";
}
cout << endl;
}
In Python (without using list manipulation for rotation):
- pythist August 08, 2017