Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
5
of 9 vote

Partition function of quick sort

- Anonymous June 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Normal algorithm won't work if pivot is repeated. One more array is needed

def lowPivotHighSort(array, pivot)
  smaller = []
  equal = []
  bigger = []
  
  return nil if array.index(pivot).nil?
  array.each do |elem|
    smaller << elem if elem < pivot
    equal << elem if elem == pivot
    bigger << elem if elem > pivot
  end
  
  return smaller + equal + bigger  
end

- the | Coder June 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

public static void partition(int[] A, int key )
	{
		int i;
		for(i=0; i<A.length; i++)
		{
			if(A[i]==key)
			{
				int temp = A[0];
				A[0] = A[i];
				A[i]= temp;
				break;
			}
		}
		if(i >= A.length)
		{
			System.out.println("KEY NOT FOUND");
			return;
		}
		
		
		// now A[0] is the pivot

		i =1;
		int j = A.length-1;
		
		while(i<j)
		{
			while(i< A.length-1  && A[i]<=A[0])
				i++;
			
			while(j > 0 && A[j] > A[0])
				j--;
			
			
			int temp = A[j];
			A[j] = A[i];
			A[i] = temp;
		   
		}
		
		if(i!=j)
		{
			int temp = A[j];
			A[j] = A[i];
			A[i] = temp;
		}
		
		int temp = A[j];
		A[j] = A[0];
		A[0] = temp;
		
	}

- Anonymous July 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

quick sort partition function

#include <stdio.h>
int a[] = {22, 2,3,3,0,1,4,5,23,215,215};
 
void swap(int a[], int left, int right)
{
    int temp = a[left];
    a[left] = a[right];
    a[right] = temp;
}
 
int partition(int key)
{
    int left=0;int right=sizeof(a)/sizeof(a[0])-1;
    int key_element;int copy = right--;
    if(key < 1 && key > sizeof(a)/sizeof(a[0]))
        return -1;
    else        
        key_element = a[key-1];
    /*put the key in the end of array*/
    swap(a, key-1, sizeof(a)/sizeof(a[0])-1);
    while(left<right){
        while(a[left]<=key_element && left <= right){
            left++;
        }
        while(a[right]>key_element && right > left){
            right--;
        }
        if(left >= right)
            break;
        swap(a, left, right);
    }
    if(left > right){
        
    }
    else
        swap(a, copy, left);
    return left;
}
 
int main()
{
    int key, i;
    scanf("%d", &key);
    printf("key index now %d\n", partition(key));
    for(i=0;i<sizeof(a)/sizeof(a[0]);i++)
        printf("%4d", a[i]);
}

- aka July 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

quick sort partitioning wont work here.......
a different approach is taken....
1).take two pointers,one to starting(say i) and other to ending(say j)...
2). just iterate through the array(say k), if you find element equal to key just increment(k++)...
3).if you find element <key swap(a[i] ,a[k]),and increment i...
4).if you find element greater than key swap(a[k],a[j]) and decrement j(j--).
but note that in this case you must not increment k,as u have a new element at position k,which u have not traversed..

#include<iostream>
using namespace std;
void swap(int &a,int &b)
{
	int t;
	t=a;
	a=b;
	b=t;
}

void display(int a[],int n)
{
    for(int i=0;i<n;i++)
	{
		cout<<a[i]<<" ";
	}	
	cout<<endl;
}

void arrange(int a[],int n,int key)
{
	int i=0,j=n-1,k=0;
	while(k<j)
	{
//		cout<<"k="<<k<<"  ";
		if(a[k]<key)
		{
			swap(a[k],a[i]);
			i++;
		}
		else if(a[k]>key)
		{
			swap(a[k],a[j]);
			j--;
			k=k-1;
		}
		k++;
//		display(a,n);        uncomment these lines to see what happens at each iteration
	}
}

int main()
{
	int n,*a,key;
	cin>>n;
	a=new int[n];
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	cout<<"Enter the key. \n";
	cin>>key;
	arrange(a,n,key);
	display(a,n);
	return 0;
}

- chaitanya July 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Agreed its similar to quick sort's pivot selection and moving it to right position.

- naveen.maanju July 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
5
of 7 vote

It's a variant of classical Dutch National Flag problem.

- Anonymous July 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

And the solution for it:

