Epic Systems Interview Question Software Engineer / Developers
hunt, your code does not seem to do the job. You're just moving the pointers forward. There are two options: either you create a new list or trim the existing list so that at the end it just contains the unique elements. Your code is not doing either.
My approach would be two trim the existing list and in this case you have to swap elements so that you skip the repeating elements.
My take:
// Remove duplicates from a sorted list
void RemoveDuplicates(struct node* head)
{
struct node* current = head;
if (current == NULL) return; // do nothing if the list is empty
// Compare current node with next node
while(current->next!=NULL) {
if (current->data == current->next->data) {
struct node* nextNext = current->next->next;
free(current->next);
current->next = nextNext;
} else {
current = current->next; // only advance if no deletion
}
}
}
Cunomad, wer r u getting these q's from. r these from the main test or the 2nd round. plz tell us
c++ code
void getUnique(list<int>& input) {
//less than 2 element
if (input.size() < 2)
return;
list<int>::iterator it = input.begin();
list<int>::const_iterator cit = input.begin();
++it;
while (it != input.end()) {
if (*it != *cit) {
++it;
++cit;
} else {
list<int>::iterator itTemp = it;
++it;
input.erase(itTemp);
}
}
}
c++ code
void getUnique(list<int>& input) {
//less than 2 element
if (input.size() < 2)
return;
list<int>::iterator it = input.begin();
list<int>::const_iterator cit = input.begin();
++it;
while (it != input.end()) {
if (*it != *cit) {
++it;
++cit;
} else {
list<int>::iterator itTemp = it;
++it;
input.erase(itTemp);
}
}
}
void getUnique(list<int>& input) {
//less than 2 element
if (input.size() < 2)
return;
list<int>::iterator it = input.begin();
list<int>::const_iterator cit = input.begin();
++it;
while (it != input.end()) {
if (*it != *cit) {
++it;
++cit;
} else {
list<int>::iterator itTemp = it;
++it;
input.erase(itTemp);
}
}
}
O(n) solution :
for(i = 0 ; i < arraySize ; i++)
{
if(i!= arraySize && a[i] != a[i+1])
printf("%d",a[i]);
}
printf("%d",a[i-1]);
#include<iostream>
using namespace std;
void main()
{
int a[20], n, ele;
int x=0, cur=0, nxt = 1;
char ans;
do
{
cout << "\n Enter a no. and y/n if you would like to continue ? ";
cin >> a[x++] >> ans;
}while(ans=='y' && x<20);
while(cur<x)
{
ele=a[cur];
if(ele == a[nxt])
{
while(ele==a[++nxt]);
cur=nxt;
}
else
{
cur++;
}
nxt++;
cout << "\n " << ele;
}
cout <<"\n ";
}
This can solve the problem by Jay's code (in JAVA)
public class unique_sorted_array
{
public static void main(String args[])
{
int arr[] = {1,1,2,3,3,3,4,5,5,6};
//System.out.println(arr[0]);
for(int i=0;i<arr.length-2;i++)
{
if((arr[i] ^ arr[i+1]) == 1)
System.out.println(arr[i]);
}
int k =arr.length-1;
if((arr[k] ^ arr[k-1]) != 0)
{
System.out.println(arr[k]);
}
}
}
<pre lang="" line="1" title="CodeMonkey11391" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
int a[] = {1,1,3,3,3,3,5,5,5,8,8,8,8,8};
int j = 0;
for (int i = 0; i < a.length()-1; i++) {
j = i+1;
while (a[i] == a[j]) {
j++;
}
System.out.println(""+a[i]);
i = j - 1;
} //end for
if (a[a.length()-1] != a[a.length()-2])
System.out.println(""+a[a.length()-1]);
}
}
</pre><pre title="CodeMonkey11391" input="yes">
</pre>
import java.util.ArrayList;
public class uniqueValues {
static int[] arr={1, 1, 3, 3, 3, 5, 5, 5, 9, 9, 9, 9};
public static void main(String[] args) {
StringBuffer sb=new StringBuffer();
ArrayList<String> al=new ArrayList<String>();
for(int i:arr){
sb.append(i);
String s=Integer.toString(i);
al.add(s);
}
System.out.println(al);
String result=al.get(0);
for(int i=0;i<al.size();i++){
if(!result.contains(al.get(i))){
result+=al.get(i);
}
}
System.out.println(result);
}
}
I tried it this way : Please let me know if it is good enough:
package epic.java;
public class UniqueElementsInArray {
public static void main(String[] args){
Integer[] intArray={1,1,3,3,3,5,5,5,9,9,9, 9,10};
int len=intArray.length;
int i=0;
int j=1;
while(j<len){
if(intArray[i]!=intArray[j]){
intArray[i+1]=intArray[j];
i++;
}
j++;
}
for(int m=0;m<i+1;m++)
System.out.println(intArray[m]);
}
}
public class RemoveDuplicates {
public static int[] remove(int[] a){
int i=0;
int l=a.length;
int count=0;
int duplicate=a[0];
for(i=1;i<l;i++){
if(a[i]==duplicate)
count++;
a[i-count]=a[i];
duplicate=a[i];
}
return a;
}
public static void main(String[] args){
int[] a={1,1,1,2,3,4};
int[] result=remove(a);
for(int i=0;i<result.length;i++)
System.out.println(result[i]);
}
}
package EPIC;
import java.util.LinkedList;
import java.util.List;
public class ExtracUniqueElements {
public static List<Integer> extractor(List<Integer> S) {
List<Integer> R = new LinkedList<>();
System.out.println(S.get(0));
R.add(S.get(0));
for (int i = 1; i <= S.size() - 1; i++) {
if (S.get(i - 1) != S.get(i)) {
System.out.println(S.get(i));
R.add(S.get(i));
}
}
return R;
}
public static void main(String[] args) {
List<Integer> L = new LinkedList<>();
L.add(1);
L.add(1);
L.add(3);
L.add(3);
L.add(3);
L.add(5);
L.add(5);
L.add(5);
L.add(5);
L.add(9);
System.out.println(L);
List<Integer> r = extractor(L);
System.out.println(r);
}
}
All O(n) solutions are incorrect as O(log n) solutions are possible. You do not need to check values between unique values as you know what they are. Hence, binary search that returns value when both start and end of split range are equal would give correct result much faster in cases where array is long and has only few unique values.
forgot to add we cant use Hash :)
- cunmoad September 17, 2009