Coding Interview Questions
 1of 1 vote
Cross the street
ABC Company is involved in the logistics business.
The company has many outlets and stockyards in a city. The city is like an
N
×
M
N×M grid. We consider a single cell of the given grid to be a single block in the city. The stockyard is at the upperleft corner and the outlet is located in the lower right corner. Everyday, one of the employees has to travel from the upper left to the lower right corner for supplies. Each block in the city has a height, where the height of the block located at position (i,j) in the grid is equal to
A
[
i
]
[
j
]
A[i][j]. The company wants to change the heights of some of the blocks, so that the employee can enjoy a highspeed drive from the stockyard to the outlet. But this change comes at a certain cost.
Specifically, if they change a block height from x to y, then they must pay exactly

x
−
y

x−y dollars. Please help them find the minimum cost, such that by spending that specific amount, they can get a path from stockyard to the outlet with all blocks along the path having the same height.
In a single move, the employee can move from a block to any of its adjacent blocks. Note that during this journey, the employee is allowed to move in all four directions, fulfilling the condition that he never goes out of the grid at any point in time.
Input :
First line contains two positive integers N and M  number of rows and columns in the city. Then, N lines follow, each containing M integers, where the
j
t
h
jth integer on the
i
t
h
ith line denotes
A
[
i
]
[
j
]
A[i][j].
Output :
The first and only line of output should contain minimum cost.
Constraints :
1<= N, M <=100
1<= height of blocks <=100
Sample Input
5 5
1 1 1 1 1
9 9 9 9 1
1 3 3 3 1
1 9 9 9 9
1 1 1 1 1
Sample Output
6
Explanation
Optimal path taken by the employee will be : (1,1) > (1,2) > (1,3) > (1,4) > (1,5) > (2,5) > (3,5) > (3,4) > (3,3) > (3,2) > (3,1) > (4,1) > (5,1) > (5,2) > (5,3) > (5,4) > (5,5) The height of each block along this path can be changed to
1
1, at a total cost of
6
6. There is no way to get a cost less than this.
 1of 1 vote
Write a program to reveres string from intervals
 1of 1 vote
