Algorithm Interview Questions
- 3of 5 votes
AnswersQ: Find the absolute paths to all directories with image files, given a file system that looks like this. The subdirectory is one indent over.
- aonecoding January 15, 2017 in United States/usr /local profile.jpg /bin config.txt dest.png /rbin image.gif /sys /re /tmp pic.jpg ..... ……
| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersATM has x currency notes of 100 rupee,y currency notes of 500 rupee,and z currency notes of 1000 rupee notes.
- rajat sadh January 10, 2016 in India
Customer wants to withdraw n amount at any given time. as per bank rules,Customer can not withdraw more than INR.40000/-per transaction.
If ATM is running out of cash it should throw a message that insufficient Balance, Kindly enter multiple of m value of currency note.where m>=4000 and m<=total number of cash available in ATM.
An intelligent banker has found in customer survey that customer prefers to receive more than 5 currency notes 100 rupee,more than 2 currency noes of 500 rupee and rest of the currency notes is of 1000 rupee where ever possible.
If amount is less than 500,customer will receive 100 rupee currency notes. Bankers goal is to tender the minimum number of currency notes to save customer waiting time and increase customer satisfaction by following customer survey.Banker has hired you to program ATM dissaptch function.
FOR Example: Lets ATM has 200 currency notes of 100 rupees,90 currency notes of 500 rupee and 50 currency notes of 1000 rupee.Customer has placed a withdrawal request of Rs 22,200.00. Dispatch function has given him 7 currency notes of 100,3 currency notes of 500 and 20 currency notes of 1000 rupee| Report Duplicate | Flag | PURGE
Adobe SDE1 Algorithm - 3of 3 votes
AnswersQ1.- Written exam (Amazon, Bangalore)
- Nitin Gupta May 12, 2012 in India
Given a singly link list and a number 'K', swap the Kth node from the start with the Kth node from the last. Check all the edge cases.
Sample Input: 1->2->3->4->5->6->7->8 and K = 3
Sample Output : 1->2->6->4->5->3->7->8
Sample Input: 1->2->3->4->5->6->7->8 and K = 10
Sample Output: print error "LIST IS OF LESSER SIZE".| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm C C# C++ Coding Data Structures Java Linked Lists - 3of 3 votes
AnswersGiving a string and an string dictionary, find the longest string in dictionary which can formed by deleting some characters of the giving string.
- IKnowThings January 28, 2017 in United States
eg:S = abpcplea, Dict = {ale, apple, monkey, plea}, the return "apple"
I was thinking of the following approach,
Build a Trie for all words in the Dict - O( n * k) where k is the longest string in the dict
For each character c, in S check if there is a word in Trie that starts with it and has the letters that appear in S after c. We can short circuit based on remaining characters and the length of longest string found so far.
This should take O( N * k) where N is length of S.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersGiven a circular single linked list.Write a program that deletes every kth node until only one node is left.
- Aashish August 01, 2012 in India
After kth node is deleted, start the procedure from (k+1)th node.
e.g.list is 1->2->3->4->5->1
k=3
1. You are at 1, delete 3.
List is: 1->2->4->5->1
2. You are at 4, delete 1
List is: 2->4->5->2
3. You are at 2,delete 5
List is: 2->4->2
4. You are at 2, delete 2
List is: 4
Return 4.
How efficient you can do it?| Report Duplicate | Flag | PURGE
Amazon Google Software Engineer / Developer Algorithm - 3of 3 votes
AnswersGiven a binary search tree (BST), write a mehtod that will convert this BST into a doubly linked list that is sorted (ascending or descending order) and returns the first element in this list. You may assume you are given following Node class:
public class Node { public Node left, right; public String val; }
Example: The following BST
- autoboli January 06, 2015 in United States
G
/ \
A T
can be converted into a list
A = G = T
Do it in place! Hnce the memory complexity of your algorithm shoul be O(1).| Report Duplicate | Flag | PURGE
Google Algorithm - 3of 3 votes
AnswersCheck if an integer array is arithmetic sequence.
- PS February 08, 2016 in United States
Example: 1, 2, 3, 4, 5, 6, 7, 8 => true
1, 3, 5, 7, 9 => true
Array may not be sorted.| Report Duplicate | Flag | PURGE
Amazon Software Developer Algorithm - 3of 3 votes
AnswersGiven a value and a binary search tree.
- vodangkhoa April 24, 2007
Print all the paths(if there exists more than one) which sum up to that value. It can be any path in the tree. It doesn't have to be from the root.| Report Duplicate | Flag | PURGE
Microsoft Yahoo Software Engineer / Developer Trees and Graphs Coding Algorithm - 3of 3 votes
AnswersQuestion: Given a sequence of positive integers A and an integer T, return whether there is a continuous sequence of A that sums up to exactly T
- ep February 27, 2015
Example
[23, 5, 4, 7, 2, 11], 20. Return True because 7 + 2 + 11 = 20
[1, 3, 5, 23, 2], 8. Return True because 3 + 5 = 8
[1, 3, 5, 23, 2], 7 Return False because no sequence in this array adds up to 7| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 3of 3 votes
AnswersConsider an array of integers wherein each element is +1 or -1 its preceding element. Given a number, find the first occurence of this number (index) in this array without using linear search.
- nilukush June 04, 2013 in India for World Wide Operations
For example, consider the array :
4 5 6 5 6 7 8 9 10 9 10 (each element in this array is +1 or -1 its preceding element)
Input : 10 (find first occurence of 10 without using linear search)
Output : 8| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm Arrays - 3of 3 votes
AnswersYou are given a dictionary, in the form of a file that contains one word per line. E.g.,
- audi March 14, 2013 in United States
abacus
deltoid
gaff
giraffe
microphone
reef
qar
You are also given a collection of letters. E.g., {a, e, f, f, g, i, r, q}.
The task is to find the longest word in the dictionary that can be spelled with the collection of
letters. For example, the correct answer for the example values above is “giraffe”. (Note that
“reef” is not a possible answer, because the set of letters contains only one “e”.)| Report Duplicate | Flag | PURGE
Google Algorithm - 3of 3 votes
AnswersWrite a program to determine whether n/2 distintinctve pairs can be formed from given n integers where n is even and each pair's sum is divisible by given k. Numbers cannot be repeated in the pairs, that means only you can form total n/2 pairs.
- topjobsncr October 09, 2012 in India| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 3 votes
AnswersGiven a length n, return the number of strings of length n that can be made up of the letters 'a', 'b', and 'c', where there can only be a maximum of 1 'b's and can only have up to two consecutive 'c's
- djway August 10, 2016 in United States for None
Example:
findStrings(3) returns 19
since the possible combinations are: aaa,aab,aac,aba,abc,aca,acb,baa,bac,bca,caa,cab,cac,cba,cbc,acc,bcc,cca,ccb
and the invalid combinations are:
abb,bab,bba,bbb,bbc,bcb,cbb,ccc| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 3 votes
Answerssuppose a string is consists of a, b, and c
- codingfunnyguy November 25, 2013 in United States
Now given a integer N, output the amount of all possible strings of length N that don't of have consecutive a,b,c.
e.g. given N=5, string bacca is invalid since the first 3 letters have consecutive a,b,c. and bbbbb is valid.| Report Duplicate | Flag | PURGE
Google Algorithm - 3of 3 votes
AnswersGiven a dictionary that contains mapping of employee and his/her manager like this
- enok April 09, 2015 in United States
Dictionary<string, string> employees = new Dictionary<string, string>()
{
{ "A","C" },
{ "B","C" },
{ "C","F" },
{ "D","E" },
{ "E","F" },
{ "F","F" }
};
Write a function to get no of employees under each manager in the hierarchy not just their direct reports.
In the above dictionary the root node/ceo is listed as reporting to himself.
Output should be a Dictionary<string,int> that contains this
A - 0
B - 0
C - 2
D - 0
E - 1
F - 5| Report Duplicate | Flag | PURGE
Microsoft SDE1 Algorithm - 3of 3 votes
AnswersGiven an array A[], find (i, j) such that A[i] < A[j] and (j - i) is maximum.
- lyra_vega November 09, 2011 in -| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 3 votes
AnswersYou are given an array of N elements.arrange array in such a way that sum of any cunsucative k numbers are divisible
- dilip kasana October 25, 2012 in India
by NUM.if not possible print -1.(it may possible that there are many solution possible then return any one)
For example:
N=6
k=3
NUM=63
array={80,17,90,82,27,19}
Answer:{19,17,27,82,80,90}
any 3 cunsucative no. like (27+82+80)%63=0
another solution={27,19,17,90,82,80}
may be a hint :try to group all no.'s in mod NUM map and use vector and map.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 3of 3 votes
AnswersA binary search tree is given. Find the ceiling value present in the BST of a given key.
eg-8 3 12 2 6 10 15 4
key - 13 => 15
- LAP June 24, 2013 in United States
key - 4 =>6
key - 8 =>10| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm - 3of 3 votes
AnswersGiven a String find the first non repeating char in a single pass of the string.
- um01 April 18, 2015 in United States
Assume a big character set like utf-8 (eleminate use of char[256])
Avoid any subloop to have a very optimal solution| Report Duplicate | Flag | PURGE
Yahoo SDE1 Algorithm - 3of 3 votes
AnswersThere are N floors and N persons each one is tagged with some random unique number between 1 to N(represents floor number).
- bharat May 31, 2013 in India
We have a lift which can accommodate one person at a time. Every person is in some random floor.
Initially lift is at floor 1 and all floors have single person. Problem here is.. we have to move the persons to their corresponding floor with minimum travelled distance of lift.
Restriction : Lift can have at most one person at a time.
One more thing we have to think of is .. At a time, we can keep more than one person in a floor.. means, we don't necessarily need to take the person out from the floor if we keep another person on the same floor.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 3of 3 votes
AnswersImplement LookAndSay function. For example, first, let user input a number, say 1. Then, the function will generate the next 10 numbers which satisfy this condition:
- Kevin February 22, 2013 in United States
1, 11,21,1211,111221,312211...
explanation: first number 1, second number is one 1, so 11. Third number is two 1(previous number), so 21. next number one 2 one 1, so 1211 and so on...| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer Algorithm - 3of 3 votes
Answers# take an array and print non over lapping in order pairs. example:
- thegeek21 June 05, 2016 in United States# [1,2,3,4] => input # output below is in order combination # (1234) # (1)(234) # (1)(23)(4) # (1)(2)(34) # (12)(34) # (12)(3)(4) # (123)(4) # (1)(2)(3)(4)
| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 3 votes
AnswersYou're given a dictionary of strings, and a key. Check if the key is composed of an arbitrary number of concatenations of strings from the dictionary. For example:
- davelee71047 October 25, 2014 in United States
dictionary: "world", "hello", "super", "hell"
key: "helloworld" --> return true
key: "superman" --> return false
key: "hellohello" --> return true| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Algorithm - 3of 3 votes
Answers/**
- g April 23, 2014 in United States
* Implement a function OneEditApart with the following signature:
* bool OneEditApart(string s1, string s2)
*
* OneEditApart("cat", "dog") = false
* OneEditApart("cat", "cats") = true
* OneEditApart("cat", "cut") = true
* OneEditApart("cat", "cast") = true
* OneEditApart("cat", "at") = true
* OneEditApart("cat", "acts") = false
* Edit is: insertion, removal, replacement
*/| Report Duplicate | Flag | PURGE
Facebook Algorithm - 3of 3 votes
AnswersRound 3 :
- sonesh January 03, 2013 in India
Q 5 : You are given a binary search tree, and a value(data item), you need to tell the left most right cousin in as minimum time and as minimum space ?(need to minimize actual time complexity, he need minimum order of complexity as well as number of node access should be minimum)| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm Data Structures Trees and Graphs - 3of 3 votes
AnswersFind if a given binary tree has duplicate sub trees or not.
- neer.1304 December 25, 2015 in United States
(Two leaf nodes of a parent do not count as subtree)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersWrite a program to find pattern.
- pritishshah.it November 20, 2014 in United States
0: 1
1: 11
2: 21
3: 1211
4: 111221
5: 312211
Iterate over the previous number, and find count for same number number. Append that count before number.
e.g.,
public String pattern(int input){}
If input = 4, function should return 111221.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 3of 3 votes
AnswersSuppose we are given an array A[1 .. n] with the special property that A[1] ≥ A[2] and
- Anonymous March 24, 2011
A[n − 1] ≤ A[n]. We say that an element A[x] is a local minimum if it is less than or equal
to both its neighbors, or more formally, if A[x − 1] ≥ A[x] and A[x] ≤ A[x + 1]. For example,
there are five local minima in the following array:
9 7 7 2 1 3 7 5 4 7 3 3 4 8 6 9
We can obviously find a local minimum in O(n) time by scanning through the array. Describe
and analyze an algorithm that finds a local minimum in O(log n) time.| Report Duplicate | Flag | PURGE
Google Algorithm - 3of 3 votes
AnswersFind popular item in sorted array of natural numbers.
- dreamchaser1984 February 25, 2015 in United States
An item is popular is if its repeated n/4 times or more.
For Ex:
Input: 123444445678
Popular item is 4.
Liner scan is O(n), but solution needs to be in O(logN) complexity and O(1) space complexity.| Report Duplicate | Flag | PURGE
Google Principal Software Engineer Algorithm - 3of 3 votes
AnswersYou have a lists with integers. Find all the pairs of numbers that sum less than or equal to to a particular number k. The list contains minimum 5 Million number.
- hirajhil February 05, 2014 in United States
(I provided a n^2logn solution but they may be looking forward to having a better answer).| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm