## Google Interview Question for Software Engineer / Developers

• 4

Team: Chrome Team
Country: United States
Interview Type: Phone Interview

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

This doesn't need a sort, and operates in O(n). It is guaranteeing that in every group of 3 the middle element is the greatest. If in the next group of 3 a swap is done on the right hand element of the previous group of 3, it can only be replaced by a smaller element. The problem is that it only guarantees >=, not >

``````for (int i = 1; i < arr.size(); i += 2)
{
if (arr[i - 1] > arr[i])
std::swap(arr[i - 1], arr[i]);
if ((i < arr.size() - 1) && (arr[i + 1] > arr[i]))
std::swap(arr[i + 1], arr[i]);
}``````

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

how would this behave if the array is [10,12,20,80,100] ?

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

anon is correct. By the third iteration, the array would look like this:

[10, 12, 20, 80, 100]

since we have already looked an index 1 we can't change it.
This algorithm is a bit too localized.

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

Not true, I tried it to make sure. The result is:
{10, 20, 12, 100, 80}
First iteration swaps 12 and 20, second swaps 80 and 100. There is no third iteration, since it counts by 2s.

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

Oh. I see now. I misread and assumed you were incrementing by one.

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

first:

{6, 5, 4,3,2,1}

then

{5,6,4,3,2,1}

then

{5,6,3,4,2,1}

then

{5,6,3,4, 1, 2}

I see nothing wrong

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

Hey tjcbs2, I think this is a great solution, I actually implemented the same thing before looking at your answer. I think for the case where you have duplicates in the array, you can simply create a second array without duplicates, then apply your algorithm above to the second array. This, of course, is based on the assumption that the original question doesn't require the output array to be the same size as the input.

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

Excellent solution. First 3, the largest goes in the middle. The second 3 has the left element overlapped with the first 3. But it does not matter. Because if the overlapped element is not the largest, it stays where it is. If it is the largest, then a smaller is swapped here, then the relationship in the first 3 is kept.

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

In order traversal of a Max-heap

Heap Creation From an array is O(n)
In Order Traversal is O(n)

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

How is heap creating O(n).
Isn't heapify and O(logn) operation. We do it for every insert.

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

How is heap creation O(n).

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

Its the heapify portion of heapsort algorithm. Thats why O(n)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

If you can create a max-heap in O(n) then you found a faster sorting algorithm than O(n log n), which by the Stirling's theorem is not possible.

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

Building a max heap with an array is O(nlogn). But my question is how you do inorder traversal in an array?
Eg arr[1...n]?

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

Building a max heap from an array is O(nlogn).

My question is how you perform an inorder traversal on the heap which is an array?

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

You can in fact build a Max/Min Heap using a heapfiy() O(n) call on all the structure of the array to construct the heap from.

The Ordinary case is insert data as it comes and that takes O(n log n) to build the heap.

But in case of in-order traversal of the heap you will basically remove one element at a time and that takes O(log n) each so you will have:

O(n) construct heap.
O(n log n) to get your in-order traversal.
-------------
O(n log n) over all runtime.

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

I can't seem to think of a solution without a sort which would mean the best is nlogn. An alternate solution is to sort and then add the first element to the new array and then for every sequential pair of elements afterwards add the larger element of the pair first and then the smaller element. For instance, if the sort yields [1 2 3 4 5 ...], then add 1 followed by 3 then 2 and 5 then 4 and so on with the result being [1 3 2 5 4 7 6 ...]. Essentially, you are swapping the 2nd and 3rd elements, the 4th and 5th elements, etc. Still same runtime as your solution above, but the advantage of mine is that it could be performed in place (which I understand is not the question).

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

Check my solution. It is O(n) average/best case

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

Use quickselect (from quicksort) to find the median, copy elements < median at 1,3,5,... positions
Copy elements > median at remaining positions 2,4,6,...

Best/Averate time complexity O(n)
Worst time complexity O(n*n)

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