Find the maximum consecutive 1's in an array of 0's and 1's.
Example:
a) 00110001001110  Output :3 [Max num of consecutive 1's is 3]
b) 1000010001  Output :1 [Max num of consecutive 1's is 1]
 0of 0 votes
Object Oriented Design Problem

Design an OO parking lot. What classes and functions will it have. It should say, full, empty and also be able to find spot for Valet parking. The lot has 3 different types of parking: regular, handicapped and compact.
Use Case:
1. Customer are given a ticket that they can use to redeem to get their vehicle back
2. Parking spots come in three sizes, small, med, large
3. Thee types of vehicles, small[Two Wheeler], med[Car], large[Bus]
a small vehicle can park in a small, medium, and large spot
a medium vehicle can park in a medium and large spot
a large vehicle can park in a large spot
4. There are multiple entry gate to park vehicle. So Vehicle should asign nearest posible parking spot
 0of 0 votes
Please make analysis of RandomNumber1 and RandomNumber2 methods
Result: values returned by methods, description of differences in behavior.
using System;
using static System.Math;
namespace Program
{
public class Analysis
{
public double RandomNumber1()
{
Random random = new Random();
return Round((random.NextDouble()  0.5) * 2.00);
}
public double RandomNumber2()
{
Random random = new Random();
return Round((random.NextDouble()  0.5) * 2.99);
}
}
}
 0of 0 votes
Write code for transforming equation into canonical form. An equation can be of any order. It may contain any amount of variables and parentheses.
The equation will be given in the following form:
P1 + P2 + ... = ... + PN
where P1..PN  terms that look like:
ax^k
where a  floating point value;
k  integer value;
x  variable (each term can have many variables).
For example:
x^2 + 3.5xy + y = y^2  xy + y
Should be transformed into:
x^2  y^2 + 4.5xy = 0
 1of 1 vote
Programming Challenge Description:
Develop a service to help a client quickly find a manager who can resolve the conflict between two employees. When there is a conflict between two employees, the closest common manager should help resolve the conflict. The developers plan to test the service by providing an example reporting hierarchy to enable the identification of the closest common manager for two employees. Your goal is to develop an algorithm for IBM to efficiently perform this task. To keep things simple, they just use a single relationship "isManagerOf" between any two employees. For example, consider a reporting structure represented as a set of triples:
Tom isManagerOf Mary
Mary isManagerOf Bob
Mary isManagerOf Sam
Bob isManagerOf John
Sam isManagerOf Pete
Sam isManagerOf Katie
The manager who should resolve the conflict between Bob and Mary is Tom(Mary's manager). The manager who should resolve the conflict between Pete and Katie is Sam(both employees' manager). The manager who should resolve the conflict between Bob and Pete is Mary(Bob's manager and Pete's manager's manager).
Assumptions:
There will be at least one isManagerOf relationship.
There can be a maximum of 15 team member to a single manager
No cross management would exist i.e., a person can have only one manager
There can be a maximum of 100 levels of manager relationships in the corporation
Input:
R1,R2,R3,R4...Rn,Person1,Person2 R1...Rn  A comma separated list of "isManagerOf" relationships. Each relationship being represented by an arrow "Manager>Person". Person1,Person2  The name of the two employee that have conflict
Output:
The name of the manager who can resolve the conflict Note: Please be prepared to provide a video followup response to describe your approach to this exercise.
Test 1:
Test Input
Frank>Mary,Mary>Sam,Mary>Bob,Sam>Katie,Sam>Pete,Bob>John,Bob,Katie
Expected Output
Mary
Test 2:
Test Input
Sam>Pete,Pete>Nancy,Sam>Katie,Mary>Bob,Frank>Mary,Mary>Sam,Bob>John,Sam,John
Expected Output
Mary
 1of 1 vote
You are given the arrival and departure times of airplanes at an airport for a single day. Schedules for the airplanes remain the same across all days. You are to determine the number of gates the airport should have so that no plane spends time waiting for a gate.
arr = [9:30, 11:15, 16:30]
dep = [11:45, 11:30, 16:45]
Arr array is sorted by time. And departure array is sorted by corresponding arrival times. Plane 'i' arrives at time arr[i] and departs at time dep[i]
Notes:
After some questions, it was decided that minute was the smallest unit of time we cared about. Gate was considered occupied on the arriving minute, but empty on the departing minute. And that the arrival and departure times could be represented as such as integers. e.g. Day runs from minute 0 to minute 1339 (since using a zerobased index). So our example times represented as:
arr = [570, 675, 990]
dept = [705, 690, 1005]
 0of 0 votes
Same question asked in 27th Aug 2016 face to face interview.
Find length of longest palindrome string, you can shuffle or remove any characters in string.
 1of 1 vote
Given a linked list a random ptr also exists. Clone the original linked list.I was asked to write test cases for it.
 0of 0 votes
Implement a Reader/Writers lock by only using primitive locking semantics (such as mutex,semaphore, etc..)
 3of 3 votes
Write program that takes integer, deletes one of two consecutive digits and return greatest of all results.
 0of 4 votes
Take an example of the traditional Iterator interface which has the following methods
Interface Iterator<E>{
public boolean hasNext() {}
public E next() {}
public E remove() {}
}
You are given a list of iterators. You have to design a InterleaveIterator class which implements this
interface and implement the methods:
hasNext() and next()
such that these 2 methods returns interleaved values for the list of iterators:
Implement:
class InterleaveIterator<E> implements Iterator<E>{
@override
public boolean hasNext() {}
@override
public E next() {}
}
Example:
ArrayList<Integer> i1 = [1,2,3,4,5].iterator()
List<Node> i2 = [n1,n2].iterator()
Collection<E> i3 = [e1,e2,e3].iterator()
next() method of InterleaveIterator, should return in this sequence [1,n1,e1,2,n2,e3,3,e3,4,5]
Make this InterleaveIterator class generic and make sure that the class can accept a list of iterators
and interleave them
 2of 2 votes
Write a method to count the number of 2s between 0 and n.*
 0of 0 votes
Design an algorithm to figure out if someone has won in a game of tictactoe.
 0of 0 votes
Given is an algebraic expression involving only positive integers and the operators +
and  . Design a greedy O(n) and dyamnic O(n3) solution.
For example, 5 + 3 − 6 − 7, the maximum possible value of the
expression is 7. One way of achieving this value is by parenthesizing as follows: (5 +
(3 − (6 − 7)))
 0of 0 votes
Find a sub string in a given string and replace it with another string?
 0of 0 votes
Maximize the expression value which consists of numbers and +, operators. Write a program using Greedy approach in linear complexity and Dynamic approach with O(n3) complexity.
 8of 8 votes
Given a packed file with 1Tb of 64bit doubles (first 8 bytes are first double, next 8 bytes are next, etc) find the exact value of median. For simplicity assume the number of doubles is odd.
You can't modify the file and you have only 8Gb of free memory.
Update: you may use no more than two passes through file and your algorithm shouldn't rely on some nature of file  it should work in all cases.
 0of 0 votes
Write a program to check if a chess move is valid. The api should be extendible to cover cases like castling and pawn promotion.
 0of 0 votes
there is a chess board of dimension n X n. You are given with 2 squares on that board S(x1,y1) ;M(x2,y2). S is a fixed point. M can move diagonally. it can move any number of steps or jumps in 1 move . Find the minimum number of moves M needs to reach S
 0of 0 votes
Please analyze the two slightly obfuscated Tcl procedures below and document the code as it should be. Please change the symbol names to reasonable descriptive names. In addition, an explanation of why these procedures might or might not be useful or suggestions for improvements would be most welcome. This code comes from the application you would be working on. I replaced the names and removed the comments to make the challenge. Feel free to do research and experimentation, but please do not ask anyone else to solve it for you. proc f1 {a} { set n [llength $a] set p {} for {set i 0} {$i < $n} {incr i} { for {set j [expr {$i + 1}]} {$j < $n} {incr j} { lappend p [list [lindex $a $i] [lindex $a $j]] } } return $p }
proc f2 {fn lst {vn {}\}} { set result {} lassign $fn a b n if {$n eq {}} { set n {::} } set cl {} foreach n $vn { upvar 1 $n v set cl "${cl}set $n {$v}\n" } set cfn [list $a "${cl}${b}" $n] foreach item $lst { lappend result [apply $cfn $item] } return $result }
 0of 0 votes
Find if the characters of the sample string is in the same order in the text string.. Give a simple algo..
Eg.. TextString: abcNjhgAhGjhfhAljhRkhgRbhjbevfhO
Sample string :NAGARRO
 0of 0 votes
There is a garden of strawberry plants represented by a 2D, square array.Each plant represents an element in the matrix ie it has a number of strawberries. If a plant doesnt have strawberries it is denoted by 0. If 0 is encountered you cannot travel through that path.
You can start from any cell along the left border of this ground (i.e the matrix) and travel until it finally stops at one cell in the right border, and you can only move to up/down/right. You can only visit each cell once. Calculate the maximum number of berries is obtained.
Backtracking using Dynamic programming is one of the methods i have thought of.
Also there some special conditions:
a.Even in the left border and right border, we can go up and down.
b. When we are at the top cell of one column, we can still go up, which demands us to
pay all current strawberries , then we will be teleported to the bottom cell of this column and vice
versa.
Input: user enters dimensions of ground ie size of matrix and the matrix itself
Output: is the maximum number of strawberries collected without encountering 0; in case we do we display 0.
Till now i have managed to find the largest value in the first column of the matrix but i am facing difficulty in testing the neighbours of that cell.
Also i am not able to store the position of the cell which i started from or even mark it.
Input
4 4
1 4 5 1
2 1 2 4
3 3 1 3
4 2 1 2
output
23
Input
4 4
1 4 5 1
2 1 2 4
3 3 1 1
4 2 1 2
output
22
 0of 0 votes
Create a function Demo that takes input a function f and a parameter k, and returns a function that behaves the same as f except it caches the last k distinct accessed results of f.
Demo_f = Demo(f,2)
demo_f(arg1)  computed and cached
demo_f(arg1) returned from cache
demo_f(arg2)  computed and cached
demo_f(arg3)  computed and cached, f(agr1) is evicted
I think its related to python decorators. Some one can give a hint how can I get started with this
 2of 2 votes
Evaluate the value of an expression given in Reverse Polish notation
 1of 1 vote
This question was asked in the first coding round onsite.
Give two sorted lists List<Integer> a and List<Integer> b.
Find
the Union of these two lists > the union list should also be sorted
the Intersection of these two lists > Intersection list should also be sorted.
 1of 1 vote
Those who've attended onsite interview with LinkedIn might know that there are 2 rounds of coding interviews. This question was asked in my 2nd round of coding interview,
Given two valid dictionary words of same length, write a function which returns the minimum number of steps to go from the first to the second word.
You can change only one character at a time. Also, the word formed at every step should be a valid dictionary word.
Eg: Provide minimum steps to go from 'cat' to 'dog'
cat > bat > bet > bot > bog > dog
Ans: 5
 0of 0 votes
Given two numbers L and R, find the highest occurring digit in the prime numbers present between L and R (both inclusive). If multiple digits have the same highest frequency print the largest of them. If there are no prime no.s between L and R, print 1.
 2of 2 votes
Round 6
Question 3 : You are given a word document, you have to print the words with frequencies. Now print the kth rank word in terms of frequency. Print top k words as well by frequencies