Amazon Interview Question
Software Engineer in Testsuse Data::Dumper;
%h = (a=>0,b=>1,c=>[{'one'=>1,'two'=>2},{1=>'one',2=>'two'},{'number'=>'decimals'},{3 =>'alphas'},'sample']);
%hash = ('abc'=>[123,456,789],'pqr'=>345,'xyz'=>567,'opq'=>'word','lmn'=>\%h,'hello'=>{'zhang'=>'yixing','michael'=>'zhang'});
while($input = <STDIN>) {
chomp($input);
print search(\%hash,$input);
print "\n";
}
sub search {
my $dataRef = shift;
my $key = shift;
if(exists $dataRef->{$key}) {
return $dataRef->{$key};
}
foreach $temp (keys %$dataRef) {
if(ref($dataRef->{$temp}) eq 'HASH') {
$temp = search($dataRef->{$temp},$key);
if($temp) {
return $temp;
}else {
next;
}
}if(ref($dataRef->{$temp}) eq 'ARRAY') {
return searchArray($dataRef->{$temp},$key);
}
}
}
sub searchArray {
my $dataRef = shift;
my $key = shift;
foreach my $element (@$dataRef) {
if(ref($element) eq 'ARRAY') {
return searchArray($element, $key);
}if(ref($element) eq 'HASH') {
$temp = search($element,$key);
if($temp) {
return $temp;
}else {
next;
}
}
}
}
use Data::Dumper;
%h = (a=>0,b=>1,c=>[{'one'=>1,'two'=>2},{1=>'one',2=>'two'},{'number'=>'decimals'},{3 =>'alphas'},'sample']);
%hash = ('abc'=>[123,456,789],'pqr'=>345,'xyz'=>567,'opq'=>'word','lmn'=>\%h,'hello'=>{'zhang'=>'yixing','michael'=>'zhang'});
while($input = <STDIN>) {
chomp($input);
print search(\%hash,$input);
print "\n";
}
sub search {
my $dataRef = shift;
my $key = shift;
if(exists $dataRef->{$key}) {
return $dataRef->{$key};
}
foreach $temp (keys %$dataRef) {
if(ref($dataRef->{$temp}) eq 'HASH') {
$temp = search($dataRef->{$temp},$key);
if($temp) {
return $temp;
}else {
next;
}
}if(ref($dataRef->{$temp}) eq 'ARRAY') {
return searchArray($dataRef->{$temp},$key);
}
}
}
sub searchArray {
my $dataRef = shift;
my $key = shift;
foreach my $element (@$dataRef) {
if(ref($element) eq 'ARRAY') {
return searchArray($element, $key);
}if(ref($element) eq 'HASH') {
$temp = search($element,$key);
if($temp) {
return $temp;
}else {
next;
}
}
}
}
##################################################
# Function IsArray #
# Input: reference #
# Output: 1 iff input is a reference to an array #
##################################################
sub IsArray{
if(ref($_[0]) eq 'ARRAY'){
1;
}else{
0;
}
}
##################################################
# Function IsHash #
# Input: reference #
# Output: 1 iff input is a reference to a Hash #
##################################################
sub IsHash{
#print "DEBUG-------->",ref($_[0]),"\n";
if(ref($_[0]) eq 'HASH'){
1;
}else{
0;
}
}
##################################################
# Function Search #
# Input: nested hash , key #
# Output: If key exists in the hash at any level,#
# output the value, otherwise undef #
# Algorithm: Recursively go on the values of the #
# input hash / array. #
##################################################
sub Search{
my ($hashRef , $key ) = @_;
# print "DEBUG2 ----> Seaching for $key\n";
# Input is a hash - check for the key, and if not go through the other values
if (IsHash($hashRef)) {
if (exists($$hashRef{$key})) {
return ($$hashRef{$key});
}
# Recursively go through the values of the hash
for (values %$hashRef) {
if (IsArray($_) or IsHash($_)) {
my $temp = Search($_,$key);
if (defined $temp) {
return $temp
}
}
}
}
if (IsArray($hashRef)) {
# Recursively go through the values of the array
for (@$hashRef) {
if (IsArray($_) or IsHash($_)) {
my $temp = Search($_,$key);
if (defined $temp) {
return $temp
}
}
}
}
return undef;
}
One recursive function:
sub search {
my ($hashref, $search_key) = @_;
my $ret_val = undef;
return $ret_val if ref($hashref) ne 'HASH';
while ( my ($key, $val) = each %$hashref) {
if ($key eq $search_key) {
return $val;
} elsif (ref($val) eq 'HASH') {
$ret_val = search($val, $search_key);
} elsif (ref($val) eq 'ARRAY') {
foreach my $h (grep {ref($_) eq 'HASH'} @$val) {
$ret_val = search($h, $search_key);
}
}
}
return $ret_val;
}
# Recursion makes the solution easy
sub search_hash {
my $hash_ref = shift;
my $search_key = shift;
foreach my $key (keys %$hash_ref) {
if ($key eq $search_key) {
if (ref($hash_ref->{$key}) eq 'ARRAY') {
print Dumper($hash_ref->{$key});
return;
}
elsif (ref($hash_ref->{$key}) eq 'HASH') {
print Dumper($hash_ref->{$key});
return;
}
elsif (ref($hash_ref->{$key}) eq '') {
print $hash_ref->{$key};
return;
}
}
elsif (ref($hash_ref->{$key}) eq 'HASH') {
search_hash($hash_ref->{$key}, $search_key);
}
elsif (ref($hash_ref->{$key}) eq 'ARRAY') {
search_array($hash_ref->{$key}, $search_key);
}
}
}
sub search_array {
my $arr_ref = shift;
my $search_key = shift;
foreach my $elem (@$arr_ref) {
if (ref($elem) eq 'HASH') {
search_hash($elem, $search_key);
}
if (ref($elem) eq 'ARRAY') {
search_array($elem, $search_key);
}
}
}
sub search {
my $hash_ref = shift;
my $srch_key = shift;
foreach my $key ( keys(%{$hash_ref}) ) {
if( $key eq $srch_key ) {
print "\nFound! " . $hash_ref->{$key};
return $hash_ref->{$key};
} else {
print "\nref $key == ". ref($hash_ref->{$key});
if( ref($hash_ref->{$key}) =~ /HASH/ ) {
return search($hash_ref->{$key},$srch_key);
} elsif( ref($hash_ref->{$key}) =~ /ARRAY/ ) {
my @array = @{$hash_ref->{$key}};
foreach my $element ( @array) {
if( ref($element) =~/HASH/ ) {
my $val = search($element, $srch_key);
return $val unless $val == '';
}
}
}
}
}
} # end sub search
- Abhishek May 21, 2010