## SDE1 Interview Questions

- 0of 0 votes
Balance a string with parentheses. "a(b)" -> "a(b)"; "(((((" -> ""; "(()())" -> "(()())"; ")ab(()" -> "ab()"; etc...

- 0of 0 votes
can you use union find to Detect Cycle in a Directed Graph? why or why not

- 0of 0 votes
Shell command, there is a log file, you want all the "error" inside the line to find out into another file inside,

What instruction,

- 0of 0 votes
how to design github

- 0of 0 votes
Return the most popular 10 words in the past 24 hours for twitter

Follow up in order to reduce the size of each log, do not write timestamp, how to get the same answer,

- 0of 0 votes
Given a Calendar class (there are three fields, year, month, day) and a number of N,

Implement a function that returns the calendar after N days,

For example, if the input is {2017, 3,20} and 12, then the return is {2017,4, 1}

- 0of 0 votes
implement a Fibonacci iterator

- 0of 0 votes
Now we have one server, one database, what if response time is slow?

How to optimize?

- 0of 0 votes
Given an integer n, count the total number of digit 3 appearing in all non-negative integers less than or equal to n.

(E.x: given 30, return 4 {3,13, 23, 30})

- 0of 0 votes
prime factors. given a number return the prime factor multiplication.

eg. 90 = 2 * 3 * 3 * 5.

- 0of 0 votes
Remove any number containing 9 like 9, 19, 29, ... 91, 92, ... 99, 109...

Write a function that returns the nth number. E.g. newNumber(1) = 1

newNumber(8) = 8, newNumber(9) = 10

- 0of 0 votes
Given a stream of objects, O1, O2, O1, O3, O4... Provide an algorithm to identify the first unique object at any given point in time.

So for example, in the above, after receiving the first Object, it is unique. After receiving the second, the first is still the first unique object. After receiving the 3rd, the 1st object is no longer unique (you've not seen O1 twice), so O2 is not the first unique object. etc...

- 0of 0 votes
/* Find all subsets of size k in an array that sum up to target

the array may contains negative number */

class Solution {

public List<List<Integer>> combinationSum(int[] nums, int target, int k) {

}

- 0of 0 votes
A bot is an id that visit the site m times in the last n seconds,

given a list of logs with id and time sorted by time, return all the bots's id`class Log{ String id; int time; } public HashSet<String> getBots(Log[] logs, int m, int n){ }`

- 0of 0 votes
how to implement a Wish List like this one

https://www.amazon.com/hz/wishlist/intro

- 0of 0 votes
download all urls from 1000 hosts. Imagine all the urls are graph.

Requirement: Each host has bad internet connection among each other, Has to download url exacly once.

- 0of 0 votes
Last Monday phone interview of G.

Given a vector/list of doubly linked list pointers (a pointer is the directed linkage of two nodes), count how many independent blocks of linked lists there are for the pointers given.

- 0of 0 votes
Give you a robot and a room where you do not know where the robot is in the room and you do not know the size of the room, you have a remote control that allows the robot to walk around four directions. Here you give a move method: boolean move (int direction), direction: 0,1,2,3 that four directions. If it can move in that direction, return true, and if it cannot move in that direction, return false. Ask you determine how big this room is. the shape of the room can be any shape, so you cannot assume it is rectangle or square.

- 0of 0 votes
There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You can begin the journey with an empty tank at one of the gas stations.

Return ALL the starting gas station's index where you can travel around the circuit once

public List<Integer> canCompleteCircuit(int[] gas, int[] cost) {

}

- 0of 0 votes
Given n1, n2 is the number after removing one digit from n1. Example, n1 = 123, then n2 can be 12, 13 or 23.

If we know the sum of n1 + n2, and find the possible values of n1 and n2.

public List<List<Integer>> getNumber(int sum){

}

- 0of 0 votes
Design copy-on-write string class

e.g. stringclass s("abc");

stringclass s1 = s; // no copy

s = "bcd"; // copy

- 0of 0 votes
Given an ODD number, print diamond pattern of stars recursively.

`n = 5, Diamond shape is as follows: * *** ***** *** *`

void print(int n){

}

- 0of 0 votes
/From the input array, output a subset array with numbers part of a Fibonacci series.

// input: [4,2,8,5,20,1,40,13,23]

// output: [2,5,1,8,13]

public static List<Integer> getFibNumbers(int[] nums){}

- 0of 0 votes
Can multiple threads improve the time complexity to merge k sorted arrays? If so, how?

- 0of 0 votes
Gives an array of unsorted int (may have negative number),

rearrange the array such that the

num at the odd index is greater than the num at the even index.

example

giving 5, 2, 3, 4, 1, one of the expected result is 1,4,2,5,3,

please solve it in o(n) time, where n is the length of the array

public void rearrange(int[] nums){

}

- 0of 0 votes
`Given a string, find all possible combinations of the upper and lower case of each Alphabet char, keep the none Alphabet char as it is. example1 s = "ab", return: "Ab", "ab", "aB", "AB" example2 s = "a1b", return: "A1b", "a1b", "a1B", "A1B" public List<String> getPermutation(String s){ }`

- 0of 0 votes
For a given array, find the subarray (containing at least k number) which has the largest sum.

Example:

// [-4, -2, 1, -3], k = 2, return -1, and the subarray is [-2, 1]

// [1, 1, 1, 1, 1, 1], k = 3, return 6, and the subarray is [1, 1, 1, 1, 1, 1]

try to do it in O(n) time

Followup, if input is stream, how to solve it

public int maxSubArray(int[] nums, int k) {}

- 0of 0 votes
find maximum contiguous subarray sum with size (the number of the element in the subarray) <= k

a brute force method is very simple, can you do it better?

public int maxSum(int[] nums, int k){

}

- 0of 0 votes
// Read4K - Given a function which reads from a file or

// network stream up to 4k at a time, give a function which

// which can satisfy requests for arbitrary amounts of data

private int read4K(char[] buf) {

// GIVEN

}

// IMPLEMENT:

public int read(char[] buf, int toRead) { }

Due to network latency, if the read4K method return a value < 4k, it does not necessarily mean that we reach the End of File (EOF), in this case, you should continue to read the file until you reach toRead or EOF.

- 1of 1 vote
how to keep track of the sum in a sliding window for the data that are on disk

rather than memory