Google Interview Question Software Engineer / Developers
Team: Chrome Team
Country: United States
Interview Type: Phone Interview
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.
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.
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
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.
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.
In order traversal of a Max-heap
Heap Creation From an array is O(n)
In Order Traversal is O(n)
How is heap creating O(n).
Isn't heapify and O(logn) operation. We do it for every insert.
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.
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]?
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?
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.
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).
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)
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).
No need to sort... thinking arr[1] as min, and using findMin technique O(n)
int[] arr = {11,4,5,2,3};
int min = arr[1], index = 0, nextIndex = 3;
int[] newArr = new int[arr.length];
newArr[1] = min;
if(arr[0] < min){
newArr[index] = arr[0];
index += 2;
}else{
newArr[newArr.length - 1] = arr[0];
}
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];
}
}
No need to sort, using findMinimum technique O(n)
int[] arr = {1,4,5,2,3};
int min = arr[1], index = 0, nextIndex = 3;
int[] newArr = new int[arr.length];
newArr[1] = min;
if(arr[0] < min){
newArr[index] = arr[0];
index += 2;
}else{
newArr[newArr.length - 1] = arr[0];
}
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];
}
}
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
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;
}
#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[0]);
int i;
qsort(A, n, sizeof(A[0]), compare);
pattern(A,n);
for(i = 0; i < n; i++)
printf("%d\t", A[i]);
return 0;
}
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;
}
}
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];
}
}
}
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];
}
}
}
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];
}
}
}
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;
}
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));
}
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;
}
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 >
- tjcbs2 March 17, 2015for (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]); }