Category: General

class Solution {
    
    public function palindrome2 (string $s) : bool {
        #aba - true
        #abca - 
        #abc - 
        
        $n = strlen($s); #4
        $p1 = 0;
        $p2 = $n - 1 ; #3
        $mid = floor(($n - 1) / 2); #1
        $charRemoved = false;
        
        while($p1 < $mid || $p2 > $mid) 
        {

            
            # p1:1 < mid:1 OR 
            # p2:2 > mid:1
            if ($s[$p1] == $s[$p2]) {
                $p1++; #1
                $p2--;  #1
                continue;
            }
            
            if($s[$p1+1] == $s[$p2] && $charRemoved ==false) {
                $p1 = $p1 + 1;
                $charRemoved = true;
                continue;
            } else if ($s[$p1+1] == $s[$p2] && $charRemoved == true) {
                return false;
            }

            if($s[$p2-1] == $s[$p1] && $charRemoved ==false) {
                $p2 = $p2 - 1;
                $charRemoved = true;
                continue;
            } else if ($s[$p2-1] == $s[$p1] && $charRemoved == true) {
                return false;
            }
            
            if(($s[$p1] != $s[$p2]) && ($p1 + 1 == $mid || $p2 - 1 == $mid) ) {
                return false;
            }
        }
        
        if($s[$p1] != $s[$p2] && (($n % 2) == 0)) {
            return true;
        }
        
        return true;
    }
    
}

$res = new Solution();
var_dump($res->palindrome2('abbca'));

Steps to delete qa branch

Step 1 – delete locally

git branch -d dev

Step 2 – delete remotely

git push origin origin/dev
git push origin --delete origin/dev

class Solution {

    
    public function screenFitting($rows, $cols, $sentence)
    {
        # intiialization
        $numberWords = count($sentence);
        $wordIndex = 0;
        $c = 0;
        $r = 0;

        # loop foreach row
        while($r < $rows && $c < $cols) {
            
                $wordLength = strlen($sentence[$wordIndex]); # 5 {hello} ; 5 {world}
                if(($c + $wordLength) < $cols) { # 5 < 7 ;  !! 11 < 7 ; 5 < 7; !! 11 < 7
                    $c += $wordLength;   # 5 ; 7
                    $hashmap[$sentence[$wordIndex]] += 1;
                    $wordIndex++; #1 

                    var_dump($hashmap);
                } else {
                    $r++;  #1 
                    $c = 0;
                    continue;
                }
                $c++; # 6

                if($wordIndex === $numberWords) {
                    $wordIndex = 0;
                }
            }
            
        return min($hashmap);
    }
}

$rows = 2;
$cols = 7;
$sentence = ['hello', 'world'];

$sentence = ["i","had","apple","pie"];
$rows = 4;
$cols = 15;
$solution = new Solution();
$res = $solution->screenFitting($rows, $cols, $sentence);

var_dump($res);

Simplified solution

$s = ["hello", "world"];
$cols = 7;
$rows = 6;

$col = 0;
$row = 0;
$i = 0;

$count = 0;;
while($row < $rows) 
{
    while($col < $cols) 
    {        
        $col = $col + strlen($s[$i]);
        if($col < $cols)  {
            continue;
        }
        $i++;
        if($i == 2) {
            $i = 0;
            $count++;
        }
    }
     $col = 0;
     $row++;
    
}
                            
print $count;

    
class Solution {

  public $gridNumberRows;
  public $gridNumberCols;
  public $grid;

  public function __construct() 
  {
  
  }

  public function maxConnectedColorValue(array $grid) : int
  {
     $this->grid = $grid;
    print $this->gridNumberRows = count($grid);
    $countCol = 0;
    foreach ($grid[0] as $col)
    {
      $countCol++;
    }
      
      print "\n\r";
   print  $this->gridNumberCols = $countCol;
    
      
      
    # visted cells to false
    for($r = 0; $r < $this->gridNumberRows ; $r++) {
      for($c = 0; $c < $this->gridNumberCols ; $c++)  {
        $visited[$r][$c] = false;
      }
    }

   
    $hashmapColor = [];
    for($row = 0; $row < $this->gridNumberRows ; $row++) {
      for($col = 0; $col < $this->gridNumberCols ; $col++)  {
        
        
        if($visited[$row][$col] === true) {
          continue;
        }

        
        if($grid[$row][$col] === ''){
          $visited[$row][$col] = true;
          continue;
        }

        $cellColor= $grid[$row][$col];
        $visited[$row][$col] = true;
        if(!array_key_exists($cellColor, $hashmapColor)) {
          $hashmapColor[$cellColor] = 1;
        }
        
        $this->dfs($row, $col, $visited, $hashmapColor);
        
        
        
      }
    }    
    var_dump($hashmapColor);
    return max($hashmapColor);
  }
  
