United HealthGroup Interview Question Tech Leads
Country: India
Interview Type: Written Test
Hi I am very new on this site,
Here is the My java solution, could anyone one of you please look into this and let me know if there is any space or complexity issues. Thanks in advance.
public int[] removesDuplicate(){
int arr[] = {1,2,7, 9, 9, 5, 4, 9};
int result[]= new int [arr.length];
int k=0;
boolean status = true;
for(int i=0;i<arr.length;i++){
status = true;
for(int j=0;j<k;j++){
if(arr[i]==result[j]){
status = false;
break;
}
}
if(status){
result[k] = arr[i];
k++;
}
}
for(int i=0;i<result.length;i++){
System.out.println(result[i]);
}
return result;
Pick some sort algorithm based on the more information about the element of the array. some radix sort may be used since those are numbers and there is a extra space available to contain the result. Shrink the final sorted array to remove the duplicated one using two ptrs, one writer, one reader.
Here is a draft of solution using simple hash funtion.
def remove_duplicates(input):
if not isinstance(input, list):
return "Bad input"
else:
min = 0
max = 0
for value in input:
if value < min:
min = value
if value > max:
max = value
COLLISON_CHAIN_MAX_LEN = 10
VALUE_NOT_IN_INPUT_ARR = -1
# hash function
# same as array
arr = [[VALUE_NOT_IN_INPUT_ARR for _ in range (0, COLLISON_CHAIN_MAX_LEN)] for _ in range (min, max + 1)]
def hash_function(val):
return val % (max - min)
for value in input:
index = hash_function(value)
for i, hashed in enumerate (arr[index]):
if (hashed == value):
# duplicate found
break;
else:
if hashed == VALUE_NOT_IN_INPUT_ARR:
# adding new value
arr[index][i] = value;
if (i == COLLISON_CHAIN_MAX_LEN -1):
# TODO code for hash chain size change here.
pass
break;
else:
# colision with other value hashed to this index,
# still dont know nothing - do nothing (in python pass)
pass
for chain in arr:
for value in chain:
if (value == VALUE_NOT_IN_INPUT_ARR):
break;
print value
if __name__ == '__main__':
remove_duplicates([1,2, 1, 4, 1, 6, 7, 4, 1, 10,])
This is just interview purpose....can try like this....
int[] arr = {1,2,7, 9, 9, 5, 4, 9};
int[] newarr = new int[arr.length];
StringBuffer valueCheck = new StringBuffer();
StringBuffer valueappend = new StringBuffer();
int newarrcount=0;
for(int i=0;i<arr.length;i++){
if(valueappend.indexOf(valueCheck.append(arr[i]).toString())<0){
newarr[newarrcount++]=arr[i];
valueappend.append(arr[i]);
}
valueCheck = new StringBuffer();
}
for(int i=0;i<valueappend.length()-1;i++){
System.out.println(newarr[i]);
}
Sorted array and insert into array1 ,cost time is n*log(n)+n，but usually the method is not vary fast.
We can designer a simple getHashCode method.
If got hashCode conflict, create new an array named buckets store others.
function remove_duplicates(arr){
var len = arr.length;
var buckets = new Array(len);
var target = new Array(len);
for(var i=0;i<len;i++){
var p = arr[i] % len;
if(!target[p]){
target[p] = arr[i];
}else{
var bucket = buckets[p];
if(bucket){
var exist = false;
for(var n = 0;n<bucket.length;n++){
if(bucket[n] == arr[i]){
exist = true;
break
}
}
if(!exist){
bucket.push(arr[i]);
}
}else{
buckets[p] = [arr[i]];
}
}
}
console.log(target);
console.log(buckets);
var result = [];
for(var i=0;i< target.length ;i++){
if(target[i]){
result.push(i);
}
}
for(var i=0;i<buckets.length;i++){
if(buckets[i]){
for(var j=0;j<buckets[i].length;j++){
result.push(buckets[i][j]);
}
}
}
console.log(result);
}
remove_duplicates([1,2,7, 9, 9, 5, 4, 9]);
Can try like this..... :)
int[] arr = {1,2,7, 9, 9, 5, 4, 9};
int[] newarr = new int[arr.length];
StringBuffer valueCheck = new StringBuffer();
StringBuffer valueappend = new StringBuffer();
int newarrcount=0;
for(int i=0;i<arr.length;i++){
if(valueappend.indexOf(valueCheck.append(arr[i]).toString())<0){
newarr[newarrcount++]=arr[i];
valueappend.append(arr[i]);
}
valueCheck = new StringBuffer();
}
for(int i=0;i<valueappend.length()-1;i++){
System.out.println(newarr[i]);
}
Treeset or Hashmap or hashtable like these.....we can try these for removing duplicates like....
int[] arr = {1,2, 1, 4, 1, 6, 7, 4, 1, 10};
int[] newarr = new int[arr.length];
Map map = new HashMap();
int newarrcount=0;
for(int i=0;i<arr.length;i++){
map.put(new String(arr[i]+""),new Integer(arr[i]));
}
for(Iterator iterator = map.keySet().iterator();iterator.hasNext();){
newarr[newarrcount++]=((Integer)map.get(iterator.next()+"")).intValue();
System.out.println(newarr[newarrcount-1]);
}
public class ArraysMain {
public static void main(String[] args) {
int[] arr = {1,2,7, 9, 9, 5, 4, 9};
int[] newarr = new int[arr.length];
int k = 0;
for(int i : arr)
{
// check if it there in that arr
if(checkExists(i, newarr))
{
continue;
}
else
{
newarr[k] = i;
k++;
}
}
}
private static boolean checkExists(int i, int[] aa)
{
for(int j : aa)
{
if(j == i)
{
return true;
}
}
return false;
}
}
My java solution using String in O(n):
import java.util.Arrays;
public class Remove_Dup_No_Collection {
public static void main(String[] args) {
int[] a = {1,2,7, 9, 9, 5, 4, 9};
System.out.println(Arrays.toString(removeDup(a)));
}
private static int[] removeDup(int[] a) {
String dup = "";
for (int i = 0; i < a.length; i++) {
dup += "" + a[i] + ",";
}
//removing last ","
dup = dup.substring(0, dup.length()-1);
String[] dupArr = dup.split(",");
for (int i = 0; i < dupArr.length; i++) {
dup = dup.replace(dupArr[i], "");
dup += a[i] + ",";
}
String[] ans = dup.split(",");
int count = 0;
for (int i = 0; i < ans.length; i++) {
if(!ans[i].equals(""))
count++;
}
int[] newArr = new int[count];
count = 0;
for (int i = 0; i < ans.length; i++) {
if(!ans[i].equals(""))
newArr[count++] = Integer.parseInt(ans[i]);
}
return newArr;
}
}
Output:
[1, 2, 7, 5, 4, 9]
Integer array is converted to a String, i.e:
dup = "1,2,7,9,9,5,4,9";
then it is converted to String array:
String[] dupArr = dup.split(",");//[1, 2, 7, 9, 9, 5, 4, 9]
Then all occurrences of a number are removed then the number is added to the string:
dup = dup.replace(dupArr[i], "");
dup += a[i] + ",";
Finally, the integer array is reconstructed without duplicate.
Java already has implemented Merge-sort.
Run-time complexity: On avg, nlogn.
Space complexity: O(n).
static int[] removeDups(final int[] array)
{
int[] copyArray = array.clone();
Arrays.sort(copyArray);
int[] newArray=new int[array.length];
int endMarker=0;
newArray[0]=copyArray[0];
endMarker++;
for(int i=1;i<copyArray.length;i++)
{
if(copyArray[i]!=copyArray[i-1])
{
newArray[endMarker++]=copyArray[i];
}
}
newArray=null;
copyArray=null;
int[] resultArray=new int[endMarker];
for(int i=0;i<endMarker;i++)
{
resultArray[i]=copyArray[i];
}
return resultArray;
}
import java.lang.reflect.Array;
public class Duplicate {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[]={1,3,4,4,5,6,6,66};
int[] b=new int[a.length];
int j=0;
for(int i=0;i<a.length;i++)
{
if(b.length<1 && j<b.length)
{
b[j++]=a[i];
}
else
{
int flag=0;
for(int k=0;k<j;k++)
{
if(a[i]==b[k])
flag=1;
}
if(flag==1)
continue;
else b[j++]=a[i];
}
}
for(int i=0;i<j;i++)
{
System.out.println(b[i]);
}
}
}
Using Array List
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class RemoveSameElements {
public static void RemoveSameNumber(List<Integer> myArr)
{
for(int i = 0 ; i < myArr.size(); i++)
{
if(myArr.get(i) == myArr.get(i+1))
{
myArr.remove(i);
myArr.remove(i);
if(myArr.size() > 1)
{
RemoveSameNumber(myArr);
}
}
}
System.out.println(myArr);
}
public static void main(String[] args) {
int[] arr = {1,2,2,1,4,5,6,6,5};
List<Integer> myArr = new ArrayList<>();
for(int i = 0 ; i < arr.length; i ++)
{
myArr.add(arr[i]);
}
RemoveSameNumber(myArr);
}
}
If it is not a sorted Array, we will use merge sort, which will take o(log N) time.
- Prashanth April 04, 2013Now take the sorted array, and copy into new array inthis fashion, which takes o(n) time.
int copiedArray[] = new int[10];
void avoidDup(int arr[])
{
int k=0;
for(int i=1;i<arr.length;i++)
{
if(arr[i-1] == arr[i])
continue;
else
copiedArray[k++] = arr[i-1]
}
}