Saturday, January 06, 2018

remove duplicates from an unsorted linked list

more fun with algorithms: how to remove duplicates from an unsorted linked list in cpp?
easy - just walk along the list and delete duplicate items.
but how to know an item is a duplicate?
well, for every item we could scan the list from the beginning, but this is a ridiculously naive solution - how about keeping all values we encounter while iterating and checking if we have already met a current value?
putting those in an unordered set would be good enough i'd say
#include 
#include 
using namespace std;

struct List {
 int data = 0;
 List* next = nullptr;
 List(int x) : data(x) {}
};

void remove_duplicates(List* head) {
 std::unordered_set cache;
 cache.insert(head->data);
 List* next = head->next;
 while (next != nullptr) {
  if (cache.count(next->data) > 0) {
   head->next = next->next;
   delete next;
   next = head->next;
  } else {
   cache.insert(next->data);
   head = next;
   next = head->next;
  }
 }
}

int main() {
 List* head = new List(1);
 List* list = head;
 for (int index = 2; index < 10; ++index) {
  List* next = new List(index);
  //a silly way to make duplicates in the list
  if (next->data % 2 == 0) {
   next->data = 2;
  } else if (next->data % 3 == 0) {
   next->data = 3;
  }
  list->next = next;
  list = next;
 }
 
 remove_duplicates(head);
 
 while (head != nullptr) {
  printf("%d\n", head->data);
  head = head->next;
 }
 
 return 0;
}

https://ideone.com/K19v5o

reverse linked list

been fooling around writing solutions to algorithms in c++.
here is a solution to reverse a linked list. nothing new - the idea is to revert the links, but before that keep somewhere the links to the nodes to come so that this information is not lost during iterating.
shouldn't have any bugs due to corner cases, i hope :D

#include 
using namespace std;

struct List {
 int value = 0;
 List* next = nullptr;
 List(int x) : value(x) {}
};

List* reverse(List* head) {
 List* next = head->next;
 head->next = nullptr;
 while (next != nullptr) {
  List* movingHead = next->next;
  next->next = head;
  head = next;
  next = movingHead;
 }
 return head;
}

int main() {
 List* head = new List(1);
 List* list = head;
 for (int index = 2; index < 10; index++) {
  List* next = new List(index);
  list->next = next;
  list = next;
 }
 head = reverse(head);
 
 while (head != nullptr) {
  printf("%d\n", head->value);
  head = head->next;
 }
 return 0;
}
https://ideone.com/Wj9ocK

it seems like often it is easier to come up with a recursive solution. here is one: recursively go the the end of the list and then, on winding back, attach "prior" nodes as "next"s to the new head
#include 
using namespace std;

struct List {
 int value = 0;
 List* next = nullptr;
 List(int x) : value(x) {}
};

List* reverse(List* head) {
  List* list = head;
  List* new_head = list;
  if (list->next != nullptr) {
     list = reverse(list->next);
     new_head = list;
     while (list->next != nullptr) {
      list = list->next;
     }
     list->next = head;
     head->next = nullptr;
  }
  return new_head;
}

int main() {
 List* head = new List(1);
 List* list = head;
 for (int index = 2; index < 10; index++) {
  List* next = new List(index);
  list->next = next;
  list = next;
 }
 head = reverse(head);
 
 while (head != nullptr) {
  printf("%d\n", head->value);
  head = head->next;
 }
 return 0;
}
https://ideone.com/Lcfc4r

Sunday, October 23, 2016

nodejs postgres pg.client returning partial results in json

i had a very weird problem with a nodejs and postgre app i'm building:
i'm running a sql query with join in dbeaver:
select matches.match_date, t1.team_long, t1.team_short, t1.id, 
t1.logo, t2.team_long, t2.team_short, t2.id, t2.logo 
from teams t1, teams t2, matches 
where t1.id=matches.host_team_id 
and t2.id=matches.guest_team_id
and in dbeaver it is returning the expected result
match_date team_long team_short 
2016-11-22 Juventus JUVE 
id logo team_long team_short id logo
6 1juventus.png Everton EVE 7 1everton.png
which includes all expected columns.
but when run in my node app with pg client, i'm only receiving a portion of the columns in the resulting json:
{"match_date":"2016-11-22","team_long":"Everton",
"team_short":"EVE","id":7,"logo":"everton-badge-2014-90x90.png"}
in the above json, the data for Juventus is missing.
for some crazy reason, i thought.

here is the js code i'm using to read the data in node:
// SQL Query > Select Data
const query = client.query(' select matches.match_date, 
t1.team_long as host_team_long, t1.team_short 
as host_team_short, 
t1.id as host_id, t1.logo as host_logo, 
t2.team_long as guest_team_long, 
t2.team_short as guest_team_short, t2.id guest_id, 
t2.logo as guest_logo from teams t1, 
teams t2, matches where t1.id=matches.host_team_id 
and t2.id=matches.guest_team_id');

// Stream results back one row at a time
query.on('row', (row) => {
    console.log(row);
    resultData.push(row);
});
so, somewhere here hides the key to the weird behavior.
but what could it be???
is it something in the postgre db 'driver'?
or nodejs itself?

about an hour of guessing later, i turned to write a question about this problem on stackoverflow.com.

copy/paste the sql query, copy paste the results...should i include the column names as well?
let's do it for readibility...

wait a second!

the column names for the same fields of different records are the same!
but, but, but - how will this project in the json results?

apparently you cannot have two properties with the same name so....SOOOOOOOO...here lies the reason for my 'trimmed' results!

whatever json lib the pg client is using it doesn't care (perhaps rightly so, perhaps not) that we may be overwriting values in result of a sql query


 schoooop

quickly changing the sql query with custom result column names (using 'as') solved the problem! here are the correct and beautiful results:
{ match_date: '2016-10-22',
  host_team_long: 'Atl├ętico de Madrid',
  host_team_short: 'ATL',
  host_id: 3,
  host_logo: 'Atletico_Madrid.png',
  guest_team_long: 'Internazionale',
  guest_team_short: 'INT',
  guest_id: 8,
  guest_logo: 'Inter_Milan.png' }


on to the next problem!
cya!