Groupon Interview Question Applications Developers
Country: India
Interview Type: Written Test
I think your code always sets the start index as 0. If the first element is not 7 or 42, what happens? I'm not sure if this is the correct code.
int findIndex(int A[],int N,int X,int Y)
{
int nx =0;
int ny=0;
int result = -1;
int startIndx = -1;
for( int i=0;i<N;i++)
{
if(A[i] == X) nx+=1;
if(A[i] == Y) ny+=1;
if ((nx!=0 || ny!=0) && (startIndx == -1))
startIndx = i;
if(nx== ny&& nx!=0&&ny!=0)
result = i;
}
if ((startIndx != -1) && (result!=-1))
result = result - startIndx;
return result;
}
def advance(nums, counts, i, j, X, Y):
while 0 <= i < j and counts[X] > counts[Y]:
if nums[j] == X:
counts[X] -= 1
j -= 1
else:
if nums[i] == X:
counts[X] -= 1
i += 1
else:
i += 1
j -= 1
return i, j
def largestContainingXandY(nums, X, Y):
counts = collections.Counter(nums)
i, j, res = 0, len(nums) - 1, 0
while i < j:
i, j = advance(nums, counts, i, j, X, Y)
i, j = advance(nums, counts, i, j, Y, X)
if counts[X] == counts[Y]:
res = max(res, j - i + 1)
break
return res
nums = [7, 42, 5, 6, 42, 8, 7,5, 7, 6, 7]
nums1 = [7, 42, 7, 42, 7, 7, 42, 42, 7, 7, 7, 7, 7, 7, 42]
nums2 = [7, 7]
print(largestContainingXandY(nums1, 7, 42))
/**
* @author kkanaparthi
*
*/
public class FindHighestIndexOfOccurances {
/**
*
*/
public FindHighestIndexOfOccurances() {
}
public static void main(String a[]) {
int x =5,y=10;
int array[] = new int[]{1,5,5,10,10,7,5,10,6,9,14,5,10,7,9,4};
int matchingIndex = -1;
int length = array.length;
int xCount=0 ,yCount =0;
for(int i=0;i<length;i++) {
if(array[i] == x) {
xCount++;
matchingIndex = i;
} else if(array[i]==y) {
yCount++;
matchingIndex = i;
} else {
System.out.println
("No Match with X and Y "+array[i]);
}
}
if(xCount==yCount) {
System.out.println("x and y are repeated for the"
+ " same count of times "+xCount+" matchingIndex "+matchingIndex);
} else {
System.out.println("X and Y counts are NOT equal");
}
}
}
/**
* @author kkanaparthi
*
*/
public class FindHighestIndexOfOccurances {
/**
*
*/
public FindHighestIndexOfOccurances() {
}
public static void main(String a[]) {
int x =5,y=10;
int array[] = new int[]{1,5,5,10,10,7,5,10,6,9,14,5,10,7,9,4};
int matchingIndex = -1;
int length = array.length;
int xCount=0 ,yCount =0;
for(int i=0;i<length;i++) {
if(array[i] == x) {
xCount++;
matchingIndex = i;
} else if(array[i]==y) {
yCount++;
matchingIndex = i;
} else {
System.out.println
("No Match with X and Y "+array[i]);
}
}
if(xCount==yCount) {
System.out.println("x and y are repeated for the"
+ " same count of times "+xCount+" matchingIndex "+matchingIndex);
} else {
System.out.println("X and Y counts are NOT equal");
}
}
}
import java.util.HashMap;
public class Test3 {
public static void main(String[] args) {
int[] arr = {1,5,7,6,8,5,7,6,5,7,7,5,5,7};
printLongestPrefix(arr, arr.length, 5, 7);
}
public static void printLongestPrefix(int[] A, int N, int X, int Y) {
int[] temp = new int[N];
HashMap<Integer, Integer> start = new HashMap<Integer, Integer>();
HashMap<Integer, Integer> end = new HashMap<Integer, Integer>();
int curr = 0, p = 0, q = 0;
for (int i = 0; i < N; i++) {
if (A[i] == X) {
Integer val = start.get(curr);
if (val == null)
start.put(curr, i);
curr++;
end.put(curr, i);
} else if (A[i] == Y) {
Integer val = start.get(curr);
if (val == null)
val = i;
curr--;
end.put(curr, i);
}
Integer val = start.get(curr);
Integer val2 = end.get(curr);
if (val != null && val2 != null) {
p = val;
q = val2;
}
}
System.out.println("p = " + p + " q = " + q);
}
}
import java.util.HashMap;
public class Test3 {
public static void main(String[] args) {
int[] arr = {1,5,7,6,8,5,7,6,5,7,7,5,5,7};
printLongestPrefix(arr, arr.length, 5, 7);
}
public static void printLongestPrefix(int[] A, int N, int X, int Y) {
int[] temp = new int[N];
HashMap<Integer, Integer> start = new HashMap<Integer, Integer>();
HashMap<Integer, Integer> end = new HashMap<Integer, Integer>();
int curr = 0, p = 0, q = 0;
for (int i = 0; i < N; i++) {
if (A[i] == X) {
Integer val = start.get(curr);
if (val == null)
start.put(curr, i);
curr++;
end.put(curr, i);
} else if (A[i] == Y) {
Integer val = start.get(curr);
if (val == null)
val = i;
curr--;
end.put(curr, i);
}
Integer val = start.get(curr);
Integer val2 = end.get(curr);
if (val != null && val2 != null) {
p = val;
q = val2;
}
}
System.out.println("p = " + p + " q = " + q);
}
}
static void Main(string[] args)
{
Console.WriteLine("Enter numbers");
string elementsFromConsole= Console.ReadLine();
int[] elements = elementsFromConsole.Split(',').Select(e => Convert.ToInt32(e)).ToArray();
Console.WriteLine("Enter X");
int x = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("Enter Y");
int y = Convert.ToInt32(Console.ReadLine());
int xFoundCount=0;
int yFoundCount = 0;
Dictionary<int, int> xFoundDic=new Dictionary<int, int>();
Dictionary<int, int> yFoundDic=new Dictionary<int, int>();
for (int i = 0; i < elements.Length; i++)
{
if (elements[i] == x)
{
xFoundDic.Add(++xFoundCount,i);
}
if (elements[i] == y)
{
yFoundDic.Add(++yFoundCount, i);
}
}
if (xFoundCount == 0 || yFoundCount == 0)
Console.WriteLine(-1);
var value = (xFoundCount > yFoundCount)?xFoundDic[xFoundCount]:yFoundDic[ yFoundCount];
Console.WriteLine("Largest Prefix is "+(value-1));
Console.Read();
}
A simple solution in Python3.
from typing import List
def solution(A: List[int], a: int, b: int) -> int:
cnt_of_a = 0
cnt_of_b = 0
result = -1
for idx in range(len(A)):
if a == A[idx]:
cnt_of_a += 1
elif b == A[idx]:
cnt_of_b += 1
if cnt_of_a and cnt_of_a == cnt_of_b:
result = idx
return result
if __name__ == '__main__':
test_cases = {
# expected output : input parameters
9: ([7, 42, 5, 6, 42, 8, 7, 5, 3, 6, 7], 7, 42),
}
for key, value in test_cases.items():
if key != solution(*value):
print("input: %s, expected output: %d" % (value, key))
Here is the correction and solution:
It easy, once you find the ending index, you need to backtrack it and find out where they were equal, the least index would be the starting point;
package Java;
/**
* Author: Nitin Gupta(nitin.gupta@walmart.com)
* Date: 26/04/19
* Description:
*/
public class EqualXandY {
public static void main(String[] args) {
int[] arr = {1, 5, 7, 6, 8, 5, 7, 6, 5, 7, 7, 5, 5, 7};
print(arr, arr.length, 5, 7);
int[] arr2 = {7, 42, 5, 6, 42, 8, 7, 5, 7, 6, 7};
print(arr2, arr2.length, 7, 42);
int[] arr3 = {7, 42, 5, 6, 42, 8, 7, 5, 3, 6, 7};
print(arr3, arr3.length, 7, 42);
int[] arr4 = {5, 6, 7, 42, 42, 8, 7, 5, 3, 6, 7};
print(arr4, arr4.length, 7, 42);
}
public static void print(int arr[], int n, int X, int Y) {
// counters for X and Y
int nx = 0, ny = 0;
int result = -1;
int count = 0;
int resultCount = 0;
for (int i = 0; i < n; i++) {
// If value is equal to X increment counter of X
if (arr[i] == X)
nx++;
// If value is equal to X increment counter of X
if (arr[i] == Y)
ny++;
// If counters are equal(but not zero) save
// the result as i
if ((nx == ny) && (nx != 0 && ny != 0)) {
count = nx;
result = i;
}
}
nx = 0;
ny = 0;
resultCount = count;
count = 2 * count;
int start = -1;
for (int i = result; i >= 0; i--) {
if (arr[i] == X) {
count--;
nx++;
}
if (arr[i] == Y) {
count--;
ny++;
}
if (nx == ny)
start = i;
if (count == 0)
break;
}
System.out.println("s : " + start + " end " + result + " total count : " + resultCount);
}
}
outputs
s : 1 end 13 total count : 5
s : 0 end 7 total count : 2
s : 0 end 9 total count : 2
s : 2 end 9 total count : 2
You should keep track of previous index at which the result was updated .. Otherwise both na and nb would be equal and the result would keep on increasing.. !! Hope this helps.. :) :)
- Nimesh July 28, 2016