Algorithm Interview Questions
- 0of 0 votes
Answersbuild BST from sorted array of integers
- igorratn@yahoo.com December 09, 2015 in United States| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersTwo files are there file1.txt, file2.txt - both have some random names.
- Rajarathinam Antony December 08, 2015 in India
Like,
file1.txt file2.txt
---------- -----------
Raja Uthaya
Antony Karthi
Christopher Raja
Manickam Antony
Veeramani
Assume file1.txt can have more names(whole database of names), file2.txt has some selected names
You have to display what are all the mismatching items from file1.txt
Need efficient algorithm to do this| Report Duplicate | Flag | PURGE
Honeywell Software Developer Algorithm - 29of 29 votes
AnswersGiven string say ABCGRETCABCG and substring length let us take length as 3, find the count of possible substrings, for example in above string ABC => 2 and BCG => 2 , where CGR and other 3 word length substrings has a count of 1.
- softwaregeek December 08, 2015 in India for Not known| Report Duplicate | Flag | PURGE
Linkedin Software Developer Algorithm - 0of 0 votes
AnswersGiven a set of numbers find if a triplet can form a triangle a+b > c , b+c > a and c+a > b. The result to display all possible combinations of triplets. [ 10 5 3 4 7 1] [5,3,4 ] is one possible triplet and there can be many more.
- softwaregeek December 08, 2015 in India for Not known| Report Duplicate | Flag | PURGE
Linkedin Software Developer Algorithm - 0of 0 votes
AnswersThis was a javascript interview.
- jsduder December 06, 2015 in United States
There are two arrays:
var arr1 = [2,"undefined",7,"undefined", 10,"undefined","undefiend"];
var arr2 = [5,8,12,14];
They need to be merged such that arr1=[2,5,7,8,10,12,14]
This needs to be done in place and in constant time.| Report Duplicate | Flag | PURGE
Developer Program Engineer Algorithm - 0of 0 votes
AnswersGiven a tree.
Each node is of type:public class Node { public IEnumerable<Node> Children { get; set; } }
Write a function GetAllNodes which returns collection, containing all nodes from given tree. (Given only the root node), i.e.:
IEnumerable<Node> allNodes = GetAllNodes( rootNode );
(The task is given in C#, but this is not a restriction, you may use any language you want).
- zr.roman December 03, 2015 in Russia| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm - 0of 0 votes
AnswersI was asked this question in an algorithm interview. Since my coding language was javascript I was asked to implement a hashmap n white board with collision detection.
- jsduder December 02, 2015 in United States
I guess they were looking for a hashing algorithm that will create a linked list in case of a collision and also an equals method| Report Duplicate | Flag | PURGE
StartUp Developer Program Engineer Algorithm - 2of 2 votes
AnswersYou know result of a soccer match, print all the possible ways that this game ends up with this result.
- u-11i24223 December 01, 2015 in United States
Example: final score 1 - 1:
0 - 0
0 - 1
1 - 1
0 - 0
1 - 0
1 - 1
Another example if the final score is 2 - 3 there are many possibilities for reaching to that score:
2 - 3
0 - 0
1 - 0
2 - 0
2 - 1
2 - 2
2 - 3
0 - 0
1 - 0
1 - 1
1 - 2
2 - 2
2 - 3
0 - 0
0 - 1
0 - 2
0 - 3
...| Report Duplicate | Flag | PURGE
unknown Software Engineer Algorithm - 0of 0 votes
AnswersUsing Javascript write code to detect and remove a loop from a cylic linked list
- jsduder December 01, 2015 in United States| Report Duplicate | Flag | PURGE
Developer Program Engineer Algorithm - 0of 0 votes
AnswerYou are given a rectangular grid with 2 rows and N columns. The top row is labeled 1 and the bottom row is labeled 2. The columns are labeled from 1 to N in increasing order. Each cell in the grid contains a single character.
- lodhi November 30, 2015 in United States
Consider a hamiltonian walk in this grid. Meaning, pick a starting cell, say (i,j), and consider a path that starts from (i,j) and goes through every cell in the grid exactly once. Note that you can only walk to adjacent cells, or cells that you share a common edge with. There may be several such paths. Let us concatenate the characters in the order in which the cells are visited during a walk. The string formed can be called the string for the walk.
Among all the possible walks, and their respective strings, find out the lexicographically smallest string. We know that the length of the strings are all the same - to be precise, 2N. Thus, the lexicographically smallest string is simply the alphabetically smallest string if you compare the characters from left to right.
Input
The first line of input contains a number T, the number of test cases. Then follow T test cases. Each test case contains 3 lines. The first line contains the number N, the number of columns in the grid. It is well known of course that the grid contains 2 rows. The next two lines contain the description of the grid in the form of two strings; the string of N characters in row 1 from left to right and the string of N characters in row 2 from left to right, respectively. Each character will be a lowercase english letter.
Output
Output a single line for each test case. The line must contain a string with 2N characters. This string should be the lexicographically smallest string for some hamiltonian walk in the grid.
Constraints
1 ≤ T ≤ 100
1 ≤ N ≤ 10
Sample Input
2
3
abc
def
10
ababaaabab
bababababa
Sample Output
abcfed
aaababababababababab
Explanation
In the first test the possible strings are { abcfed, adebcf, adefcb, badefc, bcfeda, cbadef, cfedab, cfebad, dabcfe, dabefc, defcba, edabcf, efcbad, fedabc, fcbade, fcbeda }. The smallest string is abcfed.| Report Duplicate | Flag | PURGE
Algorithm - 3of 3 votes
AnswersGiven a singly connected linked list, find the largest palindrome in the list in O(1) space.
- neer.1304 November 29, 2015 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 3of 3 votes
AnswersGiven a linked list consisting of String in each Node . Given just a pointer to the head Node find whether the resultant String formed by combining all the Nodes of the linked list is a palindrome or not in O(1) space and O(n) time.
- neer.1304 November 29, 2015 in United States
eg – Consider this linked List structure
“aba” -> “cd” -> “efe” -> “d” -> “caba”
Hence this structure is palindrome .| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersFace to Face
- siva.sai.2020 November 29, 2015 in United States
Q4) two arrays given to you. First array contains number s. Second array contains key values.
We need to find smallest window in first array which covers all second array elements.
e.g:
Input= {6,7,1,3,2,4,5,2,3,1,2,5}
Keys = {2,5,1}
answer: from 9th index to 11th index is the smallest window.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswersFace to face
- siva.sai.2020 November 29, 2015 in India
Q3) stream of numbers coming, get 'n' min elements at any point of time| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersWritten test:
- siva.sai.2020 November 29, 2015 in India
Q2) in single linked list reverse alternative k nodes.
e.g. k=3 , 1->2->3->4->5->6->7->8->9->10
3->2->1->4->5->6->9->8->7->10
void reverseAlternativeKNodes(node *&head, int k);| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersWritten Test question:
- siva.sai.2020 November 29, 2015 in India
Q1) Given binary tree find largestPath size from one leaf to another leaf.
int getLargestPathSize(node *root);| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersFor typical word ladder problem to get the shortest path, BFS has complexity exponential to the word string length. How to optimize?
- jiangok2006 November 28, 2015 in United States| Report Duplicate | Flag | PURGE
Linkedin Algorithm - -1of 1 vote
AnswerGiven an N-ary tree with thousands of nodes in it. Pair (Join) the Leaf nodes which do NOT SHARE the common path. i.e. Two Leaves can be Paired only if they do NOT have Intersecting path.
- neer.1304 November 28, 2015 in United States
For example,
A
/ | \
B C D
/ / | \
E F G H
Leaf nodes: E, F, G, H & D
Possible Pairs in O/Ps:
a) (E-F), (G-H) or
b) (E-G), (F-H) or
c) (E-H), (F-G) or
d) (E-D), (F-G) or
e) (E-D), (G-H) or
f) (E-D), (F-H) or
g) (D-H), (F-G) or
h) (D-G), (F-H) or
i) (D-F), (G-H)
Note: If we pair(join) say, (E-F) then we can NOT pair any of the (D-G) or (D-H) as they SHARE the COMMON path from A to C.
i.e. E-B-A-C-F —> (E-F) pair
D-A-C-G —> (D-G) pair
D-A-C-H —> (D-H) pair| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersGiven a tree, and a pointer to some node in the tree, print the left most element in the same level as that node
- neer.1304 November 28, 2015 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersGiven an input of the calendar objects of 10,000 employees, input is a time interval T and an employee[] array, find the first interval where all the employees in the employee[] array are free for a minimum time interval T (i.e schedule the meeting)
- neer.1304 November 28, 2015 in United States| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 2 votes
AnswersGiven a binary tree, connect all node in the same level in toggle manner.
- neer.1304 November 27, 2015 in United States
Toggle the linking every K level. For first K level, you should link to next right node. Next K you should link to next left and so on.
Node structure is :
struct node
{
int data;
struct node *left, *right, *next;
};
Each level next should point to the next right or left node in the level. For last node in each level, next should be NULL
For ex - if K=2 then for first 2 level of tree connect next pointer from left to right and for next 2 levels connect next pointer from right to left and so on.| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Algorithm - 0of 0 votes
AnswersSort a set of ip address given either in ascending or descending order
- johnsvakel November 27, 2015 in India for Azure
char** SortIPAsc(char** pIPAddress);
char** SortIPDesc(char** pIPAddress);| Report Duplicate | Flag | PURGE
Microsoft Member Technical Staff Algorithm - 5of 5 votes
AnswersGiven N balloons, if you burst ith balloon you get Ai−1∗Ai∗Ai+1 coins and then (i-1)th and (i+1)th balloons become adjacent. Find maximum number of coins you can gather.
- dp November 25, 2015 in United States
Assume that we have extra 1 at left most and right most positions. (don't take in answer just for boundary positions)
Hence if we have left or right boundary positions we multiply 1.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersGiven a very large array of sorted integers, find the number of times a particular integer has been repeated in the array. Required complexity : O(logN)
- Abhigyan Mehra November 25, 2015 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersAt regular interval, we are receiving data (Price,Quantity). We need to find Most Sold Price(MSP). Need to design the solution to print the current MSP with total Qty of that price, every time a set of price and its quantity sold is provided as input.
Time Price Qty MSP(Total Qty) 11:01AM $10.01 100 $10.01(100) 11:03AM $11.01 200 $11.01(200) 11:04AM $12.81 150 $11.01(200) 11:06AM $10.01 210 $10.01(310) 11:07AM $10.01 180 $10.01(490) 11:08AM $12.81 400 $12.81(550) 11:09AM $11.01 200 $12.81(550)
In the interview, I wrote a solution using priority queue where each element of the priority queue is a tuple consisting of price and quantity. The priority queue arranges itself based on the quantity value of each tuple. When new value comes we access the tuple having the particular price, retrieve its quantity. Delete this tuple and insert a new tuple with the same price and updated quantity.
- Edd November 24, 2015 in United States
The interviewer was not satisfied with the solution and commented this is not how a large scale application will be build which is running throughout the day.| Report Duplicate | Flag | PURGE
Amazon Software Engineer Algorithm - 0of 0 votes
AnswersJavascript check if string can be chained:
- jsduder November 24, 2015 in United States
Given an array of strings, find if the strings can be chained to form a circle.
Eg:
arr = ["aab", "bac", "aaa", "cda"]
can be chained as "aaa"-> "aab"-> "bbb" -> "baa"
(Each string differs by one letter)| Report Duplicate | Flag | PURGE
StartUp Algorithm - 2of 2 votes
Answersfor given array
s[] = {5,1,0,4,2,3}
1) length of array is not given.
- idforbc November 24, 2015 in United States
2) If length of array is 5 content is guaranteed to be between 0 to 5. There is no repetition of numbers. Sample example for length(s, 3)
- a[3] = 4 , a[4] = 2, a[2] = 0, a[0] = 5, a[5] =3
returns length of 4 .
For given condition write subroutine
int length (s, 3)
- to find the number of steps it takes to find given value - It's a function api - that I was asked to write with the conditions - I cannot change parameters of the function - I have to make sure return value is correct
Additional Condition:
You cannot use any loop statements like for, while and so on -
You cannot use any global or static variables.
You cannot call other routines inside this routine
You cannot modify given function parameters - it stays length (s, n) only
You cannot change original array too| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 2of 2 votes
AnswersWe have an iterator class as below:
class CIterator { int Next(); //Returns the value of the next element in the iteration by advancing the iterator bool HasNext() const; //check whether any next element for the current iterator };
We need a CPeekIterator class which is having below functionalities
Class CPeekIterator { int Next (); //Same as CIterator does bool HasNext() const; //same as CIterator does int Peek(); // Returns the next element in the iteration without advancing the iterator };
Write the CPeekIterator class
- johnsvakel November 24, 2015 in United States for GFS| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 0of 0 votes
AnswersFind summation of n records added in past 60 secs
Items of the typestruct { int i; time_t timestamp; }
needs to be stored in a C++ container. One of the requirement is to calculate summation of 'i' s of these items added in past 60secs.
- northernlight November 24, 2015 in United States
What container/datastructure will you use. (number of items can be in the order of 10s of thousands.| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Application Engineer Algorithm