## SDE1 Interview Questions

- 1of 1 vote
given a string, and integer k, check if this string contain all the binary string of length k

For example, k is 2, then 00,10,01,11.

Followup 1, find a string that can contain all binary string of length k.

Followup 2, find a shortest string that can contain all binary string of length k.

- 0of 0 votes
Expression evolution

expr :: = int | '(' op expr + ')'

op :: = '+' | '*'

Cite a few examples:

"3" -> 3

"(+ 1 2)" -> 3

"(+ 3 4 5)" -> 12

"(+7 (* 8 12) (* 2 (+ 9 4) 7) 3)" -> ...

Public int getValue(String s){

}

- 0of 0 votes
`Insert a number into an array of sorted intervals. For example, [1,4], [6,8], after insert 5, return [1,8]. class Interval{ int start; int end; public Interval(int start, int end){ this.start = start; this.end = end; } } class Solution{ public List<Interval> insert(List<Interval> list, int val){ } }`

- 0of 0 votes
give a bunch of job dependency, such as A-> B, A -> C, B-> D, and so on, implement two interfaces.

The first one is get_next_stage, which returns jobs in parallel for the next phase. The second is job_done, which tells you which job completed.

- 0of 0 votes
determine whether a number is the sum of two squares, such as 17 = 16 +1

- 0of 0 votes
`Give a matrix, for example 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1 Find if there is a rectangle in the matrix, all four corners are 1 For the example, there is only one rectangle, that is 1 0 1 0 1 0 1 0 1`

- 0of 0 votes
class DirectedGraphNode {

int label;

List<DirectedGraphNode> neighbors;

DirectedGraphNode(int x) {

label = x;

neighbors = new ArrayList<>();

}

}

check if there is a cycle in a directed graph, if there is a cycle, remove all the cycles

- -1of 1 vote
Sachin wants to buy a laptop for programming. he plans on buying a laptop whose price is made of digits 4 and 7 only. The number of 4s and 7s in the price should be equal. You are given laptop brand names and their prices. Find and print the name of the laptop brand that satisfies the above criteria. If there are multiple brands that meet the criteria, print the name of the one with the minimum price. If none of the laptops meet the criteria print -1.

For example, if Sharon has a choice between laptops 'BestBook' priced at 444777 and 'LapBook' priced at 7744, the solution should indicate ideal choice to be 'LapBook'. Although both 'BestBook' and 'LapBook' have equal number of 4s and 7s in the price, 'LapBook' is priced lower which makes it the right choice for Sharon.

