## SDE1 Interview Questions

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

rather than memory

- 0of 0 votes
Insert a node in a complete binary tree efficiently.

it is not BST, it is just a regular binary tree

public TreeNode insert(TreeNode root, int val){

}

this my solution using bfs (O(n) time), is there any more efficient method?`import java.util.*; class TreeNode{ int val; TreeNode left; TreeNode right; public TreeNode(int val){ this.val = val; } } class Solution{ public TreeNode insertCompleteTree(TreeNode root, int val){ if(root == null){ return new TreeNode(val); } Queue<TreeNode> q = new LinkedList<>(); q.add(root); while(!q.isEmpty()){ int size = q.size(); for(int i = 0; i < size; i++){ TreeNode cur = q.remove(); if(cur.left == null){ cur.left = new TreeNode(val); return root; }else{ q.add(cur.left); } if(cur.right == null){ cur.right = new TreeNode(val); return root; }else{ q.add(cur.right); } } } return null; } public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if(root == null){ return res; } Queue<TreeNode> q = new LinkedList<>(); q.add(root); while(!q.isEmpty()){ int size = q.size(); List<Integer> list = new ArrayList<>(); for(int i = 0; i < size; i++){ TreeNode cur = q.remove(); list.add(cur.val); if(cur.left != null){ q.add(cur.left); } if(cur.right != null){ q.add(cur.right); } } res.add(list); } return res; } public static void main(String[] args){ Solution s = new Solution(); TreeNode root = null; int[] nums = {1, 2, 3, 4, 5, 6, 7}; for(int num : nums){ root = s.insertCompleteTree(root, num); System.out.println(s.levelOrder(root)); } } }`

- 0of 0 votes
A table has some number of balls at various positions on a line segment.

All are moving with same speed in one or the other direction.

Wherever a collision occurs they change direction.

A ball falls from the edges of the table.

Find the time when all balls fall of the table

given initial position of each ball and speeds

- 0of 0 votes
given a graph: example -> A company holds 10% of B company’s share,

B company holds 5% of C company’s share, A company holds 2% of C company’s share,

what percent of C company’s share does A company hold?

- 0of 0 votes
`// Design and implement key value system // // string -> string // Insert a key-value pair or modify a value void put(string key, string value); // Delete a key-value pair void delete(string key); // Gets a value given a snapshot string get(string key, Snapshot snap); // Take a snapshot Snapshot takeSnapshot(); // Delete a snapshot void deleteSnapshot(Snapshot snap); // put(k1,v1) // put(k2,v2) // put(k3,v3) // takeSnapshot -> snap1 { k1 -> v1, k2 -> v2, k3 -> v3 } // get(k1,snap1) -> v1 // put(k1,v4) // delete(k3) // takeSnapshot -> snap2 { k1 -> v4, k2 -> v2 } // get(k1,snap2) -> v4 // get(k1,snap1) -> v1 // get(k3,snap2) -> XX // deleteSnapshot(snap1) // get(k1,snap1) -> XX // Space efficient is more important than time efficient, thus please use as small space as possible.`

- 0of 0 votes
What is the cost / complexity of a String.indexof() function call in java?

- 0of 0 votes
Given a task sequence tasks such as ABBABBC, and an integer k, which is the cool down time between two same tasks. Assume the execution for each individual task is 1 unit.

rearrange the task sequence such that the execution time is minimal.

Example:

S = AAABBBCCC, K = 3

Result: ABCABCABC (all 'A's are 3 distance apart, similarly with B's and C's), thus return 9

S = AAABC, K=2

Result: ABCA_ _A, thus return 7

S = AAADBBCC, K = 2:

Result: ABCABCDA, thus return 8

public int rearrangeTasks(String tasks, int cooldown){

}

- 0of 0 votes
Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times. Find these repeating numbers in O(n) and using only constant memory space.

Try to do it in one pass

example

[4, 2, 0, 5, 2, 0, 1] return: 0, 2

[1, 2, 3, 0, 0, 1, 3, 6, 6,6] return 0, 1, 3, 6

public List<Integer> findRepeat(int nums[]){

}

- 0of 0 votes
How to check the validity of a 4 digit credit card expiration date (mm/yy)

that still works 100 years from now.

public boolean isValid(String s){

}

