## SDE1 Interview Questions

- 1of 1 vote

AnswersGive you a pattern (digit in the pattern matches the corresponding

- ajay.raj January 05, 2018 in United States

number of letters,

letter means match the letter itself),

a string to determine whether match:

ex:

abc -> 'abc' true

'1oc3' -> 'aoczzz', 'bocabc' true| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

Answersassuming there is a freeway, n cars on the road, each car has a different integer speed, but are in the 1-n range. Now give you an array that represents the speed of each car. The starting order of the vehicle is the order of the array, ask the final formation of several clusters, the size of each cluster is how much? It can be understood that, although the vehicle speed is different, but even behind the car faster than the previous car, because you cannot pass, the last must only travel at the speed of the previous car, which formed a cluster. For example [2,4,1,3], finally [2,4] is a cluster, [1,3] is a cluster.

- ajay.raj January 04, 2018 in United States

Follow up is now suppose you want to add a car, the speed of the car than other large, but not sure the car's starting order, so that the final output of each possible cluster (List of List). Requirements can be adjusted and call the previous function, but can only be called once| Report Duplicate | Flag | PURGE

Google SDE1 - -1of 1 vote

AnswersThere is a stream of data <Symbol, timestamp, price>, and possibly also Correction Data <Symbol, timestamp, price> and then addData (symbol, timestamp, price) and correctData , Update minPrice, maxPrice, recentPrice in these two functions.

- ajay.raj January 04, 2018 in United States| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswerGive you a bunch of data <key, value, expiredTime>, design a data structure storage.

- ajay.raj January 04, 2018 in United States

About the idea, based on Map solution.

class NewMap {

Map <Integer, Integer> data = new HashMap <> (); // store key-value pairs

Map <Integer, Integer> expired = new HashMap <> (); // store key-expired pairs

}

Then implement the three functions get (), put (), expire ().| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

Answershow to implement the standard JSON.stringify and JSON.parse method

- ajay.raj January 01, 2018 in United States| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersFibonacci asked if you want to query 1-2 ^ 32 any one but the memory can only remember 2 ^ 20 number of how to do O (1) query

- ajay.raj December 22, 2017 in United States| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

Answerson a bench, sitting a number of people, and now come up a person, how to find a seat that is farthest from other people,

- ajay.raj December 22, 2017 in United States| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

Answers0 change to 01,1 change to 10.

- ajay.raj December 22, 2017 in United States

Line 0 is 0, the first line is 01, the second line is 0110, the third line 01101001. . . Keep asking what is the vale at kth row and jth col| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersAssuming your budget is N, you need to buy a rectangular land. Give a matrix of land prices and ask what is the largest area available for buying land. Land prices must be non-negative. For example, the budget is 11.

`1 2 3 1 0 1 4 2 1 9 10 4 The output should be. 1 2 3 0 1 4`

Such a matrix, because 1 +2 +3 +0 +1 +4 = 11. And the largest area.

- ajay.raj December 22, 2017 in United States| Report Duplicate | Flag | PURGE

Google SDE1 - 1of 1 vote

AnswersThe grid is n by m. Each cell contains a unique number on it. Maga is at the left-top and wants to go to right-bottom. But there is a condition. Maga can go through only two way - right and down. And the path of your move is called the nodes you have passed through over them. The path is called the most beautiful if the following condition is satisfied: The sorted of the path has to be lexicographic smallest as possible as. Output the most beautiful path for given grid.

Input:

In the first line you are given two numbers: the dimensions of grid - n and m. The next n lines contains m numbers. Each number is unique.

Output:

Output the most beautiful path.`4 2 3 1`

Return 1 2 4

- ajay.raj December 22, 2017 in United States

There are 2 ways to reach at (2,2) cell. The pathes are 4, 3, 1 or 4, 2, 1 respectively. So The most beautiful of them is 4, 2, 1 because if looking the sorted of them it looks like these : 1, 3, 4 and 1, 2, 4 respectively. So 1, 2, 4 is lexicographic smaller than the other. So the ans is 1 2 4.| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersTwo binary tree, to determine whether the two trees "similar", similar refers to the corresponding node in each tree in the left child and right child can be the same or in the opposite order, such as the following two trees, D, E where DE And DE can also be DE and ED, BC is the same, but the parent child relationship must be the same.

Followup is if left and right can be the same how to do,

- ajay.raj December 21, 2017 in United States`A / \ B C / \ D E A / \ C B / \ D E`

| Report Duplicate | Flag | PURGE

Google SDE1 - 1of 1 vote

Answersgiven n player competition, a bool canbeat (int a, int b) can return a whether beat b. Asked to return a sequence, the sequence only requires two adjacent to the front beat behind. Example, 1 beat 2, 2 beat 3, 3 beat 4, 3 beat 1, 4 beat 1 You can return "1234", that is, although 3,4 can beat 1, but not adjacent does not matter

