Bloomberg LP Interview Question
Software DevelopersCountry: United States
Interview Type: Phone Interview
we can make little correction to above code
int index=shuffle(array);
System.out.println("Index is:-"+index);
for (int i = 0; i <= index; i++) {
System.out.print(array[i] + " ");
}
the condition
if (array[i] == array[j])
is useless, we can simply remove it:
public static int shuffle(int[] array) {
if (array.length == 1 || array.length == 0) {
return 0;
}
int i = 0;
for (int j = 1; j < array.length; j++) {
if (array[i] != array[j]) {
i++;
array[i] = array[j];
}
}
return i;
}
public int deleteDup (int [] A){
int tail = 0 ;
for (int i = 1; i < A.length ; ++i) {
if (A[i] != A[tail]) {
A[++tail] = A[i] ;
}
}
return tail ;
}
int _tmain(int argc, _TCHAR* argv[])
{
int arraySize = 9;
int array[] = { 3, 3, 4, 5, 5, 6, 7, 7, 7 };
int lastUniqueIndex = CreateUniqueArray(array, arraySize);
cout << "Last unique index = " << lastUniqueIndex << endl;
_getch();
return 0;
}
int CreateUniqueArray(int* inputArray, int arraySize)
{
int replacementIndex = 0;
for (int inputArrayIndex = 1; inputArrayIndex < arraySize; inputArrayIndex++)
{
if (inputArray[inputArrayIndex] != inputArray[replacementIndex])
{
// Since each number is a unique index, increment the replacement position
// whenever we find a new one
replacementIndex++;
// Copy unique value into next available position
inputArray[replacementIndex] = inputArray[inputArrayIndex];
}
}
return replacementIndex;
}
If we use vector instead of array, we can just use a built-in algorithm unique() in C++.
public class sorted_to_unique {
private static int[] arr = {3, 3, 4, 5, 5, 6, 7, 7, 7};
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int unique = 1;
for(int i=0; i<arr.length; i++){
if(i<(arr.length-1)){
if(arr[i]<arr[i+1]){
arr[unique]= arr[i+1];
unique++;
}
}
}
for(int k=0; k<unique; k++){
System.out.print(" "+arr[k]);
}
}
}
public class AryInt {
public static void main(String[] args) {
Integer[] arr = new Integer[]{0,0,1,1,2,2,2,2,3,3};
int ele = arr[0];
int j = 0;
for(int i = 1; i < arr.length;)
{
if(arr[i] == ele)
i++;
else
{
arr[j] = ele;
ele = arr[i];
j = j+1;
i=i+1;
}
}
arr[j] = ele;
for( int i = j+1; i< arr.length; i++)
arr[i] = -9999;
for( int i = 0; i< arr.length; i++)
System.out.print(arr[i] + " ");
}
}
My question is, based on the problem description and how the "sample output" array is presented, it seems like the shuffled output sequence is required to maintain the order property. Is this the case, or can the sort property be relaxed for the output array? That makes a big difference in the approach to the solution. Seems like everyone is assuming here that the output sequence does NOT need to maintain the ordering property.
As the array is already sorted this can be done in a single loop.
int main()
{
int arr[]={1,1,1,2,2,3,3,6,6};
int index=1,i=1;
while (i<9)
{
if(arr[index] < arr[i+1])
{
//swap the integers
arr[index] = arr[i+1] + arr[index] ;
arr[i+1]= arr[index] - arr[i+1];
arr[index]=arr[index] - arr[i+1];
i++;
index++;
}
i++;
}
index--; // as the index was initialized to the second element
cout << "Index" << index << endl;
for (i=0;i<index;i++)
cout <<arr[i] << endl;
return 0;
}
int main()
{
// cout << "Hello World" << endl;
int arr[]={1,1,1,2,2,3,3,6,6};
int index=1,i=1;
while (i<9)
{
if(arr[index] < arr[i+1])
{
//swap the integers
arr[index] = arr[i+1] + arr[index] ;
arr[i+1]= arr[index] - arr[i+1];
arr[index]=arr[index] - arr[i+1];
//cout << "aind" << arr[index] << endl;
//cout << "ai" << arr[i] << endl;
i++;
index++;
}
i++;
}
index--;
cout << "Index" << index << endl;
for (i=0;i<index;i++)
cout <<arr[i] << endl;
return 0;
}
Eventually you will be asked to give an algorithm with O(1) space complexity and O(n) run time complexity. Here is one solution
void unique_sorted(vector<int> &arr) {
if (arr.empty()) return;
int i = 1, j = 1;
while (j < arr.size()) {
if (arr[j] != arr[i-1]) {
swap(arr[i++], arr[j++]);
} else {
++j;
}
}
}
public static void main(String[] args) {
Integer[] s= {3,3,4,5,5,6,7,7,7};
TreeSet<Integer> ts= new TreeSet<>();
List<Integer> list= new ArrayList<>();
for (int i = 0; i < s.length; i++)
{
if(!ts.add(s[i]))
{
list.add(s[i]);
}
}
System.out.println("Unique Elements ="+ts +" index="+(ts.size()-1));
}
public static void main(String[] args) {
Integer[] s= {3,3,4,5,5,6,7,7,7};
TreeSet<Integer> ts= new TreeSet<>();
List<Integer> list= new ArrayList<>();
for (int i = 0; i < s.length; i++)
{
if(!ts.add(s[i]))
{
list.add(s[i]);
}
}
System.out.println("Unique Elements ="+ts +" index="+(ts.size()-1));
}
#include <algorithm>
int sorted_to_unique_std(int *data, int sz)
{
return std::unique(data, data+sz) - data - 1;
}
//same algorithm implemented manually
int sorted_to_unique(int *data, int sz)
{
if (!data || sz < 1)
return -1;
int x = data[0], offset, pos;
for (offset = 1; offset<sz && data[offset]>x; ++offset)
x = data[offset];
offset++;
for (pos = offset - 1; offset < sz; ++offset)
{
if (x != data[offset])
{
x = data[offset];
data[pos++] = x;
}
}
return pos - 1;
}
void main()
{
int data[] = {3, 3, 4, 5, 5, 6, 7, 7, 7};
int ret = sorted_to_unique_std(data, 9);
assert(ret == sorted_to_unique(data, 9));
printf("ret: %d [", ret);
for (int i=0; i<=ret; ++i)
printf("%d ", data[i]);
printf("]\n");
}
int shuffle(vector<int>& arr) {
int last_value = arr[0];
int unique_index = 0;
int spot_index = -1;
for (int i = 1; i < arr.size(); i++) {
if (arr[unique_index] == arr[i] && (spot_index < 0 || (spot_index > 0 && arr[unique_index] != arr[spot_index]))) {
spot_index = i;
}
else if (arr[unique_index] != arr[i]) {
if (i - unique_index > 1) {
arr[spot_index] = arr[i];
unique_index = spot_index;
spot_index++;
}
else {
unique_index++;
}
}
}
return unique_index;
}
public class UniqueElements {
public static void main(String[] args) {
int[] elements = { 3, 3, 4, 5, 5, 6, 7, 7, 7 };
System.out.println("====BEFORE removing duplicates ======");
for (int e : elements)
System.out.print(e + " ");
System.out.println("");
System.out.println("index of the last: " + getIndexOfLast(elements));
System.out.println("====AFTER removing duplicates ======");
for (int e : elements)
System.out.print(e + " ");
System.out.println("");
}
private static int getIndexOfLast(int[] elements) {
final int MAX_VALUE = Integer.MAX_VALUE;
final int N = elements.length;
int duplicatesNum = replaceDuplicatesWithValue(elements, MAX_VALUE);
int lastIndex = N - duplicatesNum - 1;
System.out.println("====AFTER replacing duplicates====");
for (int e : elements)
System.out.print(e + " ");
System.out.println("");
if (duplicatesNum == 0)
return lastIndex;
for (int i = 0; i < N; i++) {
if (i > lastIndex)
break;
if (elements[i] != MAX_VALUE)
continue;
int testStartIndex = i + 1;
int testShiftStep = 1;
while (elements[testStartIndex] == MAX_VALUE) {
testStartIndex += 1;
testShiftStep++;
}
shiftToLeft(elements, testStartIndex, testShiftStep, MAX_VALUE);
}
// just to make the values of the array consistent (replace ALL duplicates with a certain value)
for (int i = lastIndex + 1; i < N; i++) elements[i] = MAX_VALUE;
return lastIndex;
}
private static void shiftToLeft(int[] elements, int start, int step, int stopValue) {
for (int i = start; i < elements.length; i++) {
if (elements[i] == stopValue && elements[i+1] == stopValue)
break;
elements[i - step] = elements[i];
}
}
private static int replaceDuplicatesWithValue(int[] elements, int value) {
int duplicatesNum = 0;
for (int i = elements.length - 1; i > 0; i--) {
if (elements[i] == elements[i - 1]) {
elements[i] = value;
duplicatesNum++;
}
}
return duplicatesNum;
}
}
public class UniqueElements {
public static void main(String[] args) {
int[] elements = { 3, 3, 4, 5, 5, 6, 7, 7, 7 };
System.out.println("====BEFORE removing duplicates ======");
for (int e : elements)
System.out.print(e + " ");
System.out.println("");
System.out.println("index of the last: " + getIndexOfLast(elements));
System.out.println("====AFTER removing duplicates ======");
for (int e : elements)
System.out.print(e + " ");
System.out.println("");
}
private static int getIndexOfLast(int[] elements) {
final int MAX_VALUE = Integer.MAX_VALUE;
final int N = elements.length;
int duplicatesNum = replaceDuplicatesWithValue(elements, MAX_VALUE);
int lastIndex = N - duplicatesNum - 1;
System.out.println("====AFTER replacing duplicates====");
for (int e : elements)
System.out.print(e + " ");
System.out.println("");
if (duplicatesNum == 0)
return lastIndex;
for (int i = 0; i < N; i++) {
if (i > lastIndex)
break;
if (elements[i] != MAX_VALUE)
continue;
int testStartIndex = i + 1;
int testShiftStep = 1;
while (elements[testStartIndex] == MAX_VALUE) {
testStartIndex += 1;
testShiftStep++;
}
shiftToLeft(elements, testStartIndex, testShiftStep, MAX_VALUE);
}
// just to make the values of the array consistent (replace ALL duplicates with a certain value)
for (int i = lastIndex + 1; i < N; i++) elements[i] = MAX_VALUE;
return lastIndex;
}
private static void shiftToLeft(int[] elements, int start, int step, int stopValue) {
for (int i = start; i < elements.length; i++) {
if (elements[i] == stopValue && elements[i+1] == stopValue)
break;
elements[i - step] = elements[i];
}
}
private static int replaceDuplicatesWithValue(int[] elements, int value) {
int duplicatesNum = 0;
for (int i = elements.length - 1; i > 0; i--) {
if (elements[i] == elements[i - 1]) {
elements[i] = value;
duplicatesNum++;
}
}
return duplicatesNum;
}
}
public class UniqueElements {
public static void main(String[] args) {
int[] elements = { 3, 3, 4, 5, 5, 6, 7, 7, 7 };
System.out.println("====BEFORE removing duplicates ======");
for (int e : elements)
System.out.print(e + " ");
System.out.println("");
System.out.println("index of the last: " + getIndexOfLast(elements));
System.out.println("====AFTER removing duplicates ======");
for (int e : elements)
System.out.print(e + " ");
System.out.println("");
}
private static int getIndexOfLast(int[] elements) {
final int MAX_VALUE = Integer.MAX_VALUE;
final int N = elements.length;
int duplicatesNum = replaceDuplicatesWithValue(elements, MAX_VALUE);
int lastIndex = N - duplicatesNum - 1;
System.out.println("====AFTER replacing duplicates====");
for (int e : elements)
System.out.print(e + " ");
System.out.println("");
if (duplicatesNum == 0)
return lastIndex;
for (int i = 0; i < N; i++) {
if (i > lastIndex)
break;
if (elements[i] != MAX_VALUE)
continue;
int testStartIndex = i + 1;
int testShiftStep = 1;
while (elements[testStartIndex] == MAX_VALUE) {
testStartIndex += 1;
testShiftStep++;
}
shiftToLeft(elements, testStartIndex, testShiftStep, MAX_VALUE);
}
// just to make the values of the array consistent (replace ALL duplicates with a certain value)
for (int i = lastIndex + 1; i < N; i++) elements[i] = MAX_VALUE;
return lastIndex;
}
private static void shiftToLeft(int[] elements, int start, int step, int stopValue) {
for (int i = start; i < elements.length; i++) {
if (elements[i] == stopValue && elements[i+1] == stopValue)
break;
elements[i - step] = elements[i];
}
}
private static int replaceDuplicatesWithValue(int[] elements, int value) {
int duplicatesNum = 0;
for (int i = elements.length - 1; i > 0; i--) {
if (elements[i] == elements[i - 1]) {
elements[i] = value;
duplicatesNum++;
}
}
return duplicatesNum;
}
}
public class sorted_to_unique {
private static int[] arr = {3, 3, 4, 5, 5, 6, 7, 7, 7};
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int unique = 1;
for(int i=0; i<arr.length; i++){
if(i<(arr.length-1)){
if(arr[i]<arr[i+1]){
arr[unique]= arr[i+1];
unique++;
}
}
}
for(int k=0; k<unique; k++){
System.out.print(" "+arr[k]);
}
}
}
public class sorted_to_unique {
private static int[] arr = {3, 3, 4, 5, 5, 6, 7, 7, 7};
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int unique = 1;
for(int i=0; i<arr.length; i++){
if(i<(arr.length-1)){
if(arr[i]<arr[i+1]){
arr[unique]= arr[i+1];
unique++;
}
}
}
for(int k=0; k<unique; k++){
System.out.print(" "+arr[k]);
}
}
}
void unique_sorted(vector<int> &arr) {
if (arr.empty()) return;
int i = 1, j = 1;
while (j < arr.size()) {
if (arr[j] != arr[i-1]) {
swap(arr[i++], arr[j++]);
} else {
++j;
}
}
}
public static void main(String[] args) {
Integer[] s= {3,3,4,5,5,6,7,7,7};
TreeSet<Integer> ts= new TreeSet<>();
List<Integer> list= new ArrayList<>();
for (int i = 0; i < s.length; i++)
{
if(!ts.add(s[i]))
{
list.add(s[i]);
}
}
System.out.println("Unique Elements ="+ts +" index="+(ts.size()-1));
}
public static void main(String[] args) {
Integer[] s= {3,3,4,5,5,6,7,7,7};
TreeSet<Integer> ts= new TreeSet<>();
List<Integer> list= new ArrayList<>();
for (int i = 0; i < s.length; i++)
{
if(!ts.add(s[i]))
{
list.add(s[i]);
}
}
System.out.println("Unique Elements ="+ts +" index="+(ts.size()-1));
}
- nikamirulmukmeen March 19, 2015