Linkedin Interview Question
Software DevelopersTeam: Software Developement - Tools
Country: United States
Interview Type: Phone Interview
Thought it would be fun to do this in C. Since you can't know the size of an int array in C I was obliged to use a second parameter and I modify this parameter to make it reflect the size of the new array so it can be used later to display that new array.
#include <stdlib.h>
size_t count_unique_ints(int *arr, size_t size)
{
size_t i;
size_t j;
size_t count;
int curr;
i = -1;
count = 0;
while (++i < size)
{
j = -1;
curr = arr[i];
while (++j < size)
if (arr[j] == curr && j != i)
break ;
if (j == size)
count++;
}
return (count);
}
int *get_unique_ints(size_t res_size, int *arr, size_t size)
{
size_t i;
size_t j;
size_t k;
int curr;
int *result;
i = -1;
k = 0;
result = (int *)malloc(sizeof(int) * res_size);
if (!result)
return (NULL);
while (++i < size)
{
j = -1;
curr = arr[i];
while (++j < size)
if (arr[j] == curr && j != i)
break ;
if (j == size)
result[k++] = curr;
}
return (result);
}
int *once_integers(int *integers, size_t *size)
{
int *result;
int i;
size_t res_size;
i = 0;
res_size = count_unique_ints(integers, *size);
result = get_unique_ints(res_size, integers, *size);
*size = res_size;
return (result);
}
Use this for testing:
#include <stdio.h>
#include <stdlib.h>
int *once_integers(int *integers, size_t *size);
int main(void)
{
int ints[8] = {1, 2, 3, 5, 2, 2, 3, 4};
int *ints2;
size_t size = 8;
size_t i;
i = 0;
ints2 = once_integers(ints, &size);
while (i < size)
printf("%d\n", ints2[i++]);
free(ints2);
return (0);
}
#include <stdio.h>
#include <stdlib.h>
int check_single(int nb, int *array)
{
int i = 0;
int count = 0;
while (array[i])
{
if (array[i] == nb)
count++;
i++;
}
if (count == 1)
return (1);
return (0);
}
int *once_integers(int *array, int size)
{
int i = 0;
int j = 0;
int *res;
while(i < size)
{
if (check_single(array[i], array) == 1)
j++;
i++;
}
i = 0;
j = 0;
res = (int*)malloc(sizeof(int) * j + 1);
while(i < size)
{
if (check_single(array[i], array) == 1)
{
res[j] = array[i];
j++;
}
i++;
}
return (res);
}
public void once_integers(int nums[]) {
Map<Integer, Integer> store = new HashMap<>();
for (Integer i : nums) {
if (store.containsKey(i)) {
store.put(i, store.get(i) + 1);
} else {
store.put(i, 1);
}
}
for(Map.Entry<Integer, Integer> e : store.entrySet()) {
if (e.getValue() == 1) {
System.out.print(e.getKey() + " - ");
}
}
}
public void once_integer_sorted(int nums[] ) {
int count = 0;
for (int i = 0; i< nums.length; i++) {
if (i == nums.length - 1) {
if (count == 0) {
System.out.print(nums[i] + " - ");
}
break;
}
if (nums[i] != nums[i+1]) {
if (count == 0) {
System.out.print(nums[i] + " - ");
}
count = 0;
} else {
count++;
}
}
}
// From ZoomBA , with Love
def not_sorted( a ){
select ( mset( a ) ) :: { $.o.value == 1 } -> { $.o.key }
}
def sorted_imp( a ){
lfold ([0: #|a| ], [ a[0] , 1 , list() ] ) -> {
if ( $.p.0 == a[$.o] ){
$.p.1 += 1
} else{
if ( $.p.1 == 1 ) { $.p.2 += $.p.0 }
$.p.0 = a[$.o]
$.p.1 = 1
}
$.p
}
For the first part:
Method-1:
print([x for x in lst if lst.count(x)==1])
Method -2:
for item in lst:
if item in count_dict.keys():
count_dict[item]+=1
else:
count_dict[item]=1
for item in count_dict:
if count_dict[item]==1:
print(item)
For the second part :Optimized space
for i in range(len(lst)):
for j in range(i,len(lst)):
if lst[i]==lst[j]:
flag=1
break
if flag == 0:
print(lst[i])
public List<Integer> unique(List<Integer> arr) {
if (arr == null || arr.size == 0) return arr;
Set<Integer> hs = new HashSet<>();
for (int i = 0; i < arr.size; i++) {
if (!hs.contains(arr.get(i))) hs.put(arr.get(i))
}
return new ArrayList<Integer>(hs);
}
public List<Integer> unique(List<Integer> arr) {
if (arr == null || arr.size == 0) return arr;
List<Integer> ret = new ArrayList<>();
ret.add(arr.get(0));
Integer curr = ret.get(0);
for(Integer i : arr) {
if (i != null && i != curr) {
ret.add(i);
curr = i;
}
}
return ret;
}
Below is a solution with runtime of O(N) and space of O(N). Idea is to use unordered_map<int, bool> to process array. Then result can be returned as an vector or array.
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
vector<int> once_int(int *arr, int size) {
unordered_map<int, bool> myMap;
for(int i=0; i<size; i++) {
if(myMap.find(arr[i]) == myMap.end()) {
myMap[arr[i]] = true;
} else {
myMap[arr[i]] = false;
}
}
vector<int> vec;
for(unordered_map<int, bool>::iterator it=myMap.begin(); it!=myMap.end(); ++it) {
if(it->second == true)
vec.push_back(it->first);
}
return vec;
}
int main() {
// your code goes here
int arr[] = {4, 3, 3, 1};
vector<int> vec = once_int(arr, 4);
for(vector<int>::iterator it=vec.begin(); it!=vec.end(); ++it) {
cout<<*it<<" ";
}
return 0;
}
public class uniqueRecs {
public static List<Integer> UniqueRecords(int[] nums){
Map<Integer,Integer> store = new HashMap<>();
for(int e=0;e<nums.length-1;e++)
{
if(store.containsKey(nums[e]))
{
store.put(nums[e], store.get(nums[e])+1);
}
else
{
store.put(nums[e], 1);
}
}
//System.out.println(store.keySet());
List<Integer> res = new ArrayList<>(store.keySet());
return res;
}
public static void main(String[] args)
{
int[] nums = {1,1,2,2,3,3,3};
List<Integer> res = UniqueRecords(nums);
System.out.println(res);
}
}
Simple Java Implementation using HashMap
/*For unsorted array*/
int[] in = new int[]{1,5,5,3,3,6,6,6};
int[] out = new int[in.length];
out[0] = in[0];
int outLen = 1;
for(int i=1;i<in.length;i++){
int j=0;
for(;j<outLen;j++){
if(out[j]==in[i]){
break;
}
}
if(j==outLen){
out[outLen]=in[i];
outLen++;
}
}
System.out.println(Arrays.toString(out));
A: O(n), Space O(N)
Dictionary<int, boolean> elementExists = new Dictionary<int, boolean>();
foreach(int i in arr)
{
if(!elementExists.ContainsKey(i))
elementExists.Add(i, true);
}
foreach(var item in elementExists.Keys)
{
Console.Writeline(item);
}
B: O(N), Space (1) if arrays sorted.
int curr = 0; //1,1,2,2,3,4,4,5,5
for(int item=0;item<array.Length; item++)
{
if(array[item] != array[item+1])
{
arr[curr++] = array[item];
}
}
vector<int> GetUniques(vector<int> const &a)
{
unordered_map<int, int> counts;
for (int n : a) {
++counts[n];
}
vector<int> out;
for (auto const &count : counts) {
if (count.second == 1) {
out.push_back(count.first);
}
}
return out;
}
vector<int> GetUniquesSortedInput(vector<int> const &a)
{
vector<int> out;
int size = a.size();
for (int i = 0; i < size; ++i) {
while (i + 1 < size &&
a[i + 1] == a[i])
{
int val = a[i];
while (i < size &&
a[i] == val)
{
++i;
}
}
if (i < size) {
out.push_back(a[i]);
}
}
return out;
}
- SomeGuy October 05, 2016