    public function dfs($r, $c, &$visited, &$hashmapColor)
    {
      
      $cellColor = $this->grid[$r][$c];
        if($cellColor == '')
            return;
                
                
      # structure [R,C]
      $neighborInstruction = [[-1,0],[0,1],[1,0],[0,1]];
      
      foreach ($neighborInstruction as $neighbor) 
      {
        $neighborRow = $neighbor[0];
        $neighborCol = $neighbor[1];
        
    

          
          
          
        #if whithin boundaries
        if(((($neighborRow + $r) >= 0) && ($neighborRow + $r) < $this->gridNumberRows)
          && ($neighborCol + $r) >= 0 && ($neighborCol + $r) < $this->gridNumberCols)
        {
        
          # check same color
          if($this->grid[$neighborRow + $r][$neighborCol + $c] === $this->grid[$r][$c] 
            && $visited[$neighborRow + $r][$neighborCol + $c] === false) {
            
              if (array_key_exists($cellColor, $hashmapColor)) {
                $hashmapColor[$cellColor] += 1;
            } 

            $visited[$r][$c] = true;
            $this->dfs($neighborRow + $r, $neighborCol + $c, $visited, $hashmapColor);

          }
        }
        
      }
    }

  
}



$grid = [
['','r','b',''],
['','b','b','b'],
['','','b','']];

$solution = new Solution();
$res = $solution->maxConnectedColorValue($grid);

var_dump($res);

class Node {
  
  public $value;
  public $left;
  public $right;
  
  public function __construct(int $value) 
  {
    $this->value = $value;
   $this->left = null;
   $this->right = null;
  }
}



class Solution {

  public function bfs($node, &$hashmap, $level) 
  {
    
    if($node === null) {
      return;
    }

    
    $queue = new SplQueue();
  
    if($node->left)
    {
      $queue->enqueue($node->left);  
    }

    if($node->right)
    {
      $queue->enqueue($node->right);
    }


    
    while ($queue->count() > 0) {
    
      $childNode = $queue->pop();
      
      $hashmap[$level][] = $childNode->value;
      
        $this->bfs($childNode, $hashmap, $level + 1);
      
    }

    
  }
  
  public function AverageSumLevel($node) 
  {
    $hashmap = [];
    $level = 0;
    $hashmap[$level][] = $node->value;
    $this->bfs($node, $hashmap, $level + 1) ;
    
      
    foreach ($hashmap as $level => $values) 
    {
      $result[] = array_sum($values) / count($values);
    }
      
      
    return $result;
  }
}


$node5 = new Node(5);
$node5->left = new Node(4);
$node5->right = new Node(8);


$node5->left->left = new Node(2);
$node5->left->right = new Node(1);

$node5->right->right = new Node(9);
$node5->right->right->right = new Node(12);

$solution = new Solution();
$res = $solution->AverageSumLevel($node5);
var_dump($res);

Seating ArrangementsThere are n guests attending a dinner party, numbered from 1 to n. The ith guest has a height of arr[i-1] inches.The guests will sit down at a circular table which has n seats, numbered from 1 to n in clockwise order around the table. As the host, you will choose how to arrange the guests, one per seat. Note that there are n! possible permutations of seat assignments.Once the guests have sat down, the awkwardness between a pair of guests sitting in adjacent seats is defined as the absolute difference between their two heights. Note that, because the table is circular, seats 1 and n are considered to be adjacent to one another, and that there are therefore n pairs of adjacent guests.The overall awkwardness of the seating arrangement is then defined as the maximum awkwardness of any pair of adjacent guests. Determine the minimum possible overall awkwardness of any seating arrangement.

