Recent Interview Questions
- 3of 3 votes
AnswersAsked in Google - 2020, Goldman Sachs - 2020
- Gaurav Sohaliya August 22, 2020 in India
Given two Array.
A = [1,3,4,2,5,6] B = [3,4,6,5,7]
we have to remove 3,1,2,6 and Insert 6,7 to make A equal to B.
we can delete and insert any element at anywhere from first array and make that array same as second array. Output is Minimum Number of elements required to be insert in first array.
constraints:
1 <= First Array Size <= 10^5
1<= Second Array SIze <= 10^5
1 <= firstarray[i] <= 10^9
1 <= secondarray <= 10^9
second array consist of distinct element.
Note : it is same as edit distance but here our constraints are 10^5.| Report Duplicate | Flag | PURGE
Goldman Sachs Software Engineer / Developer Arrays - 3of 3 votes
Answers/**
- aonecoding January 13, 2018 in United States
* 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.
**/| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersYou are given an old touch smartphone numbers having dial pad and calculator app.
- neovivek14 July 23, 2017 in United States
Aim: The goal is to type a number on dialpad.
But as phone is old, some of the numbers and some operations can't be touched.
For eg. 2,3,5,9 keys are not responding , i.e you cannot use them
But you can always make a number using other numbers and operations in Calculator. There could be multiple ways of making a number
.Calculator have 1-9 and +,-,*,/,= as operations. Once you have made the number in Calculator you can copy the number and use it.
You have to find minimum number to touches required to obtain a number.
#Input:#
There will be multiple Test cases .Each test case will consist of 4 lines
1) First line will consist of N,M,O
N: no of keys working in Dialpad (out of 0,1,2,3,4,5,6,7,8,9)
M:types of operations supported (+,-,*,/)
O: Max no of touches allowed
2) second line of input contains the digits that are working e.g 0,2,3,4,6.
3) Third line contains the valued describing operations, 1(+),2(-),3(*),4(/)
4) fourth line contains the number that we want to make .
#Output:#
Output contains 1 line printing the number of touches required to make the number
#Sample Test Case:#
1 // No of test cases
5 3 5 // N ,M, O
1 2 4 6 0 // digits that are working (total number of digits = N),
1 2 3 // describing operations allowed (1--> '+', 2--> '-', 3--> '*' , 4--> '/' )(total number is equals to M)
5 // number we want to make
Answer 3
How 4? 1+4= , "=" is also counted as a touch
2nd Sample Case
3 // No of Test cases
6 4 5 // N ,M, O
1 2 4 6 9 8 // digits that are working (total number of digits = N),
1 2 3 4 // describing operations allowed (1--> +, 2--> -, 3--> , 4-->/)
91 // number we want to make
6 2 4 // 2nd test case
0 1 3 5 7 9
1 2 4 // +, -, / allowed here
28
5 2 10
1 2 6 7 8
2 3 // -, allowed
981
#Output:#
2 // 91 can be made by directly entering 91 as 1,9 digits are working, so only 2 operations
5// 35-7=, other ways are 1+3*7=
9//62*16-11=
Order for computation will be followed as symbols entered, if + comes, it will be computed first
One more example: lets say 1,4,6,7,8,9 works and +,-,* works.
2,3,5 and / doesn't work.
If you have to type 18-> 2 operations. (Each touch is considered an operation),br> If you have to type 5 -> '1+4=' that requires 4 operations. There could be other ways to make '5'.| Report Duplicate | Flag | PURGE
Samsung Software Engineer Algorithm - 3of 3 votes
Answers1 year exp. Interviewed at Cambridge, MA
- aonecoding July 11, 2017 in United States
Round1
LC304. Follow-up: given a char stream instead a string as the input, get the longest substring with at most K distinct characters.
Round2
Find out the area of a number of squares on a plane, an advanced version of LC223.
Had no clue on that problem at all so the interviewer kindly gave another one LC305.
Round3
Similar to LC393 but the interviewer made a slightly different rule for encoding.
Follow-up: decode with utf-16. It took quite a while for me to understand the rules.
Round4
Card game rule: the hand is drawn from a pack of cards (no jokers).
Play cards ONLY when they are
1. 3 of a kind ('AAA' ) or 4 of a kind('AAAA’).
2. a straight flush of 3 or more cards('JQK' or 'A23456...' in the same suit).
Find out whether the player is able to play the whole hand given.
e.g. [Spade A, Spade K, Spade Q, Diamond Q, Heart Q] return false.
[Spade A, Spade K, Spade Q, Diamond Q, Heart Q, Club Q] return true.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
Answersn points on a 2D space. You observe the points from (0,0) with viewing direction and viewing angle.
- Casper November 17, 2016 in United States
Given an array (xn,yn), and a viewing angle v (45 degree), find the direction that can observe max number of points.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer C++ - 3of 3 votes
AnswersWrite your own regular expression parser for following condition:
- techpanja October 22, 2013 in United States for yammer
az*b can match any string that starts with and ends with b and 0 or more Z's between. for e.g. azb, azzzb etc.
a.b can match anything between a and b e.g. ajsdskjb etc.
Your function will have to parameters: Input String and Regex. Return true/false if the input string satisfies the regex condition. Note: The input string can contain multiple regex. For e.g. az*bc.g| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer - 3of 3 votes
AnswersWrite a class that will have following functions:
- JSDUDE May 04, 2013 in United States
long CheckOut()
CheckIn(long)
Range of values is 1 to LONG_MAX
At any given point in time checkout should return the minimum available LONG number
Checkin can return the value back
No need to check for border conditions (e.g. check out when all values are exhausted)
Implement:
1. long checkout()
2. void checkIn(long input)| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 3of 3 votes
AnswersIn a Binary maze with 0 and 1, 0 is the valid cell to which we can travel and 1 means that the cell is blocked. Given source and destination. We have to find-
- richa.cseit July 03, 2018 in India
1. IF path exists, if yes, find shortest path.
2. If we are given a chance to toggle single cell from 1 to 0 , which cell you will toggle so that you will surely get the shortest path.| Report Duplicate | Flag | PURGE
Uber SDE-3 Algorithm - 3of 3 votes
AnswersConvert a string with digits into a literal representation of the number like: 1001 to one thousand one
- aonecoding February 15, 2018 in United States| Report Duplicate | Flag | PURGE
Uber Software Engineer Algorithm - 3of 3 votes
AnswersDesign a hit counter which counts the number of hits received in the past 5 minutes.
- aonecoding January 18, 2018 in United States
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?| Report Duplicate | Flag | PURGE
Dropbox Software Engineer Algorithm - 3of 3 votes
AnswersWe are planning an orienteering game.
- ajay.raj September 19, 2017 in United States
The aim of this game is to arrive at the goal (G) from the start (S) with the shortest distance.
However, the players have to pass all the checkpoints (@) on the map.
An orienteering map is to be given in the following format.
########
#@....G#
##.##@##
#..@..S#
#@.....#
########
In this problem, an orienteering map is to be given.
Calculate the minimum distance from the start to the goal with passing all the checkpoints.
Specification
* A map consists of 5 characters as following.
You can assume that the map does not contain any invalid characters and
the map has exactly one start symbol 'S' and exactly one goal symbol 'G'.
* 'S' means the orienteering start.
* 'G' means the orienteering goal.
* '@' means an orienteering checkpoint.
* '.' means an opened-block that players can pass.
* '#' means a closed-block that players cannot pass.
* It is allowed to move only by one step vertically or horizontally (up, down, left, or right) to the
next block.
Other types of movements, such as moving diagonally (left up, right up, left down and right down)
and skipping one or more blocks, are NOT permitted.
* You MUST NOT get out of the map.
* Distance is to be defined as the number of movements to the different blocks.
* You CAN pass opened-blocks, checkpoints, the start, and the goal more than once if necessary.
* You can assume that parameters satisfy following conditions.
* 1 <= width <= 100
* 1 <= height <= 100
* The maximum number of checkpoints is 18.| Report Duplicate | Flag | PURGE
Facebook SDE1 - 3of 3 votes
AnswersGiven a list of system packages, some packages cannot be installed until the other packages are installed. Provide a valid sequence to install all of the packages.
- aonecoding January 15, 2017 in United States
e.g.
a relies on b
b relies on c
then a valid sequence is [c, b, a]| Report Duplicate | Flag | PURGE
Uber Software Engineer Algorithm - 3of 3 votes
AnswersDesign Live comments. If your facebook.com homepage is open with bunch of feeds and if someone comments on those feeds, the comments should automatically show up in facebook.com home page without refreshing the page. Feeds could be a simple status update by a friend, post in a group, post by a person you're following, post in a page you've liked etc.
- Rejected September 29, 2015 in United States
Few things what they are looking for -
1. How do you solve it initially and how do you scale it?
2. How do you scale push model in-case if you choose PUSH model to solve it?
3. If push cannot scale how do you solve it?
4. How pull model solves it?
5. When will you use push vs pull?| Report Duplicate | Flag | PURGE
Facebook Software Developer Software Design - 3of 3 votes
AnswersYou are given an external library (lets say a binary search library) which claims to have certain running time complexity. How would you verify that the claim of the rum time complexity is correct.
- deadman July 09, 2013 in India
I told him give input of different length(1,N,N^2...) and see the differential change in running time. But he said in the shared system resources it wont give the good idea of running time.
Any other way we can do this?| Report Duplicate | Flag | PURGE
- 3of 3 votes
AnswersHow would you test the search functionality on Bing?
- aap67 June 08, 2013 in United States| Report Duplicate | Flag | PURGE
Testing / Quality Assurance Testing - 3of 3 votes
AnswersDesign a system for showing quotes on the web.
- Steve November 09, 2012 in United States
For example, when the user is looking at page A, part of which is reproduced in page B, the system could highlight part of page A present the user with a link to page B.
This is an open-ended system design question.
What constitutes a quote?
How do you find quotes?
How do you make it scale to the web?
How do you handle updates?
How would you arrange the servers?
What data structures would you use?
How much storage would you need?
How would the user agent present information about quotes?| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Application / UI Design - 3of 3 votes
AnswersGoogle
- aonecoding January 05, 2018 in United States
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.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
Answers3.1 design: design fb inbox search —> just focus on the post
- aonecoding July 15, 2017 in United States
4.1 binary tree to circular double linked list.
4.2 two arrays, find the common elements of two sorted array. if one array is small, the other is very big.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 3of 3 votes
AnswersGoogle full-time phD candidate w/ work experience.
- aonecoding June 22, 2017 in United States
Q1. On a 1 meter walkroad, randomly generate rain. The raindrop is 1 centimeter wide.
Simulate how raindrops cover the 1 meter [0~1] road. How many drops does it take to fully cover the 1meter?
Q2. Find out the maximum number of isosceles triangles you can make from a plane of points(cannot reuse points)
Q3.Longest holiday - Every city has a different days of holidays every week. You may only travel to another city at the weekends. What is the max days of holiday you can get this year.
Q4.
Design merchandising product data storage service| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersA soccer league has n matches with A,B,C teams with number of goals scored by each team in each match.If a team wins against another team ,It gets 3 points and lost team gets 0 point.If a tie ,both team gets 1 point.Now how do you frame the ranking of teams.
- sriramMS December 20, 2012 in United States
1) All teams played n matches.
2) A team 1 match,B Team 2 matches, 3 team 3 matches.Like wise it goes.
They looked for coding and data structure techniques.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Data Structures - 3of 3 votes
AnswersGiven two two integer arrays. Find the longest common subsequence.
- acoding167 June 02, 2019 in United States
eg: a =[1 5 2 6 3 7], b = [5 6 7 1 2 3]. return [1 2 3] or [5 6 7]| Report Duplicate | Flag | PURGE
Google Software Engineer - 3of 3 votes
AnswersApple phone interview
- aonecoding July 23, 2017 in United States
Given an API to find all IPv4 addresses in a log file, find all IPs that occurred only once.
Follow-up: What if the log comes from a data stream.
Follow-up: If the machine has 4GB RAM, is there going to be a problem?| Report Duplicate | Flag | PURGE
Apple Backend Developer Algorithm - 3of 3 votes
Answers3. Write a class that represents a minimal heap. The heap class should at a minimum support the following methods:
- Pritam March 04, 2014 in United States
- AllocTinyHeap() which should initialize the heap with a given amount of bytes
- DeleteTinyHeap() which frees all memory associated with the heap
- TinyAlloc() which allocates a given number of bytes on the heap if there is room
- TinyFree() which frees a specific location on the heap
You may define whatever parameters are necessary for the above methods as well as write any additional methods. Overall consideration will be given to correctness, design, code readability as well as any unit testing done. As part of a final solution please submit test cases you used to verify correctness in addition to any unit tests done.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Algorithm - 3of 3 votes
AnswerHow would you work with a backend engineer to design a news feed on mobile. Imagine that we only care about showing the user feed and posting a picture.
- tbag February 15, 2018 in United States
Follow-ups
1. what kind of apis would you want him to expose and what would they look like
2. How would you refresh the news feed on the iOS app and how often?
3. How would you cache the data/images. What size cache would you have?| Report Duplicate | Flag | PURGE
Facebook iOS Developer System Design - 3of 3 votes
AnswerBob And GCD
- uppubhai December 11, 2017 in India
Bob has an array A of size N. He doesn't like arrays in which the GCD of all elements is not K. He can perform multiple operations on an array. In each operation, he can either increase or decrease the value of an element by 1.
You have to tell the minimum operation Bob will take to make GCD of all elements in an array equal to KK ?
GCD here is Greatest Common Divisor.
Input Format
The first line contains T, the number of test cases.
For Each Testcase :
The first line contains 2 integers - K and N respectively, separated by a space.
The second line contains N integers, separated by a space, in order of their position in array.
Input Constraints
1≤T≤10
1≤N≤10^6
1≤A[i]≤10^6
1≤K≤10^6
Output Format
For each test case, print minimum number of operations Bob take in a new line.
Sample Input
1
5 3
4 5 6
Ans - 2| Report Duplicate | Flag | PURGE
ThoughtWorks SDE1 - 3of 3 votes
AnswerDesign Uber or Lyft like architecture keeping scale, latency and availability in mind. The design can be at macro level first, that is, major components like persistent store (SQL/NoSQL/redundant), cache, communication/messaging. The design and if time permits, details will then be discussed/challenged.
- Blue Ocean November 29, 2015 in United States| Report Duplicate | Flag | PURGE
Amazon Principal Software Engineer Distributed Computing - 3of 3 votes
AnswerYou want to go for a movie. You will select a day Sun-sat by flipping coins (You have infinite coins) such that the probability of selecting any day is always same.
- Mumbaiya_Chori January 30, 2015 in India
My answer: flip seven coins, select the coins which have heads if x coins are head, flip head coins. Follow this process until you just have one day left.
The interviewer confused me in this approach and made me believe I am wrong. But later he said that this method may work.
Also the answer he gave is flip 3 coins so outcome will be 2^3 you can discard all heads or alll tails| Report Duplicate | Flag | PURGE
Pubamatic - 3of 3 votes
AnswersI was asked to sort extra large file 10GB which contains single word in each line, within 4GB RAM. I told External sort and optimised it with min-heap but interviewer was asking to optimise disk I/O. As last he told that use CS fundamentals. Don't know what was he expecting. Please help.
- sulabh.shkl March 22, 2020 in India| Report Duplicate | Flag | PURGE
Microsoft Software Developer Algorithm - 3of 3 votes
AnswersHow to find out distinct ngrams from a email_alias.
- ashwini.padhy89 December 05, 2018 in India
For instance xyz@gmail.com here the email_alias is xyz.for xyz if we want to find bigram then function should have input the email_id,and the number of grams lets say 2.
Than it has to return the distinct count of ngrams present in the email_alias.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Coding - 3of 3 votes
AnswersThe power of three: 3 reasons why your business needs an app.
- shrivcommediait10 October 08, 2018 in United States| Report Duplicate | Flag | PURGE
Adjetter Media Network Pvt Ltd. Top mobile application Development Company in India