Facebook Interviews Flashcards
(3 cards)
In Javascript, how do you find the longest substring without duplicate characters?
function longestSubstringWithoutDupes(s) {
let seen = {};
let start = 0;
let maxLen = 0;
let maxSubstring = “”;
for (let end = 0; end < s.length; end++) {
let char = s[end];
if (seen[char] >= start) {
start = seen[char] + 1;
}
seen[char] = end;
if (end - start + 1 > maxLen) {
maxLen = end - start + 1;
maxSubstring = s.slice(start, end + 1);
}
}
return maxSubstring; }
console.log(longestSubstringWithoutDupes(“abcabcbb”)); // “abc”
console.log(longestSubstringWithoutDupes(“pwwkew”)); // “wke”
(0) Before For Loop
start = 0;
maxLen = 0;
seen = {};
(1) “a” on “abcabcbb” end 0
for (let end = 0; end < s.length; end++) {
let char = s[end];
if (seen[char] >= start) {
start = seen[char] + 1;
}
seen[char] = end;
maxLen = Math.max(maxLen, end - start + 1);
}
OUTPUT:
if (seen[“a”] >= start)
// if (undefined >= 0) => false; start //unchanged
if (end - start + 1 > maxLen) {
//if (0 - 0 + 1 > 0) // 1 > 0 => true
maxLen = max(0, 0 - 0 + 1) = 1;
[ a ]
0 0
start = 0, end = 0
seen[“a”] = 0;
seen = {
“a”: 0
}
✅ Longest substring still: “a”
(2) “b” on “abcabcbb” end = 1
for (let end = 0; end < s.length; end++) {
let char = s[end];
if (seen[char] >= start) {
start = seen[char] + 1;
}
seen[char] = end;
maxLen = Math.max(maxLen, end - start + 1);
}
OUTPUT:
maxLen = max(1, 1 - 0 + 1) = 2;
if (seen[“b”] >= start)
// if (undefined >= 0) => false
//start remains 0
[ a b ]
0 1
if (end - start + 1 > maxLen) {
//if (1 - 0 + 1 > 1) // 2 > 1 => true
start = 0, end = 1
seen[“b”] = 1;
seen = {
“a”: 0,
“b”: 1
}
✅ Longest substring still: “ab”
(3) “c” on “abcabcbb” end = 2
for (let end = 0; end < s.length; end++) {
let char = s[end];
if (seen[char] >= start) {
start = seen[char] + 1;
}
seen[char] = end;
maxLen = Math.max(maxLen, end - start + 1);
}
OUTPUT:
if (seen[“c”] >= start)
// if (undefined >= 0) => false
if (end - start + 1 > maxLen) {
if (2 - 0 + 1 > 2) // 3 > 2 => true
maxLen = max(2, 2 - 0 + 1) = 3;
[ a b c]
0 1 2
start = 0, end = 2
seen[“c”] = 2;
seen = {
“a”: 0,
“b”: 1,
“c”: 2
}
✅ Longest substring still: “abc”
(4) “a” on “abcabcbb” end = 3
for (let end = 0; end < s.length; end++) {
let char = s[end];
if (seen[char] >= start) {
start = seen[char] + 1;
}
seen[char] = end;
maxLen = Math.max(maxLen, end - start + 1);
}
OUTPUT:
if (seen[“a”] >= start)
// if (0 >= 0) => true
//start now becomes 1
if (end - start + 1 > maxLen) {
//if (3 - 1 + 1 > 3) // 3 > 3 => false
maxLen = max(3, 3 - 1 + 1) = 3;
[ b c a ]
1 2 3
start = 1, end = 3
seen[“a”] = 3;
seen = {
“a”: 3,
“b”: 1,
“c”: 2
}
✅ Longest substring still: “abc”
(5) “b” on “abcabcbb” end = 4
for (let end = 0; end < s.length; end++) {
let char = s[end];
if (seen[char] >= start) {
start = seen[char] + 1;
}
seen[char] = end;
maxLen = Math.max(maxLen, end - start + 1);
}
OUTPUT:
if (seen[“b”] >= start)
// if (1 >= 1) => true
//start is now 2
seen[“b”] = 4;
maxLen = Math.max(3, 4 - 2 + 1) = 3;
seen = { “a”: 3, “b”: 4, “c”: 2 }
if (end - start + 1 > maxLen) {
if (4 - 2 + 1 > 3) // 3 > 3 => false
[ c a b ]
2 3 4
start = 2, end = 4
✅ Longest substring still: “abc”
(6) “c” on “abcabcbb” end = 5
for (let end = 0; end < s.length; end++) {
let char = s[end];
if (seen[char] >= start) {
start = seen[char] + 1;
}
seen[char] = end;
maxLen = Math.max(maxLen, end - start + 1);
}
OUTPUT:
if (seen[“c”] >= start)
// if (2 >= 2) => true
//start becomes 3
seen[“c”] = 5;
maxLen = Math.max(3, 5 - 3 + 1) = 3;
if (end - start + 1 > maxLen) {
//if (5 - 3 + 1 > 3) // 3 > 3 => false
seen = { “a”: 3, “b”: 4, “c”: 5 }
[ a b c ]
3 4 5
start = 3, end = 5
✅ Longest substring still: “abc”
(7) “b” on “abcabcbb” end = 6
for (let end = 0; end < s.length; end++) {
let char = s[end];
if (seen[char] >= start) {
start = seen[char] + 1;
}
seen[char] = end;
maxLen = Math.max(maxLen, end - start + 1);
}
OUTPUT:
if (seen[“b”] >= start)
// if (4 >= 3) => true
//start becomes 5
seen[“b”] = 6;
maxLen = Math.max(3, 6 - 5 + 1) = 3;
if (end - start + 1 > maxLen) {
//if (6 - 5 + 1 > 3) // 2 > 3 => false
seen = { “a”: 3, “b”: 6, “c”: 5 }
[ c b ]
5 6 start = 5, end = 6 ✅ Longest substring still: "abc"
(8) “b” on on “abcabcbb” end = 7
for (let end = 0; end < s.length; end++) {
let char = s[end];
if (seen[char] >= start) {
start = seen[char] + 1;
}
seen[char] = end;
maxLen = Math.max(maxLen, end - start + 1);
}
OUTPUT:
if (seen[“b”] >= start)
// if (6 >= 5) => true
//start is now 7
seen[“b”] = 7;
if (end - start + 1 > maxLen) {
//if (7 - 7 + 1 > 3) // 1 > 3 => false
maxLen = Math.max(3, 7 - 7 + 1) = 3;
seen = { “a”: 3, “b”: 7, “c”: 5 }
[ b ]
7
start = 7, end = 7
✅ Longest substring still: “abc”
Write a solution to find the second highest distinct salary from the Employee table. If there is no second highest salary, return null (return None in Pandas).
Example 1:
Input:
Employee table:
+—-+——–+
| id | salary |
+—-+——–+
| 1 | 100 |
| 2 | 200 |
| 3 | 300 |
+—-+——–+
Output:
+———————+
| SecondHighestSalary |
+———————+
| 200 |
+———————+
Example 2:
Input:
Employee table:
+—-+——–+
| id | salary |
+—-+——–+
| 1 | 100 |
+—-+——–+
Output:
+———————+
| SecondHighestSalary |
+———————+
| null |
+———————+
Write your MySQL query statement below
SELECT
(SELECT DISTINCT salary
FROM Employee
ORDER BY salary DESC
LIMIT 1 OFFSET 1)
AS SecondHighestSalary;
Write a solution to find the nth highest distinct salary from the Employee table. If there are less than n distinct salaries, return null.
The result format is in the following example.
Example 1:
Input:
Employee table:
+—-+——–+
| id | salary |
+—-+——–+
| 1 | 100 |
| 2 | 200 |
| 3 | 300 |
+—-+——–+
n = 2
Output:
+————————+
| getNthHighestSalary(2) |
+————————+
| 200 |
+————————+
Example 2:
Input:
Employee table:
+—-+——–+
| id | salary |
+—-+——–+
| 1 | 100 |
+—-+——–+
n = 2
Output:
+————————+
| getNthHighestSalary(2) |
+————————+
| null |
+————————+
CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
RETURN (
SELECT DISTINCT salary
FROM Employee
ORDER BY salary DESC
LIMIT 1 OFFSET N - 1
);
END