Signature

int minOverallAwkwardness(int[] arr)

Input

n is in the range [3, 1000]. Each height arr[i] is in the range [1, 1000].

Output

Return the minimum achievable overall awkwardness of any seating arrangement.

Example

n = 4 arr = [5, 10, 6, 8] output = 4If the guests sit down in the permutation [3, 1, 4, 2] in clockwise order around the table (having heights [6, 5, 8, 10], in that order), then the four awkwardnesses between pairs of adjacent guests will be |6-5| = 1, |5-8| = 3, |8-10| = 2, and |10-6| = 4, yielding an overall awkwardness of 4. It’s impossible to achieve a smaller overall awkwardness.Report Bug

 
function minOverallAwkwardness($arr) {
  // Write your code here

    #big O NLogN
    sort($arr);
    $n = count($arr);
    
    $temp = $arr[$n-1];
    $arr[$n-1] = $arr[$n-2] ;
    $arr[$n-2] = $temp;
    

    return smallestAwkwardnes($arr);
}

function smallestAwkwardnes($arr){
    $heap = new SplMaxHeap();
    for ($i=0; $i < count($arr) - 1; $i++) {
        $akwardness = $arr[$i] - $arr[$i + 1];
        if($akwardness < 0){
            $akwardness *= -1;
        }
        $heap->insert($akwardness);
    }
    return $heap->extract();
}

Element SwappingGiven a sequence of n integers arr, determine the lexicographically smallest sequence which may be obtained from it after performing at most k element swaps, each involving a pair of consecutive elements in the sequence.Note: A list x is lexicographically smaller than a different equal-length list y if and only if, for the earliest index at which the two lists differ, x’s element at that index is smaller than y’s element at that index.

Signature

int[] findMinArray(int[] arr, int k)

Input

n is in the range [1, 1000]. Each element of arr is in the range [1, 1,000,000]. k is in the range [1, 1000].

Output

Return an array of n integers output, the lexicographically smallest sequence achievable after at most k swaps.

Example 1

n = 3 k = 2 arr = [5, 3, 1] output = [1, 5, 3]We can swap the 2nd and 3rd elements, followed by the 1st and 2nd elements, to end up with the sequence [1, 5, 3]. This is the lexicographically smallest sequence achievable after at most 2 swaps.

Example 2

n = 5 k = 3 arr = [8, 9, 11, 2, 1] output = [2, 8, 9, 11, 1]We can swap [11, 2], followed by [9, 2], then [8, 2].

   function findMinArray(array $arr, int $k) : array
  {
    #arr = [5, 3, 1]
    # k:2, 1
    while($k >= 1) 
    {
    
      # swapping
      $temp = $arr[$k];        # temp 1      ; 1
      $arr[$k] = $arr[$k - 1]; # $arr[2] = 3; $arr[1] = 5
      $arr[$k - 1] = $temp;    # $arr[1] = 1; $arr[0] = 1

      #arr = [5, 1, 3]
      #arr = [1, 5, 3]
      $k--; #1 #0
    }
    
    return $arr;
    
  }

Suppose we have a list of N numbers, and repeat the following operation until we’re left with only a single number: Choose any two numbers and replace them with their sum. Moreover, we associate a penalty with each operation equal to the value of the new number, and call the penalty for the entire list as the sum of the penalties of each operation.For example, given the list [1, 2, 3, 4, 5], we could choose 2 and 3 for the first operation, which would transform the list into [1, 5, 4, 5] and incur a penalty of 5. The goal in this problem is to find the highest possible penalty for a given input.Signature: int getTotalTime(int[] arr)Input: An array arr containing N integers, denoting the numbers in the list.Output format: An int representing the highest possible total penalty.Constraints: 1 ≤ N ≤ 10^6 1 ≤ Ai ≤ 10^7, where *Ai denotes the ith initial element of an array. The sum of values of N over all test cases will not exceed 5 * 10^6.Example arr = [4, 2, 1, 3] output = 26First, add 4 + 3 for a penalty of 7. Now the array is [7, 2, 1] Add 7 + 2 for a penalty of 9. Now the array is [9, 1] Add 9 + 1 for a penalty of 10. The penalties sum to 26.