There is a deterministic, worst-case O(n) algorithm for finding the median of a given array.

So:

1. find the median and partition the array into L, U accordingly (note you might have multiple occurrences of the median: just balance the L and U partitions) => O(n)

2. interleave => O(n)

will yield a worst-case O(n) algorithm for this problem.

Note: if an element is repeated more than n/2 times, one cannot build an array with the desired property a_(2i-1) < a_(2i) and a_(2i+1) < a_(2i).

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

No need to sort... thinking arr as min, and using findMin technique O(n)

int[] arr = {11,4,5,2,3};
int min = arr, index = 0, nextIndex = 3;

int[] newArr = new int[arr.length];

newArr = min;

if(arr < min){
newArr[index] = arr;
index += 2;
}else{
newArr[newArr.length - 1] = arr;
}

for(int i = 2; i < arr.length; i++){

if(arr[i] < min && index <= 2){
newArr[index] = arr[i];
index += 2;
}else{
newArr[nextIndex++] = arr[i];
}
}

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

No need to sort, using findMinimum technique O(n)

int[] arr = {1,4,5,2,3};
int min = arr, index = 0, nextIndex = 3;

int[] newArr = new int[arr.length];

newArr = min;

if(arr < min){
newArr[index] = arr;
index += 2;
}else{
newArr[newArr.length - 1] = arr;
}

for(int i = 2; i < arr.length; i++){

if(arr[i] < min && index <= 2){
newArr[index] = arr[i];
index += 2;
}else{
newArr[nextIndex++] = arr[i];
}
}

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

You can merge/quick sort, then add to the array like the following:

index i = 0
index j = 2

loop:
i++
j++
i+=3
i+=3

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

Sorting is unnecessary. You are seeking a version of an array where odd-index elements (1,3,5...) are local maxima in the range of their adjacent even-index elements.

My solution has the use of the mod operator (for better design, i recommend use of a flipping boolean as mod isn't the best operator in terms of efficiency if I recall correctly).
Each iteration, you determine whether to switch with the next element by whether or not you are on a odd element.

In python, it looks like this:

``````def find_local_max(arr):
for i in range(0, len(arr) - 1):
if (arr[i] < arr[i+1] and i%2 != 0) or (arr[i] > arr[i+1] and i%2 == 0):
tmp = arr[i]
arr[i] = arr[i+1]
arr[i+1] = tmp
return arr``````

Depending on if the index is even or odd, the logic of when to trigger a swap is inversed. Because it iterates one index at a time, you can handle the edge case where some values would get lost in the skipping portion and you could have a returned array that isn't matching the requirements.

As this only loops through the array once, its runtime is O(n).
To sum up the central logic component of this solution in pseudocode:

``````for each value/index in array:
if current val is less than next, and current index is odd, swap them
else if current val is greater than next and current index is even, swap them``````

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

Nice. Follow-up would be to prove the correctness of this by induction.

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

I implemented a version of your described algorithm and it seems to work

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

Its wokring fin9

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

No need for a flipping boolean, ((i&1) == 0) is true for even.

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

Description for question does't say that all values are unique. I think this solution doesn't work for input array {5,5,5,5,1,1,1,1}

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

2 different implementations based on the ideas of the author and the idea of swapping adjacent elements:

``````/**
* based on sorting and iterative approach using aux. array:
*
* O(n*log(n)) time, O(n) space
*
* @param a
* @return
*/
public static int[] getOrderedArrayDecIncSequence(int[] a) {
if (a == null || a.length == 1) {
return a;
}
Arrays.sort(a);
int[] b = new int[a.length];
int k = 0;
for (int i = 0, j = a.length-1; i < a.length && j >= i; i++, j--) {
b[k] = a[i];
if (j > i) {
b[k + 1] = a[j];
}
k+=2;
}

return b;
}

/**
* Based on swapping adjacent positions: O(n) time, O(1) space
* @param a
* @return
*/
public static int[] getOrderedArrayDecIncSequenceSwapping(int[] a) {
if (a == null || a.length == 1) {
return a;
}
boolean odd = true;
int temp;
for (int i = 1; i < a.length; i++) {
if (odd) {
if (a[i - 1] > a[i]) {
temp = a[i];
a[i] = a[i - 1];
a[i - 1] = temp;
}
} else {
if (a[i - 1] < a[i]) {
temp = a[i];
a[i] = a[i - 1];
a[i - 1] = temp;
}
}
odd = !odd;
}

return a;
}``````

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

``````#include <stdio.h>
#include <stdlib.h>

int compare(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}

void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}