public void threeWayPartition(int[] arr, int key) {
	int low = 0;
	int high = arr.length - 1;
	for (int lookAt = 0; lookAt <= high;) {
		if (arr[lookAt] < key) {
			swap(arr, lookAt++, low++);
		} else if (arr[lookAt] > key) {
			swap(arr, lookAt, high--);
		} else {
			++lookAt;
		}
	}
	
	void swap(int[] arr, int p1, int p2) {
		int temp = arr[p1];
		arr[p1] = arr[p2];
		arr[p2] = temp;
	}

}

- Anonymous July 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This problem can be solved by using an approach of binary search:
a. Every time the array is divided into 2 parts and then solve for the left half and the right half as:
b. If the current element is less than the key then enter it into one array and if the current element is greater then enter it into second array. If both are equal then enter into the 2nd array. At last combine the or concatenate the two arrays .Thus the solution O(n). You can test it:

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

void numberPrintLess(int arr[],int arr1[],int arr2[],int low,int high,int *left,int *right,int key)
{
    if(low==high)
        {
            if(key<arr[low])
            {
                arr2[*right]=arr[low];
                *right=*right+1;
            }
            else
            {
                arr1[*left]=arr[low];
                *left=*left+1;
            }
        return;
        }
    if(low+1==high)
    {
        if(key<arr[low]&&key<arr[high])
        {
            arr2[*right]=arr[low];
            *right=*right+1;
            arr2[*right]=arr[high];
            *right=*right+1;
        }
        else if(key>arr[low]&&key>arr[high])
        {
            arr1[*left]=arr[low];
            *left=*left+1;
            arr1[*left]=arr[high];
            *left=*left+1;
        }
        else if(key>arr[low]&&key<arr[high])
        {
            arr1[*left]=arr[low];
            *left=*left+1;
            arr2[*right]=arr[high];
            *right=*right+1;
        }
        else if(key<arr[low]&&key>arr[high])
        {
            arr1[*left]=arr[high];
            *left=*left+1;
            arr2[*right]=arr[low];
            *right=*right+1;
        }
        else if(key==arr[low]&&arr[low]<arr[high])
        {
            arr1[*left]=arr[low];
            *left=*left+1;
            arr2[*right]=arr[high];
            *right=*right+1;
        }
        else if(key==arr[low]&&arr[high]<arr[low])
        {
            arr1[*left]=arr[high];
            *left=*left+1;
            arr2[*right]=arr[low];
            *right=*right+1;
        }
        else if(key==arr[high]&&arr[high]<arr[low])
        {
            arr1[*left]=arr[high];
            *left=*left+1;
            arr2[*right]=arr[low];
            *right=*right+1;
        }
        else if(key==arr[high]&&arr[low]<arr[high])
        {
            arr1[*left]=arr[low];
            *left=*left+1;
            arr2[*right]=arr[high];
            *right=*right+1;
        }
        else if(key==arr[low]&&arr[high]==arr[low])
        {
            arr1[*left]=arr[high];
            *left=*left+1;
            arr1[*left]=arr[low];
            *left=*left+1;
        }
    }
    else
    {
        int mid=low+(high-low)/2;
        if(arr[mid]<key)
        {
            arr1[*left]=arr[mid];
            *left=*left+1;
        }
        else if(arr[mid]>key)
        {
            arr2[*right]=arr[mid];
            *right=*right+1;
        }
        else if(arr[mid]==key)
        {
            arr2[*right]=arr[mid];
            *right=*right+1;
        }
        numberPrintLess(arr,arr1,arr2,low,mid-1,left,right,key);
        numberPrintLess(arr,arr1,arr2,mid+1,high,left,right,key);
    }
    return;
}
void concatenate(int arr1[],int arr2[],int *left,int *right)
{
    int i,arr[25];
    for(i=0;i<*left ;i++)
    {
        arr[i]=arr1[i];
    }
    int j=i;
    for(i=0;i<*right;i++)
    {
        arr[j]=arr2[i];
        j++;
    }
    for(i=0;i<j;i++)
        printf(" %d ",arr[i]);
}
int main()
{
    int arr[]={0,-1,-2,0,3,5};
    int arr1[25],arr2[25];
    int n=sizeof(arr)/sizeof(arr[0]);
    int left=0;
    int right=0;
    numberPrintLess(arr,arr1,arr2,0,n-1,&left,&right,0);
    concatenate(arr1,arr2,&left,&right);
}

- vgeek July 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

#include <stdio.h>