- 0of 0 votes
`convert a ternary expression into a Binary tree structure. a?b:c a / \ b c a?b?c:d:e a / \ b e / \ c d class TreeNode{ char val; TreeNode left; TreeNode right; public TreeNode(char val){ this.val = val; } } public TreeNode build(String s){}`

try to do it in o(n) time complexity, n is the size of the string

- 0of 0 votes
`Suppose you have a 2-D grid. Each point is either land or water. There is also a start point and a goal. There are also keys that open up doors. Each key corresponds to one door. Implement a function that returns the shortest path from the start to the goal using land tiles, keys and open doors. Data Representation The board will be passed as an array of chars. A board can have the following tiles. 0 = Water 1 = Land 2 = Start 3 = Goal uppercase = door lowercase = key Example Maps (keys at each step are not required) `No doors` char[][] board1 = {{'0', '2', '1', '1', '1'}, {'0', '1', '0', '0', '1'}, {'0', '1', '0', '0', '3'}, {'0', '1', '0', '0', '1'}, {'0', '1', '1', '1', '1'}}; path : [0,1]->[0,2]->[0,3]->[0,4]->[1,4]->[2,4] `One door` char[][] board2 = {{'0', '2', '1', '1', '1'}, {'0', '1', 'a', '0', 'A'}, {'0', '1', '0', '0', '3'}, {'0', '1', '0', '0', '1'}, {'0', '1', '1', '1', '1'}}; path : [0,1]->[0,2]->[1,2]->[0,2]->[0,3]->[0,4]->[1,4]->[2,4]`