void pattern(int A[], int n)
{
int i = 1;
while(i < n-1)
{
swap(&A[i], &A[i+1]);
i = i+2;
}
}

int main()
{
int A[] = {1, 4, 5, 2, 3, 8, 9, 6, 7};
int n = sizeof(A)/sizeof(A);
int i;

qsort(A, n, sizeof(A), compare);

pattern(A,n);

for(i = 0; i < n; i++)
printf("%d\t", A[i]);

return 0;
}``````

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

``````void swapNum(int *a, int *b){
int temp;
temp = *a;
*a = *b;
*b = temp;
}

void sortByPattern(int *a, int n){
sort(a, a+n);
for(int i = 1; i < n; i = i+2){
if(a[i] < a[i+1]){
swapNum(&a[i], &a[i+1]);
}
}
}``````

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

What if there is a follow up say find out all arrays that meet this requirement? I think in this case it is very hard I can only think brute force all arrays and check if they meet the requirement. Do you guys have any good ideas?

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

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

``````public class BetwnGr{
public static void main(String [] args){
int [] arr= { 10, 12, 20, 80, 100 };
arr=incr(arr);
int l=arr.length;
int m=l/2;
int j=1,k=m+1;
for(int i=1;i<=m;i++){
int temp=arr[j];
arr[j]=arr[k];
for(int p=k;p>j+1;p--){
arr[p]=arr[p-1];
}
arr[j+1]=temp;
j+=2;
k+=1;
}
System.out.println("\nArry");
for(int r=0;r<arr.length;r++)
System.out.print(" "+arr[r]);
}
public static int [] incr(int [] a){
for(int i=0;i<a.length;i++){
int k=a[i];
int loc=i;
for(int j=i+1;j<a.length;j++){
if(k>a[j]){
k=a[j];
loc=j;
}
}
if(k!=a[i]){
a[loc]=a[i];
a[i]=k;
}
}
return a;
}
}``````

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

it is working fine for odd number of integers in array but not for even . Can any one tell me, What is wrong with this???

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

This worked perfectly for me
Sort O(n log(n))
and Swap O(n/2)=O(n)

If someone has a better solution i really like to know.
Any suggestion is a welcome

Thank You

package xTester;

import java.util.Arrays;
import java.util.Scanner;

/**
*
*/
public class GArray {

/**
*
*/
Integer arr[] ;

public static void main(String args[])
{

@SuppressWarnings("resource")
Scanner scan = new Scanner(System.in);
int size = scan.nextInt();

GArray gaO = new GArray();
gaO.arr = new Integer[size];
for(int i=0;i<size;i++)
{
gaO.arr[i] = Integer.valueOf(scan.nextInt());
}

gaO.getInPattern();
System.out.println(Arrays.asList(gaO.arr));
}

/**
*
*/
@SuppressWarnings("boxing")
private void getInPattern()
{
//int length = arr.length;
Arrays.sort(arr); // Dual Pivote Quick sort O(n log(n))
for(int i=0;i<arr.length-1;i+=2)
{
arr[i] += arr[i+1];
arr[i+1] = arr[i] - arr[i+1];
arr[i] = arr[i] - arr[i+1];
}
}

}

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

