## Software Engineer Interview Questions

- 0of 0 votes
I am surprised by this GS question.I thought this is one of the classic number theory partition problem which is so hard that the best algorithm is approximation one.

Given value, find all possible combination of ways which equals to that sum.

- 0of 0 votes
Google Fucked up question.

Given a random list of appointments (Start Date , End Date). Find all the appointments that are colliding.

This pretty easy looking question screwed me up today.There are tons of edge cases, I couldn't complete em all and 45 minutes pass like 15 minutes while explaining and coding same time.

- 0of 0 votes
You have two arrays of strings, words and parts. Return an array that contains the strings from words, modified so that any occurrences of the substrings from parts are surrounded by square brackets [], following these guidelines:

If several parts substrings occur in one string in words, choose the longest one. If there is still more than one such part, then choose the one that appears first in the string.

Example

For words = ["Apple", "Melon", "Orange", "Watermelon"] and parts = ["a", "mel", "lon", "el", "An"], the output should be

findSubstrings(words, parts) = ["Apple", "Me[lon]", "Or[a]nge", "Water[mel]on"].

While "Watermelon" contains three substrings from the parts array, "a", "mel", and "lon", "mel" is the longest substring that appears first in the string.

- 0of 0 votes
Given an integer n, replace its bits starting from the bit at position a to the bit at position b, inclusive, with the bits of integer k. Count from the least significant bit to the most significant bit, starting from 0.

Example:

For n = 1024, a = 1, b = 6 and k = 17, the output should be

insertBits(n, a, b, k) = 1058.

n = 100 0000 00002, k = 1 00012, 1058 = 100 0010 00102.

For n = 11, a = 1, b = 2 and k = 2, the output should be

insertBits(n, a, b, k) = 13.

n = 10112, k = 102, 13 = 11012.

- 0of 0 votes
Implement a function that takes two strings, s and x, as arguments and finds the first occurrence of the string x in s. The function should return an integer indicating the index in s of the first occurrence of x. If there are no occurrences of x in s, return -1.

Example:

For s = "AGoogleInterviewIsAwesome" and x = "IA", the output should be

strstr(s, x) = -1;

For s = "AGoogleIsAwesome" and x = "IsA", the output should be

strstr(s, x) = 10.

Apparently, my solution was not efficient enough with string lengths that are 2000+:`int findFirstSubstringOccurrence(String s, String x) { int sLen = s.length(); int xLen = x.length(); int tracker = 0; if (sLen == xLen) { if (s.equals(x)) { return 0; } else { return -1; } } else { if (xLen >= 1) { for (int index = 0; index < sLen; index++) { if (s.charAt(index) == x.charAt(tracker)) { tracker++; if (tracker == xLen) { return index - (xLen - 1); } } else { index -= tracker; tracker = 0; } } } } return -1; }`

- 2of 2 votes
Convert a string with digits into a literal representation of the number like: 1001 to one thousand one

- 1of 1 vote
Imagine a computer where you have no "/" (divide) operation. All other operations are implemented including addition, multiplication, binary shift etc. Implement function div(int a, int b) using available operators only.

- 2of 2 votes
Given the list of the numbers. In this list, there are the numbers from the Fibonacci sequence.

Write the algorithm that retrieves all the numbers which belong to the Fibonacci sequence of numbers.

- 2of 2 votes
Decompress string - string (s) followed by {n} denotes s repeating n times

"a(b(c){2}){2}d" decompresses to "abccbccd"

"((x){3}(y){2}z){2}" decompresses to "xxxyyzxxxyyz"

- 1of 1 vote
Write a function that takes two numbers as strings and returns the result as a string:

mul(l string, r string) : string

Assume the numbers might be too large to be parsed into a variable of any numeric type the language has.

- 0of 0 votes
Give a decimal number, such as 123. Asking a total of smaller num than 123 made up by 1 and 0 composed of decimal numbers.

111, 110, 101, 100, 11, 10, 1, 0.

- 0of 0 votes
To a word, and a map, map which is a word, ask this if a word is smash able? That is, you can smash one letter each time, and the rest of the letters can form a single word (the new word is still in the map) until it is completely hit.

For example: sprint -> print -> pint -> pit -> it -> i -> ""

- 2of 2 votes
Minimum number of swaps of chars in only one string to make two strings the same

- 0of 0 votes
Given a function that reads 4096 bytes from a file. write a new function which takes in a buffer and the number of bytes to be read from the user and uses the given function to write values into the buffer.

//given

//returns the number of bytes read

private int read4k(int[] buffer, int offset)

//TODO:

// it should return the bytes read

public int readIntoBuffer(int[] buffer, int byteCount);

- 1of 1 vote
Google

1st round

Given a box with N balls in it, each ball having a weight, randomly choose pick one out base on the weight.

Input ball1-> 5kg, ball2 -> 10kg and ball3 -> 35kg,

then Prob(ball1 chosen) = 10%, Prob(ball2) = 20%,

Prob(ball3) = 70% ;

Follow-up:

Select a ball randomly based on weights. Once a ball is chosen, remove it. Next time select from the remaining balls. Go on until there is nothing left in the box.

- 2of 2 votes
Find whether string S is periodic.

Periodic indicates S = nP.

e.g.