# int1 + int2
  #  [4, 2, 1, 3]
  # [7, 2, 1] penalty 7
  # [9, 1] penalty 7 + 9 = 16
  # 10 penalty 7 + 9 = 16 + 10 = 26
  
  #highest penalty
  
  
  #  [4, 2, 1, 3]
  # [5, 2, 3] penalty 5
  # [7,3] penalty 5 + 7 = 12
  # 10 penalty  5 + 7 = 12 + 10 = 22
  
  function getTotalTime(array $arr) : int 
  {
  $penalty = 0;
    $heap = new SplMaxHeap();
    
    # array(4, 2, 1, 3)
    foreach ($arr as $value) 
    {
      $heap->insert($value);
    }
    #heap  4,3,2,1
    
    
    while ($heap->count() > 1) # count 4; 3
    {
      $int1 = $heap->extract(); # 4 ; 7 ; 9
      $int2 = $heap->extract(); # 3 ; 2 ; 1
      $sum = ($int1 + $int2);   # 7 ; 9 ; 10
      $penalty +=  $sum;         # 7; 7+9=16;16+10 = 26 
      $heap->insert($sum);      # 7,2,1 ; 9,1; 10
    }
    
    return $penalty; #26
}

You’re given a list of n integers arr[0..(n-1)]. You must compute a list output[0..(n-1)] such that, for each index i (between 0 and n-1, inclusive), output[i] is equal to the median of the elements arr[0..i] (rounded down to the nearest integer).The median of a list of integers is defined as follows. If the integers were to be sorted, then:

• If there are an odd number of integers, then the median is equal to the middle integer in the sorted order.
• Otherwise, if there are an even number of integers, then the median is equal to the average of the two middle-most integers in the sorted order.

Signature

int[] findMedian(int[] arr)

Input

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

Output

Return a list of n integers output[0..(n-1)], as described above.

Example 1

n = 4 arr = [5, 15, 1, 3] output = [5, 10, 5, 4]The median of [5] is 5, the median of [5, 15] is (5 + 15) / 2 = 10, the median of [5, 15, 1] is 5, and the median of [5, 15, 1, 3] is (3 + 5) / 2 = 4.

Example 2

n = 2 arr = [1, 2] output = [1, 1]The median of [1] is 1, the median of [1, 2] is (1 + 2) / 2 = 1.5 (which should be rounded down to 1).

 function findMedian(array $arr) : array
  {
      # initialization variables
      $endWindowPosition = 0;
      $output = [];
      $maxHeap = new SplMaxHeap();
  
      # iterate throug ARR
      foreach ($arr as $key => $value) # key 0,1,2,3 ; value 5,15,1,3
      {
          # detect is_odd_number
          $isEvenNumber = false;
          if ((($endWindowPosition + 1) % 2) === 0) 
          {
            $isEvenNumber = true;
              //var_dump($endWindowPosition);
          }    

          # $endWindowPosition : 0 -> $isEvenNumber: false
          # $endWindowPosition : 1 -> $isEvenNumber: true


          # building output
          if($key === 0) 
          {
            $output[] = $value; # output[5]
          }

          # EVEN
          if ($key > 0 && $isEvenNumber === true) 
          {
             # build temp arr1
              for ($i = 0; $i <= $endWindowPosition; $i++) 
              {
                $arrEvenNumber[] = $arr[$i];
              }
              # $arrEvenNumber[5,15]
              # $arrEvenNumber[5,15,1,3]
              sort($arrEvenNumber); # $arrOddNumber[1,3 5,15]
              
              $mediumIndex = floor(($endWindowPosition + 1) / 2); #1, 1
              $int1 = $arrEvenNumber[$mediumIndex - 1 ]; # 5, 3
              $int2 = $arrEvenNumber[$mediumIndex ]; # 15 ,5        
              
              $median = floor(($int1 + $int2) / 2); # 5+15 / 2 === 10 # 3 + 5 / 2 = 4
              
              $output[] = $median; #output[5, 10]; #output[5, 10, 5,4]
              $arrEvenNumber =  [];
          }

          # ODD
         if(($key > 0) && ($isEvenNumber === false)) {
             //var_dump($endWindowPosition);
           # build temp arr1
            for ($i = 0; $i <= $endWindowPosition; $i++) 
            {
              $arrOddNumber[] = $arr[$i]; # $arrOddNumber[5,15,1]
            }
            sort($arrOddNumber); # $arrOddNumber[1, 5,15]
            $mediumIndex = floor($endWindowPosition  / 2);
            // var_dump($endWindowPosition);
            $intOddMedian = $arrOddNumber[$mediumIndex]; # 5
            $output[] = $intOddMedian; # output[5, 10, 5]
             $arrOddNumber = [];
         }
       $endWindowPosition++; # 1, 2, 3
      }    
     
    
      return $output; 

  }