- ajay.raj December 19, 2017 in United States| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersGive a two-dimensional array, which represents the value of the jump to the four directions, asked whether from the upper left corner to the lower right corner, follow up the shortest distance

- ajay.raj December 19, 2017 in United States| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersTo A and B two list, B is A shuffle obtained, find the mapping used shuffle,

- ajay.raj December 19, 2017 in United States

To be able to handle duplicate elements.

Follow-up: Requirements space O (1),| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

Answerslist, push is pushed to the head, pop return each element with the same probability. If you push a sorted list into it, how to pop a sorted list out. Follow-up, asked if pop is from head, and push each element with the same probability in any position, how pop a sorted list out?

- ajay.raj December 17, 2017 in United States| Report Duplicate | Flag | PURGE

Google SDE1 - 1of 1 vote

AnswersDetermines whether two strings containing backspace keys are the same.

- ajay.raj December 17, 2017 in United States| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersA car can receive two instructions A and R. A moves forward for a second and then doubles in speed. R stopped and then reversed. Given a String composed of AR, find where will the car stop.

- ajay.raj December 17, 2017 in United States

Follow-up, given the location if the final stop, find the instruction string.| Report Duplicate | Flag | PURGE

Google SDE1 - 1of 1 vote

Answersclass EncodingChecker {

- ajay.raj December 17, 2017 in United States

EncodingChecker (String pattern) {...} // constructor

boolean isEncoded (String s) {...} // for any string s, check whether s is encoded from pattern, see below

}

pattern = 'abcabc'

s = '123123' -> True

= 'cbzabc' -> False

= 'xyzxyz' -> True

Second question: If the pattern is not one but one million, how to write isEncoded?| Report Duplicate | Flag | PURGE

Google SDE1 - 1of 1 vote

AnswersDefine a flight class, the flight has four attributes start, end, start time and arrival time,

- ajay.raj December 16, 2017 in United States

There is also a list of strings, represents there is a crew member on that site.

given a list of flights, along with the list of strings mentioned above, asking if the flight crew availability is available for all flights.

example: flight 1 {A, B, 3, 10}, flight 2 {A, C, 1, 7}, flight 3 {C, D, 9, 11} crew member list {"A", "A"} Then return true because flight 3 can take off as flight 1 and flight 2 take off first, then flight 2 descends to bring flight crew A to C.

If flight 3 is {C, D, 6, 12} then return false because no flight crew member is in C at time 6.| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersGiven an array (may have negative num) and an integer(may be negative), find the smallest subarray whose sum is >= the given integer.

- ajay.raj December 16, 2017 in United States

int[] nums2 = {5,4,-8,16};

int x=10;

return 1, because 16 >= x

try to solve it in o(n) time

