DailyInterviewPro

Questions

0917 | Edit Distance

• recently asked by AirBnB

Given two strings, determine the edit distance between them. 
The edit distance is defined as the minimum number of edits (insertion, deletion, or substitution) 
needed to change one string to the other.

For example, "biting" and "sitting" have an edit distance of 2 (substitute b for s, and insert a t).

Here's the signature:

• solution:

Solution Not Ready Yet

---

0916 | Find Pythagorean Triplets

• recently asked by Uber

Given a list of numbers, find if there exists a pythagorean triplet in that list. A pythagorean triplet is 3 variables a, b, c where a^2 + b^2 = c^2

Example:
Input: [3, 5, 12, 5, 13]
Output: True
Here, 5^2 + 12^2 = 13^2.

• solution:

Solution Not Ready Yet

---

0915 | Number of Ways to Climb Stairs

• recently asked by LinkedIn

You are given a positive integer N which 
represents the number of steps in a staircase. 
You can either climb 1 or 2 steps at a time. 
Write a function that returns the number of unique ways to climb the stairs.

• Can you find a solution in O(n) time?

• solution:

Solution Not Ready Yet

---

0914 | Maximum in a Stack

• recently asked by Twitter

Implement a class for a stack that supports all the regular functions 
(push, pop) and an additional function of max() which returns the 
maximum element in the stack(return None if the stack is empty). 
 Each method should run in constant time.

• solution:

Solution Not Ready Yet

---

0913 | Invert a Binary Tree

• recently asked by Twitter

You are given the root of a binary tree. 
Invert the binary tree in place. That is, all left children should become 
right children,and all right children should become left children.

• solution:

Solution Not Ready Yet

---

0912 | Floor and Ceiling of a Binary Search Tree

• recently asked by Apple

Given an integer k and a binary search tree, find the floor 
(less than or equal to) of k,and the ceiling (larger than or equal to) of k. 
If either does not exist, then print them as None.

• solution:

Solution Not Ready Yet

---

0911 | Non-decreasing Array with Single Modification

• recently asked by Microsoft

You are given an array of integers in an arbitrary order. 
Return whether or not it is possible to make the array non-decreasing 
by modifying at most 1 element to any value.

We define an array is non-decreasing if array[i] <= array[i + 1] holds for 
every i (1 <= i < n).

Example:

[13, 4, 7] should return true, since we can modify 13 to any value 4 or less,
 to make it non-decreasing.
[13, 4, 1] however, should return false, since there is no way to modify 
just one element to make the array non-decreasing.

• solution:

Solution Not Ready Yet

---

[DONE] 0910 | Find the Non-duplicate number

• recently asked by Facebook

Given a list of numbers, where every number shows up twice except for
 one number, find that one number.

Example:
Input: [4, 3, 2, 4, 1, 3, 2]
Output: 1

• Solution: leetCode passed (Q136)
• 解法說明:
  • 最笨:(single) 雙層 loop, 這個最慢
  • 較佳:(single2) 建立一個空陣列 $match
    • 跑Foreach, 如果 ! in_array($match) -> 則把該 num 丟進去
    • 如果 in_array($match), 則把該筆從 $match中消掉
    • 兩兩相消, 最後會得到 $match裡面就是他 -> 答案
  • 佳: (single3)組合 array_search 和 array_count_values
    • array_count_values 會去計算 Array 中每個element 出現的次數 -> 結果組成一個陣列
    • array_seach 再去從剛剛的結果內, 撈出只有出現一次的 element

//2940ms, 17.8mb
public function single($nums)
{
    $size = count($nums);

    for($i=0;$i<$size;$i++){
        for($j=$i+1;$j<$size;$j++){
            if($nums[$i] == $nums[$j]){
               unset($nums[$i]);
               unset($nums[$j]);
               $size -= 2;
               $i--;
               $nums = array_values($nums);
               break;
            }
        }
    }

    return $nums[0];
}

//220ms, 17.4mb
public function single2($nums)
{
    $matchArray = [];

    foreach($nums as $num){

        if(!in_array($num, $matchArray)){
            $matchArray[$num] = $num;
        }else{
            unset($matchArray[$num]);
        }
    }

    return current($matchArray);
}

//20ms, 17.4mb
public function single3($nums)
{
    return array_search(1, array_count_values($nums));
}

---

[DONE] 0909 | Two-Sum

• recently asked by Facebook

You are given a list of numbers, and a target number k. 
Return whether or not there are two numbers in the list that add up to k.
Example:
Given [4, 7, 1 , -3, 2] and k = 5,
return true since 4 + 1 = 5.

• solution: leetCode passed (Q1)
• 解法說明: 要 loop兩次, 鎖定一個數, 然後後面去查找.
  • 假設總和為 P
  • 外層 loop, 選定該數(假設為X), 則剩下的數為 P-X
  • 進入內層loop, 看哪一個數為 P-X, 則就是答案

/**
 * @param String $s
 * @return Integer
 */
public function twoSum($nums, $target)
{
    $size = count($nums);

    for($i=0;$i<$size;$i++){

        $result = $target - $nums[$i];
        for($j=$i+1; $j<$size; $j++){

            if($nums[$j] == $result){
                return [$i, $j];
            }
        }
    }
}