public List<int[]> solve(char[][] board) {

- 0of 0 votes
Group a list of words so that the same group of words have a common substring, and this common substring is also in the word lists,

example

[cow "," cold "," an "," co "], return [[" can "," an "], [" cow "," cold "," co "]]

["can", "cow", "cold"], return [["can"], ["cow"], ["cold"]]

["c", "ca", "can"], return [["c", "ca", "can"]]

public List<List<String>> groupWords(String[] s)

- 1of 1 vote
Write a function that returns true if the binary representation of an integer is a palindrome.

9 = 1001 = palindrome

8 = 1000 = not palindrome

- 0of 0 votes
Enter a two digit number, find the year closest to this year.

Example input 99, return 1999;

Input 15, return 2015.

public int getClosestYear(int input){

}

- -2of 4 votes
generate random number which differs from the number generated last time in the range of [min, max)

what is the best way to do it?

public int getNumber(int min, int max){

}

- 1of 1 vote
Given a undirected graph with each node representing a char and a word,

check if the word can be formed by any path of the graph

example

graph:

a--d--o--g--a--c--t

word : dog, return true;

word: cat, return false;

The same letter may not be used more than once.`class Node { char label; List<Node> neighbors; Node(char x) { label = x; neighbors = new ArrayList<>(); } } class Solution { public boolean exist(List<Node> nodes, String word) { } }`

- 0of 0 votes
Given a Binary tree (Not binary Search Tree ), find the inorder successor of a node.

`class TreeNode{ TreeNode left; TreeNode right; int val; public TreeNode(int val){ this.val = val; } } public TreeNode inOrderSuccessor(TreeNode root, TreeNode n) {`

- 0of 0 votes
Given a positive integer n, find the no of integers less than equal to n, whose binary representation doesn't contain consecutive 1s.

eg:

I/P : 4

O/P: 4 (0,1,2,4 Valid)

public int count(int n){

}

- 1of 1 vote
Given m 0 and n 1, count the total number of permutations where two 1 cannot be adjacent

public int count(int m, int n){

}

- 0of 0 votes
Given a binary tree, return all the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:

Given a binary tree`/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ 1 / \ 2 3 / \ 4 5 Return [4,2,1,3] and [5,2,1,3]. Public List<List<Integer>> getLongestPath(TreeNode root) { }`

- 1of 1 vote
write a function that randomly return a random Fibonacci number in range [min, max)

public int getRandom (int min, int max){}

- 0of 0 votes
write a function that randomly return a random prime number in range [min, max)

public int getRandom (int min, int max){}

- 0of 0 votes
how does java implement priority queue?

i answered min heap, the interviewer seemed it was not right

- 0of 0 votes
`class Log{ String fun_name; String enterOrExit;// enter or exit int time; public Log(String fun_name, String enterOrExit, int time){ this. fun_name = fun_name; this. enterOrExit = enterOrExit; this.time = time; } } public void printInclusiveAndExclusiveTime (List<Log> logs){ } Log for some functions, calculate the inclusive time and exclusive time for each function E.g Fun_name enter / exit time F1 enter 1 F2 enter 2 F2 exit 3 F1 exit 4 F1: inclusive time = 4-1 = 3, exclusive time = 3-1 = 2 F2: inclusive time = 3-2 = 1, exclusive time = 1`

- 0of 0 votes
I have a series of strings sort {"A","B","C","D"....}

Sort them and display them in 4 columns.Instead of displaying horizontally they should be display vertical if the string size is greater than 4.

Important:null should be in last row alone

eg

A C D E

B

If string size is less than 4

A B C D

Also,the program should be production ready and reusable,readjust the values upon deletion.

- 0of 0 votes
tokenize string, "" and [] are token flags, such as

mytable "foo" [bar] "" [[[[]]].

"" Turned into ",]] turned into], [[not escaped

The results of the example given above:

mytable

foo

bar "

[[]

public List<String> tokenizestring(String s){

}

- 0of 0 votes
F (n) = 3n + 1 (if n is odd) or n / 2 (if n is even)

Collapse sequence refers to each number according to this formula

until the sequence becomes equal to 1,

Find the number (which is not greater than 10000), which will have the longest Collapse sequence.

public int getlongestCollapsesequence(int n){

}

- 0of 0 votes
write a function to generate a random 4 digit unique even number, the four digits cannot be the same, 1234 is valid, but 1134 is not valid

- 0of 0 votes
You've escaped Commander Lambda's exploding space station along with numerous escape pods full of bunnies. But - oh no! - one of the escape pods has flown into a nearby nebula, causing you to lose track of it. You start monitoring the nebula, but unfortunately, just a moment too late to find where the pod went. However, you do find that the gas of the steadily expanding nebula follows a simple pattern, meaning that you should be able to determine the previous state of the gas and narrow down where you might find the pod.

From the scans of the nebula, you have found that it is very flat and distributed in distinct patches, so you can model it as a 2D grid. You find that the current existence of gas in a cell of the grid is determined exactly by its 4 nearby cells, specifically, (1) that cell, (2) the cell below it, (3) the cell to the right of it, and (4) the cell below and to the right of it. If, in the current state, exactly 1 of those 4 cells in the 2x2 block has gas, then it will also have gas in the next state. Otherwise, the cell will be empty in the next state.

For example, let's say the previous state of the grid (p) was:

.O..

..O.

...O

O...

To see how this grid will change to become the current grid (c) over the next time step, consider the 2x2 blocks of cells around each cell. Of the 2x2 block of [p[0][0], p[0][1], p[1][0], p[1][1]], only p[0][1] has gas in it, which means this 2x2 block would become cell c[0][0] with gas in the next time step:

.O -> O

..

Likewise, in the next 2x2 block to the right consisting of [p[0][1], p[0][2], p[1][1], p[1][2]], two of the containing cells have gas, so in the next state of the grid, c[0][1] will NOT have gas:

O. -> .

.O

Following this pattern to its conclusion, from the previous state p, the current state of the grid c will be:

O.O

.O.

O.O

Note that the resulting output will have 1 fewer row and column, since the bottom and rightmost cells do not have a cell below and to the right of them, respectively.

Write a function answer(g) where g is an array of array of bools saying whether there is gas in each cell (the current scan of the nebula), and return an int with the number of possible previous states that could have resulted in that grid after 1 time step. For instance, if the function were given the current state c above, it would deduce that the possible previous states were p (given above) as well as its horizontal and vertical reflections, and would return 4. The width of the grid will be between 3 and 50 inclusive, and the height of the grid will be between 3 and 9 inclusive. The answer will always be less than one billion (10^9).

- 0of 0 votes
For a string chemical formula like “C6H2(NO2)3CH3”, and output a map with key as element and value as its count.

element can have two chars, for example Fe2(SO4)3

public HashMap<Character, Integer> getCount(String chemicals){

}