This works perfectly fine for me
Sort and then Swap
Sort Dual pivote sort O(nlog(n))
Swap O(n/2) = O(n)

I dont think there is a better solution
If there is any i really like to know

Any suggestion is a welcome

``````import java.util.Arrays;
import java.util.Scanner;

/**
*
*/
public class GArray {

/**
*
*/
Integer arr[] ;

public static void main(String args[])
{

@SuppressWarnings("resource")
Scanner scan = new Scanner(System.in);
int size = scan.nextInt();

GArray gaO = new GArray();
gaO.arr = new Integer[size];
for(int i=0;i<size;i++)
{
gaO.arr[i] = Integer.valueOf(scan.nextInt());
}

gaO.getInPattern();
System.out.println(Arrays.asList(gaO.arr));
}

/**
*
*/
@SuppressWarnings("boxing")
private void getInPattern()
{
//int length = arr.length;
Arrays.sort(arr); // Dual Pivote Quick sort O(n log(n))
for(int i=0;i<arr.length-1;i+=2)
{
arr[i] += arr[i+1];
arr[i+1] = arr[i] - arr[i+1];
arr[i] = arr[i] - arr[i+1];
}
}

}``````

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

This works perfectly fine for me
Sort and then Swap
Sort Dual pivote sort O(nlog(n))
Swap O(n/2) = O(n)

I dont think there is a better solution
If there is any i really like to know

Any suggestion is a welcome

``````import java.util.Arrays;
import java.util.Scanner;

/**
*
*/
public class GArray {

/**
*
*/
Integer arr[] ;

public static void main(String args[])
{

@SuppressWarnings("resource")
Scanner scan = new Scanner(System.in);
int size = scan.nextInt();

GArray gaO = new GArray();
gaO.arr = new Integer[size];
for(int i=0;i<size;i++)
{
gaO.arr[i] = Integer.valueOf(scan.nextInt());
}

gaO.getInPattern();
System.out.println(Arrays.asList(gaO.arr));
}

/**
*
*/
@SuppressWarnings("boxing")
private void getInPattern()
{
//int length = arr.length;
Arrays.sort(arr); // Dual Pivote Quick sort O(n log(n))
for(int i=0;i<arr.length-1;i+=2)
{
arr[i] += arr[i+1];
arr[i+1] = arr[i] - arr[i+1];
arr[i] = arr[i] - arr[i+1];
}
}

}``````

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

``````int[] SecondIsGreaterLeftRight(int[] array)
{
int[] arrayOut = new int[array.Length];
int rightIndex = (int)(((double)array.Length / (double)2) + 0.5);
int leftIndex = 0;

Array.Sort(array);
bool left = true;
for (int i = 0; i < array.Length; i++) {
if (left)
{
arrayOut[i] = array[leftIndex];
leftIndex++;
left = false;
}
else
{
arrayOut[i] = array[rightIndex];
rightIndex++;
left = true;
}
}
return arrayOut;
}``````

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

``````public static void main(String[] args){
Integer[] intArray = {5, 3, 8, 6, 12, 4, 7, 9, 15};
Collections.sort(Arrays.asList(intArray));
System.out.println("Sorted Array: ");
Integer temp;
for(int i=0; i< intArray.length; i++) {
System.out.println(intArray[i]);
}
for(int i=1; i<intArray.length-1; i=i+2) {
temp = intArray[i];
intArray[i]= intArray[i+1];
intArray[i+1] = temp;

}
System.out.println("Result: "+Arrays.asList(intArray));
}``````

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

``````public static int[] getZigZag(int[] a) {
if (a == null || a.length <= 1) return a;

int temp;
for (int i = 1; i < a.length; i+=2) {
if (a[i] < a[i-1]) {
temp = a[i];
a[i] = a[i-1];
a[i-1] = temp;
}

if (i < a.length-1 && a[i] < a[i + 1]) {
temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
}
}

return a;
}``````

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.