public static int miniSubArrayLen(int[] nums, int s) {| Report Duplicate | Flag | PURGE

Facebook SDE1 - 0of 0 votes

AnswersYou are given a binary tree in which each node contains an integer value.

- ajay.raj December 15, 2017 in United States

Find the number of paths that sum to a given value.

The path does not need to start at root, but need to end at a leaf, and it must go downwards (traveling only from parent nodes to child nodes).

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

class Solution {

public int pathSum(TreeNode root, int sum) {

}

}| Report Duplicate | Flag | PURGE

Google SDE1 - 1of 1 vote

AnswersGive a bunch of rectangles, randomly return a point within the rectangle, the probability to be proportional to the size of the rectangle.

- ajay.raj December 15, 2017 in United States

Follow up1: If you want to repeatedly call the function to generate random points how to do.

Follow up2: If the rectangles overlap how to do?| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersWe have 4 swimmers A,B,C,D with their records in 4 types of swimming races i.e Freestyle, Frontstroke , Backstroke and Butterffly respectively.The data is given as 4 arrays each for one player where each element in the array represents their time in particular race.

- Abhishek_108 December 14, 2017 in India

We have to select these players for a relay race such that the total time is minimum.| Report Duplicate | Flag | PURGE

Motorola SDE1 - 0of 0 votes

AnswersMagical binary strings are non-empty binary strings if the following two conditions are true:

- ajay.raj December 14, 2017 in United States

The number of 0's is equal to the number of 1's.

For every prefix of the binary string, the number of 1's should not be less than the number of 0's.

A magical string can contain multiple magical substrings. If two consecutive substrings are magical, then we can swap the substrings as long as the resulting string is still a magical string. Given a magical binary string, str, perform zero or more swap operations on its consecutive magical substrings such that the resulting string is aslexicographically large as possible. Two substrings are considered to be consecutive if the last character of the first substring occurs exactly one index before the first character of the second substring.

-----

Input Format

a single binary string, str.

Constraints

It is guaranteed that str is a binary string of 1's and 0's only.

1 ≤ length(str) ≤ 50

It is guaranteed that str is a magical string.

Output Format

Find a string denoting the lexicographically largest magical string that can be formed from str.

Sample Input 0

11011000

Sample output

11100100

Explanation of sample

Given the magical string str = 11011000, we can choose two consecutive magical substrings, 1100 and 10, to swap such that the resultant string, str' = 11100100, is the lexicographically largest possible magical string possible. Thus, we return the value of str', which is 11100100, as our answer.| Report Duplicate | Flag | PURGE

SDE1 - 0of 0 votes

AnswersQuestion: Given a sorted integer array, return sum of array so that each element is unique by adding some numbers to duplicate elements so that sum of unique elements is minimum.

- ajay.raj December 14, 2017 in United States

I.e., if all elements in the array are unique, return the sum. If some elements are duplicates, then increment them to make sure all elements are unique so that the sum of these unique elements is minimum.

Some examples:

input1[] = { 2, 3, 4, 5 } => return 19 = 2+3+4+5 (all elements are unique, so just add them up)

input2[] = { 1, 2, 2 } => return 6 = 1+2+3 (index 2 is duplicate, so increment it)

input3[] = { 2, 2, 4, 5 } => return 14 = 2+3+4+5 (index 1 is duplicate, so increment it)| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersMr. Octopus has recently shut down hisfactory and want to sell off his metal rods to a local businessman.

- ajay.raj December 14, 2017 in United States

In order to maximize profit, he should sellthe metal of same size and shape. If he sells metal rods of length ,he receives N x L xmetal_price. The remaining smallermetal rods will be thrown away. To cut the metal rods, he needs to pay cost_per_cut for every cut.

What is the maximum amount of money Mr.Octopus can make?

Input Format

First line of input contains cost_per_cut

Second line of input contains metal_price

Third line contains L, the number of rods Mr. Octopus has,followed by L integers in each line representinglength of each rod.

Output Format

Print the result corresponding to the testcase.

Constraints

1 <= metal_price, cost_per_cut <= 1000

1 <= L <= 50

Each element of lenghts will lie in range [1, 10000].

Sample Input#00

1

10

3

26

103

59

Sample Output#00

1770

Explanation Here cuts are pretty cheap. So we can make largenumber of cuts to reduce the amount of wood wasted. Most optimal lengths ofrods will be . So we will cut pieces of length from rod,and throw peice of length from it. Similarly we will cut piecesof length from rod and throw away a piece of length .From rod, we will cut pieces of length andthrow a piece of length . So in total we have pieces of length andwe have made cuts also. So total profit is

Sample Input#01

100

10

3

26

103

59

Sample Output#01

1230| Report Duplicate | Flag | PURGE

coursea SDE1 - 2of 2 votes

Answersgiven two strings a and b.

- ajay.raj December 14, 2017 in United States

print out the minimum number of flips of the characters in a such

that a is an anagram of b.| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersJSON parsing is an essential toolkit in modern web development. Whether you are on the client side or server side, these methods need to be fast, efficient and dependable. But what if one day...

- ajay.raj December 14, 2017 in United States

Suddenly, all of the JSON parser libraries went missing.

You have been called upon to save us all from impending doom.

Please re-implement the standard json parsing methods in your favorite language and restore the world to it's natural order.

Subproblem #1

Write a function, dictionaryToJson to convert a dictionary into a string.

For example, assuming you have dictionary like: dict(“a”: “apple”, “b”: dict(“b”: “blueberry”, “c”: “cranberry”)), the key field is always a string type, the value field could be a string type or a nested dictionary type. And the output would be "{a:apple,b:{b:blueberry,c:cranberry}}"

Subproblem #2

Write a reverse function, jsonToDictionary to convert a string into a dictionary.

Convert a string into the dictionary. e.g., given the input of “{a:apple,b:{b:blueberry,c:cranberry}}”, output dict(“a”: “apple”, “b”: dict(“b”: “blueberry”, “c”: “cranberry”)).

The names and values only contains letters. You can assume that there is no error in the input. You should not use regular expressions.| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersTo a binary array, if you want to move 1 to the array side, 0 to the other side, Can only swap two adjacent elements each time, ask the least number of swap Why? For example, the number of min swaps for [0, 1, 1, 0, 0] is 2 (01100 -> 10100 -> 11000)

- ajay.raj December 14, 2017 in United States| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersbalanceSum, return to the array to meet the minimum sum equal to the minimum index. Title conditions are all positive numbers, the array length> = 3, there must be solution. If a = [1,2,1,3] returns 3 because a [1] + a [2] = a [4]

- ajay.raj December 14, 2017 in United States| Report Duplicate | Flag | PURGE

Google SDE1

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window