Google Interview Question
Backend DevelopersCountry: United States
#include <stdio.h>
void DupLastIndex (int *arr, int n) {
int i;
if (arr == NULL || n <= 0) {
return;
}
for (i = n - 1; i > 0; i--) {
if (arr[i] == arr[i - 1]) {
printf("Last index: %d\nLast duplicate item: %d\n", i, arr[i]);
return;
}
}
}
int main() {
int arr[] = {1, 2, 5, 6, 6, 7, 9};
DupLastIndex (arr, sizeof(arr)/sizeof(int));
return 0;
}
- Walk the array from right to left.
- Compare i-th item with (i - 1)th item.
- If there's a match, print i. You are done.
#include <stdio.h>
void DupLastIndex (int *arr, int n) {
int i;
if (arr == NULL || n <= 0) {
return;
}
for (i = n - 1; i > 0; i--) {
if (arr[i] == arr[i - 1]) {
printf("Last index: %d\nLast duplicate item: %d\n", i, arr[i]);
return;
}
}
}
int main() {
int arr[] = {1, 2, 5, 6, 6, 7, 9};
DupLastIndex (arr, sizeof(arr)/sizeof(int));
return 0;
}
- Walk the array from right to left.
- Compare i-th item with (i - 1)th item.
- If there's a match, print i. You are done.
#include <stdio.h>
void DupLastIndex (int *arr, int n) {
int i;
if (arr == NULL || n <= 0) {
return;
}
for (i = n - 1; i > 0; i--) {
if (arr[i] == arr[i - 1]) {
printf("Last index: %d\nLast duplicate item: %d\n", i, arr[i]);
return;
}
}
}
int main() {
int arr[] = {1, 2, 5, 6, 6, 7, 9};
DupLastIndex (arr, sizeof(arr)/sizeof(int));
return 0;
}
- Walk the array from right to left.
- Compare i-th item with (i - 1)th item.
- If there's a match, print i. You are done.
#include <stdio.h>
void DupLastIndex (int *arr, int n) {
int i;
if (arr == NULL || n <= 0) {
return;
}
for (i = n - 1; i > 0; i--) {
if (arr[i] == arr[i - 1]) {
printf("Last index: %d\nLast duplicate item: %d\n", i, arr[i]);
return;
}
}
}
int main() {
int arr[] = {1, 2, 5, 6, 6, 7, 9};
DupLastIndex (arr, sizeof(arr)/sizeof(int));
return 0;
}
O(nlogn) using binary search
#include <iostream>
using namespace std;
int FindIndex(int* array, int mid)
{
if(array[mid-1] == array[mid] && array[mid] == array[mid+1])
{
return mid+1;
}
else if(array[mid-1] == array[mid])
{
return mid;
}
else if(array[mid] == array[mid+1])
{
return mid+1;
}
else
{
return -1;
}
}
int FindLastIndexOfDuplicate2(int* array, int start, int end)
{
if(start == end)
{
return -1;
}
if(start+1 == end)
{
return (array[start] == array[end] ? end : -1);
}
else if(start+2 == end)
{
return FindIndex(array, start+1);
}
else if(start+3 == end)
{
int x = FindIndex(array, start+2);
return x == -1 ? FindIndex(array, start+1) : x;
}
int mid = (end-start)/2 + start;
if(array[mid-1] == array[mid] && array[mid] == array[mid+1])
{
return FindLastIndexOfDuplicate2(array, mid, end);
}
else if(array[mid-1] == array[mid])
{
return FindLastIndexOfDuplicate2(array, mid-1, end);
}
else if(array[mid] == array[mid+1])
{
return FindLastIndexOfDuplicate2(array, mid, end);
}
else
{
return FindLastIndexOfDuplicate2(array, mid+1, end);
}
}
int FindLastIndexOfDuplicate(int array[], int length)
{
return FindLastIndexOfDuplicate2(array, 0, length-1);
}
int main() {
int n;
cin>>n;
int A[n];
for(int i=0; i<n; i++)
{
cin>>A[i];
}
cout<<FindLastIndexOfDuplicate(A, n);
return 0;
}
private static Integer getLastIndexOfLastDuplicateNumber(Integer[] arr) {
ArrayList<Integer> numbers = new ArrayList<>(Arrays.asList(arr));
for (int index = 0; index < numbers.size(); index++) {
int lastDuplicateElementIndex = numbers.lastIndexOf(numbers.get(index));
if (lastDuplicateElementIndex > -1 && lastDuplicateElementIndex != index)
return lastDuplicateElementIndex;
}
return -1;
}
We can achieve this with Time Complexity O(n) and Auxiliary Space O(1)
def findLastIndex(arr: [int]) -> int:
last_index = -1
for i in range(len(arr)-1):
if arr[i] == arr[i + 1]:
last_index = arr[i + 1]
return last_index
If the input is not sorted, we can still achieve this with Time Complexity O(n) and Auxiliary Space O(n).
def findLastNotOrdered(arr: [int]) -> int:
elem_map = {}
max_index = -1
for i in range(len(arr)):
if arr[i] in elem_map:
elem_map[arr[i]].append(i)
if len(elem_map[arr[i]]) > 1:
max_index = i
else:
elem_map[arr[i]] = [i]
return max_index
{{
- gentleman January 11, 2018public class IndexofLastDuplicate {
public static void main(String[] args) {
int arr[] = { 1, 2, 5, 6, 6, 7, 9, 9, 9, 9, 9, 9 };
int lastIndex = findLastDuplicateIndex(arr);
System.out.println("Last duplicate" + lastIndex);
}
public static int findLastDuplicateIndex(int[] arr) {
int lastIndex = -1;
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] == arr[i + 1]) {
lastIndex = i + 1;
}
}
return lastIndex;
}
}
}}