kartiktalwar / algorithms Goto Github PK

http://www.keithschwarz.com/interesting/todo.html

• Find the youngest common ancestor in a directed graph, where you can only go to a node's parent and cannot go back
• Counting the number of nodes at each level of a tree
• Binary Search Tree where each node knows its parent and the leaf nodes are in a linked list. Print the in order traversal.
• Read from file and find top ten most occuring words in file
• Find out if there's a loop in a linked list
• Reverse all words in a sentence
• Given a node, find its successor node in a BST(follow ups: in place, with or without root node, parent node)
• Given str1 and str2, find if they are rotated strings of each other
• three highest numbers in an array
• how to construct nested SQL statements
• write atoi().
• memory handling between C++ and Java
• Find the two elements of an array that sum up to a given sum
• Given an InOrder traversal and a PreOrder traversal of a binary tree, rebuild the tree
• Implement a reverse hash table
• retrieve the maximum number of repeated strings in a array or strings
• In a list of integers, give an algorithm to find the block with the largest sum
• Given a list of words, describe an algorithm for finding duplicate strings, find a way to do it using no additional memory
• Implement run-length encoding
• arraylist and linkedlist
• Given a set of number ranges, i.e. [1,5], [3,6], [7,9], write a program to merge overlapping number ranges. In the above example, the result should be [1,6], [7,9]
• In a collection of strings, output the string that occurs most often
• find words through a grid maze of characters
• Print a binary tree by levels of depth
• how to merge two sorted linklist here
• find LCA for two nodes of a binary tree
• write a function that takes in an int and returns a string that would be how one would say that number
• Given a tree, output levelwise nodes (Ans: It was actually the BFS algorithm, but I didn't realize it at that time)
• Find first unique substring (In O(n))
• Convert an array into balanced binary search tree (Ans: First sort the array, then use recursive algorithm after splitting the array at mid, and using the mid as a node)
• From two arrays N and M find the combinations that add up to say X
• Given an array of ints, sum up all the even numbers and print it.
• Given a two words, write a function/method to determine if they are anagrams
• Merge 2 sorted arrays without having duplicates
• Find all the possible permutations of a given string
• Find the youngest common ancestor in a directed graph, where you can only go to a node's parent and cannot go back
• game where you switch one letter at a time until you make an entirely new word
• counting the number of nodes at each level of a tree
• Find two integers in an unsorted array that produced a certain sum in linear time
• Hashtable/Binary Search/BST Worst case complexity, Average case complexity
• The second round of interview I was asked to calculate the product of three highest numbers in an array
• find a substring of a string
• reverse every k nodes in a given linked list
• quickselect algorithm
• design an address book / library/ calendar/shopping cart
• every number occurs an even number of times except one number, which occurs an odd number of times, return the value of the odd number. Question should be done with a hash map but I used a n log n solution
• powerset of array
• string permutations
• Basic Java ques - interface, abstract class differences and uses
• Compute 'a' raised to 'b'
• Find second max number in a BST
• count occurrences of an integer in a given sorted array
• Write code to find the next least node in a binary search tree given a node.
• array intersection
• Describe how recursion isn't always efficient.
• Given a list of K sorted arrays of average length N, how would you combine them into one sorted array
• keep exactly the same whitespace when reverse string by word
• Print multiplication tables from 1 to 12
• given a node in a binary search tree, find the next highest value (in-order successor) assuming that the nodes have a parent link
• r two given binary trees are identical are not
• Define BST. Describe different approaches to determine whether a tree is BST.
• Write an algo to merge two ascending sorted LL in a descending manner
• Create an algorithm to find the length of a binary tree
• Design a data structure that has constant time pop, push, and constant minimum value
• Given two sorted arrays find the elements of the first array not present in the second
• Given a N*N array where N is even such as 4, 8 and so on . Print the array from the center.
• traversing circular list in O(n)
• Remove repeating characters from a string.
• Find the sum of all elements in a binary tree at a certain level
• Implement integer division
• How would you reverse a doubly-linked list
• http://www.glassdoor.ca/Interview/Given-a-linked-list-flip-every-pair-of-nodes-such-that-if-given-a-b-c-d-e-return-b-a-d-c-e-QTN_154287.htm
• X==NULL and NULL==x
• What is the difference between C and Java
• Delete the duplicate elements in a linked list
• difference between an array and a vector

• Write a method that prints out an in order traversal of a binary tree
• k closest points to origin out of N on a map
• given a string and a mapping of a character to another set of characters, print all the possible combinations of chars.
• Write a function that converts an int into its alpha-numeric equivalent represented as a null terminated string. The function should accept an int as input and return a string as output. For instance, calling the function with an int value of 324 would return a null terminated string containing "324". Ensure that your function checks for appropriate boundary conditions and edge cases. Assume you cannot use any standard libraries (for example, no itoa or sprintf).
• given a list of strings, return a list of lists of all the anagrams
• Given two sorted arrays with N elements each, find the median of their union in O(log n)
• How to eliminate duplicates in a string.
• traverse array in a spiral order
• check if directed graph contains a cycle
• Check if two different BSTs have same inorder traversal
• gave me array, with elements first strictly increasing, then strictly decreasing. Asked me to find the largest number
• iven infinite doubly linked list, and separate list of elements, which are linked to some linked list elements. Find out from the list of elements how many neighboring groups are formed.
• add two numbers in base 3 system
• He gave me file size, and asked me to partition file into chunks, so that each chunk size is power of two, and the number of chunks is minimal. I suggested to find the nearest power of two and obtain absolute value of difference between the original file size, and nearest power of two. Then re-apply the process until reminder is power of two (1 is 2^0)
• function that computes the product of two numbers in string form and outputs the result in the string form
• Find if two nodes in a binary tree have a common ancestor.
• build a stack class and then extend that stack with functionality for tracking a minimum or maximum value
• Determine if a binary search tree is valid or not.
• Multiple two large nums, Print num level by level
• N sorted arrays of each size k are given, print final sorted output. There will duplicates num
• Given an array where each entry can be another array, and so forth, flatten the array
• Given a value N, return the corresponding string according to this pattern. 1 11 21 1211 111221 312211
• write a function which given a string will return if it contains correctly matched open and closed parentheses
• Given a binary tree, write a function which will check if it's a binary search tree
• Given a node of a binary search tree, return the node immediately bigger than it. Convert this from recursive to iterative. What's the difference between the two?
• If you received 50 oranges for free, how would you make the most amount of money from the oranges
• Find the single number in a array, all other elements are paired
• Give a array A[k], define the set S{k} := { A[k], A[A[k]], A[A[A[k]]], ... }, write program to count the maximum size of Sks
• write a function that takes an integer N and returns an NxN matrix with incrementing integers in a spiral
• Print Fizz, Bang, or Buzz based on divisible by 3, 7 or 11. Very easy
• writing a function to find a hidden guess integer given a helper function
• Find the k-lowest elements of an unsorted array.
• Given a tree find out whether is a BST or not.
• Given a URL. How do you find a phone no. in it?
• Then a coding question about given a lowercase string 'ab',write a program to generate all possible lowercase and uppercase combination
• Given an 2d array of numbers that is sorted in both rows and columns, how would you find if a number is in the array or not.
• function given that will receive two arrays find and return the union using array list
• Find the element that appears an odd number of times in an array where all elements except one appear an even number of times
• Design a Data Structure for a phonebook
• Find if there are two elements in an int array that sum up to a given x
• Given a 0-5 random int generator create a 0-7 random int generator
• Design of an elevator system