Largest Triple ProductsYou’re given a list of n integers arr[0..(n-1)]. You must compute a list output[0..(n-1)] such that, for each index i (between 0 and n-1, inclusive), output[i] is equal to the product of the three largest elements out of arr[0..i] (or equal to -1 if i < 2, as arr[0..i] then includes fewer than three elements).Note that the three largest elements used to form any product may have the same values as one another, but they must be at different indices in arr.

Signature

int[] findMaxProduct(int[] arr)

Input

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

Output

Return a list of n integers output[0..(n-1)], as described above.

Example 1

n = 5 arr = [1, 2, 3, 4, 5] output = [-1, -1, 6, 24, 60]The 3rd element of output is 3*2*1 = 6, the 4th is 4*3*2 = 24, and the 5th is 5*4*3 = 60.

Example 2

n = 5 arr = [2, 1, 2, 1, 2] output = [-1, -1, 4, 4, 8]The 3rd element of output is 2*2*1 = 4, the 4th is 2*2*1 = 4, and the 5th is 2*2*2 = 8.

function findMaxProduct($arr) {
  // Write your code here
     $heap = new SplMaxHeap();
        $result = [-1, -1];
        $n = count($arr);
        

        for($i = 0; $i <= $n - 3; $i++)
        {
            $product = slidingWindowProduct($i, $arr, $heap);
            $result[] = $product;
        }
        
        
        return $result;
    }
    
     function slidingWindowProduct($strartIndex, $arr, &$heap)  
    {
        $product = 1;
        if($strartIndex == 0) {
            for($i = $strartIndex; $i <= $strartIndex + 2; $i++) 
            {
                $heap->insert($arr[$i]);
            }            
        } 
        else 
        {
            $heap->insert($arr[$strartIndex + 2]);
        }

        
        for($i=0; $i < 3; $i++) 
        {
            $value = $heap->extract();
            $temp[] = $value;
            $product *= $value;
        }


        while(count($temp) > 0) 
        {
            $val = array_shift($temp);
            $heap->insert($val);
        }
        
        return $product; #6
    }

class solution {
    
    public function __construct(){}
    
    public function findMaxProduct(array $arr) : array
    {
        $heap = new SplMaxHeap();
        $result = [-1, -1];
        $n = count($arr);
        

        for($i = 0; $i <= $n - 3; $i++)
        {
            $product = $this->slidingWindowProduct($i, $arr, $heap);
            $result[] = $product;
        }
        
        
        return $result;
    }
    
    private function slidingWindowProduct($strartIndex, $arr, &$heap) : mixed 
    {
        $product = 1;
        if($strartIndex == 0) {
            for($i = $strartIndex; $i <= $strartIndex + 2; $i++) 
            {
                $heap->insert($arr[$i]);
            }            
        } 
        else 
        {
            $heap->insert($arr[$strartIndex + 2]);
        }

        
        for($i=0; $i < 3; $i++) 
        {
            $value = $heap->extract();
            $temp[] = $value;
            $product *= $value;
        }


        while(count($temp) > 0) 
        {
            $val = array_shift($temp);
            $heap->insert($val);
        }
        
        return $product; #6
    }
}


$arr_1 = array(1, 2, 3, 4, 5);
$arr_2 = array(2, 4, 7, 1, 5, 3);


$solution = new Solution();
$res =  $solution->findMaxProduct($arr_2);
var_dump($res);