Given a linked list and a number n. Split the link list into two based on the following pattern input: 1->2->3->4->5->6->7->8->null and n=2 output: 1-2->3->4->null and 5->6->7->8->null input: 2->3->1->4->6->7->7->6->null and n=4 output: 2-3->null and 1->4->6->7->7->6->null return the right partition pointer. First note that pattern. For n=2 it is effectively partitioning the list into two halves. […]
Given two arrays. Find the smallest difference between two elements from both of the arrays. For example: A=[0, -6, 4, 6, 5, -2], and A=[-4, 8, 2, 3, 10, 9] then then the smallest difference between two elements of the two array is 1 with pairs (4, 3) from the arrays repectively. Approach 1: w/o […]
Given an array of integer A[] and the size of sliding window w. Assume that the window of size w starting from left keeps sliding by moving the window one element to right each time. Find the stream of sliding minimums in optimal way. A sliding minimum is the minimum element of current window. Let’s […]
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure. For example, one possible format of serialized tree […]
You are given a list of n float numbers x_1, x_2, x_3, … x_n, where x_i > 0. A traveler starts at point (0, 0) and moves x_1 metres to the north, then x_2 metres to the west, x_3 to the south, x_4 to the east and so on (after each move his direction changes […]
A sorted array has been rotated (in one direction) for unknown number of times. Search a value in the array Note that, if the array was rotated exactly number of times equal to its length then its sorted again. So, we could have done a normal binary search on the sorted array. As the array […]
Write an efficient algorithm that searches for a value in an m x n matrix. Matrix can have two forms. Solve it for each form of the matrix. This matrix has the following properties: Version 1 Integers in each row are sorted from left to right. The first integer of each row is greater than […]
Given an array of integer with duplicated elements. Find the first occurrence of a given number in the array. For example: A = [1, 1, 1, 2, 2, 3, 3, 3, 4]. So, first occurrence of 2 is in index 3, first occurrence of 4 is in index 8. The problem can be solved efficiently […]
Given an array of integers. Rotate the array by k position to right (or left). For example, given array A=[1,2,3,4,5,6] then rotateRight(A, 2) will return [5, 6, 1, 2, 3, 4] and rotateLeft(A,2) will return [3, 4, 5, 6, 1, 2]. Also, otateRight(A, 8) will return [5, 6, 1, 2, 3, 4] because after k=length […]
Reverse a link list using one/single pointer. We first try to device straightforward solution to reverse a linked list recursively. For example, given a linked list 1->2->3->4->5->null, how we can reverse this? Let’s start with straightforward solution using two temp pointers. We will basically keep a new pointer to append nodes from the list into […]