Categories
General

Number of Visible Nodes Facebook

There is a binary tree with N nodes. You are viewing the tree from its left side and can see only the leftmost nodes at each level. Return the number of visible nodes.Note: You can see only the leftmost nodes, but that doesn’t mean they have to be left nodes. The leftmost node at a level could be a right node.Signature int visibleNodes(Node root) {Input The root node of a tree, where the number of nodes is between 1 and 1000, and the value of each node is between 0 and 1,000,000,000Output An int representing the number of visible nodes.Example

            8  <------ root
           / \
         3    10
        / \     \
       1   6     14
          / \    /
         4   7  13            

output = 4

<?php

// Add any extra import statements you may need here


class TreeNode{
  public $val;
  public $left;
  public $right;
  public function __construct($val=0) {
    $this->val = $val;
    $this->left = NULL;
    $this->right = NULL;
  }
}

// Add any helper functions you may need here


function visibleNodes($root) {
        $result = [];
        
        $numberVisibleNode = 1;
 
        dfs($root, $result, $numberVisibleNode);
       
        return  max($result);;
    }
    
     function dfs(TreeNode $currentNode, array &$result,$numberVisibleNode )  {
        if(($currentNode->left === null)  && ($currentNode->right === null)) {
                   
           // var_dump($currentNode->val.' '.$numberVisibleNode);
            $result[$currentNode->val] = $numberVisibleNode;
            return ;
        }
        
        if($currentNode->left != null) {
          //  var_dump('leftside '.$currentNode->val.' '.$numberVisibleNode);
            $numberVisibleNodeLeft = $numberVisibleNode;
            $numberVisibleNodeLeft++; #2
            dfs($currentNode->left, $result, $numberVisibleNodeLeft);
        }
        
        if(($currentNode->right !== null)) {
           // var_dump('righttside '.$currentNode->val.' '.$numberVisibleNode);
            $numberVisibleNodeRight = $numberVisibleNode;
            $numberVisibleNodeRight++;#5,
            dfs($currentNode->right, $result, $numberVisibleNodeRight);
        }
    }

Categories
General

Reverse to Make Equal Facebook

Given two arrays A and B of length N, determine if there is a way to make A equal to B by reversing any subarrays from array B any number of times.Signature bool areTheyEqual(int[] arr_a, int[] arr_b)Input All integers in array are in the range [0, 1,000,000,000].Output Return true if B can be made equal to A, return false otherwise.Example A = [1, 2, 3, 4] B = [1, 4, 3, 2] output = trueAfter reversing the subarray of B from indices 1 to 3, array B will equal array A.

function areTheyEqual($s, $t) {
  
  // Write your code here
  $arr_a = $s;
  $arr_b = $t;
  
  $isEqual = false;
            $hashMapArrayA = array();
            $hashMapArrayB = array();

            #sanity check 
            $sizeArr_a = count($arr_a); #4
            $sizeArr_b = count($arr_b); #4
            if ($sizeArr_a !== $sizeArr_b)
            {
                return false;

            }
            
            #building hashMapA
            #hashMapA[1] = 1
            #hashMapA[2] = 1
            #hashMapA[3] = 1
            #hashMapA[4] = 1
            foreach ($arr_a as $key => $value) {
                if(array_key_exists($value, $hashMapArrayA)){
                    $hashMapArrayA[$value] = $hashMapArrayA[$value] + 1;     
                } else {
                    $hashMapArrayA[$value] = 1;
                }
            }



            #building hashMapB
            #hashMapB[1] = 1
            #hashMapB[2] = 1
            #hashMapB[3] = 1
            #hashMapAB[4] = 1

            foreach ($arr_b as $key => $value) {
                if(array_key_exists($value, $hashMapArrayB)){
                    $hashMapArrayB[$value] = $hashMapArrayB[$value] + 1;     
                } else {
                    $hashMapArrayB[$value] = 1;
                }
            }

            
            #sanity check 
            $sizehashMapArrayB = count($hashMapArrayB); #4
            $sizehashMapArrayA = count($hashMapArrayA); #4
            if ($sizehashMapArrayA !== $sizehashMapArrayB)
            {
                return false;
            }
            

            foreach($hashMapArrayA as $key => $valueA) {
                #hashMapA[1] exist
                #hashMapA[1] == hashMapB[1] equals
                #hashMapA[1] exist
                #hashMapA[1] == hashMapB[1] equals

                if(!array_key_exists($key, $hashMapArrayB))
                {
                    return false;
                }
                    
                if ($hashMapArrayA[$key] !== $hashMapArrayA[$key]) 
                {
                    return false;;
                 }

            }
            
                foreach($hashMapArrayB as $key => $valueB) {
                #hashMapA[1] exist
                #hashMapA[1] == hashMapB[1] equals
                #hashMapA[1] exist
                #hashMapA[1] == hashMapB[1] equals
                    


                if(!array_key_exists($key, $hashMapArrayA))
                {
                    return false;
                }
                    
                if ($hashMapArrayB[$key] !== $hashMapArrayA[$key]) 
                {
                    return false;;
                 }
            }
            

  
            $isEqual = true;
            return $isEqual;
}  
Categories
General

Passing Yearbooks Facebook

There are n students, numbered from 1 to n, each with their own yearbook. They would like to pass their yearbooks around and get them signed by other students.You’re given a list of n integers arr[1..n], which is guaranteed to be a permutation of 1..n (in other words, it includes the integers from 1 to n exactly once each, in some order). The meaning of this list is described below.Initially, each student is holding their own yearbook. The students will then repeat the following two steps each minute: Each student i will first sign the yearbook that they’re currently holding (which may either belong to themselves or to another student), and then they’ll pass it to student arr[i-1]. It’s possible that arr[i-1] = i for any given i, in which case student i will pass their yearbook back to themselves. Once a student has received their own yearbook back, they will hold on to it and no longer participate in the passing process.It’s guaranteed that, for any possible valid input, each student will eventually receive their own yearbook back and will never end up holding more than one yearbook at a time.You must compute a list of n integers output, whose element at i-1 is equal to the number of signatures that will be present in student i’s yearbook once they receive it back.

Signature

int[] findSignatureCounts(int[] arr)

Input

n is in the range [1, 100,000]. Each value arr[i] is in the range [1, n], and all values in arr[i] are distinct.

Output

Return a list of n integers output, as described above.

Example 1

  • Student 1 signs their own yearbook. Then they pass the book to the student at arr[0], which is Student 2.
  • Student 2 signs their own yearbook. Then they pass the book to the student at arr[1], which is Student 1.

n = 2 arr = [2, 1] output = [2, 2]Pass 1:

Pass 2:

  • Student 1 signs Student 2’s yearbook. Then they pass it to the student at arr[0], which is Student 2.
  • Student 2 signs Student 1’s yearbook. Then they pass it to the student at arr[1], which is Student 1.

Pass 3:

  • Both students now hold their own yearbook, so the process is complete.

Each student received 2 signatures.

Example 2

n = 2 arr = [1, 2] output = [1, 1]Pass 1:

  • Student 1 signs their own yearbook. Then they pass the book to the student at arr[0], which is themself, Student 1.
  • Student 2 signs their own yearbook. Then they pass the book to the student at arr[1], which is themself, Student 2.

Pass 2:

  • Both students now hold their own yearbook, so the process is complete.

function findSignatureCounts($arr) {
  foreach ($arr as $index => $studentNumber) {
   //   var_dump('Book for student '.$studentNumber);

    $bookedSigned[$studentNumber] = [$studentNumber];
  
    dfs($arr[$studentNumber - 1], $studentNumber, $index, $bookedSigned, $arr);
    
    $result[] = count($bookedSigned[$studentNumber] );
   
    
}

//var_dump('$result');
//var_dump($result);

  return $result;


  
}



function dfs($newStudentNumber, $studentNumber, $studentIndex, &$bookedSigned, $arr) {
    if(in_array($newStudentNumber, $bookedSigned[$studentNumber])){
        return;        
    }
    $bookedSigned[$studentNumber][] = $newStudentNumber;
     // var_dump( 'for student '.$studentNumber.' Book signed by');
    //  var_dump($bookedSigned[$studentNumber] );
    
    if(($studentNumber - 1) < 0) {
        return;        
    }



     dfs($arr[$newStudentNumber - 1], $studentNumber, $studentIndex, $bookedSigned, $arr);
}

Categories
General

Rotational Cipher Facebook

One simple way to encrypt a string is to “rotate” every alphanumeric character by a certain amount. Rotating a character means replacing it with another character that is a certain number of steps away in normal alphabetic or numerical order.For example, if the string “Zebra-493?” is rotated 3 places, the resulting string is “Cheud-726?”. Every alphabetic character is replaced with the character 3 letters higher (wrapping around from Z to A), and every numeric character replaced with the character 3 digits higher (wrapping around from 9 to 0). Note that the non-alphanumeric characters remain unchanged.Given a string and a rotation factor, return an encrypted string.

Signature

string rotationalCipher(string input, int rotationFactor)

Input

1 <= |input| <= 1,000,000 0 <= rotationFactor <= 1,000,000

Output

Return the result of rotating input a number of times equal to rotationFactor.

Example 1

input = Zebra-493? rotationFactor = 3 output = Cheud-726?

Example 2

input = abcdefghijklmNOPQRSTUVWXYZ0123456789 rotationFactor = 39 output = nopqrstuvwxyzABCDEFGHIJKLM9012345678

function rotationalCipher($input, $rotation_factor) {
  
            for($i=0; $i< 26;$i++) {
              $letter = chr(97 + $i);
              $alphabetMap[$letter] = $i;
          }   
   
        $newString = '';
        $input = str_split($input);
        foreach ($input as $item) {
            #Da
            //Sanity Check
            if(!ctype_alpha($item) && !is_numeric($item))
            {
                 $newString .= $item;
            }
            //if character
            if(ctype_alpha($item))
            {
                #item D;a
                $initialstateUpperCase = false; 
                if (ctype_upper($item)) {
                    $initialstateUpperCase = true; #D
                    $item = strtolower($item);  #d
                }
                
                $value = $alphabetMap[$item]; #3;0
                $newValue = $value + $rotation_factor; #5;2
                if($newValue > 26) {
                    $newValue = $newValue % 26;
                }
                $newCharacter = array_search($newValue, $alphabetMap); #f;c
                if($initialstateUpperCase === true)
                {
                    $newCharacter = strtoupper($newCharacter);    #F
                }
            
                $newString .= $newCharacter; #Fc
            }
            
            
            //if integer
            if(is_numeric($item))
            {
                $newValue = $item + $rotation_factor;
                if($newValue > 10) {
                    $newValue = $newValue % 10;
                }
                $newString .= $newValue;
            }
        }
            return $newString;            
  
  
}  

Categories
General

Contiguous Subarrays Facebook

You are given an array arr of N integers. For each index i, you are required to determine the number of contiguous subarrays that fulfill the following conditions:

  • The value at index i must be the maximum element in the contiguous subarrays, and
  • These contiguous subarrays must either start from or end on index i.

Signature int[] countSubarrays(int[] arr)Input

  • Array arr is a non-empty list of unique integers that range between 1 to 1,000,000,000
  • Size N is between 1 and 1,000,000

Output An array where each index i contains an integer denoting the maximum number of contiguous subarrays of arr[i]Example: arr = [3, 4, 1, 6, 2] output = [1, 3, 1, 5, 1]Explanation:

  • For index 0 – [3] is the only contiguous subarray that starts (or ends) with 3, and the maximum value in this subarray is 3.
  • For index 1 – [4], [3, 4], [4, 1]
  • For index 2 – [1]
  • For index 3 – [6], [6, 2], [1, 6], [4, 1, 6], [3, 4, 1, 6]
  • For index 4 – [2]

So, the answer for the above input is [1, 3, 1, 5, 1]

 function countSubarrays(array $arr){
        $result = array();
        
        #traverse the $arr
        
        foreach ($arr as $index => $value){
            # index 0 value 3 
            # index 1 value 4
            
            # index 3 value 6

            $totalCountSubArray = 1;
            
             # 0
                $countSubbarrayLeftToRight = 
                    leftToRightSlidingWindow($index, $arr, $value);
                    
                
             # 0
                $countSubbarrayRightToleft = 
                    rightToLeftSlidingWindow($index, $arr, $value);
                    
            #$result[1]; 
                $result[] = $totalCountSubArray + 
                    $countSubbarrayLeftToRight + 
                    $countSubbarrayRightToleft;
            
        }
        
        return $result;
    }
Categories
General

Pair Sums Facebook

Pair SumsGiven a list of n integers arr[0..(n-1)], determine the number of different pairs of elements within it which sum to k.If an integer appears in the list multiple times, each copy is considered to be different; that is, two pairs are considered different if one pair includes at least one array index which the other doesn’t, even if they include the same values.

Signature

int numberOfWays(int[] arr, int k)

Input

n is in the range [1, 100,000]. Each value arr[i] is in the range [1, 1,000,000,000]. k is in the range [1, 1,000,000,000].

Output

Return the number of different pairs of elements which sum to k.

Example 1

n = 5 k = 6 arr = [1, 2, 3, 4, 3] output = 2The valid pairs are 2+4 and 3+3.

Example 2

n = 5 k = 6 arr = [1, 5, 3, 3, 3] output = 4There’s one valid pair 1+5, and three different valid pairs 3+3 (the 3rd and 4th elements, 3rd and 5th elements, and 4th and 5th elements).


class Solution {
    
    public function __construct(){
        
    }
    
    public function numberOfWays(array $arr, int $k) : int {
        sort($arr); # [1,3,3,3,5]
        $sortedArr = $arr;
        

        
        $p1PrevValue = null;
        $p1Index = 0;
        $p2Index = count($sortedArr) - 1; #$p2Index 4
        $p2Value = $sortedArr[$p2Index]; #$p2Value 5
        $prevP1 = null;
        $countOfWays = 0;
        
        #traverse array
         #$p1Index 0
        #$p2Index 4

        
        while ($p1Index < $p2Index) {
            $p1Value = $sortedArr[$p1Index]; # 1;3,3
            $p2Value = $sortedArr[$p2Index]; # 3;3,3


            
            if($p1Value + $p2Value === $k) { 
                $countOfWays++; #1;2;3
                if($p1Value === $p1PrevValue) {
                    $countOfWays++; #4
                }
                $p1PrevValue = $p1Value; #1;3
                $p1Index++;# 1;2,3
            }
            
            if($p1Value + $p2Value > $k) {
                $p2Index--; #3
            }

            if($p1Value + $p2Value < $k) {
                $p1Index++;
            }
        }
    return $countOfWays;

    }
}

$solution = new Solution();
$k = 6;
$arr = [1,5,3,3,3];

$countOfWays = $solution->numberOfWays($arr, $k);

var_dump($countOfWays);
Categories
General

Phone Numbers

<?php

class Solution {

    private $hasmapExistingLetters;
    private $phoneKeyPad =
        array(
            1 => [],
            2 => ['a','b','c'],
            3 => ['d','e','f'],
            4 => ['g','h','i'],
            5 => ['j','k','l'],
            6 => ['m','n','o'],
            7 => ['p','q','r','s'],
            8 => ['t','u','v'],
            9 => ['w','x','y','z']
        );

    public function __construct(string $phonenumber){
        $this->hasmapExistingLetters = $this->buildHashmap($phonenumber);
        // var_dump($this->hasmapExistingLetters);
    }

    #364
    public function buildHashmap(string $phonenumber ) {
        $phonenumber = str_split($phonenumber);

        foreach ($phonenumber as $index => $singleDigit) {

            # singleDigit = 3 inex =0    
            $letters = $this->phoneKeyPad[$singleDigit];
            #letters =    ['d','e','f'],


            foreach ($letters as $letter){
                #hasmapExistingLetters['d'] = 0;   
                #hasmapExistingLetters['e'] = 0;   
                #hasmapExistingLetters['f'] = 0;   

                #hasmapExistingLetters['m'] = 1;   
                #hasmapExistingLetters['n'] = 1;   
                #hasmapExistingLetters['o'] = 1;   

                #hasmapExistingLetters['g'] = 2;   
                #hasmapExistingLetters['h'] = 2;   
                #hasmapExistingLetters['i'] = 2;   
                //var_dump($letter);
                $hasmapExistingLetters[$letter] = $index;
            }
        }

        // var_dump($hasmapExistingLetters);
        return $hasmapExistingLetters;
    }


    public function returnValidWords( array $validWordsInput) : array {

        foreach ($validWordsInput as $word) {
            #dog
            $validWord = true;
            //var_dump($wordToDissect);
            $len = strlen($word);
            for ($index=0; $index < $len; $index++) {
                # 0 => d
                # 1 => o
                # 2 => g
                $letter = $word[$index];

                if(!array_key_exists($letter, $this->hasmapExistingLetters)
                    && $this->hasmapExistingLetters[$letter] !== $index) {
                    $validWord = false;
                }
            }

            if($validWord === true)
                $resultValidWord[] = $word;
        }
        return $resultValidWord;
    }
}



$phoneNumber = '364';

$validWords =
    array('dog','fog','fish','water');

$solution = new Solution($phoneNumber);

$result = $solution->returnValidWords($validWords);

var_dump($result);




#build hasmap

#each validwords
#iterate through each letter
#check if ! exist in hasmap && index === validWord -> index
#return false
#return true

#resultValidword [] = theword

#return resultValidword;
#var_dump($phoneKeyPad);

Categories
General

Climbing stairs solution – similar to fibonnaci sequence

<?php


class Solution
{

    public static function climbingStairs(int $numberOfStairs)
    {
        $numberOfWays = 0;
        $numberOfWays = self::climbingStairsHelper($numberOfStairs);

        return $numberOfWays;
    }

    public static function climbingStairsHelper($numberOfStairs)
    {
        if ($numberOfStairs <= 0) {
            return 1;
        }
        return self::climbingStairsHelper($numberOfStairs - 1) + self::climbingStairsHelper($numberOfStairs - $numberOfStairs - 2);
    }

    public static function climbingStairsMemoization(int $numberOfStairs)
    {
        $numberOfWays = 0;
        $memo = array();
        for ($i = 0; $i < $numberOfStairs; $i++) {
            $memo[$i] = 0;
        }

        $memo[0] = 0;
        $memo[1] = 2;

        $numberOfWays = self::climbingStairsHelper($numberOfStairs, $memo);

        return $numberOfWays;
    }

    public static function climbingStairsHelperMemoization($numberOfStairs, &$memo)
    {

        if ($numberOfStairs <= 0) {
            return 1;
        }


        return self::climbingStairsHelper($numberOfStairs - 1) + self::climbingStairsHelper($numberOfStairs - $numberOfStairs - 2);
    }

}


//    var_dump(Solution::climbingStairs(2));

var_dump(Solution::climbingStairsMemoization(5));
Categories
General

Longest Substring Without Repeating Characters – Sliding Window

class Solution {
/**
 * @param String $s
 * @return Integer
 */
function lengthOfLongestSubstring($s) {
    $len = strlen($s);
    $max = 0;
    $tempMax = 0;
    $freq = array();

    #loop through array
    for($i = 0; $i < $len; $i++){


        #if IN character in freq array
        if(array_key_exists($s[$i], $freq)) {
            var_dump( $s[$i]);
            $max = max($max, $tempMax);
            $tempMax = 0;
            $this->resetFreq($freq);
        }
        else {
            #if not in freq array
            $freq[$s[$i]] = 1;
            $tempMax +=1 ;
        }

   }
    return $max;
}
public function resetFreq(array $freq) : array {

    return array();
}
}

Categories
General

Why Laravel valet on windows + VPN is not working ?

I am a mac user but I had to help some members of my team to get laravel running on their professional windows laptop running VPN

Solution found was to go to the following file

#1 – c:\Windows\System32\Drivers\etc\hosts

#2 – comment all lines with 127.0.0.1

#3 – add one line with the 127.0.0.1 and the url of the laravel valet app that you desire to get running

127.0.0.1. yourlaravel.test