Student Interview Question SDE1s
Country: India
This is the correct algorithm overall. Just one nitpick. As you probably know, you may not know the range of numbers passed in to create the hashtable with. It may be helpful to have a preliminary run through of the array to find the max element so that you can more accurately instantiate your hashtable to the right size.
Best way to solve this question is to use hashtable...
/Given an integer array with multiple repeated elements, print all distinct elements in array.
#include<iostream>
using namespace std;
int main()
{
int array[13] = {4,3,2,1,6,4,1,2,4,3,2,7,1};
int hashtable[20] = {0};
for(int i = 0; i < 13; i++)
{
int index = (int)(array[i]);
hashtable[index] = hashtable[index] + 1;
}
for(int j = 0; j < 20; j++)
{
if(hashtable[j] == 1)
{
cout<<array[j]<<" ";
}
}
return 0;
}
Output-> 6,7
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
public class RemovedDuplicateDataArray {
/**
* @param args
* @throws IOException
* @throws NumberFormatException
*/
public static void main(String[] args) throws NumberFormatException, IOException {
Integer arr[]=new Integer[10];
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
for (int i = 0; i < arr.length; i++) {
System.out.println("enter element --");
arr[i]=Integer.parseInt(br.readLine());
}
//put in arralist
List<Integer> list=new ArrayList<Integer>(Arrays.asList(arr));
//put in HashSet to sort data
HashSet<Integer> hashset=new HashSet<Integer>(list);
System.out.println(list+" "+hashset);
//again put in list
list=new ArrayList<Integer>(hashset);
//again put in array final
arr=new Integer[list.size()];
list.toArray(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
public class RemovedDuplicateDataArray {
/**
* @param args
* @throws IOException
* @throws NumberFormatException
*/
public static void main(String[] args) throws NumberFormatException, IOException {
Integer arr[]=new Integer[10];
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
for (int i = 0; i < arr.length; i++) {
System.out.println("enter element --");
arr[i]=Integer.parseInt(br.readLine());
}
//put in arralist
List<Integer> list=new ArrayList<Integer>(Arrays.asList(arr));
//put in HashSet to sort data
HashSet<Integer> hashset=new HashSet<Integer>(list);
System.out.println(list+" "+hashset);
//again put in list
list=new ArrayList<Integer>(hashset);
//again put in array final
arr=new Integer[list.size()];
list.toArray(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
class multiple{
public static void main(String[] args){
int[] input = {1,2,3,4,5,5,7,8,8,0,0,12};
// printUnique(input);
printUniqueSet(input);
}
/*
* ArrayList solution
*/
static void printUnique(int[] input){
boolean[] check = new boolean[256];
ArrayList<Integer> output = new ArrayList<>();
for(int i=0; i < input.length; i++){
if(!check[input[i]]){
output.add(input[i]);
}
check[input[i]] = true;
}
System.out.println(output.toString());
}
/*
* LinkedSet Solution
*/
static void printUniqueSet(int[] input){
Set<Integer> set = new LinkedHashSet<>();
for (int x : input){
set.add(x);
}
System.out.println(set.toString());
}
}
class multiple{
public static void main(String[] args){
int[] input = {1,2,3,4,5,5,7,8,8,0,0,12};
// printUnique(input);
printUniqueSet(input);
}
/*
* ArrayList solution
*/
static void printUnique(int[] input){
boolean[] check = new boolean[256];
ArrayList<Integer> output = new ArrayList<>();
for(int i=0; i < input.length; i++){
if(!check[input[i]]){
output.add(input[i]);
}
check[input[i]] = true;
}
System.out.println(output.toString());
}
/*
* LinkedSet Solution
*/
static void printUniqueSet(int[] input){
Set<Integer> set = new LinkedHashSet<>();
for (int x : input){
set.add(x);
}
System.out.println(set.toString());
}
}
class multiple{
public static void main(String[] args){
int[] input = {1,2,3,4,5,5,7,8,8,0,0,12};
// printUnique(input);
printUniqueSet(input);
}
/*
* ArrayList solution
*/
static void printUnique(int[] input){
boolean[] check = new boolean[256];
ArrayList<Integer> output = new ArrayList<>();
for(int i=0; i < input.length; i++){
if(!check[input[i]]){
output.add(input[i]);
}
check[input[i]] = true;
}
System.out.println(output.toString());
}
/*
* LinkedSet Solution
*/
static void printUniqueSet(int[] input){
Set<Integer> set = new LinkedHashSet<>();
for (int x : input){
set.add(x);
}
System.out.println(set.toString());
}
}
void distinctElements(int iArr[n])
{
int iDistinctEle[n];
std::fill(iDistinctEle,iDistinctEle+n,-1);
for(int i=0;i<n;i++)
{
if(iDistinctEle[i] !=-1)
{
if(iArr[i] ==iDistinctEle[i])
continue;
}
iDistinctEle[iArr[i]] = iArr[i];
}
for(int j=0;j<n;j++)
{
if(iDistinctEle[iDistinctEle[j]] ==j)
cout << iDistinctEle[j] <<' ';
}
return;
}
This is how I write it in Java which would be very simple'
public static Integer[] unique(Integer[] input){
Set<Integer> mySet= new HashSet<>(input.length);
for(Integer i:input)
mySet.add(i);
return mySet.toArray(new Integer[1]);
}
The trick of question is for C for not using hashtable:
int* unique(int* input, int length){
int max=0x7FFFFFFF+1;//minimum integer
int min=0x7FFFFFFF;//maximum integer
int i;
//find the max and min of the array O(n)
for(i=0;i<length;i++){
if(max<input[i])
max=input[i];
if(min>input[i])
min=input[i];
}
char* countArr = calloc(max-min+1,sizeof(char));
int count=0;
for(i=0;i<length;i++){
countArr[input[i]-min]=1;
count++;
}
int* output= calloc(count, sizeof(input[0]));
int index;
index=0;
for(i=min;i<=max;i++)
if(countArr[i-min]){
output[index++]=i;
}
return output;
}
I have to return the size of return array somehow that I did not do here.
import java.util.HashSet;
import java.util.LinkedHashSet;
public class Test {
public static void main(String args[]) {
int arr[] = {4,3,2,1,6,7,4,1,2,4,3,2,1};
HashSet<Integer> hs = new HashSet<Integer>();
for(int i=0;i<arr.length;i++) {
hs.add(arr[i]);
}
System.out.println(hs);
LinkedHashSet<Integer> hs1 = new LinkedHashSet<Integer>();
for(int i=0;i<arr.length;i++) {
hs1.add(arr[i]);
}
System.out.println(hs1);
}
}
import java.util.HashSet;
import java.util.LinkedHashSet;
public class Test {
public static void main(String args[]) {
int arr[] = {4,3,2,1,6,7,4,1,2,4,3,2,1};
HashSet<Integer> hs = new HashSet<Integer>();
for(int i=0;i<arr.length;i++) {
hs.add(arr[i]);
}
System.out.println(hs);
LinkedHashSet<Integer> hs1 = new LinkedHashSet<Integer>();
for(int i=0;i<arr.length;i++) {
hs1.add(arr[i]);
}
System.out.println(hs1);
}
}
package test;
public class FirstElement {
public static void main(String[] args) {
Integer a[] = {2,5,5,6,2,7,6,7,1,10};
int k=0;
Integer arr[][] = new Integer[1][a.length];
for(int i=0,j=0; i<a.length; ){
if(j<=k){
if(arr[0][j] != null){
if(arr[0][j] == a[i])
{
i++;
j=0;
}
else
j++;
}
else{
arr[0][j] = a[i];
k++;
i++;
j=0;
}
}
}
for(int h=0; h<k; h++){
System.out.print(arr[0][h]+" ");
}
}
}
package test;
public class FirstElement {
public static void main(String[] args) {
Integer a[] = {2,5,5,6,2,7,6,7,1,10};
int k=0;
Integer arr[][] = new Integer[1][a.length];
for(int i=0,j=0; i<a.length; ){
if(j<=k){
if(arr[0][j] != null){
if(arr[0][j] == a[i])
{
i++;
j=0;
}
else
j++;
}
else{
arr[0][j] = a[i];
k++;
i++;
j=0;
}
}
}
for(int h=0; h<k; h++){
System.out.print(arr[0][h]+" ");
}
}
}
- Monali April 07, 2015#include<iostream> using namespace std; int main() { int array[13] = {4,3,2,1,6,7,4,1,2,4,3,2,1}; int hashtable[20] = {0}; for(int i = 0; i < 13; i++) { int index = (int)(array[i]); hashtable[index] = hashtable[index] + 1; } for(int j = 0; j < 20; j++) { if(hashtable[j] == 1) { cout<<array[j]<<" "; } } return 0; } output-> 6,7