Interviewstreet CS 2 - Fraud Prevention
This challenge was posted by Groupon.
--
This isn't an algorithmic problem. Therefore, I think it's quite simple. My solution was in PHP:
--
This isn't an algorithmic problem. Therefore, I think it's quite simple. My solution was in PHP:
Spoiler
<?php
class GrouponFraud {
private $fraud;
public function __construct() {
// Index elements
define('ORDER_ID', 0);
define('DEAL_ID', 1);
define('EMAIL', 2);
define('STREET', 3);
define('CITY', 4);
define('STATE', 5);
define('ZIP', 6);
define('CC', 7);
define('ORDER', 8);
$this->fraud = array();
}
// Get the fraudulent cases
public function getFraud() {
ksort($this->fraud);
return $this->fraud;
}
// Whether or not an order is deemed fraudulent
public function isFraud($order, $subset) {
$count = 0;
foreach ( $subset as $sOrder ) {
if ( ( is_array( $order ) && is_array( $sOrder ) ) == false ) {
continue;
}
if ( $this->isFraud1($order, $sOrder) || $this->isFraud2($order, $sOrder) ) {
$this->fraud[intval($order[ORDER_ID])] = true;
$this->fraud[intval($sOrder[ORDER_ID])] = true;
return true;
}
}
return false;
}
// Let's check the first condition - same email, different credit card
private function isFraud1($order, $comparison) {
if ( $this->equalArray($order, $comparison) == true ) {
return false;
}
return $this->sameEmail( $order[email], $comparison[email] ) == true && ( $this->sameCC($order[cc], $comparison[cc]) == false );
}
// Let's check the second condition - same address/city/state/zip, different CC, regardless of emailo
private function isFraud2($order, $comparison) {
// If the two arrays are identical, we can just return false - they're the same order, no fraud here.
if ( $this->equalArray($order, $comparison) == true ) {
return false;
}
return ( $this->sameStreet($order[street], $comparison[street]) && $this->sameState( $order[state], $comparison[state] ) && $this->sameZip( $order[zip], $comparison[zip] ) && $this->sameCity($order[city], $comparison[city]) );
}
// Checks whether two credit cards are the same
private function sameCC($cc1, $cc2) {
return $this->cleanCC($cc1) == $this->cleanCC($cc2);
}
// Clean the credit card
private function cleanCC($cc) {
return preg_replace('/[^\d]/', '', $cc);
}
// Checks whether two orders have the same city
private function sameCity($city1, $city2) {
return $this->cleanCity($city1) == $this->cleanCity($city2);
}
// 'Clean' the city
private function cleanCity($city) {
return strtolower($city);
}
// Checks whether the zip code is the same for two order
private function sameZip($zip1, $zip2) {
return $this->cleanZip($zip1) == $this->cleanZip($zip2);
}
// 'Cleans' the zip code
private function cleanZip($zip) {
return preg_replace('/[^\d]/', '', $zip);
}
// Checks whether 2 orders have the same state
private function sameState($state1, $state2) {
return $this->cleanState($state1) == $this->cleanState($state2);
}
// 'Clean' the state
private function cleanState($state) {
$clean = strtolower($state);
$clean = $this->removeWhitespace($clean);
if ( $clean == 'il' ) {
$clean = 'illinois';
}
else if ( $clean == 'ca' ) {
$clean = 'california';
}
else if ( $clean == 'ny' ) {
$clean = 'new york';
}
return $clean;
}
// Remove excess whitespace
private function removeWhitespace($clean) {
$clean = trim($clean);
$clean = preg_replace('/\s\s+/', ' ', $clean);
if ( in_array( substr($clean, -1 ), array("\n", "\t", "\r", " " ) ) ) {
$clean = substr($clean, 0, strlen($clean) - 1 );
}
if ( in_array( substr($clean, 0, 1 ), array("\n", "\t", "\r", " " ) ) ) {
$clean = substr($clean, 1, strlen($clean) );
}
return $clean;
}
// Checks whether 2 orders have the same street
private function sameStreet($street1, $street2) {
return $this->cleanStreet($street1) == $this->cleanStreet($street2);
}
// 'Clean' the street
public function cleanStreet($street) {
$clean = strtolower($street);
$clean = $this->removeWhitespace($clean);
$clean .= PHP_EOL;
$clean = str_replace( array(' street' . PHP_EOL, ' road' . PHP_EOL), array(' st.', ' rd.'), $clean );
$clean = str_replace(PHP_EOL, '', $clean);
return $clean;
}
// Checks whether two arrays are identical
private function equalArray($arr1, $arr2) {
return ! array_diff( $arr1, $arr2 ) && ! array_diff( $arr2, $arr1 );
}
//private Checks whether or not they have the same email address
private function sameEmail($first, $second) {
return $this->cleanEmail($first) == $this->cleanEmail($second);
}
// 'Clean' an email (remove all attempts to trick it)
private function cleanEmail($email) {
$clean = strtolower($email);
$clean = $this->removeWhitespace($clean);
$username = current(explode("@", $clean));
$rest = str_replace($username, '', $clean); // Rest of the email portion
$username = str_replace('.', '', $username); // Remove full stops
$username = current(explode("+", $username, 2)); // Remove all plus signs
return $username . $rest;
}
}
$input = '5
1,1,bugs@BUNNY.com,123 Sesame St.,New York,NY,10011,12345689010
3,4,bugs+bunny@bunny.com,123 Sesame St.,New York,NY,10011,12345689010
2,2,elmer@fudd.com,123 Sesame St.,New York,NY,10011,10987654321
5,6,bugs@bunny.com,123 Sesame street,New York,NY,10011,123456839010
4,3,bugs@bunny.com,123 Sesame street,New York,NY,10011,123456839010';
// Sort the orders in to deals by deal id
$grouponFraud = new GrouponFraud;
$orders = array();
foreach ( explode( "\n", $input ) as $id => $order ) {
if ( $id == 0 ) {
$limit = (int) $order;
continue;
}
if ( $id > $limit ) {
break;
}
list($orderId, $dealId,$rest) = explode(",", $order, 3);
$arr = explode(",", $order, 8);
$arr[] = $id;
$orders[intval($dealId)][] = $arr;
}
// Let's detect fraudulent errors
foreach ( $orders as $dealId => $subset ) {
foreach ( $subset as $order ) {
$grouponFraud->isFraud( $order, $subset );
}
}
// Let's output the fraudulent cases
$str = "";
foreach ( $grouponFraud->getFraud() as $id => $val ) {
$str .= $id . ",";
}
if ( strlen( $str ) > 0 ) {
$str = substr( $str, 0, strlen($str) - 1 );
}
echo $str;[/city][/city][/zip][/zip][/state][/state][/street][/street][/cc][/cc][/email][/email]