main() {
	int a[] = { 0, -1, -2, 2, 0, 3, 5},n=7,i,j,k,temp;
	i = k = 0;
	j = n-1;
	while(i<j) {
		if(a[i] > k) {
			temp = a[i];
			a[i] = a[j];
			a[j] = temp;
			j--;
		}
		else
			i++;
	}
	printf("Result is : \n");
	for(i=0;i<n;i++)
		printf("%d ",a[i]);
	printf("\n");
}

- Sairam July 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey it is not working correctly for key 0 the output is 0 -1 -2 0 3 5 2 which is completely wrong..!!

- vgeek July 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes it won't work if key is duplicated more than once in a given array

- Sairam Yendluri July 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

its utterly wrong. just disregard my solution

- Sairam Yendluri July 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Its really simple logic.... good. but need to handle duplicates also. its not much tough. any way good logic

- Venkat M July 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] returnArray(int[] arr, int key){
      
         int count = 0;
         int count1 = 0;
         int[] arr1 = new int[arr.length];
      
         for(int ij = 0 ; ij < arr.length; ij++){
            if (arr[ij] < key)
               count++;
            else if (arr[ij] == key)
               count1++;
         }
         
         arr1[(count + count1) - 1] = key;
      	
         int p = 0, j = (count + count1) - 1, k = j + 1;
      	
         for(int i = 0; i < arr.length; i++){
            if (arr[i] < key){
               arr1[p] = arr[i];
               p++;
            }
            else if (arr[i] > key){
               arr1[k] = arr[i];
               k++;
            }
            else if (arr[i] == key){
             if (count1 == 1)
             {
             }
             else{
            	 arr1[j-1] = arr[i];
            	 count1--;
             }
               j--;
            }
            
         }
         return arr1;
      }

- Anonymous July 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class ArrageNumberByKey {
	
	
	public static int[] arrrageNumberByKey(int[] array , int key)
	{
		int length = array.length;
		int[] returnArray = new int[array.length];
		
//		if(length%2 == 0)
//		{
//			
//		}
		int currentKeyIndex = -1;
		
		for (int i=0; i<length ;i++)
		{
			
			if (array[i] < key)
			{
				currentKeyIndex++;
				returnArray[currentKeyIndex] = array[i];

			}

		}
	//	returnArray[currentKeyIndex]=key;
		
		for (int i=0; i <length; i++)
		{
			if (array[i] >= key)
			{
				currentKeyIndex++;
				returnArray[currentKeyIndex] =array[i];
			}
		}
		
		
		return returnArray;
		
	}
	

	
	public static void switchPos(int[] arr, int idx1, int idx2)
	{
		int tmp = arr[idx1];
		arr[idx1] = arr[idx2];
		arr[idx2] = tmp;
	}
	public static void main(String[] arg)
	{
		int[] array = {-1,0,0,-3,3,4,5};
		int[] returnArray = arrrageNumberByKey(array, 0);
		for (int i=0; i< returnArray.length ; i++)
		{
			System.out.println("value "+returnArray[i]);
		}
		
	}
}

- bhashkar July 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;
public class MainGeneric {
	
	public static void main(String[] args) {
		
		int[] a = {2, 3, -1, 0, -2 , 1, 8, 10};
		int[] tobefilled = new int[a.length];
		int right = a.length-1 , left = 0;
		int key = 8;
		for(int i = 0 ; i < a.length ; i++)
			if(a[i] < key){
				tobefilled[left] = a[i];
				left++;
			}else if(a[i] > key){
				tobefilled[right] = a[i];
				right--;
			}
		tobefilled[left] = key;
		System.out.println(Arrays.toString(tobefilled));
	}
}

- Divya Anand July 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

you need add

for(int j = left;j<=right;j++){
tobefilled[j] = key;
}

- Sher10ck July 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int key = 0;
	arr = { 0, -1, -2, 2, 0, 3, 5},
	count =0;
		for(int i = 0 ; i < a.length ; i++)
			if(a[i] < key){
				result[left] = a[i];
				left++;
			}else if(a[i] > key){
				result[right] = a[i];
				right--;
			} else 
                        {
			        Count++;
			}
		for(int i = left ; i < count ; i++)
		result[left] = key;
		System.out.println(Arrays.toString(result));

- Gowri Shankar July 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The solution is very simple assuming everyone is using an extra space scan the input array maintain 2 points left and right. Insert into the left index and increment if you find the element is less than the pivot and insert into the right index and decrement the right index.

