## Recent Interview Questions

- 21of 37 votes

AnswersGive you an array which has n integers,it has both positive and negative integers.Now you need sort this array in a special way.After that,the negative integers should in the front,and the positive integers should in the back.Also the relative position should not be changed.

- lxfuhuo August 23, 2013 in CHINA

eg. -1 1 3 -2 2 ans: -1 -2 1 3 2.

o(n)time complexity and o(1) space complexity is perfect.| Report Duplicate | Flag | PURGE

Google Intern Algorithm - 10of 14 votes

AnswersGiven an int array which might contain duplicates, find the largest subset of it which form a sequence.

- learner October 06, 2011 in -

Eg. {1,6,10,4,7,9,5}

then ans is 4,5,6,7

Sorting is an obvious solution. Can this be done in O(n) time| Report Duplicate | Flag | PURGE

Google Software Engineer in Test Software Engineer / Developer Arrays Algorithm - 5of 5 votes

AnswersGiven a N*N Matrix.

- 646 November 23, 2010

All rows are sorted, and all columns are sorted.

Find the Kth Largest element of the matrix.| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm - 4of 4 votes

AnswersIf [a1,a2,a3...,an,b1,b2...bn] is given input change this to [a1,b1,a2,b2.....an,bn] , solution should be in-place

- Anonymous February 05, 2011| Report Duplicate | Flag | PURGE

Amazon Microsoft Developer Program Engineer Software Engineer / Developer Algorithm Arrays - 2of 2 votes

AnswersRound 1: Q2:

- Abee July 20, 2011

Puzzle

Given 25 horses, find the best 3 horses with minimum number of races. Each race can have only 5 horses. You don't have a timer.| Report Duplicate | Flag | PURGE

Amazon Software Engineer / Developer Brain Teasers Highbridge Capital Deshaw Inc - 17of 17 votes

AnswersIf a=1, b=2, c=3,....z=26. Given a string, find all possible codes that string can generate. Give a count as well as print the strings.

- diffuser78 June 07, 2013 in United States

For example:

Input: "1123". You need to general all valid alphabet codes from this string.

Output List

aabc //a = 1, a = 1, b = 2, c = 3

kbc // since k is 11, b = 2, c= 3

alc // a = 1, l = 12, c = 3

aaw // a= 1, a =1, w= 23

kw // k = 11, w = 23| Report Duplicate | Flag | PURGE

Facebook Software Engineer / Developer Algorithm Coding - 4of 8 votes

AnswersDesign an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n >=0 )

- Aashish June 27, 2012 in India

You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm - 0of 0 votes

AnswersPath to deepest 1 in a binary tree.

- shilpa February 02, 2011

We have a binary tree (not a BST) made up of only 0s and 1s. we need to find the deepest 1 with a path from root made up only of 1's.| Report Duplicate | Flag | PURGE

Microsoft Software Engineer in Test Algorithm - 2of 2 votes

Answersfind the longest palindrome in a string?

- handiaya November 09, 2009| Report Duplicate | Flag | PURGE

Microsoft Amazon Software Engineer / Developer Algorithm Arrays C++ Coding String Manipulation C - 19of 19 votes

AnswersGiven two strings a and b, find whether any anagram of string a is a sub-string of string b. For eg:

- Masterchief117 March 23, 2014 in United States

if a = xyz and b = afdgzyxksldfm then the program should return true.| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer String Manipulation - 33of 39 votes

AnswersGiven an array of integers. Find two disjoint contiguous sub-arrays such that the absolute difference between the sum of two sub-array is maximum.

- LAP June 10, 2013 in United States

* The sub-arrays should not overlap.

eg- [2 -1 -2 1 -4 2 8] ans - (-1 -2 1 -4) (2 8), diff = 16

I gave him o(n^2) algorithm but he was not satisfied.| Report Duplicate | Flag | PURGE

Google Algorithm - 2of 2 votes

Answersgive me the code for :

Given a string say "I am a human being" the output should reverse all letters of each word but not the whole string as such.

Eg: O/p should be "I ma a namuh gnieb"

I somewhat wrote the code, but i was asked what if there are extra spaces etc.

(i am able to write the code sitting at my desktop at one short but there front of interviewer i am struggling. Need to build up my confidence)

let me know the best and optimised way of writing this code.