---

0908 | Sorting a list with 3 unique numbers

• recently asked by Google

Given a list of numbers with only 3 unique numbers (1, 2, 3), sort the 
list in O(n) time.

Example 1:
Input: [3, 3, 2, 1, 3, 2, 1]
Output: [1, 1, 2, 2, 3, 3, 3]

• solution:

Solution Not Ready Yet

---

0907 | Reverse a linked-list

• recently asked by Google

Given a singly-linked list, reverse the list. This can be done iteratively 
or recursively. Can you get both solutions?

Example:
Input: 4 -> 3 -> 2 -> 1 -> 0 -> NULL
Output: 0 -> 1 -> 2 -> 3 -> 4 -> NULL

• solution:

Solution Not Ready Yet

---

0906 | First and Last Indices of an Element in a Sorted Array

• recently asked by AirBnb

Given a sorted array, A, with possibly duplicated elements, find the indices 
of the first and last occurrences of a target element, x. Return -1 if the 
target is not found.

Example:
Input: A = [1,3,3,5,7,8,9,9,9,15], target = 9
Output: [6,8]

Input: A = [100, 150, 150, 153], target = 150
Output: [1,2]

Input: A = [1,2,3,4,5,6,10], target = 9
Output: [-1, -1]

• solution:

Solution Not Ready Yet

---

[DONE] 0905 | Validate Balanced Parentheses

• recently asked by Uber

Imagine you are building a compiler. Before running any code, the compiler 
must check that the parentheses in the program are balanced. Every opening 
bracket must have a corresponding closing bracket. We can approximate this 
using strings.

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', 
determine if the input string is valid.
An input string is valid if:
- Open brackets are closed by the same type of brackets.
- Open brackets are closed in the correct order.
- Note that an empty string is also considered valid.

Example:
Input: "((()))"
Output: True

Input: "[()]{}"
Output: True

Input: "({[)]"
Output: False

• solution: leetCode passed (Q20)

• 解法說明: Loop 一次, 先建立個空陣列

• 奇怪的Case 先提前 return 掉 (如單數(必定false), 字串為空)

• 建立一個小的 assoc array, 左邊括號對應右邊括號

• Loop內的步驟:

  1. 如果為左邊的括號, 寫入一個對應的右側括號, 到 stash 裡面
  2. 如果為右邊的括號, 則去Stash 檢查(先進先出, 從stash最後檢查起)
     • 如果 相等 -> 則沒事, 把 stash 該筆拿掉 (array_pop)
     • 如果不相等 -> 對不起來 -> 可以 return false;

• Loop跑完後, 去檢查 stash

  • 全為左括號 (則 Stash會一堆又括號) -> return false 不是我們要的
  • Stash為空 -> 正確 都消掉了 -> return true;

• 基本上一次 loop 就能消掉.

/**
 * @param String $s
 * @return Integer
 */
public function validParentheses($target)
{
    //Avoid Extreme Case first
    $targetArray = str_split($target);
    $size = count($targetArray);

    if(empty($target)){
        return true;
    }

    if($size % 2 == 1){
        return false;
    }

    $checkField = [
        '(' => ')',
        '[' => ']',
        '{' => '}',
    ];

    $stash = [];

    for($i=0; $i < $size; $i++){

        //Left - 如果是左側括號, 則丟一個對應的右側括號到 stash 裡面
        if(in_array($targetArray[$i], array_keys($checkField))){

            array_push($stash, $checkField[$targetArray[$i]]);

        //right - 如果丟過來的是右側括號, 則去 Stash 裡面找
        }else{

            //從Stash最右邊開始找起, 如果對不起來, 那一定錯
            if($targetArray[$i] != $stash[count($stash)-1]){
                return false;
            }

            //對的起來 那就把 stash裡面對應的消掉
            array_pop($stash);
        }
    }

    //最後檢查 stash
    //有可能 如 `((` 會讓 stash裡面寫了兩個同側括號
    //Stash都清空 -> 那就是 True,
    //Stash還有東西 -> 非清空

    return count($stash) == 0 ? true : false;
}

---

0904 | Longest Palindromic Substring

• recently asked by Twitter

A palindrome is a sequence of characters that reads the same backwards 
and forwards. Given a string, s, find the longest palindromic substring in s.

Example:
Input: "banana"
Output: "anana"

Input: "million"
Output: "illi"

• solution:

Solution Not Ready Yet

---

0903 | Longest Substring Without Repeating Characters

• recently asked by MicroSoft

Given a string, find the length of the longest substring without repeating
 characters.

Here is an example solution in Python language. 
(Any language is OK to use in an interview, though we'd recommend Python
 as a generalist language utilized by companies like 
 Google, Facebook, Netflix, Dropbox, Pinterest, Uber, etc.,)

• solution:

Solution Not Ready Yet

---

0902 | Add two numbers as a linked list

• recently asked by MicroSoft

You are given two linked-lists representing two non-negative integers. 
The digits are stored in reverse order and each of their nodes contain a
single digit. 
Add the two numbers and return it as a linked list.

Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

• solution:

Solution Not Ready Yet