- murlikrishna.b July 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A simple way may be:
1. In the first scan - Find all positions of given key. And number of elements less than key. Now you know
- (a) first position of the key in the result array (with key in the middle and lesser ones on left etc..)
- (b) last position of the key in the result array
2. Move all key elements to middle [from indexes (a) to (b)]
3. Now keep two pointers one always pointing to lesser ones and other to greater ones and swapping at every contradiction.

Each step is O(n).

- X July 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void keyArr(int[] arr,int key){
		int lowKeyIndex=-1,highKeyIndex=-1;/* LowKey and HighKey used to indicate minimum and maximum key positions in the array*/
		int maxIndex=arr.length-1/*Length of array to process*/,temp=0;
		for(int index=0;(index<arr.length&&index<=maxIndex);)
		{
			/* If Current element is greater than Key..Just swap last element with current element..
			 * Repeat the iteration for the current element..Reduce Max Element Index by 1..
			 * E.g. [-1,8,0,2,3] Key=0
			 * Current Index is 1..So current element is 8
			 * Output [-1,3,0,2,8] maxIndex=3
			 */
			if(arr[index]>key){ 
				temp=arr[index];
				arr[index]=arr[maxIndex];
				arr[maxIndex]=temp;
				maxIndex--;
			}
			/* If Current element is equal to Key..Note down the key index in lowKeyIndex for first found key..
			 * For the consequent keys, place the keys together and increment the highKeyIndex..
			 * E.g. [-1,-8,0,2,0,3] Key=0
			 * Current Index is 4..So current element is 0..lowKeyIndex=2
			 * Output [-1,-8,0,0,2,3] highKeyIndex=3 */
			else if(arr[index]==key){
				if(lowKeyIndex!=-1){
					highKeyIndex=(highKeyIndex!=-1)?(highKeyIndex+1):(lowKeyIndex+1);
					temp=arr[highKeyIndex];
					arr[highKeyIndex]=arr[index];
					arr[index]=temp;
				}
				else
					lowKeyIndex=index;
				index++;
			}
			else{
				/* If Current element is less than but found after key is found...Place the current element in lowkeyIndex position..
				 * Place the element next to highKeyIndex to current postion and put key in the highKeyIndex+1 position
				 * Increment lowKeyIndex and highKeyIndex
				 * E.g. [-1,-8,0,0,0,2,4,-3] Key=0
				 * Current Index is 7..So current element is -3..lowKeyIndex=2 highKeyIndex=4
				 * Output [-1,-8,-3,0,0,0,2,4] lowKeyIndex=3 highKeyIndex=5 */
				if((index>lowKeyIndex)&&(lowKeyIndex!=-1)){
					temp=arr[index];
					if(maxIndex==-1)maxIndex=lowKeyIndex+1;
					arr[index]=arr[highKeyIndex+1];
					arr[lowKeyIndex]=temp;
					arr[highKeyIndex+1]=key;
					lowKeyIndex+=1;
					highKeyIndex+=1;
					index++;
				}
			}

		}
		for(int i=0;i<arr.length;i++)
			System.out.print(arr[i]+" ");
	}

- SATHISH July 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what about using a stack?

- yogin July 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

quick sort partitioning wont work here.......
a different approach is taken....
1).take two pointers,one to starting(say i) and other to ending(say j)...
2). just iterate through the array(say k), if you find element equal to key just increment(k++)...
3).if you find element <key swap(a[i] ,a[k]),and increment i...
4).if you find element greater than key swap(a[k],a[j]) and decrement j(j--).
but note that in this case you must not increment k,as u have a new element at position k,which u have not traversed..

#include<iostream>
using namespace std;
void swap(int &a,int &b)
{
	int t;
	t=a;
	a=b;
	b=t;
}

void display(int a[],int n)
{
    for(int i=0;i<n;i++)
	{
		cout<<a[i]<<" ";
	}	
	cout<<endl;
}

void arrange(int a[],int n,int key)
{
	int i=0,j=n-1,k=0;
	while(k<j)
	{
//		cout<<"k="<<k<<"  ";
		if(a[k]<key)
		{
			swap(a[k],a[i]);
			i++;
		}
		else if(a[k]>key)
		{
			swap(a[k],a[j]);
			j--;
			k=k-1;
		}
		k++;
//		display(a,n);        uncomment these lines to see what happens at each iteration
	}
}