Also i suggest people to aviod using inbuilt functions as much as possible

My Answer is as below in perl

- i_learn April 11, 2014 in India`#i want the reverse of the letters of all words in a string #eg Input is "I am a human being" then o/p shud be "I ma a namuh gnieb" $str="I am a human being"; @arr=split(' ',$str); print @arr; for($i=@arr-1;$i>=0;$i--) { $_=@arr[$i]; ####intead of above for loop if we use foreach(@arr) then it will reverse the whole string @word=split('',$_); { foreach $n (@word) { unshift(@final,$n); } } } print "\n @final \n";`

| Report Duplicate | Flag | PURGE

Amazon Testing / Quality Assurance Algorithm Android Application / UI Design Arrays Automata Coding Data Structures Dynamic Programming Perl - 3of 3 votes

Answersone unsorted array is given.Find out the index i and j ,j> i for which a[j] - a[i] is maximum.perform in linear time complexity

- rahul baid February 17, 2012 in India| Report Duplicate | Flag | PURGE

Amazon Developer Program Engineer Data Structures Arrays - 75of 77 votes

AnswersYou have k lists of sorted integers. Find the smallest range that includes at least one number from each of the k lists.

- ericaturner0 April 01, 2013 in United States

For example,

List 1: [4, 10, 15, 24, 26]

List 2: [0, 9, 12, 20]

List 3: [5, 18, 22, 30]

The smallest range here would be [20, 24] as it contains 24 from list 1, 20 from list 2, and 22 from list 3.| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm - 4of 4 votes

AnswersYou are given a string S and a set of n substrings. You are supposed to remove every instance of those n substrings from S so that S is of the minimum length and output this minimum length.

- pnkapadia6 June 08, 2014 in India

Eg:

S- ccdaabcdbb

n=2 - substrings-- ab, cd

Output: 2

Explanation:

ccdaabcdbb -> ccdacdbb -> cabb -> cb (length=2)

Can someone help me with the algo?| Report Duplicate | Flag | PURGE

Hackerrank Software Engineer Intern String Manipulation - 1of 1 vote

AnswersPush all the zero's of a given array to the end of the array. In place only. Ex 1,2,0,4,0,0,8 becomes 1,2,4,8,0,0,0

- CheckThisResume.com March 09, 2012 in United States| Report Duplicate | Flag | PURGE

Facebook Software Engineer / Developer Algorithm Arrays C Coding - 8of 8 votes

Answers1. qaz is a value for a number where this number is less than the other next values which have indexes larger than the index of this number.

- Pointer January 27, 2015 in United States for Autocomplete

for example: 33 , 25 , 26 , 58 , 41 , 59 -> qaz of (33) = 3 where 33 less than 3 numbers (58 , 41 , 59), qaz of (25) = 4 and not 5 because the index of 33 is less than the index of 25, qaz of (26) = 3 , qaz of (58) = 1 , qaz of (41) = 1 , qaz of (59) = 0.

the question is to find the max qaz.

it can be solved simply using 2 loops which takes time of O(n^2).

that's ok but how can we solve this problem in O(nlogn).

I have an approach and know the algorithm I got during the interview but it take a 40 of me to find it and write the code, but it was hard to think about it during the interview in that way.

I want to know if somebody can think and write the code in less than 20 minutes !!!| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer - 32of 34 votes

AnswersA k-palindrome is a string which transforms into a palindrome on removing at most k characters.

- sc.shobhit August 28, 2013 in India

Given a string S, and an interger K, print "YES" if S is a k-palindrome; otherwise print "NO".

Constraints:

S has at most 20,000 characters.

0<=k<=30

Sample Test Case#1:

Input - abxa 1

Output - YES

Sample Test Case#2:

Input - abdxa 1

Output - No| Report Duplicate | Flag | PURGE

Facebook Intern Algorithm - 1of 1 vote

AnswersYou are given an array ' containing 0s and 1s. Find O(n) time and O(1) space

- Anonymous August 25, 2010

algorithm to find the maximum sub sequence which has equal number of 1s and

0s.

Examples

1) 10101010

The longest sub sequence that satisfies the problem is the input itself

2)1101000

The longest sub sequence that satisfies the problem is 110100| Report Duplicate | Flag | PURGE

Amazon Software Engineer / Developer Algorithm - 4of 6 votes

