## Interview Question

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

So do you want to return the elements position of duplicates too?

Comment hidden because of low score. Click to expand.
0
of 0 vote

If we know the size of an array, get the first element of an array (ascending order) and get the last element of an array(descending order), whichever is smaller return that element,

if we need to find position also, once we find the smallest just increment or decrement array index until the smaller returned element value matches.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int  a[] = {4, 5, 8, 9, 11, -1, 0, 3, 2};

int x = a[0];

int l = 1;
int r = sizeof(a) / sizeof(a[0]) - 1;

while (l < r - 1) {
int m = (l + r) / 2;

if (a[m] > x)
l = m;
if (a[m] <= x)
r = m;
}

cout << "min = " << a[r] << endl;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

simple recursive solution

``````# include <iostream>

using namespace std;

int MinElement(int *arr, int low, int high)
{
int mid;

if(low > high)
return -1;

mid = (low + high)/2;

if(arr[mid] - arr[mid-1] > 0)
return arr[mid-1];

return arr[mid] < arr[mid-1] ? MinElement(arr,mid+1, high) : MinElement(arr,low,mid-1);
}

int main()
{
int arr[6] = { 3, 2, 1, 6, 5, 4 };

cout<<MinElement(arr,0,sizeof(arr)/sizeof(arr[0]));

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive Solution, which can find min Element even if the array is roated Either Clockwise or Anticlock wise.

Complexity : O(n log n)

``````# include <iostream>

int MIN(int a, int b)
{
return a>b?b:a;
}

int MIN(int a,int b,int c){
int min = 0;
if(a>b)
min = b;
else
min =a;

if(min >c)
return min;
else
return c;

}

using namespace std;

int MinElement(int *arr, int low, int high)
{
int mid, min, min1;

if(low >= high)
return -1;

mid = (low + high)/2;

if(arr[mid] < arr[mid-1] && arr[mid] < arr[mid+1])
return arr[mid];
if(arr[mid] > arr[mid-1] && arr[mid-1] < arr[mid+1])
return MinElement(arr,low,mid);
else
return MinElement(arr,mid,high);

}

int main()
{
//int arr[6] = { 3, 2, 1, 6, 5, 4 };
int arr[9] = {4, 5, 8, 9, 11, 0, 1, 3, 2};
cout<<MinElement(arr,0,sizeof(arr)/sizeof(arr[0]));

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

find_min(A, l, r) {
mid = (l+r)/2;

int min_index;
int mid_left = mid - 1;
int mid_right = mid + 1;

if (l == r) {
return A[l];
} else if (r-l == 1) {
if (A[r] < A[l])
return A[r]
else
return A[l];
}
while (A[mid_left] == A[m] && mid_left > l) {
mid_left --;
}

while (A[mid_right] == A[m] && mid_right > r) {
mid_right ++;
}

if (A[mid_left] >= A[mid] && A[mid] <= A[mid_right])
return A[mid]
else
if (A[mid_left] < A[mid_right])
find_min(A, l , mid_left);
else
find_min(A, mid_right, r);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public void do_findMinRotDupAry() {
int a[] = {5, 6, 8, 9, 11, -1, 0, 2, 3};
// int a[] = { 3, 1, 2, 2, 2};
// int a[] = { 3, 2, 0, 6, 5, 4, 4};
// int a[] = { -1, 0, 1, 2, 3,4, 4};
int x = a[0];
for(int i=1; i<a.length; i++) {
x = Math.min(x,a[i]);
}
System.out.println(" a[] " + Arrays.toString(a) + " min dup cir ary = " + x);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class SortedButRotted {
//sorted but rotted means, sorted elements but rotted by one or two places
public static void main(String args[]){
int arr[]={ 4, 4, 5, 5, 5, 6, 1, 1, 2, 2, 3, 3, 3};
int a=0;

System.out.println(4>=5);
for(a=0; a<arr.length-1;a++){
if(arr[a]<=arr[a+1]){
continue;
}else{
break;
}
}
if(a !=(arr.length-1))
System.out.println("pivot--"+arr[a+1]);
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

int arr [] = {4, 5, 6, -1, -1, 2, 3};
int l = 0;
int r = n-1; //n is size of array
while(l<=r)
{
if(arr[i] > arr[r])
{
l++; r--;
}
else
return arr[l];
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class sortedRotated {
public static void main(String args[]){
int[] arr = {4, 4, 5, 5, 5, 6, 1, 1, 2, 2, 3, 3, 3};
minSortedRotated(arr);

}
public static void minSortedRotated(int[] arr){
int min=0;
int i=0;
//if the array is ascending
while(arr[i]<=arr[i+1] && i != arr.length-2){
min = arr[i];
i++;
}
//if the array is descending
while(arr[i]>=arr[i+1] && i != arr.length-2){
min = arr[i+1];
i++;
}
//Unrotated
if(min == 0){
System.out.println("Array is not rotated");
}
else{
System.out.println("Min is " + min);
}
}
}``````

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

If array sorted descending order like 6,5,4,3,2,1 rotated like 3 2 1 6 5 4 then it fails.

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

It stucks in the second loop for {1,2,3,4,5}

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

May I know why do we need Math.min statement in the end? Is there a case where arr[r] is lesser than the minimum found in the first loop or vice versa.

Comment hidden because of low score. Click to expand.
0

{ 5, 1, 2, 3, 4, 5} don't work

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.

### 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.