CareerCup

import java.util.ArrayList;

public class Test {

	public static void main(String[] args) {
		int in[]={1,2,2,2,2,2,3,4,5,6,7,8,9,10};
		int key=2;
		Test test=new Test();
		ArrayList<Integer> indexList=test.getIndexes(in,key);
		System.out.println(indexList);
	}

	private  ArrayList<Integer> getIndexes(int[] in, int key) {
		ArrayList<Integer> indexList=new ArrayList<Integer>();
		for(int i=0;i<in.length;i++){
			if(in[i]==key)
				indexList.add(i);
		}
		return indexList;
	}
}

function geyIndexes(arr, key) {
    var indexes = [];
    
    if (!key || !arr) {
        return [];
    }

    for (var i = 0; i < arr.length; i++) {
        if (arr[i] === key) {
            indexes.push(i);
        }
    }

    return indexes;

}

#print (search_careercup([3,4,5,5,6,6,7],6))
      def search_careercup(inp,key):
            indexes = [i for i in range(0,len(inp)-1) if (inp[i] == key)]
	return indexes

Binary search to find the key, then look to the left and to the right of it until the number changes

#include <cstdio>
#include <algorithm>

int keys[] = {1,2,2,2,2,2,3,4,5,6,7,8,9,10};

int main () {
    unsigned length = sizeof(keys)/sizeof(keys[0]);
    auto lower = std::lower_bound(&keys[0], &keys[length], 2);
    auto upper = std::upper_bound(&keys[0], &keys[length], 2);
    unsigned index = lower - &keys[0];
    while (lower++ < upper)
        printf("%u ", index++);
    printf("\n");
    return 0;
}

package algo;

/**
 * Given a sorted integer array. Find the first occurance of given number
 */
public class FirstIndex {

    
    public static void main(String... args) {
        int[] input = {1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,8,8,8,8,9};
        int n = 8;
        
        /*
        Expected output:
        First index of 8 is : 19
        First index of 2 is : 1
         */
        
        System.out.println("First index of " + n + " is : " + getFirstIndex(input, n, 0, input.length - 1));
        
        n = 2;
        System.out.println("First index of " + n + " is : " + getFirstIndex(input, n, 0, input.length - 1));

    }

    private static int getFirstIndex(int[] input, int n, int leftIndex, int rightIndex) {

        if (leftIndex > rightIndex) {
            return Integer.MAX_VALUE;
        }

        int mid = (rightIndex - leftIndex) / 2 + leftIndex;

        if (input[mid] > n) {

            return getFirstIndex(input, n, leftIndex, mid - 1);

        }
        if (input[mid] < n) {

            return getFirstIndex(input, n, mid + 1, rightIndex);

        }
        // we are left with equality case

        return mid < getFirstIndex(input, n, leftIndex, mid - 1) ? mid : getFirstIndex(input, n, leftIndex, mid - 1);

    }
}

package algo;

/**
 * <p/>
 * Given a sorted integer array. Find the first occurance of given number
 */
public class FirstIndex {

    
    public static void main(String... args) {
        int[] input = {1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,8,8,8,8,9};
        int n = 8;
        
        /*
        Expected output:
        First index of 8 is : 19
        First index of 2 is : 1
         */
        
        System.out.println("First index of " + n + " is : " + getFirstIndex(input, n, 0, input.length - 1));
        
        n = 2;
        System.out.println("First index of " + n + " is : " + getFirstIndex(input, n, 0, input.length - 1));

    }

    private static int getFirstIndex(int[] input, int n, int leftIndex, int rightIndex) {

        if (leftIndex > rightIndex) {
            return Integer.MAX_VALUE;
        }

        int mid = (rightIndex - leftIndex) / 2 + leftIndex;

        if (input[mid] > n) {

            return getFirstIndex(input, n, leftIndex, mid - 1);

        }
        if (input[mid] < n) {

            return getFirstIndex(input, n, mid + 1, rightIndex);

        }
        // we are left with equality case

        return mid < getFirstIndex(input, n, leftIndex, mid - 1) ? mid : getFirstIndex(input, n, leftIndex, mid - 1);

    }
}

public class Findingkeyindex {
	