Answersgiven an int array with no duplicate numbers, write a function to return number of ways to calculate a target number.

- cooldog March 15, 2013 in United States

example: given {2,4,6,8} Target = 12

2 + 4 + 6 = 12,

4 + 8 = 12,

6 + 8 - 2 = 12,

2 - 4 + 6 + 8 = 12,

return 4| Report Duplicate | Flag | PURGE

Microsoft Software Engineer / Developer Algorithm Software Engineer in Test - 4of 4 votes

AnswersWe have an array of objects A and an array of indexes B. Reorder objects in array A with given indexes in array B. Do not change array A's length.

example:

- u-11i24223 October 26, 2015 in United States`var A = [C, D, E, F, G]; var B = [3, 0, 4, 1, 2]; sort(A, B); // A is now [D, F, G, C, E];`

| Report Duplicate | Flag | PURGE

Facebook Front-end Software Engineer Front End Web Development - 1of 1 vote

AnswersImplement the plusplus operator when we are getting the input as integer array = { 9,9,9,9 }.output will be {1,0,0,0,0}

- JobHunter July 11, 2012 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm Arrays C Coding Data Structures - 2of 0 votes

AnswersSimulate a seven-sided die using only five-sided

- vodangkhoa March 23, 2008| Report Duplicate | Flag | PURGE

Amazon Microsoft Software Engineer / Developer Algorithm - 5of 5 votes

AnswersThree strings say A,B,C are given to you. Check weather 3rd string is interleaved from string A and B.

- learn August 27, 2012 in United States

Ex: A="abcd" B="xyz" C="axybczd". answer is yes. o(n)| Report Duplicate | Flag | PURGE

Google - 11of 11 votes

AnswersGiven a string which only contains lowercase. You need delete the repeated letters only leave one, and try to make the lexicographical order of new string is smallest.

- lxfuhuo September 09, 2015 in -

i.e:

bcabc

You need delete 1 'b' and 1 'c', so you delete the first 'b' and first 'c', the new string will be abc which is smallest.

ps: If you try to use greedy algorithm to solve this problem, you must sure that you could pass this case:

cbacdcbc. answer is acdb not adcb

I can't solve this problem well and the interviewer said that you can scan the string twice. First scan is do some preprocess, and the second is to get the answer, but I really can't come up this idea.| Report Duplicate | Flag | PURGE

Google Software Developer Algorithm - 3of 3 votes

AnswersPrint a character 1000 times without using loop and recursion.

- arun September 07, 2012 in India| Report Duplicate | Flag | PURGE

ThoughtWorks Applications Developer - 7of 7 votes

AnswersGiven a string (for example: "a?bc?def?g"), write a program to generate all the possible strings by replacing ? with 0 and 1.

- pennepalli May 30, 2014 in United States

Example:

Input : a?b?c?

Output: a0b0c0, a0b0c1, a0b1c0, a0b1c1, a1b0c0, a1b0c1, a1b1c0, a1b1c1.| Report Duplicate | Flag | PURGE

Google Developer Program Engineer Algorithm C# C++ Java - 5of 9 votes

AnswersQ: Given a sorted 2D N x N array (where array[i][j] < array[i][j+1] and array[i][j] < array[i+1][j]), can you write a function that converts this to a sorted 1D array?

- pdoggeth October 18, 2013 in United States

The obvious and naive way that I thought of was to convert the entire array into a 1D and do a mergesort on it, but there must be a better way than that. I'm wondering what the better and more efficient way is.| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm - 1of 1 vote

AnswersGiven an integer array, sort the integer array such that the concatenated integer of the result array is max. e.g. [4, 94, 9, 14, 1] will be sorted to [9,94,4,14,1] where the result integer is 9944141

- Anonymous February 18, 2011| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm Arrays - 4of 4 votes

AnswersGiven a Start Node and an End Node in a graph report if they are “necessarily connected”. This means that all paths from the start node lead to the end node. Report true all paths from start node lead to end node and false if at least one path does not lead to the end node. This is a directed graph which can have cycles

- nikki December 31, 2018 in United States

Does anyone know how to solve this? I had it in my interview at Google in CA and I still cant solve it| Report Duplicate | Flag | PURGE

Google SDE1 Algorithm

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

Open Chat in New Window