S = "ababab", then n = 3, and P = "ab"

S = "xxxxxx", then n = 1, and P = "x"

S = "aabbaaabba", then n = 2, and P = "aabba"

follow up:

Given string S, find out the P (repetitive pattern) of S.

- 1of 1 vote
Design a hit counter which counts the number of hits received in the past 5 minutes.

Each function accepts a timestamp parameter (in seconds granularity) and you may assume that calls are being made to the system in chronological order (ie, the timestamp is monotonically increasing). You may assume that the earliest timestamp starts at 1.

Example:

HitCounter counter = new HitCounter();

// hit at timestamp 1.

counter.hit(1);

// hit at timestamp 2.

counter.hit(2);

// hit at timestamp 3.

counter.hit(3);

// get hits at timestamp 4, should return 3.

counter.getHits(4);

// hit at timestamp 300.

counter.hit(300);

// get hits at timestamp 300, should return 4.

counter.getHits(300);

// get hits at timestamp 301, should return 3.

counter.getHits(301);

Follow-up:

Due to latency, several hits arrive roughly at the same time and the order of timestamps is not guaranteed chronological.

Follow up 2:

What if the number of hits per second could be very large? Does your design scale?

- 0of 0 votes
If I need to read .txt file (inside +4000 words) and print 100 most repeated which structure is the easiest:

hash table?

binary tree?

linked list?

Thanks

- 0of 0 votes
Hi, my question is about linked list? If I read .txt file (there is 5000 words inside) in to linked list. Is it possible to print 100 mostly repeated words and print them ??

example:

cat cat dog dog dog

dog3

cat 2

Thank you in advance for any help you can provide.

- 1of 3 votes
Round3 Google

For N light bulbs , implement two methods

I. isOn(int i) - find if the ith bulb is on or off.

II. toggle(int i, int j) - i <= j. Switch state (switch on if it's off, turn off if it's on) of every bulb in range i to j.

All bulbs are off initially.

- 2of 2 votes
/**

* Google

* Given a list of non-negative numbers and a target integer k,

* write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

**/

- 0of 0 votes
Write a function that given a string would print the 'expanded' version of it.

For example a2[bc2[c]]d would print out abcccbcccd

Note:

The number before the opening and closing square brackets is the multiplier for the characters within the square brackets

Method Signature [Java]:`public String expanded(String str)`

- 3of 3 votes
Amazon

Given an ArrayList of Nodes, with each Node having an ID and a parent ID, determine whether the List is given in preorder.

- 2of 2 votes
Google

Given an array a[] and an integer k, a[i] means flower at position a[i] will blossom at day i. Find the first day that there are k slots between two blooming flowers.

- 1of 1 vote
Google

Given a string that represents time like "15:31", find the next time that is formed by the numbers in the string(a number can be used more than once). For "15:31", the answer should be "15:33".

- 0of 0 votes
Find the Kth most Frequent Number in an Array.

Example:`arr[] = {1, 2, 3, 2, 1, 2, 2, 2, 3} k = 2 Result: 3 Because '3' is the second most occurring element.`

Follow up: What if the array is extremely large?

- 1of 1 vote
Twitter

Create a simple stack which takes a list of elements.

Each element contains a stack operator (push, pop, inc) and a value to either push/pop or two values, n and m,

which increment the bottom n values by m.

Then print the topmost value of the stack after every operation. If the stack is empty, print "empty"

- 0of 0 votes
design a zigzag iterator, implement the prev() and hasPrev function

- 0of 0 votes
Create a SQL-like language parser that manipulates directories and files (The compiler/parser may be created in any other language).

To summarize, I want you to create a "file and directory manipulation language" with the following rules/syntax (you may create another commands):

CREATE DIR <path>

CREATE FILE <name> IN <path> [WITH <data>]

'WITH' insert the <data> in the file on the fly, but it's optional

GET DATA FROM <path/to/file>

Examples on how this language may be used:`import FDML ex = "Hey guys" data = FDML.get('GET DATA FROM "./path/to/file"'); FDML.statement("""CREATE DIR "./imgs"; CREATE FILE "test.txt" IN "./path/to/dir""") FDML.statement('CREATE FILE "welcome.txt" IN "./path/to/dir" WITH "{}"'.format(ex)) print(data)`

Or those commands can be run in a shell:

> fdml "CREATE DIR './dir'"

> /dir was created!

- 2of 2 votes
DropBox Dec 2017

Congrats to Brian landing @DropBox

Round 3：

Develop an web crawler API, find all sub-sites reachable from a given URL.

Given this method - vector<string> getURLs(string url);

Comparison of DFS vs BFS in the scenario

Follow up：

Support multi-thearding.

Round 4：

Build an ID allocator. Max ID value is given as MAX. Allocate IDs from 0 to MAX.

Must be able to handle when an ID gets released.

Must be able to handle exceptions.

Follow-up: Improve time/space efficiency.

Optimal approach:

Segment tree + bit map.

Looking for interview experience sharing and coaching?

Visit aonecode.com for private lessons by FB, Google and Uber engineers

ONE TO ONE real-time coaching on SYSTEM DESIGN, ALGORITHMS, and mock interviews.

Feel free to email us aonecoding@gmail.com with any questions. Thanks!