int main()
{
	int n,*a,key;
	cin>>n;
	a=new int[n];
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	cout<<"Enter the key. \n";
	cin>>key;
	arrange(a,n,key);
	display(a,n);
	return 0;
}

- chaitanya July 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

in worst case it will take O(n) time complexity
and o(1) space complexity...
any suggestions are invited.....

- chaitanya July 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Runs in O(n)

public void arrangeLessThanK (int[] array, int k) {
		for (int i = 0; i < array.length; i++) {
			if (array[i] > k) {
				for (int j = i + 1; j < array.length; j++) {
					if (array[j] <= k) {
						int temp = array[i];
						array[i] = array[j];
						array[j] = temp;
					}
				}
			}
		}

		return array;

}

- Anonymous July 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void Main(string[] args)
{
int[] a = new int[] { 0, 0, -1, -2, 2, 0, 3, 5, 0, 0, 0, 10, -1 };

ArrangeByKey(a, 0);
}

static void ArrangeByKey(int[] a, int key)
{
if (a == null)
return;

int i = 0;
int j = a.Length - 1;

int i0 = -1;

while (i <= j)
{
while (a[i] <= key)
{
if (a[i] == key && i0 == -1)
i0 = i;
else if (a[i] < key && i0 != -1)
{
Swap(a, i0, i);
i0++;
}
i++;
}
while (a[j] > key)
{
j--;
}

if (i <= j)
{
Swap(a, i, j);
}

}
}

static void Swap(int[] a, int i, int j)
{
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}

- Зфмуд July 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void Main(string[] args)
        {
            int[] a = new int[] { 0, 0, -1, -2, 2, 0, 3, 5, 0, 0, 0, 10, -1 };

            ArrangeByKey(a, 0);
        }

        static void ArrangeByKey(int[] a, int key)
        {
            if (a == null)
                return;

            int i = 0;
            int j = a.Length - 1;

            int i0 = -1;

            while (i <= j)
            {
                while (a[i] <= key)
                {
                    if (a[i] == key && i0 == -1)
                        i0 = i;
                    else if (a[i] < key && i0 != -1)
                    {
                        Swap(a, i0, i);
                        i0++;
                    }
                    i++;
                }
                while (a[j] > key)
                {
                    j--;
                }

                if (i <= j)
                {
                    Swap(a, i, j);
                }

            }
        }

        static void Swap(int[] a, int i, int j)
        {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }

- Pavel July 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void Main(string[] args)
        {
            int[] a = new int[] { 0, 0, -1, -2, 2, 0, 3, 5, 0, 0, 0, 10, -1 };

            ArrangeByKey(a, 0);
        }

        static void ArrangeByKey(int[] a, int key)
        {
            if (a == null)
                return;

            int i = 0;
            int j = a.Length - 1;

            int i0 = -1;

            while (i <= j)
            {
                while (a[i] <= key)
                {
                    if (a[i] == key && i0 == -1)
                        i0 = i;
                    else if (a[i] < key && i0 != -1)
                    {
                        Swap(a, i0, i);
                        i0++;
                    }
                    i++;
                }
                while (a[j] > key)
                {
                    j--;
                }

                if (i <= j)
                {
                    Swap(a, i, j);
                }

            }
        }

        static void Swap(int[] a, int i, int j)
        {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }

- Pavel July 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void Main(string[] args)
        {
            int[] a = new int[] { 0, 0, -1, -2, 2, 0, 3, 5, 0, 0, 0, 10, -1 };

            ArrangeByKey(a, 0);
        }

        static void ArrangeByKey(int[] a, int key)
        {
            if (a == null)
                return;

            int i = 0;
            int j = a.Length - 1;

            int i0 = -1;

            while (i <= j)
            {
                while (a[i] <= key)
                {
                    if (a[i] == key && i0 == -1)
                        i0 = i;
                    else if (a[i] < key && i0 != -1)
                    {
                        Swap(a, i0, i);
                        i0++;
                    }
                    i++;
                }
                while (a[j] > key)
                {
                    j--;
                }

                if (i <= j)
                {
                    Swap(a, i, j);
                }

            }
        }

        static void Swap(int[] a, int i, int j)
        {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }

- Pavel July 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i came up this solution it's partially correct someone please help me out to correct the whole solution...

Test case sucess:
test case 1: 0 ,-1,-2,2,0,3,5 n=7 key =0
test case 2: 1 ,7,5,8,3,9,5 n=7 key =5
test case 3: 1 ,6,2,4,3,7 n=6 key =3

