Quick select: Select Kth smallest element in an array of size n in O(n) time.
Knuth-Morris-Pratt Pattern Matching Algorithm
Pascal Triangle.
MAX XOR
FILL BITS
RANGE OPERATION
COUNT BITS
HIT BIT
You are given an array of n integers which can contain integers from 1 to n only . Some elements can be repeated multiple times and some other elements can be absent from the array . Write a running code on paper which takes O(1) space apart from the input array and O(n) time to print which elements are not present in the array and the count of every element which is there in the array along with the element number
Given a sorted rotated array, find an element in O(logn) time without finding the pivot element.
Convert an Infix expression to pre/post fix expression.
Implementation of K-DTrees (2-D).
Print encoding for an Array: Rules: consider BST made from given array. Let say number x is present in the BST and to reach x, If you go right print 1, if left then 0.Now you are given an index i in the array A (so x = A[i]) and print the encoding without constructing BST to reach x and without space with least time complexity.
Implementation of SkipList Datastructure.
Given an array of n elements, with all elements ranging from 1 to n except one is missing and one is duplicated; find the duplicate and missing element.
Given a number print the nex largest number that have same number of 1's in binary representation.
Rotate a matrix 90 degrees clockwise.
Find Inorder Successor of a node in a binary tree.
There is a big file of words which is dynamically changing. We are continuously adding some words into it. How would you keep track of top 10 trending words at each moment?
Ancestor Matrix Problem. There is a binary tree of size N. All nodes are numbered between 1-N(inclusive). There is a N*N integer matrix Arr[N][N], all elements are initialized to zero. So for all the nodes A and B, put Arr[A][B] = 1 if A is an ancestor of B (NOT just the immediate ancestor).
Write a function that returns the length of the longest leaf-to-leaf path in a binary.
To find if there is any root to leaf path with specified sum in a binary tree.
There is a sequence where alphabets are written like this.. a,b,c,d,.......,x,y,z,aa,ab,ac........,az,ba,bb,bc,bd......bz,ca,cb.........cz........,aaa,aab,aac.....aaz,............zzz,aaaa...........zzzz..... and so on..WAP to find out the string value at kth position. like if k= 28 the string on 28 will be "ab".
Given a very large number (any number of digits), find the next greater number formed by permutation of digits of this number.
Add 2 linked lists where each node represents a digit of the number formed by the linked lists.
Given a 2-D Matrix find path from starting cell to Goal cell, a bot can move in 8 directions (North, North east, east , south east, south, south west, west, north west). if cell value =0 implies block and if cell Value =1 implies Path exist.
Construct Binary tree from given inorder and pre-order traversal of Binary Tree.
Oobleck Boxes
Queue with push_rear(), pop_front() and get_min() in constant time
Find all the sets of length k in an array such that the sum of all the elements of set is equal to a given number S.
Write a program to check whether a linked list is palindromic linked list O(n) complexity. Do not use extra space.
Find Length of longest substring without repeating characters in O(n). eg if string is "HELLOWORLD" then output is "WORLD" len = 5.
Initialise an array in spiral form (inside out).
Print 2D array in spiral form.
SUDOKU SOLVER
N QUEEN PROBLEM: On a NxN board place N queens such that no queen is under attack where a queen can move any steps horizontally, vertically and diagnolly.
Given an array containing only 0's and 1's, now we have to find the maximum subarray which contain equal no of 0's and 1's. Time complexity O(n).
Find the subset of an array having maximum sum.
There is an integer array consisting positive and negative integers. Find maximum positive difference S defined as: S = a[i] - a[j] where i>j and S > 0.
Count the number of elements in a binary tree.
calculate the depth of the binary tree.
In a binary tree given any node, trace its path from root node.
Print bfs and dfs traversal of binary tree.
In a linked list print odd nodes first and then even nodes and also sort a linked list.
In a linked list display nth element from the last in a single traversal.
Given a large array of int return the length of the longest increasing(non-necessarily-adjacent) sub-sequence.
Implementation of TRIE / PREFIX TREE .
Find least jumps to reach end of the array: Given an array of Integers,if u are on ith element u can make max arr jumps. If i am at an element with value zero, i cannot move forward.find the least selection to reach end of the array. ex: 1 3 5 8 9 2 6 7 6 8 9 starting with arr[0] i can only make one jump to 3, from 3 i can jump either 1 step 0r 2 steps 0r 3 steps.
To find the longest increasing subarray in an array.
Find nth Fibonacci number in less than 0(n).
Prime factors of an integer and count of each of those.
Given an array (length n), we need to find the subarray (length k) such that the sum of the first j elements of the subarray equals the sum of the remaining (k-j) elements of the subarray.
Given a string with no repeated characters generate all the permutations of the string. Also sort the permutations in the lexical order.
heap sort
Merge Sort
Quick Sort
Knuth-Morris-Pratt Pattern Matching Algorithm
Pascal Triangle.
MAX XOR
FILL BITS
RANGE OPERATION
COUNT BITS
HIT BIT
You are given an array of n integers which can contain integers from 1 to n only . Some elements can be repeated multiple times and some other elements can be absent from the array . Write a running code on paper which takes O(1) space apart from the input array and O(n) time to print which elements are not present in the array and the count of every element which is there in the array along with the element number
Given a sorted rotated array, find an element in O(logn) time without finding the pivot element.
Convert an Infix expression to pre/post fix expression.
Implementation of K-DTrees (2-D).
Print encoding for an Array: Rules: consider BST made from given array. Let say number x is present in the BST and to reach x, If you go right print 1, if left then 0.Now you are given an index i in the array A (so x = A[i]) and print the encoding without constructing BST to reach x and without space with least time complexity.
Implementation of SkipList Datastructure.
Given an array of n elements, with all elements ranging from 1 to n except one is missing and one is duplicated; find the duplicate and missing element.
Given a number print the nex largest number that have same number of 1's in binary representation.
Rotate a matrix 90 degrees clockwise.
Find Inorder Successor of a node in a binary tree.
There is a big file of words which is dynamically changing. We are continuously adding some words into it. How would you keep track of top 10 trending words at each moment?
Ancestor Matrix Problem. There is a binary tree of size N. All nodes are numbered between 1-N(inclusive). There is a N*N integer matrix Arr[N][N], all elements are initialized to zero. So for all the nodes A and B, put Arr[A][B] = 1 if A is an ancestor of B (NOT just the immediate ancestor).
Write a function that returns the length of the longest leaf-to-leaf path in a binary.
To find if there is any root to leaf path with specified sum in a binary tree.
There is a sequence where alphabets are written like this.. a,b,c,d,.......,x,y,z,aa,ab,ac........,az,ba,bb,bc,bd......bz,ca,cb.........cz........,aaa,aab,aac.....aaz,............zzz,aaaa...........zzzz..... and so on..WAP to find out the string value at kth position. like if k= 28 the string on 28 will be "ab".
Given a very large number (any number of digits), find the next greater number formed by permutation of digits of this number.
Add 2 linked lists where each node represents a digit of the number formed by the linked lists.
Given a 2-D Matrix find path from starting cell to Goal cell, a bot can move in 8 directions (North, North east, east , south east, south, south west, west, north west). if cell value =0 implies block and if cell Value =1 implies Path exist.
Construct Binary tree from given inorder and pre-order traversal of Binary Tree.
Oobleck Boxes
Queue with push_rear(), pop_front() and get_min() in constant time
Find all the sets of length k in an array such that the sum of all the elements of set is equal to a given number S.
Write a program to check whether a linked list is palindromic linked list O(n) complexity. Do not use extra space.
Find Length of longest substring without repeating characters in O(n). eg if string is "HELLOWORLD" then output is "WORLD" len = 5.
Initialise an array in spiral form (inside out).
Print 2D array in spiral form.
SUDOKU SOLVER
N QUEEN PROBLEM: On a NxN board place N queens such that no queen is under attack where a queen can move any steps horizontally, vertically and diagnolly.
Given an array containing only 0's and 1's, now we have to find the maximum subarray which contain equal no of 0's and 1's. Time complexity O(n).
Find the subset of an array having maximum sum.
There is an integer array consisting positive and negative integers. Find maximum positive difference S defined as: S = a[i] - a[j] where i>j and S > 0.
Count the number of elements in a binary tree.
calculate the depth of the binary tree.
In a binary tree given any node, trace its path from root node.
Print bfs and dfs traversal of binary tree.
In a linked list print odd nodes first and then even nodes and also sort a linked list.
In a linked list display nth element from the last in a single traversal.
Given a large array of int return the length of the longest increasing(non-necessarily-adjacent) sub-sequence.
Implementation of TRIE / PREFIX TREE .
Find least jumps to reach end of the array: Given an array of Integers,if u are on ith element u can make max arr jumps. If i am at an element with value zero, i cannot move forward.find the least selection to reach end of the array. ex: 1 3 5 8 9 2 6 7 6 8 9 starting with arr[0] i can only make one jump to 3, from 3 i can jump either 1 step 0r 2 steps 0r 3 steps.
To find the longest increasing subarray in an array.
Find nth Fibonacci number in less than 0(n).
Prime factors of an integer and count of each of those.
Given an array (length n), we need to find the subarray (length k) such that the sum of the first j elements of the subarray equals the sum of the remaining (k-j) elements of the subarray.
Given a string with no repeated characters generate all the permutations of the string. Also sort the permutations in the lexical order.
heap sort
Merge Sort
Quick Sort
No comments:
Post a Comment