Interview Question
Country: United States
I think using a HashSet (java) will do the trick. It implements the Set interface so uniqueness is guaranteed.
The code below will run in worst case O(i*j) time, but I THINK this is a mandatory step anyway to read the matrix. All other functions are O(1) time.
Note: no -ve K or other error condition checks.
public boolean findDuplicateWithinIndex(int[][] input, int k)
{
int currentK = 0;
for(int i = 0; i < input.length-1; i++)
{
for(int j=0; j < input[i].length-1; j++)
{
Integer cell = input[i][j];
System.out.println(cell.hashCode());
if(!hs.add(cell)) //collision
{
if(currentK < k) //found collision within k indices
return true;
}
if(currentK < k)
currentK++;
else
currentK = 0; //reset if we've surpassed K
}
}
return false; //no collision within K indices.
Sample input:
int[][] findDuplicateInput = new int[][] { { 1,2,3,4} , { 5, 6, 3, 8 }, {9, 2, 11, 12 } };
DuplicateEntriesWithinIndex duplicate = new DuplicateEntriesWithinIndex();
int k = 9;
boolean found = duplicate.findDuplicateWithinIndex(findDuplicateInput, k);//no collision
if(found)
System.out.println("Find duplicate: " + k);
else
System.out.println("No dupes.");
Output:
Dupe found at 9
I think of multiple ways to solve this.
- Anonymous August 11, 20151) start traversing matrix, insert k node into binary tree and keep it balanced.Create queue and add the element in that as well.
Before adding new element, search binary tree if element with same value found thats the answer. If not then continue.
After k elements, when new elements comes,dequeue from queue, remove that element from binary search tree, search inside binary search tree for same value elements, if not found add element in queue and binary search tree as well.
Time Complexity nlong
N for traversing matrix elements (here n is total number of elements in matrix)
logn for insertion, deletion in binary search tree (insertion and search can be done on one go)
2) Same approach can be done using hash table for insertion n deletion. Hashtable will contain k elements.