unknown Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
// ZoomBA :: reverse consecutive +ve no within -ve :: better style
def reverse_between_indices( arr , i, j){
len = ( j - i + 1 )/2
lfold( [i : i + len ] ) ->{
l = arr[$.o]
arr[$.o] = arr[ j - $.i ]
arr[ j - $.i ] = l
}
}
def reverse_pos( arr ){
end = 0
while ( true ){
previous = index ( [end:#|arr|] ) :: { arr[$.o] >= 0 }
break ( previous < 0 )
previous += end
end = index ( [previous:#|arr|] ) :: { arr[$.o] < 0 }
break ( end < 0 )
end += previous
reverse_between_indices ( arr, previous, end - 1 )
}
if ( previous >= 0 ){
reverse_between_indices ( arr, previous, #|arr| - 1 )
}
}
arr = [4, 3, 8, 9, -2, 6, 10, 13, -1, 2, 3]
println( arr )
reverse_pos( arr )
println( arr )
// Given an array reverse the consecutive positive numbers between -ve numbers.
public class ReversePositiveNumbers {
public static int[] reverse(int[] arr) {
if (arr == null || arr.length == 0) {
return arr;
}
int i = 0, j = 1;
while (j < arr.length) {
if (arr[j] <= 0) {
if (i != j - 1) {
if(arr[i]<=0) {
i++;
}
reverse(arr, i, j-1);
}
/*
* Print it or whatever because the array has already been
* reversed.
*/
i = ++j;
}
j++;
}
return arr;
}
private static void reverse(int[] arr, int i, int j) {
while (j > i) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
public static void main(String[] args) {
int[] arr = new int[] { 4, 3, 8, 9, -2, 6, 10, 13, 4, 5, -9, 0, -2 };
ReversePositiveNumbers.reverse(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
// Given an array reverse the consecutive positive numbers between -ve numbers.
public class ReversePositiveNumbers {
public static int[] reverse(int[] arr) {
if (arr == null || arr.length == 0) {
return arr;
}
int i = 0, j = 1;
while (j < arr.length) {
if (arr[j] <= 0) {
if (i != j - 1) {
if(arr[i]<=0) {
i++;
}
reverse(arr, i, j-1);
}
/*
* Print it or whatever because the array has already been
* reversed.
*/
i = ++j;
}
j++;
}
return arr;
}
private static void reverse(int[] arr, int i, int j) {
while (j > i) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
public static void main(String[] args) {
int[] arr = new int[] { 4, 3, 8, 9, -2, 6, 10, 13, 4, 5, -9, 0, -2 };
ReversePositiveNumbers.reverse(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
package test.org.positivenumbers;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class PositiveOrderChange {
private List<Integer> finalIntegerList;
public PositiveOrderChange() {
finalIntegerList = new ArrayList<Integer>();
}
public void execute(List<Integer> integers) {
System.out.println("Received values: "+integers.toString());
List<Integer> localResults = new ArrayList<Integer>();
Iterator<Integer> iterator = integers.iterator();
Integer current = null;
while (iterator.hasNext()) {
current = iterator.next();
if(isPositive(current)) {
localResults.add(current);
} else {
changeOrder(localResults, current);
}
}
changeOrder(localResults, current);
}
private boolean isPositive(Integer integer) {
return integer>=0;
}
public void printNewOrder() {
System.out.println("New order: "+finalIntegerList.toString());
}
private void changeOrder(List<Integer> positiveValues, Integer negativeValue) {
int len = (positiveValues.size() -1);
for(int i = len; i>=0 ; i--) {
finalIntegerList.add(positiveValues.get(i));
}
if(!isPositive(negativeValue)) {
finalIntegerList.add(negativeValue);
}
positiveValues.clear();
}
}
c++, stack, O(n log n)
void reversePositive(vector<int>& arr) {
vector<int>::iterator it;
stack<int> stck;
int head;
head = 0;
it = arr.begin();
while (it != arr.end()) {
if (*it <= 0) {
while (!stck.empty()) {
arr[head] = stck.top();
head++;
stck.pop();
}
head++;
} else {
stck.push(*it);
}
it++;
}
while (!stck.empty()) {
arr[head] = stck.top();
head++;
stck.pop();
}
}
#include <iostream>
using namespace std;
int main()
{
int arr[] = {4, 3, 8, 9, -2, 6, 10, 13, -1, 2, 3};
int size = sizeof(arr) / sizeof(int);
int i = 0;
int j;
do {
// find start
i = j;
while (i < size && arr[i] < 0)
++i;
// find end
j = i + 1;
while (j < size && arr[j] > 0)
++j;
// sort
bool repeat;
do {
repeat = false;
for (int k = i; k < j - 1; ++k)
if (arr[k] < arr[k + 1]) {
int tmp = arr[k];
arr[k] = arr[k + 1];
arr[k + 1] = tmp;
repeat = true;
}
} while (repeat);
} while (j < size);
for (int i = 0; i != size; ++i)
cout << arr[i] << " ";
cout << endl;
}
#include <iostream>
using namespace std;
int main()
{
int arr[] = {4, 3, 8, 9, -2, 6, 10, 13, -1, 2, 3};
int size = sizeof(arr) / sizeof(int);
int i = 0;
int j;
do {
// find start
i = j;
while (i < size && arr[i] < 0)
++i;
// find end
j = i + 1;
while (j < size && arr[j] > 0)
++j;
// sort
bool repeat;
do {
repeat = false;
for (int k = i; k < j - 1; ++k)
if (arr[k] < arr[k + 1]) {
int tmp = arr[k];
arr[k] = arr[k + 1];
arr[k + 1] = tmp;
repeat = true;
}
} while (repeat);
} while (j < size);
for (int i = 0; i != size; ++i)
cout << arr[i] << " ";
cout << endl;
}
{{
public static void main(String[] args) {
// TODO code application logic here
int[] mainArray = { 4, 3, 8, 9, -2, 6, 10, 13, 4, 5, -9, 0, -2 };
final ArrayList<Integer> localArray = new ArrayList<>();
final ArrayList<Integer> finalArray = new ArrayList<>();
for (int i = 0; i < mainArray.length; i++) {
if (mainArray[i] >= 0) {
localArray.add(mainArray[i]);
} else {
Collections.sort(localArray);
Collections.reverse(localArray);
finalArray.addAll(localArray);
finalArray.add(mainArray[i]);
localArray.clear();
}
}
System.out.println("INIT = " + Arrays.toString(mainArray));
System.out.println("FINAL = " + finalArray);
}
}}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.Collections;
//C#
namespace ConsoleApplication16
{
class Program
{
static void Main(string[] args)
{
int Index = 0;
int IndexBegin = 0;
int[] InputData = new int[] { -1,100, 200, -2, 1, 2, 3, 4, -6, -5, 10, 20, -2,0 };
ArrayList OutputData = new ArrayList();
foreach (int item in InputData)
{
if (item < 0)
{
for (int i =Index-1; i>=IndexBegin;i--)
{
OutputData.Add(InputData[i]);
}
OutputData.Add(InputData[Index]);
IndexBegin = Index+1;
}
Index++;
}
if(IndexBegin != Index + 1)
for (int i = Index - 1; i >= IndexBegin; i--)
{
OutputData.Add(InputData[i]);
}
foreach (int item in OutputData) Console.Write(item);
Console.ReadKey();
}
}
}
c# implementation.
Time complexity: O(n).
Running time of worst case (when all integers are positive) - 2*n,
Running time of best case (when all integers are negative) - n.
Running time average 1,5*n.
using System;
using System.Collections.Generic;
namespace ReversePositiveIntegers {
static class Program {
static private void ProcessArray( int[] arr ) {
int i = 0;
int startPos = -1;
Stack<int> stack = new Stack<int>();
while ( true ) {
if ( arr[ i ] < 0 ) {
CheckAndReverse( arr, stack, ref startPos, i );
} else {
stack.Push( arr[ i ] );
}
i++;
try {
int nextIndex = arr[ i ];
}
catch (IndexOutOfRangeException) {
CheckAndReverse( arr, stack, ref startPos, i );
break;
}
}
}
static private void CheckAndReverse( int[] arr, Stack<int> stack, ref int startPos, int endPos ) {
var length = endPos - startPos - 1;
if ( length > 1 ) {
int t = 0;
while ( stack.Count > 0 ) {
arr[ startPos + 1 + t ] = stack.Pop();
t++;
}
}
stack.Clear();
startPos = endPos;
}
static void Main(string[] args) {
int[] arr = new[] {-5, 100, 200, -2, 0, 1, 2, 3, 4, -6, -5, 10, 20, -2, 30, 40 };
ProcessArray( arr );
for ( int j = 0; j < arr.Length; j++ ) {
Console.Write($"{arr[j]} ");
}
Console.ReadLine();
}
}
}
public class SortingArray {
public static void main(String[] args) {
int [] a = { 6, 8, 7, 4, -2, 78, 3, 9, -1, 66, 100, 77, -3 };
int start = -1;
for (int index = start+1; index < a.length; index++) {
if(a[index] < 0){
for (int i = start+1; i < index; i++) {
for (int j = i+1; j < index; j++) {
int temp = 0;
if(a[i] < a[j]){
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
start = index;
}
}
System.out.println(Arrays.toString(a));
}
}
public class SortingArray {
public static void main(String[] args) {
int [] a = { 6, 8, 7, 4, -2, 78, 3, 9, -1, 66, 100, 77, -3 };
int start = -1;
for (int index = start+1; index < a.length; index++) {
if(a[index] < 0){
for (int i = start+1; i < index; i++) {
for (int j = i+1; j < index; j++) {
int temp = 0;
if(a[i] < a[j]){
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
start = index;
}
}
System.out.println(Arrays.toString(a));
}
}
private void positiveOrderReverse(int[] pattern)
{
Stack<Integer> stack = new Stack<Integer>();
int[] resultPattern = new int[pattern.length];
for(int j = 0 ; j < pattern.length; j ++)
{
int integer = pattern[j];
if( integer > 0)
{
stack.push(integer);
}
else
{
int size = stack.size();
for(int i = 0 ; i< size; i++)
{
int stackValue = stack.pop();
resultPattern[j-size + i] = stackValue;
}
resultPattern[j] = integer;
}
}
System.out.println(Arrays.toString(resultPattern));
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
namespace ConsoleApplication44
{
class Program
{
static void Main(string[] args)
{
string[] input_data = File.ReadAllText(@"G:\input.txt").Split(new char[] { ' ','\r'},StringSplitOptions.RemoveEmptyEntries);
Stack<int> stack = new Stack<int>();
int begin = 0;
int end = 0;
for (int i = 0; i < input_data.Length; i++)
{
int item = int.Parse(input_data[i]);
if (item < 0 )
{
end = i-1;
Reverse(input_data, begin, end, stack);
begin = i + 1;
}
else
{
stack.Push(item);
}
if (i == input_data.Length - 1 && stack.Count>0)
{
end = i;
Reverse(input_data,begin,end,stack);
}
}
for (int i = 0; i < input_data.Length; i++)
{
Console.Write(input_data[i]);
}
}
static void Reverse(string[] arr, int begin, int end, Stack<int> stack)
{
for (int i = begin; i<= end;i++)
{
arr[i] = stack.Pop().ToString();
}
stack.Clear();
}
}
}
public class ReversePositiveInteger {
public static void main(String[] args) {
int input[]={4,3,8,9,-2,6,10,13,-1,2,3,-1,-1,3,4};
reversePositiveInteger(input);
for(int i=0;i<input.length;i++){
System.out.print(","+input[i]);
}
}
private static int[] reversePositiveInteger(int[] input) {
int j=0,k=0;
for(int i=0;i<input.length;i++){
if(input[i]<0 ){
j=i-1;
swap(k,j,input);
k=i+1;
}
if(i==input.length-1 && (input[i]>0)){
j=i;
swap(k,j,input);
}
}
return input;
}
private static void swap(int k, int j,int [] input) {
while(k<j){
int temp=input[k];
input[k]=input[j];
input[j]=temp;
k++;
j--;
}
}
}
- NoOne October 08, 2016