	public static void main(String[] args) {
		int [] values={1,2,2,2,2,2,3,4,5,6,7,8,9,10};
		int key=2;
		
		for (int i = 0; i < values.length; i++) {
			if(values[i]==key){
				System.out.println(i);
			}
		}
	}

}

///{public class Findingkeyindex {

public static void main(String[] args) {
int [] values={1,2,2,2,2,2,3,4,5,6,7,8,9,10};
int key=2;

for (int i = 0; i < values.length; i++) {
if(values[i]==key){
System.out.println(i);
}
}
}

}///

Use binary search, but instead of just comparing mid with the key(key is 2 here) add another condition.
if(ary[mid] == key && (mid == 0 || ary[mid - 1] != key))
return mid;

Use binary search, but modify the search condition to this
key is 2 here,
if(ary[mid] == key && (mid == 0 || ary[mid -1] != key))
return mid;

Ruby solution - O(n)

def index_at_key key, arr
  puts 'key is: ' + key.to_s
  i, j, key_arr = 0, 0, []
  while i <= arr.size - 1
    if arr[i] == key
      key_arr[j] = i
      j += 1
    end
    i += 1
  end
  key_arr.join(', ')
end

class GetKeyIndexFromArraySolution {

    /** Will only return one index where given key is present else -1
     * @return index where key is present otherwise -1 */
    public static int getAnyIndex(int[] arr, int key) {
        if (arr.length == 0) {
            return -1;
        }
        int low = 0;
        int high = arr.length;
        while (low < high) {
            int mid = (low + high) / 2;
            if (arr[mid] == key) {
                return mid;
            } else if (key < arr[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return -1;
    }

    /** This method will return all the index where given key is present
     * @param arr
     * @param key
     * @return */
    public static ArrayList<Integer> getAllIndex(int[] arr, int key) {
        if (arr.length == 0) {
            return null;
        }

        int start = 0;
        int end = arr.length - 1;
        boolean fStart = false;
        boolean fEnd = false;

        while (start <= end) {
            if (!fStart && arr[start] == key) {
                fStart = true;
            }if (!fStart && arr[start] != key) {
                start++;
            }

            if (!fEnd && arr[end] == key) {
                fEnd = true;
            } else if (!fEnd && arr[end] != key) {
                end--;
            }

            if (fStart && fEnd) {
                break;
            }
        }

        ArrayList<Integer> out = new ArrayList<Integer>();
        for (int i = start; i <= end; i++) {
            System.out.println("IND: " + i);
            out.add(i);
        }
        return out;
    }
}

#include<iostream>
using namespace std;

int main()
{
   int key = 2;
   int in[] = { 1, 2, 2, 2, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
   int len = sizeof(in) / sizeof(in[0]);
   cout << "Indices with the key 2 are: ";
   for (int i = 0; i < len; ++i)
   {
      if (in[i] > key)
         return 0;
      else
         if (in[i] == 2)
         {
            cout << i + 1<< " ";
         }
   }
   return 0;
}

l = [1,2,2,2,2,2,3,4,5,6,7,8,9]

print([i for i,x in enumerate(l) if x == 2])

#include<iostream>
using namespace std;

int sorted(int arr[],int l,int h,int key){
	cout<<l<<" "<<h<<endl;
	if(arr[l]==key){
		return l;
	}
	if(l==h){
		if(arr[l]==key){
			return l;
		}else{
			return -1;
		}
	}else{
		if(arr[l]<key && arr[h]>=key){
			int mid = (l+h)/2;
			if(arr[mid]<key){
				sorted(arr,mid+1,h,key);
			}else{
				sorted(arr,l,mid,key);
			}
		}else{
			return -1;
		}
	}
}
int main()
{
	//int arr[]={1,1,1,2,2,2,2,2,3,3,3,3,3,4,4,4,4,4,5,6,7,7,7,7,8,9,10,10};
	int arr[]={1,2,3,5,100};
	int x;
	cin>>x;
	while(x!=-1){
	
		cout<< sorted(arr,0,sizeof(arr)/sizeof(int)-1,x);
		cin>>x;
	}
}

/**
* Being a QA/QE - Conditions to be noted
* 1.Array length should be greater than 0.
* 2.If first element is equal to key then no need to run the loop
* 3.if K > last element of array , that means element is not in the array
* 4.Loop -
* 4.1. low , high and mid are indexes not elements , but compare key with array[mid]
* 5.when exit from the loop low will be equal to high , ie. means
* 5.1 we have found the element / not found
* 5.2 Hence check if array[low] || array[high] == key
* 5.3 else return -1
* @param arr
* @param k
* @return
*/
public int getFirstIndex(int arr[] , int k){
if(arr.length == 0 ){
//throw new RuntimeErrorException(null,"array is null");
return -1;
}
if(arr[0] == k){
return 1;
}
else if (k > arr[arr.length -1]){
return -1;
}
int result = -1;
int low = 0;
int high = arr.length - 1;// 2
while(low < high){
int mid = (low + high - low)/2;//(2/2)
if(k< arr[mid]){
high = mid -1;
}
else if(k > arr[mid]){
low = mid + 1;
}
else{
low = mid;
high = low;
break;
}
}
if(arr[low] == k){
result = low +1;
int j = low -1;
while((j > -1) && (arr[low]== arr[j]) ){
j--;
result = j +1;
}
System.out.println(result);
}
return result;
}
}

/**
* Being a QA/QE - Conditions to be noted
* 1.Array length should be greater than 0.
* 2.If first element is equal to key then no need to run the loop
* 3.if K > last element of array , that means element is not in the array
* 4.Loop -
* 4.1. low , high and mid are indexes not elements , but compare key with
array[mid]
* 5.when exit from the loop low will be equal to high , ie. means
* 5.1 we have found the element / not found
* 5.2 Hence check if array[low] || array[high] == key
* 5.3 else return -1
* @param arr
* @param k
* @return
*/
public int getFirstIndex(int arr[] , int k){
if(arr.length == 0 ){
//throw new RuntimeErrorException(null,"array is null");
return -1;
}
if(arr[0] == k){
return 1;
}
else if (k > arr[arr.length -1]){
return -1;
}
int result = -1;
int low = 0;
int high = arr.length - 1;// 2
while(low < high){
int mid = (low + high - low)/2;//(2/2)
if(k< arr[mid]){
high = mid -1;
}
else if(k > arr[mid]){
low = mid + 1;
}
else{
low = mid;
high = low;
break;
}
}
if(arr[low] == k){
result = low +1;
int j = low -1;
while((j > -1) && (arr[low]== arr[j]) ){
j--;
result = j +1;
}
System.out.println(result);
}
return result;
}
}

{/**
* Being a QA/QE - Conditions to be noted
* 1.Array length should be greater than 0.
* 2.If first element is equal to key then no need to run the loop
* 3.if K > last element of array , that means element is not in the array
* 4.Loop -
* 4.1. low , high and mid are indexes not elements , but compare key with
array[mid]
* 5.when exit from the loop low will be equal to high , ie. means
* 5.1 we have found the element / not found
* 5.2 Hence check if array[low] || array[high] == key
* 5.3 else return -1
* @param arr
* @param k
* @return
*/
public int getFirstIndex(int arr[] , int k){
if(arr.length == 0 ){
//throw new RuntimeErrorException(null,"array is null");
return -1;
}
if(arr[0] == k){
return 1;
}
else if (k > arr[arr.length -1]){
return -1;
}
int result = -1;
int low = 0;
int high = arr.length - 1;// 2
while(low < high){
int mid = (low + high - low)/2;//(2/2)
if(k< arr[mid]){
high = mid -1;
}
else if(k > arr[mid]){
low = mid + 1;
}
else{
low = mid;
high = low;
break;
}
}
if(arr[low] == k){
result = low +1;
int j = low -1;
while((j > -1) && (arr[low]== arr[j]) ){
j--;
result = j +1;
}
System.out.println(result);
}
return result;
}
}}

#assume in is not an empty array and key is a valid positive integer, otherwise, extra checks needed
#code is written in python
def keyIndex(in, key):
"""
:type in: array
:type key: in
:rtype: array
"""
index = []
for i in range(len(in)):
if in[i] == key:
index.append(i)
return index