Skip to content

Latest commit

 

History

History
131 lines (70 loc) · 7.28 KB

README.md

File metadata and controls

131 lines (70 loc) · 7.28 KB
Raw

#Algorithms implemented in C/C++

✅ Completed ⭕In progress

Data Structures Questions and Cracking the Coding interview questions

  1. String Manipulation
    • CTCI chapter 1 ✅
  2. Linked Lists
  3. Binary Trees

###GENERAL-QUESTIONS / INTEVRVIEW-PRACTICE

  1. Program to which gives the next number in the Fibonacci sequence when called, starts off with 1(ignore 0).Ex: 112358

  2. Rock the Dates: Write functions to find the next day/previous day given a date, find a date after n days, check if a date is valid,etc. To add some challenge assume that the inputs are pointers to date structures. Please feel free to add any other functions you want!

  3. Zip function: You have 2 arrays of equal length, you need to merge the corresponding elements of the array into one array and return an array of arrays at the end. Conside the example of array [a,b,c] and [d,e,f] the function should return [[a,d],[b,e],[c,f]].

  4. Array of Strings in C: C program that contains a varied list of functions, that use dynamic memory to handle an array of strings in C. Sorting function added.

  5. Array representation of a binary tree: C program that represents a binary tree using an array. Partial implementation of serealization and deserealization.

  6. Kth minimum element: C Program to find the kth minimum element in array, quite common in interviews(I was asked this in the Zynga interview).

  7. Binary tree to List: C program to convert a binary tree to a list.

  8. Binary Arithmetic Using Binary trees: C program that uses binary trees to perform BODMAS calcualations

  9. Amortized analysis and Dynamic Array: C program that implements and explains amortized(average) analysis and simple intro to dynamc arrays

  10. Linked List: The interface file contains various function implemented using and for linked list. Great excercise to get familiar with them.

  11. Binary Search Tree: Implementation and various fuctions for operations such as traversal, sorting, searching, etc in bst's.

  12. Max-Min Stack: Implementation of stack that stores the maximum and minimum elements (can be retrieved in O(1) time), functions include pop, push, max , min, length, etc.

  13. Count/Sequence ADT: Implementation for storing the count (number of occurrences of an integer within a sequence and other operations related to it. Implemented using an dynamica array and using a binary search tree.

  14. Queue ADT: Implementation of Queue and various operations list add-front, remove-back, etc.

  15. Dictionary ADT: Implementation of Dictionary adt and various operations like lookup, insert, traversal etc.

  16. Towers of Hanoi Puzzle: Implementation of the recursive algorithm solution to the [Towers of Hanoi puzzle] (https://en.wikipedia.org/wiki/Tower_of_Hanoi)

  17. Level Order Traversal: Implement the level order traversal of a binary tree and state the time complexity

  18. Reverse in groups: Implement a program to reverse a linked list in groups of size k and state time complexity

  19. Is Binary Search tree : Implement a program to check whether a give tree is a binary search tree or not

  20. Tree Traversals : Implement programs to demostrate- post-order, pre-order, inorder traversals. Implement both the recursive and iterative versions

  21. Same tree : Implement a program to check whether 2 binary trees are the same. They need to have the same values and structure

  22. Maximum element in tree: Implement a program to find out the maximum element in a binary tree

  23. Pair of ints: (the exact question can be found on leetcode)

  24. Permutations of a string: Given a string list all the possible permutations of a string

  25. Different Number: Given an array arr of n unique non-negative integers, how can you most efficiently find a non-negative integer that is not in the array?

  26. Alternating Characters: Find the minimum number of character deletions required for two given strings to be anagrams(check program header for sample input)

  27. Hash Table: Implement a hash table using array and linked lists

  28. Height of tree: Program to find the height or max depth of a binary tree

  29. Remove spaces in a string: Given an string output a string with all the spaces removed

  30. Reverse string-1: Given a string reverse it word by word

  31. Reverse string-2: Given a string reverse it completely, character by character

  32. Posfix Expression evaluation: Evaluate expressions given in reverse polish notation, input is an array of strings

  33. Balanced Parentheses: Verify whether string has balanced parentheses. note: this questions assumes only round-bracket

  34. Group Anagrams: Group all anagrams together from a given array of strings

  35. Infix Expression evaluation: Asked in google interview, similar to postfix eval hence solution not provided.

  36. First non-repeating character: Find the first non repeating character in string.

  37. Word Break Problem: Given a dictionary of words and a string of characters, find if the string of characters can be broken into individual valid words from the dictionary.

  38. String Rotation check: Check given 2 string and a isSubstring method whether one is a rotation of another.

  39. String Compression: Given a string perform basic string compression.

  40. Replace Spaces: Given a string replace spaces with a certain string

  41. Remove duplicates: Remove duplicates from linked list (solution using hashMap)

  42. Is palindrome: Verifiy whether string is a palindrome.

  43. Remove extra spaces: Given a string remove unecessary spaces

  44. Rename letter: Given a string of letters, implement method that outputs string of 1's and 0's of the same size

  45. Array to Linked List: Make a linked list out of an array

  46. Delete Node: Program to delete node from a linked list given the data value of the node to be deleted

  47. Insertion sort: Given an integer array sort using insertion sort technique

  48. Merge sort: Given an integer array sort using merge sort technique

  49. Merge sorted arrays: Given two sorted arrays merge them preserving sorting [Asked by Google, Microsoft]

  50. Arrays Pairs Swap: Given two arrays of integrs, find a pair of values (one from each array) that you can swap to give the two arrays the same sum, feel free to make trivial assumptions

  51. Minimum distances: Given an array find the minimum distance between 2 equal elements in the array. If no such value exists, print -1. (https://www.hackerrank.com/challenges/minimum-distances)

###Interview Questions

Upcoming: Given a Binary Search Tree with integers at every node and an integer k, write code that decides whether or not there exists two nodes a and b such that a+b=k (The above question was asked in Zenefits interview)