## Google Interview Question for SDE1s

• 0

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

Convert the fancy swap into a proper swap and sort the array linearly.

``````using System;

namespace ConsoleApp1
{
class Program
{
private const int c_Space = -1;
private static int[] a = new int[]
{
1, c_Space, 5, 4, 2, 3
};

static void Main()
{
Sort();

for (int i = 0; i < a.Length; i++)
{
Console.WriteLine(a[i]);
}
}

static void Sort()
{
for (int i = 0; i < a.Length - 1; i++)
{
if (a[i] == c_Space)
{
Swap(i, a.Length - 1);
}
}

int index = 0;
while (index < a.Length - 1)
{
if (a[index] == index + 1) index++;
else ProperSwap(a[index] - 1, index);
}
}

static void Swap(int i, int j)
{
if (a[i] != c_Space && a[j] != c_Space)
{
throw new Exception("Must include space");
}

int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

static void ProperSwap(int i, int j)
{
Swap(i, a.Length - 1);
Swap(i, j);
Swap(j, a.Length - 1);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

You can do this with a modified quicksort.

The trick is that when you are dividing with the pivot, you are always sorting the left branch first. So once you sort the left branch of any given partition, put the space at the end of the partition, so it is available at the front of the next partition down the list

This would be n lg n time

The simple to code process would just be a selection sort, where you go pick out the largest element each time. This would be n squared

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) soln. -

``````public static void main(String[] args){
int[] arr = {3,2,999,1};
int index = -1;
int k = arr.length;
for(int i = 0; i < arr.length; i++){
if(arr[i] == 999){
index = i;
break;
}
}

sort(arr, index, k);
}

//considering ' ' as 999
public static void sort(int[] arr, int index, int k){

int n = arr.length;

if(k == 0){
for(int i = 1; i < n; i++){
System.out.print(arr[i] + " ");
}
System.out.print(999);
return;
}else if(k > 0 && index == 0){
index = n-2;
for(int i = 1; i <= index; i++){
arr[i-1] = arr[i];
}
arr[index] = 999;
}

if(index-1 >= 0 && index+1 < n && arr[index-1] > arr[index+1]){
swap(arr, index, index+1);
swap(arr, index-1, index+1);
}else{
swap(arr, index, index-1);
}
sort(arr, index-1, k-1);
}

public static void swap(int[] arr, int i, int j){
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void Sort(vector<int> &a)
{
int space_idx = -1;
for (int i = 0; i < a.size() && space_idx == -1; ++i) {
if (a[i] == 0) {
space_idx = i;
}
}

if (space_idx != -1) {
for (int i = 0; i < a.size(); ++i) {
while (i != space_idx &&
a[i] != i + 1)
{
int space_idx_stored = space_idx;
swap(a[a[i] - 1], a[space_idx]);
space_idx = a[i] - 1;
swap(a[i], a[space_idx]);
space_idx = i;
if (a[space_idx_stored] != space_idx_stored + 1) {
swap(a[space_idx_stored], a[space_idx]);
space_idx = space_idx_stored;
}
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) algorithm (at most 2*n swaps)

``````// 0 for the gap, 1...a.length - elements, k-th element must end up in a[k-1]

public class Swapper {
private static final int GAP_VALUE = 0;
private final int[] a;
private int gap;

public Swapper(final int[] a) {
this.a = a;
for (int i = 0; i < a.length; i++) {
if (GAP_VALUE == a[i]) {
gap = i;
break;
}
}
assert gap >= 0;
}

public void sortWithSwap() {
for (int i = 0; i < a.length - 1; i++) {
if (a[i] != i + 1) { // if not in place already
if (gap != a[i] - 1) {
swap(a[i] - 1);
}
swap(i);
}
}
if (a[a.length - 1] != GAP_VALUE) {
swap(a.length - 1);
}
}

private void swap(final int idx) {
assert GAP_VALUE == a[gap];
a[gap] = a[idx];
a[idx] = GAP_VALUE;
gap = idx;
}

public static void main(String[] args) {
final int[] arr = {7,9,3,0,1,4,2,8,5,6};
new Swapper(arr).sortWithSwap();
System.out.println(Arrays.toString(arr));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

@Eirk. My first version was the same. But it doesn't always work correctly.
E.g. 0, 3, 2, 5, 4, 1 gets sorted into 1, 4, 3, 2, 5, 0.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````let array = [8,4,3,7,6,'',5,2,1];
const GAP = '';

function swap(i, j) {
if((array[i] === GAP || array[j] === GAP)) {
let leftItem = array[i];
array[i] = array[j];
array[j] = leftItem;
}
}

var combSort = function (array) {
let interval = Math.floor(array.length/1.3);
let count = 0;

swap(array.indexOf(GAP), array.length-1);

while(interval > 0) {
for(var i=0; i+interval<array.length; i++) {
count++;
if (array[i] > array[i+interval]) {
let initialGapIndex = array.indexOf(GAP);

swap(i+interval, array.indexOf(GAP));
swap(array.indexOf(GAP), i);
swap(array.indexOf(GAP), initialGapIndex);
}
}

interval = Math.floor(interval/1.3);
}

return array;
};

console.log(combSort(array));``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.