- 1of 1 vote
You are given a binary tree and a function shouldBeErased(node to check whether a node should be erased. Erase all nodes that should be erased in the binary tree and return the resulting forest in the form of an array of every root node.

Follow up:

What if this is a Binary Search Tree? (In this case you are given a list of nodes that should be erased instead of the function.) Does it make the problem simpler or more complicated or just the same?

- 0of 0 votes
given a string and a segmentation length k

For example:

"This is a good day" k = 10

Cut into:

"This (1/4)"

"is a (2/4)"

"good (3/4)"

"day (4/4)"

Each line followed by a suffix in the form of (i/n) has 10 chars including space (except for the last line), return the minimum cut required, for the example, just return 4.

- 0of 0 votes
trie search, Search Return all words that match the wildcard *

such as

add ("car")

add ("caw")

add ("cauw")

search ("c*w") returns "caw" and "cauw".

- 0of 0 votes
There are n bus lines, known bus stops by bus, the bus is bi-direction, ask from station A to station B at least a few transfers.

- 0of 0 votes
`given a binary array, you can flip 0 -> 1 or 1 -> 0 to make all the 1 are in the left part and all the 0 to the right part, return the minimun flip required example 1 1011000 -> 1111000 only need one flip 0 -> 1 example 2 00001 -> 10000 require 2 flips public int findMiniFlip(int[] nums) { } }`

- 0of 0 votes
the longest unique value path in a graph

/**

* Definition for undirected graph.

* class UndirectedGraphNode {

* int label;

* List<UndirectedGraphNode> neighbors;

* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }

* };

*/

public class Solution {

public int findLongestUniqueValuePath(List<UndirectedGraphNode> node) {

}

}

- 0of 0 votes
Given a 2d grid map of '1's (land) and '0's (water), find the perimeter of each island. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

- 0of 0 votes
To determine if two graphs have isomorphism or not

- 0of 0 votes
Give an array A, find the (i, j) pairs that satisfy the condition.

Condition 1: A [j] = A [i] + 1, Condition 2: j - i is as large as possible

Followup condition 1 is changed to A [j]> A [i]

- 0of 0 votes
Given an array of length n + 1, containing elements 1 through n and a space,

Requires the use of a given swap (index i, index j) function to sort the array,

You can only swap the gap and a number, in the end, put the gap at the end

- 0of 0 votes
find a shortest string to cover all of a list of string,

For example, [aab, aabb, bc], should return aabbc,

because aab, aabb, bc are all the substring of aabbc

- 0of 0 votes
given 2 list of interval representing users online offline timestamp e.g (already sorted), find all intervals that both of users are online.

e.g A= [(3, 5), (7, 11)] B=[(2, 4), (9, 10)] --> [(3, 4), (9, 10)].

- 0of 0 votes
Design a SparseVector class that implements

Vector interface, which contains 4 methods: get(int index),

increment(int index, int delta), numNonZeros(), and dotProduct(Vector other)

- 0of 0 votes
Given an array of integers and k, find the difference between the number of the strictly increasing number of subarrays (of size more than one) and the number of the strictly decreasing subarray in the window of size k. your method should be time and space efficent

example

int[] nums = {188930, 194123, 201345, 154243, 154243};

int k = 3;

Output

3, 0, -1

Explanation

For the first window of [188930, 194123, 201345], there are 3 increasing subranges ([188930, 194123, 201345], [188930, 194123], and [194123, 201345]) and 0 decreasing, so the answer is 3. For the second window of [194123, 201345, 154243], there is 1 increasing subrange and 1 decreasing, so the answer is 0. For the third window of [201345, 154243, 154243], there is 1 decreasing subrange and 0 increasing, so the answer is -1.

public int[] getdiff(int[] nums, int l){

}

- 0of 0 votes
`give an enum, where each element has a parent-children relationship, and children's expression is the value of parent append an index, such as enum vehicle { car = 1 toyota = 11 camry = 111 corolla = 112 honda = 12 truck = 2 GMC = 21 } Ask a value, return to his parent, such as GMC = 21, return to the truck`

- 1of 1 vote
Given a list points on a 2d plane, find

largest rectangular area that can be formed

for the rectangle only considers those parallel to x and y

- 0of 0 votes
`There is an unordered interval stream, write a method, returns the total length that all intervals cover by now class Interval{ int start; int end; } public List<Integer> countCoverLength(Iterator<Interval> stream){ }`

- 0of 0 votes
‘.’Matches any single character,' * 'Matches any sequence of characters (including the empty sequence).

There are two input, one is string pattern, and the other is dictionary like dict = ["cat", "cats", "and", "sand", "dog"].

return a boolean: whether to find a dictionary in the pattern match the word

eg: dict = ["cat", "cats", "and", "sand", "dog"].

pattern = "* t", -> true (can match cat)

pattern = ".a *" -> true (can match cat, cats, can also match sand, because * can also express empty sequence)

- 0of 0 votes
How would you store and retrieve values in Memcache if the values are larger than the individual value size allowed by Memcache?

- 0of 0 votes
Find all words [A-Z] in a dictionary (about 1M words) that are made of a subset (in any order) of the chars in the input parameter [A-Z].

ex: input "ACRAT" (10 to 20 chars, up to 30 worst case)

matching words: "A", "CAR", "ACA", "ART", "RAC".

non-matching words: "BAR", "AAA"

follow up : the input is a list of words. Return a list of words that each

list is formed by exactly the characters in the input list.

For example: two lists {“DEBIT”, “CARD”} and{“BAD”, “CREDIT”}

are formed by the same exact group of characters.

- 0of 0 votes
Given a string separated by a space like "123456 abc+efg" determine

the solution by mapping integers to letters like a:1, b:2, c:3, d:4, e:5, f:6.

The only operations allowed were + or -. So the calculated solution

that made the tests pass was 123+456 = 579.

- 0of 0 votes
How many subsets of a given array sum to zero?