Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
The solution is good but the last condition should decrease p2 also;
if(p1==0 and p2!=0){
p1++;
p2--;
}
Correct me if I am wrong
search getIndex() and delete from bst ----o(logn)
delete from specific location array/list o(n)
insertion at the end 0(1)
Void Arragne(int arr[])
{
int j = -1;
int i = 0;
int len = strlen(arr);
while(i < len)
{
if(arr[i] ==0)
swap(arr[++j],arr[i])
i++;
}
}
#include<stdio.h>
#include<stdlib.h>
void push(int* array, int size){
int s = 0;
int l = 0;
int temp = 0;
s = 0;
l = size - 1;
while(s < l){
if(*(array +s) == 0){
s += 1;
continue;
}else if(*(array +l)!= 0){
l -= 1;
continue;
}else{
temp = *(array +s);
*(array+s) = *(array+l);
*(array+l) = temp;
s += 1;
l -= 1;
}
}
}
int main(){
int* array = NULL;
int size = 0, i =0;
printf("\n Size of array is \n");
scanf("%d", &size);
array = (int*) malloc(size*sizeof(int));
for(i = 0; i<size;i++){
scanf("%d", (array+i));
}
printf("\n Input is : ");
for(i = 0; i <size; i++){
printf(" %d ", *(array+i));
}
printf("\n");
push(array, size);
printf("\n Output is : ");
for(i = 0;i<size;i++){
printf(" %d ", *(array+i));
}
printf("\n");
return 0;
}
public class Amazon1 {
public static void main(String []args)
{
int []array = {3,0,4,0,5,0,1,0,2,0,0,0,0,3,0,5,0,6,0,9,8,7,0,0,0,6,0,5,0,23,0,65};
new Amazon1().pushNonZeroToLast(array);
}
public void swap(int []a,int x,int y)
{
int temp = a[x];
a[x] = a[y];
a[y] = temp;
}
public void displayArray(int []a)
{
for(int i =0;i < a.length;i++)
{
System.out.print(a[i] + " ");
}
System.out.print("\n");
}
public void pushNonZeroToLast(int []array)
{
int left,right;
displayArray(array);
for(left = 0,right = array.length - 1;left < right-1;left++,right--)
{
for(;array[left] == 0;left++); // setting left pointer to first non zero element
for(;array[right] != 0;right--);//setting right pointer to first zero element
swap(array,left,right);
displayArray(array);
}
}
}
#include <iostream>
#include <vector>
using namespace std;
int solve(vector<int> a)
{ int i,front=0,back=a.size()-1;
for(;front<back;front++)
for(;a[front] && front^back;back--)
swap(a[front],a[back]);
for(i=0;i<a.size();i++) printf("%d ",a[i]);
}
main()
{ int b[]={3,0,4,0,5,0,1,0,2,0,0,0,0,3,0,5,0,6,0,9,8,7,0,0,0,6,0,5,0,23,0,65};
vector<int> a(b,b+sizeof(b)/sizeof(int));
solve(a);
system("pause");
return 0;
}
Here is my solution in O(n) time
class ArrayQuestions
{
static void Main(string[] args)
{
ArrayQuestions aq = new ArrayQuestions();
int[] input = new int[] { 3, 0, 4, 0, 5, 0, 1, 0, 2, 0, 0, 0, 0, 3, 0, 5, 0, 6, 0, 9, 8, 7, 0, 0, 0, 6, 0, 5, 0, 23, 0, 65 };
int[] input1 = new int[] { 3, 0, 4, 0, 5, 0, 1, 0, 2, 0, 0, 0, 0, 3, 0, 5, 0, 6, 0, 9, 8, 7, 0, 0, 0, 6, 0, 5, 0, 23, 60, 0 };
int[] input2 = new int[] { 0, 3, 4, 0, 5, 0, 1, 0, 2, 0, 0, 0, 0, 3, 0, 5, 0, 6, 0, 9, 8, 7, 0, 0, 0, 6, 0, 5, 0, 23, 60, 0 };
int[] input3 = new int[] { 180, 3, 4, 170, 5, 160, 1, 150, 2, 140, 130, 120, 110, 3, 90, 5, 80, 6, 70, 9, 8, 7, 60, 50, 40, 6, 30, 5, 20, 23, 60, 10 };
int[] output = aq.SeperateElements(input);
int[] output1 = aq.SeperateElements(input1);
int[] output2 = aq.SeperateElements(input2);
int[] output3 = aq.SeperateElements(input3);
Console.WriteLine("Length of input = " + input.Length + " Length of output = " + output.Length);
foreach (var item in output)
{
Console.Write(item);
Console.Write(" ");
}
Console.WriteLine();
Console.WriteLine("Length of input = " + input1.Length + " Length of output = " + output1.Length);
foreach (var item in output1)
{
Console.Write(item);
Console.Write(" ");
}
Console.WriteLine();
Console.WriteLine("Length of input = " + input2.Length + " Length of output = " + output2.Length);
foreach (var item in output2)
{
Console.Write(item);
Console.Write(" ");
}
Console.WriteLine();
Console.WriteLine("Length of input = " + input3.Length + " Length of output = " + output3.Length);
foreach (var item in output3)
{
Console.Write(item);
Console.Write(" ");
}
Console.Read();
}
private int FindFirstZeroIndex(int[] array, int firstZeroIndex, int initialIndex)
{
while (firstZeroIndex > initialIndex && array[firstZeroIndex] == 0)
{
firstZeroIndex--;
}
return firstZeroIndex;
}
public int[] SeperateElements(int[] array)
{
/*
* n size of array Push all the non-zero's of a given array to the end of the array. In place
*/
if (array != null)
{
int firstZeroIndex = this.FindFirstZeroIndex(array, array.Length - 1, 0);
for (int i = 0; i < firstZeroIndex; i++)
{
if (array[i] == 0)
{
// Swap the elements
array[i] = array[firstZeroIndex];
array[firstZeroIndex] = 0;
// Traverse backward and find the index of first non zero element from back.
firstZeroIndex = this.FindFirstZeroIndex(array, firstZeroIndex, i);
}
}
}
return array;
}
}
public void moveNonZeros(int []array)
{
for(int k = 0; k < array.length; k++){
if(array[k] == 0){
array[k] = array[++j];
array[j] = 0;
}
}
for(int k = 0; k < array.length; k++){
System.out.print(array[k] + " ");
}
}
void pushNonZeroToLast() {
int[] array = { 3, 0, 4, 0, 5, 0, 1, 0, 2, 0, 0, 0, 0, 3, 0, 5, 0, 6, 0, 9, 8, 7, 0, 0, 0, 6, 0, 5, 0, 23, 0,
65 };
int i = 0, j = array.length - 1;
while (j > 0 && i < j) {
if (array[j] == 0) {
while (i < j) {
if (array[i] != 0) {
swap(i, j, array);
break;
}
i++;
}
}
j--;
}
}
maintain two pointers, one pointing to the beg of array(p1) and the other to the end(p2).
- alex January 11, 2013If both p1 and p2 are non zero
p2--;
if *p2==0 and p1!=0
swap values in p1 and p2, p2--, p1++
if both p1 and p2 are zero
p1++
if p1==0 and p2!=0
p1++