Test case failure:
test case 4: 1 ,7,5,8,3,9,2 n=7 key =5
test case 5: 1 ,6,2,4,3,2 n=6 key =3

#include<iostream.h>
#include<conio.h>

void main()
{
clrscr();
int arr[50];
int n,key,x,i=0,j=0;
cout<<"Enter n and key:";
cin>>n>>key;
j=n-1;
cout<<"Enter array:";
do
{
cin>>x;
if(x<key)
{
arr[i]=x;
i++;
}
if(x==key)
{}
else
{
arr[j]=x;
j--;
}
}while(j>=i);
//arr[i]=arr[j]=key;


for(i=0;i<n;i++)
cout<<arr[i] <<" ";
getch();
}

- Anonymous July 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

*errr wrong code
please help me out with this one....

#include<iostream.h>
#include<conio.h>

void main()
{
clrscr();
int arr[50];
int n,key,x,i=0,j=0;
cout<<"Enter n and key:";
cin>>n>>key;
j=n-1;
cout<<"Enter array:";
do
{
cin>>x;
if(x<=key)
{
arr[i]=x;
i++;
}
else
{
arr[j]=x;
j--;
}
}while(j>=i);

for(i=0;i<n;i++)
cout<<arr[i] <<" ";
getch();
}

- abhi July 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Do a linear scan and count how many items < key.
Place the key in the right index in the array (maybe use a separate output array).
Maintain 3 pointers - 1 at the 1st position of the array that's less than the key (unless key is the 1st), another index next position after the key and 3rd index on the key.

Do another linear scan and if element is < place at the position of 1st index & increment that index. Same if element > key, use 2nd index. If element equal, place it before or right after the 3rd index.

This will be O(n).

- aptsensdet June 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How will two linear scans of array with n elements be O(n)?

- iCoder July 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry..Disregard my comment.

- iCoder July 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

One line solution, O(nlogn) though. Still funny.

def easyLowPivotHighSort(array, pivot)
  array.sort {|x,y| x<=>pivot }
end

- the | Coder June 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

sorry for a little messy code

public static void partition(int []arr, int k)
	{
		if(arr == null || arr.length == 0)
			return;

		int left = 0, right = arr.length-1;
		int _kIdxLeft = -1, _kIdxRight = arr.length;
		while(left < right) {

			while(arr[left] <= k) {
				if(arr[left] == k)
					switchPos(arr, left++, ++_kIdxLeft);
				else
					left++;
			}

			while(arr[right] >= k) {
				if(arr[right] == k) {
					switchPos(arr, right--, --_kIdxRight);
				} else {
					right--;
				}
			}
			
			switchPos(arr, left++, right--);
		}

		while(_kIdxLeft >= 0) {
			switchPos(arr, --left, _kIdxLeft--);
		}

		while(_kIdxRight < arr.length) {
			switchPos(arr, ++right, _kIdxRight++);
		}
	}

	public static void switchPos(int[] arr, int idx1, int idx2)
	{
		int tmp = arr[idx1];
		arr[idx1] = arr[idx2];
		arr[idx2] = tmp;
	}

- Anonymous June 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You solution is not working for input sequence 0, -1, -2, 2, 0, 3,0, 5.

- Prashant Kesarwani July 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

three ways sort

- Anonymous July 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include <stdio.h>
#include <stdlib.h>
int a[] = { 0, -1, -2, 2, 0, 3, 5};
int main()
{
int key,i;
printf("enter the key:");
scanf("%d",&key);
arrange(key);
}
void arrange(int key)
{
int n = sizeof(a)/sizeof(a[0]);
int i,j,left = 0,right= n-1;
int temp;
for(i=0;i<n;i++)
{
if(a[i]==key)
{
temp = a[right];
a[right] = a[i];
a[i] = temp;
break;
}
}
if(i>=n)
{
printf("key not found\n");
exit(0);
}
int x = a[right];
i = left - 1;
int k;
for(j=left;j<right-1;j++)
{
if(a[j]<=x)
{
i++;
k = a[i];
a[i] = a[j];
a[j] = k;
}
}
k = a[i+1];
a[i+1] = a[right];
a[right] = k;
printf("after arranging the array is:\n");
for(j=0;j<n;j++)
{
printf("%d\t",a[j]);
}
printf("\n");
}

- anur@g007 July 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

your solution does not work when key is 5.Please check it.

- vgeek July 01, 2013 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More